DMTCS Proceedings, 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013)

Font Size:  Small  Medium  Large

Patterns in matchings and rook placements

Jonathan Bloom, Sergi Elizalde


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 13;West 13;Xin and Jelínek.
Résumé. Étendant la notion de motifs exclus dans des permutations, nous étudions des appariements et partitions dont le diagramme d'arc évite une configuration donnée de trois arcs. Ces configurations, qui généralisent les 3-croissements et les 3-embo&\i;tements, ont une interprétation, dans le cas d'appariements, en termes de motifs dans des placements pleins de tours sur des tables de Ferrers. Nous énumérons les appariements et les partitions qui évitent 312, obtenant des séries génératrices algébriques, contrairement au cas du motif 321. Notre approche fournit aussi une démonstration plus directe d'une formule de Bóna pour le nombre de permutations qui évitent 1342. En plus, nous donnons une preuve bijective de l'équivalence au sens de la forme et de Wilf des motifs 321 et 213 qui simplifie les preuves de Backelin 13;West 13;Xin et Jelínek.

Full Text: PostScript PDF

Valid XHTML 1.0 Transitional