Counting Subwords in a Partition of a Set

Abstract

A partition $\pi$ of the set $[n]=\{1,\ldots,n\}$ is a collection $\{B_1,\ldots ,B_k\}$ of nonempty disjoint subsets of $[n]$ (called blocks) whose union equals $[n]$. In this paper, we find explicit formulas for the generating functions for the number of partitions of $[n]$ containing exactly $k$ blocks where $k$ is fixed according to the number of occurrences of a subword pattern $\tau$ for several classes of patterns, including all words of length 3. In addition, we find simple explicit formulas for the total number of occurrences of the patterns in question within all the partitions of $[n]$ containing $k$ blocks, providing both algebraic and combinatorial proofs.