Neal Madras

York University


"Pattern-Avoiding Permutations:  A Probabilist's View"


A pattern of length k is a permutation (a[1],...,a[k]) of {1,..,k}.   This pattern is said to be contained in a permutation of {1,...,N}  (for N>k) if there is a subsequence of k elements of the (long) permutation that appears in the same relative order as the pattern.  (E.g. the pattern (132) is contained in the permutation (6425713) because the permutation contains the subsequence (273).)   For a given pattern P, let A_N[P] be the number of permutations of {1,..,N} that do not contain P.  Combinatorialists have proven that A_N[P] grows exponentially in N (rather than factorially), but little is known about the numerical value of the exponential growth rate.  For example, which patterns of length 5 are easiest/hardest to avoid?


We shall describe some Monte Carlo investigations into this and related problems.  The design and implementation of the Monte Carlo method leads to some interesting mathematical problems.  The results of the Monte Carlo lead to some new conjectures, including a description of what a typical 4231-avoiding permutation looks like.  We shall outline some rigorous progress on this last problem.  The Monte Carlo work was done by Hailong Liu while holding an NSERC Undergraduate Summer Research Award.