Exact formula and asymptotic behavior for the expected number of inversions in a random permutation avoiding a pattern of length three

Abstract

For $\tau \in S_3$, let $S_n(\tau )$ denote the set of permutations in $S_n$ which avoid the pattern $\tau$, and let $E_n^{\tau }$ denote the expectation with respect to the uniformly random probability measure on $S_n(\tau )$. Let ${\mathcal{I}}_n(\sigma )$ denote the number of inversions in $\sigma \in S_n$. We study $E_n^{\tau }{\mathcal{I}}_n$ for $\tau \in \{231,132,213,312\}\subset S_3$. We prove that $$E_n^{231}{\mathcal{I}}_n=E_n^{312}{\mathcal{I}}_n=\frac{1}{2}\frac{n!(n+1)!4^n}{(2n)!}-\frac{1}{2}(3n+1),$$ and that $$E_n^{132}{\mathcal{I}}_n=E_n^{213}{\mathcal{I}}_n=\frac{1}{2}(n-1)n-E_n^{231}{\mathcal{I}}_n.$$ From the first equation it follows that $$E_n^{231}{\mathcal{I}}_n=E_n^{312}{\mathcal{I}}_n\sim \frac{\sqrt{\pi }}{2}{n}^{\frac{3}{2}}.$$ We also show that the variance ${\text{Var}}_{P_n^{\tau }}({\mathcal{I}}_n)$ of ${\mathcal{I}}_n$ under $P_n^{\tau }$ satisfies $${\text{Var}}_{P_n^{\tau }}({\mathcal{I}}_n)\sim (\frac{5}{6}-\frac{\pi }{4})n^3\approx 0.048n^3,\text{for}\tau \in \{231,132,213,312\}.$$

arXiv commentIt was brought to the author's attention that the results already appear in the literature. The expectation can be obtained from Theorem 1 in M. Bona's paper "The absence of a pattern and the occurrences of another". The asymptotic variance follows from (2.6) in S. Janson's paper "Patterns in Random Permutations Avoiding the Pattern 132".