Pattern avoidance in compositions and multiset permutations
Pattern avoidance in compositions and multiset permutations
复制标题
DOI：
10.1016/j.aam.2005.06.003
复制
发表时间：
2005-04
期刊：
影响因子：
--
通讯作者：
C. Savage;H. Wilf
中科院分区：
文献类型：
--
作者：
C. Savage;H. Wilf
我们证明了在n的正部合成中，避开给定的三字母模式π的数g（n）与π无关.我们求出了{g（n）}的生成函数，证明了序列{g（n）}不是P-递归的。如果S是一个给定的多集，我们证明了S的排列，避免了三个字母的模式π的数量是独立的π。最后，我们给出了一个双射证明，证明了如果[公式：见正文]是一个给定的多重集，那么避免模式（123）的M的排列数是多重性a1，...，ak的对称函数。双射使用布尔格的Greene-Kleitman对称链分解。
We show that among the compositions of n into positive parts, the number g(n) that avoid a given pattern π of three letters is independent of π. We find the generating function of {g(n)}, and it shows that the sequence {g(n)} is not P-recursive. If S is a given multiset, we show that the number of permutations of S that avoid a pattern π of three letters is independent of π. Finally, we give a bijective proof of the fact that if [Formula: see text] is a given multiset then the number of permutations of M that avoid the pattern (123) is a symmetric function of the multiplicities a1,…,ak. The bijection uses the Greene–Kleitman symmetric chain decomposition of the Boolean lattice.