Counting subwords in flattened partitions of sets
Counting subwords in flattened partitions of sets
复制标题
DOI：
10.1016/j.disc.2015.04.023
复制
发表时间：
2015-11
期刊：
影响因子：
--
通讯作者：
T. Mansour;M. Shattuck;S. Wagner
中科院分区：
文献类型：
--
作者：
T. Mansour;M. Shattuck;S. Wagner
在本文中，我们考虑的问题，避免子字模式的扁平划分，这扩展了最近的工作Callan。我们确定在所有情况下明确的公式和/或生成函数的数量集分区的大小为n，避免了一个单一的子字模式的长度为3。由此产生的计数序列的渐近行为在很大程度上取决于特定的模式。对于312和213的情况，我们使用核方法来确定计算回避类成员的生成函数。此外，在132、231和123的情况下，我们还发现了记录所讨论模式出现次数的统计量在分区集合上的分布公式，并给出了一些相关的双射证明。最后，在这些情况下，它表明，出现的模式的数量渐近遵循正态分布。
In this paper, we consider the problem of avoidance of subword patterns in flattened partitions, which extends recent work of Callan. We determine in all cases explicit formulas and/or generating functions for the number of set partitions of size n which avoid a single subword pattern of length three. The asymptotic behavior of the resulting counting sequences turns out to depend quite heavily on the specific pattern. For the cases of 312 and 213, we make use of the kernel method to determine the generating function which counts the members of the avoidance class. Furthermore, in the cases of 132, 231, and 123, we also find formulas concerning the distribution on the set of partitions for the statistics recording the number of occurrences of the pattern in question and some related bijective proofs are given. Finally, in each of these cases, it is shown that the number of occurrences of the pattern asymptotically follows a normal distribution.