Patterns in matchings and rook placements

Abstract

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, unlike in the 321-avoiding (i.e., 3-noncrossing) case. Our approach also provides a more direct proof of a formula of Bóna for the number of 1342-avoiding permutations. Additionally, we give a bijection proving the shape-Wilf-equivalence of the patterns 321 and 213 which simplifies existing proofs by Backelin–West–Xin and Jelínek.

Keywords

• matching
• set partition
• bijection
• pattern avoidance
• shape-wilf-equivalence
• rook placement
• dyck path.
• [info.info-dm] computer science [cs]/discrete mathematics [cs.dm]