Fetching the paper…

Reading the bibliography…

2014

Structure of Random 312-Avoiding Permutations

Madras, Neal, Pehlivan, Lerna

Original
PDF
Post on X

Understand

We evaluate the probabilities of various events under the uniform distribution on the set of 312-avoiding permutations of 1,...,N.

We derive exact formulas for the probability that the ith element of a random permutation is a specific value less than i, and for joint probabilities of two such events.
In addition, we obtain asymptotic approximations to these probabilities for large N when the elements are not close to the boundaries or to each other.
We also evaluate the probability that the graph of a random 312-avoiding permutation has k specified decreasing points, and we show that for large N the points below the diagonal look like trajectories of a random walk.

Structure of Random 312-Avoiding Permutations · Around

Built on

Regenerative Phenomena
J. F. C. Kingman · 1972
Earlier work this paper cites.
The Art of Computer Programming, Volume 3
D. E. Knuth · 1973
Earlier work this paper cites.
Restricted permutations
R. Simion and F.W. Schmidt · 1985
Earlier work this paper cites.
Exact enumeration of 1342-avoiding permutations a close link with labeled trees and planar maps
M. Bóna · 1997
Earlier work this paper cites.
An area-to-inv bijection between Dyck paths and 312-avoiding permutations
J. Bandlow and K. Killpatrick · 2001
Earlier work this paper cites.

Similar

Permutations with restricted patterns and Dyck paths
C. Krattenthaler · 2001
Cited alongside, same era.
Combinatorics of Permutations
M. Bóna · 2004
Cited alongside, same era.
A natural extension of Catalan numbers
N. Solomon and S. Solomon · 2008
Cited alongside, same era.
A variant of the tandem duplication-random loss model of genome rearrangement
M. Bouvel and D. Rossin · 2009
Cited alongside, same era.
Random Walk: A Modern Introduction
G. Lawler and V. Limic · 2010
Cited alongside, same era.

Then

Random pattern-avoiding permutations
H. Liu and N. Madras · 2010
Later among the works it cites.
Patterns in Permutations and Words
S. Kitaev · 2011
Later among the works it cites.
Large deviations and ratio limit theorems for pattern-avoiding permutations
M. Atapour and N. Madras · 2014
Closest in time.
The shape of random pattern avoiding permutations
S. Miner and I. Pak · 2014
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…