Counting Pattern-free Set Partitions I: A Generalization of Stirling Numbers of the Second Kind
✍ Scribed by Martin Klazar
- Publisher
- Elsevier Science
- Year
- 2000
- Tongue
- English
- Weight
- 160 KB
- Volume
- 21
- Category
- Article
- ISSN
- 0195-6698
No coin nor oath required. For personal study only.
✦ Synopsis
A partition u of [k] = {1, 2, . . . , k} is contained in another partition v of [l] if [l] has a k-subset on which v induces u. We are interested in counting partitions v not containing a given partition u or a given set of partitions R. This concept is related to that of forbidden permutations. A strengthening of the Stanley-Wilf conjecture is proposed.
We prove that the generating function (GF) counting v is rational if (i) R is finite and the number of parts of v is fixed or if (ii) u has only singleton parts and at most one doubleton part. In fact, (ii) is an application of (i). As another application of (i) we prove that for each k the GF counting partitions with k pairs of crossing parts belongs to Z( √ 1 -4x).