Expected Patterns in Permutation Classes

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 $\operatorname{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 $\operatorname{Av}_n (132)$, we find several similarities between the two and prove that the number of 231 patterns is the same in each.