Skip to Main content Skip to Navigation
Conference papers

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.
Document type :
Conference papers
Complete list of metadata

Cited literature [20 references]  Display  Hide  Download

https://hal.inria.fr/hal-01229694
Contributor : Alain Monteil <>
Submitted on : Tuesday, November 17, 2015 - 10:20:04 AM
Last modification on : Wednesday, June 26, 2019 - 4:36:03 PM
Long-term archiving on: : Thursday, February 18, 2016 - 11:40:18 AM

File

dmAS0177.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : hal-01229694, version 1

Collections

Citation

Jonathan Bloom, Sergi Elizalde. Patterns in matchings and rook placements. 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013), 2013, Paris, France. pp.909-920. ⟨hal-01229694⟩

Share

Metrics

Record views

103

Files downloads

817