Frame patterns in ncycles
Jones, Miles and Kitaev, Sergey and Remmel, Jeffrey (2015) Frame patterns in ncycles. Discrete Mathematics, 338 (7). pp. 11971215. ISSN 0012365X (https://doi.org/10.1016/j.disc.2015.01.033)
PDF.
Filename: Jones_etal_DM_2015_Frame_patterns_in_n_cycles.pdf
Accepted Author Manuscript License: Download (450kB) 
Abstract
In this paper, we study the distribution of the number occurrences of the simplest frame pattern, called the $\mu$ pattern, in $n$cycles. Given an $n$cycle $C$, we say that a pair $\langle i,j \rangle$ matches the $\mu$ pattern if $i < j$ and as we traverse around $C$ in a clockwise direction starting at $i$ and ending at $j$, we never encounter a $k$ with $i < k < j$. We say that $ \lan i,j \ran$ is a nontrivial $\mu$match if $i+1 < j$. We say that an $n$cycle $C$ is incontractible if there is no $i$ such that $i+1$ immediately follows $i$ in $C$. We show that number of incontractible $n$cycles in the symmetric group $S_n$ is $D_{n1}$ where $D_n$ is the number of derangements in $S_n$. We show that number of $n$cycles in $S_n$ with exactly $k$ $\mu$matches can be expressed as a linear combination of binomial coefficients of the form $\binom{n1}{i}$ where $i \leq 2k+1$. We also show that the generating function $NTI_{n,\mu}(q)$ of $q$ raised to the number of nontrivial $\mu$matches in $C$ over all incontractible $n$cycles in $S_n$ is a new $q$analogue of $D_{n1}$ which is different from the $q$analogues of the derangement numbers that have been studied by Garsia and Remmel and by Wachs. We will show that there is a rather surprising connection between the charge statistic on permutations due to Lascoux and Sch\"uzenberger and our polynomials in that the coefficient of the smallest power of $q$ in $NTI_{2k+1,\mu}(q)$ is the number of permutations in $S_{2k+1}$ whose charge path is a Dyck path. Finally, we show that $NTI_{n,\mu}(q)_{q^{\binom{n1}{2} k}}$ and $NT_{n,\mu}(q)_{q^{\binom{n1}{2} k}}$ are the number of partitions of $k$ for sufficiently large $n$.
ORCID iDs
Jones, Miles, Kitaev, Sergey ORCID: https://orcid.org/0000000333241647 and Remmel, Jeffrey;

Item type: Article ID code: 51734 Dates: DateEvent6 July 2015Published28 February 2015Published Online28 January 2015AcceptedKeywords: frame patterns, Ncycle, linear combinatorics, Probabilities. Mathematical statistics, Discrete Mathematics and Combinatorics, Theoretical Computer Science Subjects: Science > Mathematics > Probabilities. Mathematical statistics Department: Faculty of Science > Computer and Information Sciences Depositing user: Pure Administrator Date deposited: 18 Feb 2015 09:58 Last modified: 03 Dec 2022 03:49 Related URLs: URI: https://strathprints.strath.ac.uk/id/eprint/51734