Title: Consecutive patterns in permutations
Abstract: An occurrence of a consecutive pattern sigma in a permutation pi
is a subsequence of adjacent entries of pi in the same relative
order as the entries of sigma. For example, occurrences of the
consecutive pattern 21 are descents, and alternating permutations
are those that avoid the consecutive patterns 123 and 321. The
systematic study of consecutive patterns in permutations started over
a decade ago. More recently, consecutive patterns have become
relevant in the study of one-dimensional dynamical systems, and they
are useful in creating tests to distinguish random from deterministic
time series.
We show that the number of permutations avoiding the consecutive
pattern 12…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. 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.