Pattern-avoiding set partitions and Catalan numbers (Q427473)

Summary: We identify several subsets of the partitions of \([n]\), each characterized by the avoidance of a pair of patterns, respectively of lengths four and five. Each of the classes we consider is enumerated by the Catalan numbers. Furthermore, the members of each class having a prescribed number of blocks are enumerated by the Narayana numbers. We use both algebraic and combinatorial methods to establish our results. In some of the cases, we make use of the kernel method to solve the recurrence arising when a further statistic is considered. In other cases, we define bijections with previously enumerated classes which preserve the number of blocks. Two of our bijections are of an algorithmic nature and systematically replace the occurrences of one pattern with those of another having the same length.