Structure of random 312‐avoiding permutations1. Issue 3 (8th September 2015) - Madras, Neal; Pehlivan, Lerna
Abstract: 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 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. © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 49, 599–631, 2016