Pattern Avoidance for Random Permutations

Harry Crane, Stephen DeSalvo

Published 2015-09-26Version 1

We use techniques from Poisson approximation to prove explicit error bounds on the number of permutations that avoid any pattern. Most generally, we bound the total variation distance between the Poisson distribution and the distribution of the number of occurrences of fixed patterns in random Mallows permutations, of which uniform random permutations are a special case. These bounds allow us to estimate the probability that a pattern occurs any number of times and, in particular, the probability that a random permutation avoids a given pattern. For the uniform distribution, we obtain bounds on the number of pattern avoiding permutations of all finite sizes. For large or specially structured patterns, our bounds lead to a Poisson limit theorem for the number of occurrences and yield asymptoticly exact estimates for the number of permutations that avoid such patterns.