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

Ross G. Pinsky

Published 2022-03-23Version 1

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=\frac12\frac{n!(n+1)!4^n}{(2n)!}-\frac12(3n+1), $$ and that $$ E_n^{132}\mathcal{I}_n=E_n^{213}\mathcal{I}_n=\frac12(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}2n^\frac32. $$ 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 (\frac56-\frac\pi4)n^3\approx 0.048n^3,\ \text{for}\ \tau\in\{231,132,213,312\}. $$