Cheyne Homberger

Expected Patterns in Permuation Classes

Published in the Electronic Journal of Combinatorics, 2012

Abstract:

Each length k pattern occurs equally often in the set S_n of all permutations of length n, but the same is not true in general for a proper subset of S_n. Miklós Bóna recently proved that if we consider the set of n-permutations avoiding the pattern 132, all other non-monotone patterns of length 3 are equally common. In this paper we focus on the set Av_n (123) of n-permutations avoiding 123, and give exact formulae for the occurrences of each length 3 pattern. While this set does not have the same symmetries as Av_n (132), we find several similarities between the two and prove that the number of 231 patterns is the same in each.