Pattern avoidance in matchings and partitions

Jonathan Bloom¹ ; Sergi Elizalde¹

¹Dartmouth College

The electronic journal of combinatorics, Tome 20 (2013) no. 2

Résumé

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 Backelin-West-Xin and Jelínek, 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.

Détail

DOI : 10.37236/2976

Classification : 05A15, 05A05, 05A18, 05A19
Mots-clés : patterns, matchings, set partitions, arc diagram representaion, 3-crossings, 3-nestings, full rook placements, shape-Wilf-equivalence, Dyck paths, bijection