# 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 (Jones-etal-DM-2015-Frame-patterns-in-n-cycles)
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$.

Item type: | Article |
---|---|

ID code: | 51734 |

Keywords: | frame patterns, N-cycle, 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: | 02 Apr 2017 15:05 |

Related URLs: | |

URI: | http://strathprints.strath.ac.uk/id/eprint/51734 |

Export data: |