Pattern avoidance in matchings and partitions (Q1953480): Difference between revisions
From MaRDI portal
Changed an Item |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 06:21, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Pattern avoidance in matchings and partitions |
scientific article |
Statements
Pattern avoidance in matchings and partitions (English)
0 references
7 June 2013
0 references
Summary: 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 provides a more direct proof of a formula of Bóna for the number of \(1342\)-avoiding permutations. We also give a bijective proof of the shape-Wilf-equivalence of the patterns \(321\) and \(213\) which greatly simplifies existing proofs by \textit{J. Backelin} et al. [Adv. Appl. Math. 38, No. 2, 133--148 (2007; Zbl 1127.05002)], and provides an extension of work of \textit{D. Gouyou-Beauchamps} [Eur. J. Comb. 10, No. 1, 69--82 (1989; Zbl 0672.05012)] 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.
0 references
patterns
0 references
matchings
0 references
set partitions
0 references
arc diagram representaion
0 references
3-crossings
0 references
3-nestings
0 references
full rook placements
0 references
shape-Wilf-equivalence
0 references
Dyck paths
0 references
bijection
0 references