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 also provides a more direct proof of a formula of B\’ona for the number of \(1342\)-avoiding permutations.
Additionally, we give a bijection proving the shape-Wilf-equivalence of the patterns \(321\) and \(213\) which greatly simplifies existing proofs by Backelin–West–Xin and Jelinek,
and provides an extension of work of Gouyou-Beauchamps 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.
Published: Electron. J Combin. 20 2013, #P5, arXiv.