Jonathan Bloom ; Sergi Elizalde - Patterns in matchings and rook placements

dmtcs:2353 - Discrete Mathematics & Theoretical Computer Science, January 1, 2013, DMTCS Proceedings vol. AS, 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013) - https://doi.org/10.46298/dmtcs.2353
Patterns in matchings and rook placementsArticle

Authors: Jonathan Bloom 1; Sergi Elizalde ORCID1

  • 1 Department of Mathematics [Dartmouth]

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.


Volume: DMTCS Proceedings vol. AS, 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013)
Section: Proceedings
Published on: January 1, 2013
Imported on: November 21, 2016
Keywords: matching,set partition,bijection,pattern avoidance,shape-Wilf-equivalence,rook placement,Dyck path.,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]
Funding:
    Source : OpenAIRE Graph
  • Pattern avoidance in dynamical systems; Funder: National Science Foundation; Code: 1001046

Consultation statistics

This page has been seen 340 times.
This article's PDF has been downloaded 398 times.