Frame patterns in n-cycles
Jones, Miles and Kitaev, Sergey and Remmel, Jeffrey (2015) Frame patterns in n-cycles. Discrete Mathematics, 338 (7). pp. 1197-1215. ISSN 0012-365X (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_{n-1}$ 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{n-1}{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_{n-1}$ 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{n-1}{2} -k}}$ and $NT_{n,\mu}(q)|_{q^{\binom{n-1}{2} -k}}$ are the number of partitions of $k$ for sufficiently large $n$.
ORCID iDs
Jones, Miles, Kitaev, Sergey ORCID: https://orcid.org/0000-0003-3324-1647 and Remmel, Jeffrey;-
-
Item type: Article ID code: 51734 Dates: DateEvent6 July 2015Published28 February 2015Published Online28 January 2015AcceptedSubjects: 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: 01 Sep 2024 01:10 Related URLs: URI: https://strathprints.strath.ac.uk/id/eprint/51734