Crossings and nestings of matchings and partitions

DOI10.1090/S0002-9947-06-04210-3zbMath1108.05012arXivmath/0501230MaRDI QIDQ3420370

Richard P. Stanley, Rosena R. X. Du, Eva Y. P. Deng, William Y. C. Chen, Catherine Huafei Yan

Publication date: 1 February 2007

Published in: Transactions of the American Mathematical Society (Search for Journal in Brave)

Abstract: 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).

Full work available at URL: https://arxiv.org/abs/math/0501230

zbMATH Keywords

enumerationvacillating tableau

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Partitions of sets (05A18) Combinatorial aspects of representation theory (05E10)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Partition algebras.
• Random walks in Weyl chambers and the decomposition of tensor powers
• The Cauchy identity for \(Sp(2n)\)
• A Schensted-type correspondence for the symplectic group
• Standard Young tableaux of height 4 and 5
• A linear operator for symmetric functions and tableaux in a strip with given trace
• An extension of Schensted's theorem
• Random walk in an alcove of an affine Weyl group, and non-colliding random walks on an interval
• Algebraic aspects of increasing subsequences
• The asymptotics of monotone subsequences of involutions
• Bell numbers, their relatives, and algebraic differential equations
• A map-theoretic approach to Davenport Schinzel sequences
• RSK insertion for set partitions and diagram algebras
• Longest Increasing and Decreasing Subsequences
• Differential Posets
• The Distribution of Crossings of Chords Joining Pairs of 2n Points on a Circle
• On the distribution of the length of the longest increasing subsequence of random permutations
• A Combinatorial Problem Connected with Differential Equations
• Ballot problems
• Sur Un Problème De Configurations Et Sur Les Fractions Continues

Related Items (only showing first 100 items - show all)

Strictly increasing and decreasing sequences in subintervals of words and a conjecture of Guo and Poznanović ⋮ The combinatorics of a tree-like functional equation for connected chord diagrams ⋮ Bijective enumeration of general stacks ⋮ Descents on nonnesting multipermutations ⋮ Cellular subalgebras of the partition algebra ⋮ Combinatorics of exterior peaks on pattern-avoiding symmetric transversals ⋮ Set partitions, tableaux, and subspace profiles under regular diagonal matrices ⋮ Explicit enumeration formulas for \(m\)-regular simple stacks ⋮ Regular simple queues of protein contact maps ⋮ Properties of RNA secondary structure matching models ⋮ Closed expressions for averages of set partition statistics ⋮ Counting quadrant walks via Tutte's invariant method ⋮ On some combinatorial sequences associated to invariant theory ⋮ A generating tree approach to \(k\)-nonnesting partitions and permutations ⋮ Dyck paths and pattern-avoiding matchings ⋮ Crossings and alignments of permutations ⋮ Extensions of the linear bound in the Füredi-Hajnal conjecture ⋮ Growth diagrams, and increasing and decreasing chains in fillings of Ferrers shapes ⋮ Formation of a giant component in the intersection graph of a random chord diagram ⋮ On a uniformly random chord diagram and its intersection graph ⋮ Enumerating closed flows on forks ⋮ A simple bijection for enhanced, classical, and 2-distant \(k\)-noncrossing partitions ⋮ Some enumerative results related to ascent sequences ⋮ Positive and negative chains in charged moon polyominoes ⋮ Chains of length 2 in fillings of layer polyominoes ⋮ Bijections for Weyl chamber walks ending on an axis, using arc diagrams and Schnyder woods ⋮ Transformations of partial matchings ⋮ Descent sets for symplectic groups ⋮ Analytic combinatorics of chord and hyperchord diagrams with \(k\) crossings ⋮ Counting covered fixed points and covered arcs in an involution ⋮ Distribution of descents in matchings ⋮ Bijections for walks ending on an axis, using open arc diagrams ⋮ Oscillating rim hook tableaux and colored matchings ⋮ Combinatorial methods of character enumeration for the unitriangular group. ⋮ Pattern avoidance and dominating compositions ⋮ Set partitions, tableaux, and subspace profiles of regular diagonal operators ⋮ Cyclic descents, matchings and Schur-positivity ⋮ Partitions and partial matchings avoiding neighbor patterns ⋮ On refinements of Wilf-equivalence for involutions ⋮ Vacillating Hecke tableaux and linked partitions ⋮ Hecke insertion and maximal increasing and decreasing sequences in fillings of stack polyominoes ⋮ Combinatorics of RNA structures with pseudoknots ⋮ Equidistribution of set-valued statistics on standard Young tableaux and transversals ⋮ Counting walks in a quadrant: a unified approach via boundary value problems ⋮ A semi-bijective algorithm for saturated extended 2-regular simple stacks ⋮ Tiling bijections between paths and Brauer diagrams ⋮ Pattern-avoiding inversion sequences and open partition diagrams ⋮ Limiting distribution of maximal crossing and nesting of Poissonized random matchings ⋮ Generation of RNA pseudoknot structures with topological genus filtration ⋮ Pattern avoidance in matchings and partitions ⋮ Major index for 01-fillings of moon polyominoes ⋮ Ascent sequences and 3-nonnesting set partitions ⋮ Catalan numbers and pattern restricted set partitions ⋮ Bijections on two variations of noncrossing partitions ⋮ Avoidance of partitions of a three-element set ⋮ An infinite family of inv-Wilf-equivalent permutation pairs ⋮ Folded bump diagrams for partitions of classical types ⋮ On noncrossing and nonnesting partitions of type \(D\) ⋮ Non-crossing tableaux ⋮ Linked partitions and linked cycles ⋮ Two-parameter non-commutative central limit theorem ⋮ Descents on quasi-Stirling permutations ⋮ A bijection between 2-triangulations and pairs of non-crossing Dyck paths ⋮ Crossings and nestings for arc-coloured permutations and automation ⋮ A note on statistical averages for oscillating tableaux ⋮ A major index for matchings and set partitions ⋮ Enumeration of \((k,2)\)-noncrossing partitions ⋮ Central limit theorems for some set partition statistics ⋮ Asymptotic enumeration of RNA structures with pseudoknots ⋮ Fillings of skew shapes avoiding diagonal patterns ⋮ Restricted inversion sequences and enhanced 3-noncrossing partitions ⋮ \(k\)-noncrossing and \(k\)-nonnesting graphs and fillings of Ferrers diagrams ⋮ Weighted dependency graphs ⋮ Polynomiality of certain average weights for oscillating tableaux ⋮ Representations of the Rook-Brauer Algebra ⋮ \(q\)-partition algebra combinatorics ⋮ The \((q, t)\)-Gaussian process ⋮ RNA pseudoknot structures with arc-length \(\geq 3\) and stack-length \(\geq \sigma \) ⋮ Increasing and decreasing sequences in fillings of moon polyominoes ⋮ Finding common structured patterns in linear graphs ⋮ Dimensions of irreducible modules for partition algebras and tensor power multiplicities for symmetric and alternating groups ⋮ Determinant formulas relating to tableaux of bounded height ⋮ Loop homology of bi-secondary structures ⋮ (2+2)-free posets, ascent sequences and pattern avoiding permutations ⋮ Bijections for inversion sequences, ascent sequences and 3-nonnesting set partitions ⋮ Central and local limit theorems for RNA structures ⋮ Statistics of canonical RNA pseudoknot structures ⋮ Combinatorial design of pseudoknot RNA ⋮ Tableau sequences, open diagrams, and Baxter families ⋮ Bijections between oscillating tableaux and (semi)standard tableaux via growth diagrams ⋮ Stable characters from permutation patterns ⋮ Set-partition tableaux, symmetric group multiplicities, and partition algebra modules ⋮ From Dyck paths to standard Young tableaux ⋮ The combinatorics of associated Hermite polynomials ⋮ Stacks in canonical RNA pseudoknot structures ⋮ Enumeration of bilaterally symmetric 3-noncrossing partitions ⋮ On the decomposition of \(k\)-noncrossing RNA structures ⋮ Generalized noncrossing partitions and combinatorics of Coxeter groups ⋮ Ascents and descents in 01-fillings of moon polyominoes ⋮ Pairs of noncrossing free Dyck paths and noncrossing partitions

This page was built for publication: Crossings and nestings of matchings and partitions