Clustering of consecutive numbers in permutations avoiding a pattern of length three or avoiding a finite number of simple patterns

arXiv2211.12090MaRDI QIDQ6418085

Ross G. Pinsky

Publication date: 22 November 2022

Abstract: For $etain{S}_3$, let $S_n^{extav(eta)}$ denote the set of permutations in $S_n$ that avoid the pattern $eta$, and let $E_n^{extav(eta)}$ denote the expectation with respect to the uniform probability measure on $S_n^{extav(eta)}$. For $ngekge2$ and $auin{S}_k^{extav(eta)}$, let $N_n^{(k)}(sigma)$ denote the number of occurrences of $k$ consecutive numbers appearing in $k$ consecutive positions in $sigmain{S}_n^{extav(eta)}$, and let $N_n^{(k;au)}(sigma)$ denote the number of such occurrences for which the order of the appearance of the $k$ numbers is the pattern $au$. We obtain explicit formulas for $E_n^{extav(eta)}{N}_n^{(k;au)}$ and $E_n^{extav(eta)}{N}_n^{(k)}$, for all $2leklen$, all $etain{S}_3$ and all $auin{S}_k^{extav(eta)}$. These exact formulas then yield asymptotic formulas as $noinfty$ with $k$ fixed, and as $noinfty$ with $k=k_{n}oinfty$. We also obtain analogous results for $S_n^{extav(et{a}_1,cdots,et{a}_r)}$, the subset of $S_n$ consisting of permutations avoiding the patterns ${a{u}_i}_{i=1}^r$, where $a{u}_{i}in{S}_{m_i}$, in the case that ${a{u}_i}_{i=1}^n$ are all simple permutations. A particular case of this is the set of separable permutations, which corresponds to $r=2$, $a{u}_1=2413,a{u}_2=3142$.

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Combinatorial probability (60C05)

This page was built for publication: Clustering of consecutive numbers in permutations avoiding a pattern of length three or avoiding a finite number of simple patterns

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6418085)