Counting Consecutive Pattern Matches in ${\mathcal{S}}_n(132)$ and ${\mathcal{S}}_n(123)$

Abstract

In this paper, we study the distribution of consecutive patterns in the set of 123-avoiding permutations and the set of 132-avoiding permutations, that is, in ${\mathcal{S}}_n(123)$ and ${\mathcal{S}}_n(132)$. We first study the distribution of consecutive pattern $\gamma$-matches in ${\mathcal{S}}_n(123)$ and ${\mathcal{S}}_n(132)$ for each length 3 consecutive pattern $\gamma$. Then we extend our methods to study the joint distributions of multiple consecutive patterns. Some more general cases are discussed in this paper as well.

31 pages, 10 figures