A partition π of the set [n] = {1, 2, . . . , n} is a collection {B1, . . . , Bk} of nonempty pairwise disjoint subsets of [n] (called blocks) whose union equals [n]. In this paper, we find exact formulas and/or generating functions for the number of partitions of [n] with k blocks, where k is fixed, which avoid 3-letter patterns of type x ? yz or xy ? z, providing generalizations in several instances. In the particular cases of 23 ? 1, 22 ? 1, and 32 ? 1, we are only able to find recurrences and functional equations satisfied by the generating function, since in these cases there does not appear to be a simple explicit formula for it.
展开▼
