Enumeration of permutations by number of alternating runs
Enumeration of permutations by number of alternating runs
复制标题
DOI：
10.1016/j.disc.2013.05.010
复制
发表时间：
2011-10
期刊：
影响因子：
--
通讯作者：
Shi-Mei Ma
中科院分区：
文献类型：
--
作者：
Shi-Mei Ma
让 Sn 表示 {1,2,…,n} 的所有排列的对称群。在本文中，我们考虑具有 k 个交替游程的 Sn 中的排列数 R(n,k)，以及具有长度为 k 的最长交替子序列的 Sn 中的排列数 ak(n)。通过使用 Chen 提出的语法方法，我们获得了这些数字的生成函数的语法解释，以及涉及这些生成函数的卷积恒等式。此外，我们在交替游程和安德烈排列之间建立了联系。
Let Sndenote the symmetric group of all permutations of {1,2,…,n}. In this paper, we consider the number R(n,k) of permutations in Snwith k alternating runs, and the number ak(n) of permutations in Snwith the longest alternating subsequence of length k. By using the grammatical method due to Chen, we obtain grammatical interpretations of the generating functions of these numbers, as well as convolution identities involving these generating functions. Moreover, we establish a connection between alternating runs and André permutations.