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.
Type de document :
Communication dans un congrès
Alain Goupil and Gilles Schaeffer. 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013), 2013, Paris, France. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AS, 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013), pp.909-920, 2013, DMTCS Proceedings
Liste complète des métadonnées

Littérature citée [20 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01229694
Contributeur : Alain Monteil <>
Soumis le : mardi 17 novembre 2015 - 10:20:04
Dernière modification le : jeudi 23 novembre 2017 - 15:34:02
Document(s) archivé(s) le : jeudi 18 février 2016 - 11:40:18

Fichier

dmAS0177.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-01229694, version 1

Collections

Citation

Jonathan Bloom, Sergi Elizalde. Patterns in matchings and rook placements. Alain Goupil and Gilles Schaeffer. 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013), 2013, Paris, France. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AS, 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013), pp.909-920, 2013, DMTCS Proceedings. 〈hal-01229694〉

Partager

Métriques

Consultations de la notice

75

Téléchargements de fichiers

164