Originators: Joshua Cooper (presented by Hannah Kolb - REGS 2011)
Definitions: A $\tau$-avoiding permutation is a permutation $\pi$ on $[n]$ (in word form) such that no subsequence of $\pi$ with the same length as $\tau$ has its entries in the same order as $\tau$. A particular ordering of $k$ elements, represented by the permutation $\tau$ of $[k]$, is called a pattern. We study the expected number of occurrences ("expectancy") of a pattern $\sigma$ over some set of permutations of $[n]$ when those permutations are equally likely.
Background: Much work has been done on the structure and enumeration of $\tau$-avoiding permutations. The expected number of occurrences of a given pattern has also been studied; when considering any $k$ positions and fixing the rest, the $k$ elements are equally likely to be in any order, so the expectancy of any pattern of length $k$ over all permutations of $n$ is $\frac 1{k!}\binom nk$.
Bóna [B] studied the expectancy of a pattern $\sigma$ over $\tau$-avoiding permutations when $\tau=132$. He proved that in $132$-avoiding permutations of $[n]$, the increasing pattern of length $k$ has lowest expectancy among the patterns of length $k$, and the decreasing pattern of length $k$ has highest expectancy. It is unreasonable to attempt to compute, for all pairs $\tau$ and $\sigma$, the expectancy of $\sigma$ over $\tau$-avoiding permutations of $[n]$; instead, we can ask questions that would be answerable by knowing all that information.
Question 1: For which patterns $\tau$ is it true that among patterns of length $k$, the monotone patterns have largest and smallest expectancy over $\tau$-avoiding patterns of length $n$?
Question 2: Is it always true that when one monotone pattern of length $k$ has extreme expectancy over $\tau$-avoiding permutations of $[n]$, the reverse pattern achieves the opposite extreme?
Question 3: Let $\sigma_1$ and $\sigma_2$ be patterns of the same length such that $\sigma_1$ has higher expectancy than $\sigma_2$ over $\tau$-avoiding permutations of $[n]$. Does it follow that the same inequality holds over $\tau$-avoiding permutations of $[n+1]$?
Question 4: What structural properties of $\sigma$ and $\tau$ cause the expectancy of $\sigma$ over $\tau$-avoiding permutations of $[n]$ to be especially high or especially low? What sorts of pairs are "independent" in the sense that the expectancy of $\sigma$ over $\tau$-avoiding permutations of $[n]$ is asymptotically the same as the expectancy of $\sigma$ over all permutations of $[n]$?
References:
[B] Miklós Bóna,
The absence of a pattern and the occurrences of another.
Discrete Math. Theor. Comput. Sci. 12 (2010), 89-102.