Crossings and nestings of matchings and partitions
By William Y. C. Chen, E. Y. Deng, Rosena R. X. Du, Richard P. Stanley, C. Yan. 2005
261 citations recorded by the source corpus.
We present results on the enumeration of crossings and nestings for matchings and set partitions. Using a bijection between partitions and vacillating tableaux, we show that if we fix the sets of minimal block elements and maximal block elements, the crossing number and the nesting number of partitions have a symmetric joint distribution. It follows that the crossing numbers and the nesting numbers are distributed symmetrically over all partitions of [n], as well as over all matchings on [2n]. As a corollary, the number of k-noncrossing partitions is equal to the number of k-nonnesting partitions. The same is also true for matchings. An application is given to the enumeration of matchings with no k-crossing (or with no k-nesting). Mathematics Subject Classification. Primary 05A18, secondary 05E10, 05A15.
Subfields: Discrete Mathematics and Combinatorics, Statistics and Probability
View Paper: https://www.semanticscholar.org/paper/2679b3fb1fae9ffd5555aa2c1e0292a2ebb2b8c8
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Discrete Mathematics and Combinatorics
- Elise delMas
- Christian Stump
- Drew Armstrong
- Tom Halverson
- Hugh Thomas
- I. Reiten
- Henning Krause
- Lingyan Guo
Citations in the corpus
- Representations of the Rook-Brauer Algebra (2012, methodology): “These paths are very closely related to the vacillating tableaux studied in [10] and [3].”
- Counting walks in a quadrant: a unified approach via boundary value problems (2010, unknown): “, [5, 12, 13], [4, 16, 17] and [8, 23], respectively).”
- Unlabeled (2+2)-free posets, ascent sequences and pattern avoiding permutations (2008, unknown): “Indeed, π ∈ I2n if and only if, for anyi, the chords attached toi and i + 1 are notnested, in the terminology used recently for matchings [3; 9].”
- A uniform bijection between nonnesting and noncrossing partitions (2011, background): “We also note that the interaction between “nonnesting” and “noncrossing” properties is a subtle phenomenon, even just in type A (see [9]).”
- ON PARTITIONS AVOIDING 3-CROSSINGS (2005, unknown): “Theorem 3 (Chen et al. [8]).”