2012/11/14 by Jonathan Bloom, Bloom, Jonathan, Sergi Elizalde +1 · 1 citation
Computer Science · Mathematics · #05A05 #05A15 (Primary) #05A18 #05A19 (Secondary) #Advanced Combinatorial Mathematics #Advanced Mathematical Identities #Combinatorics (math.CO) #FOS: Mathematics #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1211.3442
openalex publication_date 2012/11/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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, in contrast with the known D-finite generating functions for 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 greatly simplifies existing proofs by Backelin--West--Xin and Jel'ınek, and provides an extension of work of Gouyou-Beauchamps for matchings with fixed points. Finally, we classify pairs of patterns of length 3 according to shape-Wilf-equivalence, and enumerate matchings and partitions avoiding a pair in most of the resulting equivalence classes.