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 Connect in order to contact the contributor
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

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, ⟨10.46298/dmtcs.2353⟩. ⟨hal-01229694⟩

Share

Metrics

Record views

63

Files downloads

556