Counting pattern-free set partitions. I: A generalization of Stirling numbers of the second kind (Q1972357)

The author introduces a new class of counting problems for set partitions, similar to those arising in the problem of forbidden permutations; see \textit{R. Simion} and \textit{F. W. Schmidt} [Eur. J. Comb. 6, 383-406 (1985; Zbl 0615.05002)]. He proves that the generating function that counts partitions \(v\) not containing a given partition or a given set \(R\) of partitions is rational if \(R\) is finite and the number of parts of \(v\) is fixed, or if \(v\) has only singleton parts and at most one doubleton part. In this way a generalization of Stirling numbers of the second kind is obtained. Some other results concerning extremal problems (the Stanley-Wilf conjecture) are discussed and several problems proposed.