About this Event
Ewing Hall, University of Delaware, Newark, DE 19716, USA
A \it cluster\rm\ of length $l$ in a permutation from $S_n$ is a set of $l$ consecutive numbers that appear in any order in $l$ consecutive positions in the permutation. For $n\ge l\ge2$ and $\tau\in S_l$, let $ N^{(n)}_{l}(\sigma)$ denote the number of clusters of length $l$ in $\sigma$, and let $ N^{(n)}_{l;\tau}(\sigma)$ denote the number of clusters of length $l$ whose order is the pattern $\tau$. (For example, $\sigma=317564928\in S_9$ has the cluster 7564 of length $l=4$ and pattern $\tau=4231$.)
For $\eta\in S_3$, let $S_n^{\text{av}(\eta)}$ denote the set of permutations in $S_n$ that avoid the pattern $\eta$, and let $E_n^{\text{av}(\eta)}$ denote the expectation
with respect to the uniform probability measure on $S_n^{\text{av}(\eta)}$. We obtain explicit formulas for $E_n^{\text{av}(\eta)} N^{(n)}_{l;\tau}$ and $E_n^{\text{av}(\eta)}N^{(n)}_{l}$. These exact formulas yield asymptotic formulas as $n\to\infty$ with $l$ fixed, and also with $l=l_n\to\infty$.
In particular, for fixed $l$, depending on $\eta$ and $\tau$, the expectation $E_n^{\text{av}(\eta)} N^{(n)}_{l;\tau}$ either grows linearly in $n$ or is bounded and bounded away from zero. The expectation $E_n^{\text{av}(\eta)}N^{(n)}_{l}$ always has linear growth in $n$, when $l$ is fixed. For certain $\eta\in S_3$, $\lim_{n\to\infty}E_n^{\text{av}(\eta)}N^{(n)}_{l_n}$ is equal to infinity or zero depending on whether $l_n$ is on an order less than $n^\frac23$ or greater than $n^\frac23$, while for other $\eta\in S_3$, this dichotomy occurs depending on whether $\lim_{n\to\infty}(l_n-\frac{\log n}{\log 4})$ is equal to $-\infty$ or $+\infty$.
Analogous results are obtained for $S_n^{\text{av}(\eta_1,\cdots,\eta_r)}$, the permutations in $S_n$ simultaneously avoiding the patterns $\{\eta_i\}_{i=1}^r$, in the case that $\{\eta_i\}_{i=1}^n$ are all \it simple\rm\ permutations. A particular case of this, where we can calculate the asymptotic behavior explicitly, is the set of \it separable\rm\ permutations, which corresponds to $r=2$, $\eta_1=2413,\eta_2=3142$.
0 people are interested in this event
User Activity
No recent activity