Seminars & Colloquia Calendar

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.