Given two permutations σ and τ, what is the expected number of copies of σ in a permutation chosen uniformly at random f

Definitions and mathematical statement

Fix permutations $\sigma\in S_k$ and $\tau\in S_m$, with $m\ge2$. A classical occurrence of a pattern $\rho\in S_s$ in $\pi\in S_n$ is a choice of positions $i_1<\cdots<i_s$ whose values have the same relative order as $\rho$. Let $\operatorname{occ}_\rho(\pi)$ be the number of such choices and \[ \operatorname{Av}_n(\tau)= \{\pi\in S_n:\operatorname{occ}_\tau(\pi)=0\}. \] Choose $\Pi_n$ uniformly from this finite avoidance class, and define \[ \mu_{\sigma,\tau}(n) =\mathbb E[\operatorname{occ}_\sigma(\Pi_n)] =\frac{\sum_{\pi\in\operatorname{Av}_n(\tau)} \operatorname{occ}_\sigma(\pi)} {|\operatorname{Av}_n(\tau)|}. \] Determine these expected occurrence counts for prescribed patterns, by exact formulas, generating functions, or sharp asymptotic expressions as $n\to\infty$.

Avoidance and occurrence both refer to arbitrary subsequences of positions, not only adjacent positions. Overlapping occurrences are all counted. For $m\ge2$ the avoidance class is nonempty, so the uniform distribution is well defined; avoiding the unique length-one pattern would give no permutations of positive length. Some pairs force zero occurrences, while others produce different growth rates. The task is to explain this dependence on both patterns, rather than average over an unrestricted uniformly random permutation, for which symmetry gives a much simpler count.

Short English statement

Determine the expected number of occurrences of one permutation pattern in a uniformly chosen permutation avoiding another fixed pattern.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3100033 (AMR-030-0033), AMR Open Problem Lists. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Cooper - Combinatorial Problems I Like (2020 snapshot), Permutations, source-order bullet 33. Original source indexed by AMR-030-0033. https://people.math.sc.edu/cooper/combprob.html.