Pattern avoidance in matchings and partitions (Q1953480)

Summary: Extending the notion of pattern avoidance in permutations, we study matchings and set partitions whose arc diagram representation avoids a given configuration of three arcs. These configurations, which generalize 3-crossings and 3-nestings, have an interpretation, in the case of matchings, in terms of patterns in full rook placements on Ferrers boards. We enumerate \(312\)-avoiding matchings and partitions, obtaining algebraic generating functions, in contrast with the known D-finite generating functions for the \(321\)-avoiding (i.e., 3-noncrossing) case. Our approach provides a more direct proof of a formula of Bóna for the number of \(1342\)-avoiding permutations. We also give a bijective proof of the shape-Wilf-equivalence of the patterns \(321\) and \(213\) which greatly simplifies existing proofs by \textit{J. Backelin} et al. [Adv. Appl. Math. 38, No. 2, 133--148 (2007; Zbl 1127.05002)], and provides an extension of work of \textit{D. Gouyou-Beauchamps} [Eur. J. Comb. 10, No. 1, 69--82 (1989; Zbl 0672.05012)] for matchings with fixed points. Finally, we classify pairs of patterns of length 3 according to shape-Wilf-equivalence, and enumerate matchings and partitions avoiding a pair in most of the resulting equivalence classes.