On Pattern-Avoiding Partitions - Jelínek, Vít; Mansour, Toufik (The Electronic Journal of Combinatorics, 2008)
A set partition of size $n$ is a collection of disjoint blocks $B_1,B_2,…$, $B_d$ whose union is the set $[n]=\{1,2,…,n\}$. We choose the ordering of the blocks so that they satisfy $\min B_1 < \min B_2 < … < \min B_d$. We represent such a set partition by a canonical sequence $π_1,π_2,…,π_n$, with $π_i=j$ if $i\in B_j$. We say that a partition $π$ contains a partition $σ$ if the canonical sequence of $π$ contains a subsequence that is order-isomorphic to the canonical sequence of $σ$. Two partitions $σ$ and $σ'$ are equivalent, if there is a size-preserving bijection between $σ$-avoiding and $σ'$-avoiding partitions. We determine all the equivalence classes of partitions of size at most $7$. This extends previous work of Sagan, who described the equivalence classes of partitions of size at most $3$. Our classification is largely based on several new infinite families of pairs of equivalent patterns. For instance, we prove that there is a bijection between $k$-noncrossing and $k$-nonnesting partitions, with a notion of crossing and nesting based on the canonical sequence. Our results also yield new combinatorial interpretations of the Catalan numbers and the Stirling numbers.