Picture of athlete cycling

Open Access research with a real impact on health...

The Strathprints institutional repository is a digital archive of University of Strathclyde's Open Access research outputs. Strathprints provides access to thousands of Open Access research papers by Strathclyde researchers, including by researchers from the Physical Activity for Health Group based within the School of Psychological Sciences & Health. Research here seeks to better understand how and why physical activity improves health, gain a better understanding of the amount, intensity, and type of physical activity needed for health benefits, and evaluate the effect of interventions to promote physical activity.

Explore open research content by Physical Activity for Health...

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

[img] PDF (Jones-etal-DM-2015-Frame-patterns-in-n-cycles)
Jones_etal_DM_2015_Frame_patterns_in_n_cycles.pdf - Accepted Author Manuscript
License: Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 logo

Download (450kB)


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$.