On Pattern Avoiding Indecomposable Permutations
On Pattern Avoiding Indecomposable Permutations
复制标题
关于避免不可分解排列的模式
作者：
郜璐璐;Sergey Kitaev;张彪
孔泰在1972年提出了不可分解置换的概念。一个置换是不可分解的，当且仅当它没有本身就是置换的适当前缀。不可分解的排列在各种背景下的文献中进行了研究。特别是，这个概念已被证明是有用的，在获得非平凡的枚举和equidistribution结果的排列。
本文给出了避免长度为3或4的经典模式的不可分解置换和避免长度为3的非连续vincular模式的不可分解置换的完全分类。此外，我们提供了一个递归公式枚举$12\cdots k$-避免不可分解的排列为$k\geq 3$。我们的一些结果涉及下降统计量。我们还提供了一个双射证明的事实，我们的研究。
Comtet introduced the notion of indecomposable permutations in 1972. A permutation is indecomposable if and only if it has no proper prefix which is itself a permutation. Indecomposable permutations were studied in the literature in various contexts. In particular, this notion has been proven to be useful in obtaining non-trivial enumeration and equidistribution results on permutations.
In this paper, we give a complete classification of indecomposable permutations avoiding a classical pattern of length 3 or 4, and of indecomposable permutations avoiding a non-consecutive vincular pattern of length 3. Further, we provide a recursive formula for enumerating $12\cdots k$-avoiding indecomposable permutations for $k\geq 3$. Several of our results involve the descent statistic. We also provide a bijective proof of a fact relevant to our studies.
登录
查看更多内容
DOI：
--
发表时间：
2015
期刊：
J. Integer Seq.
影响因子：
--
作者：
F. Disanto
通讯作者：
F. Disanto
DOI：
--
发表时间：
2000
期刊：
--
影响因子：
--
作者：
E. Babson;E. Steingrímsson
通讯作者：
E. Babson;E. Steingrímsson
DOI：
10.37236/1194
发表时间：
2003-12
期刊：
Electron. J. Comb.
影响因子：
--
作者：
N. Sloane
通讯作者：
N. Sloane
影响因子：
64.8
作者：
J. Shaw
通讯作者：
J. Shaw
DOI：
10.1016/j.aam.2014.01.006
发表时间：
2013-09
期刊：
Adv. Appl. Math.
影响因子：
--
作者：
Fredrik Johansson;Brian Nakamura
通讯作者：
Fredrik Johansson;Brian Nakamura