Structure of random 312-avoiding permutations

Abstract

We evaluate the probabilities of various events under the uniform distribution on the set of $312$-avoiding permutations of $1,\dots ,N$. We derive exact formulas for the probability that the $i^{th}$ 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.