论文标题
随机排列中预期的反转数量的确切公式和渐近行为，避免了长度的三个模式
Exact formula and asymptotic behavior for the expected number of inversions in a random permutation avoiding a pattern of length three
论文作者
论文摘要
对于$τ\在s_3 $中，令$ s_n（τ）$表示避免模式$τ$的$ s_n $中的排列集，并让$ e_n^τ$表示对$ s_n（τ）$ soil of the Offication的期望。令$ \ MATHCAL {i} _n（σ）$表示$σ\ in S_n $中的反转数。我们研究$ e_n^τ\ Mathcal {i} _n $ for $τ\ in \ {231,132,213,312 \} \ subset S_3 $。我们证明了$$ e_n^{231} \ Mathcal {i} _n = e_n^{312} \ Mathcal {i} _n = \ frac12 \ frac12 \ frac {n！（n+1）！4^n} e_n^{132} \ Mathcal {i} _n = e_n^{213} \ Mathcal {i} _n = \ frac12（n-1）n-e_n^{231} {231} \ Mathcal {i} _n。 $$从第一个方程式开始，$$ e_n^{231} \ mathcal {i} _n = e_n^{312} \ Mathcal {i} _n \ sim \ sim \ frac {\sqrtπ} 2n^\ frac32。 $$我们还表明，$ \ Mathcal {i} _n）$ \ Mathcal {i} _n）$的方差$ \ text {var} _ {p_n^τ}（\ Mathcal {i} _n）$ （\ frac56- \ frac \ pi4）n^3 \大约0.048n^3，\ \ text {for} \τ\ in \ in \ {231,132,213,312 \}。 $$
For $τ\in S_3$, let $S_n(τ)$ denote the set of permutations in $S_n$ which avoid the pattern $τ$, and let $E_n^τ$ denote the expectation with respect to the uniformly random probability measure on $S_n(τ)$. Let $\mathcal{I}_n(σ)$ denote the number of inversions in $σ\in S_n$. We study $E_n^τ\mathcal{I}_n$ for $τ\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π}2n^\frac32. $$ We also show that the variance $\text{Var}_{P_n^τ}(\mathcal{I}_n)$ of $\mathcal{I}_n$ under $P_n^τ$ satisfies $$ \text{Var}_{P_n^τ}(\mathcal{I}_n)\sim (\frac56-\frac\pi4)n^3\approx 0.048n^3,\ \text{for}\ τ\in\{231,132,213,312\}. $$
