Clustering of consecutive numbers in permutations avoiding a pattern of length three

Ross G. Pinsky

Published 2022-11-22Version 1

For $\eta\in S_3$, let $S_n^{\text{av}(\eta)}$ denote the set of permutations in $S_n$ that avoid the pattern $\eta$, and let $E_n^{\text{av}(\eta)}$ denote the expectation with respect to the uniform probability measure on $S_n^{\text{av}(\eta)}$. For $n\ge k\ge2$ and $\tau\in S_k^{\text{av}(\eta)}$, let $N_n^{k}(\sigma)$ denote the number of occurrences of $k$ consecutive numbers appearing in $k$ consecutive positions in $\sigma\in S_n^{\text{av}(\eta)}$, and let $N_n^{k;\tau}(\sigma)$ denote the number of such occurrences for which the order of the appearance of the $k$ numbers is the pattern $\tau$. We obtain explicit formula formulas for $E_n^{\text{av}(\eta)}N_n^{k;\tau}$ and $E_n^{\text{av}(\eta)}N_n^k$, for all $2\le k\le n$, all $\eta\in S_3$ and all $\tau\in S_k^{\text{av}(\eta)}$. These exact formulas then yield asymptotic formulas as $n\to\infty$ with $k$ fixed, and as $n\to\infty$ with $k=k_n\to\infty$.