The University of Michigan Combinatorics Seminar


Abstract 

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 StanleyWilf exconjecture, 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 patternrestricted 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. 