Peter Winkler, Dartmouth College

Abstract

A "pattern" of length k in a permutation P in S_n is a permutation in S_k determined by choosing k elements from {1,2,...,n} and looking at the order of their images under P.  For example, if P_3 > P_5 then the positions 3 and 5 produce the pattern 21.

P is "d-prolific" if every pattern of length n-d is different; equivalently, the set of patterns of P of length n-d has size n choose d.

We show that the probability that a uniformly random P in S_n is d-prolific tends to e^{-d^2-d} as n grows.

Joint work with Simon Blackburn and Cheyne Homberger.