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 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, and Remmel, Jeffrey;
• Item type: Article 51734 DateEvent6 July 2015Published28 February 2015Published Online28 January 2015Accepted frame patterns, N-cycle, linear combinatorics, Probabilities. Mathematical statistics, Discrete Mathematics and Combinatorics, Theoretical Computer Science Science > Mathematics > Probabilities. Mathematical statistics Faculty of Science > Computer and Information Sciences Pure Administrator 18 Feb 2015 09:58 29 Nov 2021 01:55 https://strathprints.strath.ac.uk/id/eprint/51734