The University of Michigan Combinatorics Seminar
Winter 2011
February 25, 4:10-5:00, 3866 East Hall

The pattern-restricted factorial function

Jonathan Novak

U. Waterloo


The factorial function N! counts the number of permutations of the numbers 1 to N. The pattern restricted factorial function, N(w)!, counts permutations of these numbers in which a given string w of smaller length is not observed. Unlike the ordinary factorial function, which grows superexponentially, the growth of N(w)! is bounded by C^N for some constant C=C(w) (this is the Stanley-Wilf ex-conjecture, now a theorem of Marcus and Tardos). But how fast does N(w)! actually grow, i.e. what is the analogue of Stirling's formula for the pattern-restricted factorial function? The answer is known only in the case where w is a monotone pattern, and turns out to be given by the number of rectangular Young tableaux of height |w| and width going to infinity at the rate 2N/|w|. I will outline a proof of this result, and point out how one sees a glimpse of the connection between random permutations and random matrices in this context. If time permits I will also discuss some recent results of Joel Lewis which seem to suggest that the cardinality of the set of alternating permutations avoiding a monotone pattern also grows like the dimension of a rectangular representation.