Videos

The Most and the Least Avoided Consecutive Patterns

Presenter
November 10, 2014
Keywords:
  • Permutation Group
MSC:
  • 20Bxx
Abstract
A permutation pi avoids a consecutive pattern sigma if no subsequence of adjacent entries of pi is in the same relative order as the entries of sigma. We show that the number of permutations avoiding the consecutive pattern dots m --that is, containing no m adjacent entries in increasing order-- is asymptotically larger than the number of permutations avoiding any other consecutive pattern of length m. This had been conjectured in 2001 by Elizalde and Noy. At the other end of the spectrum, the number of permutations avoiding 12...(m-2)m(m-1) is asymptotically smaller than for any other consecutive pattern. This had been conjectured by Nakamura.