Picture of smart phone in human hand

World leading smartphone and mobile technology research at Strathclyde...

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 University of Strathclyde researchers, including by Strathclyde researchers from the Department of Computer & Information Sciences involved in researching exciting new applications for mobile and smartphone technology. But the transformative application of mobile technologies is also the focus of research within disciplines as diverse as Electronic & Electrical Engineering, Marketing, Human Resource Management and Biomedical Enginering, among others.

Explore Strathclyde's Open Access research on smartphone technology now...

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)

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