Growth diagrams, and increasing and decreasing chains in fillings of Ferrers shapes

DOI10.1016/J.AAM.2005.12.006zbMATH Open1108.05095arXivmath/0510676OpenAlexW1978059000MaRDI QIDQ863323FDOQ863323

Authors: C. Krattenthaler 

Publication date: 26 January 2007

Published in: Advances in Applied Mathematics (Search for Journal in Brave)

Abstract: We put recent results by Chen, Deng, Du, Stanley and Yan on crossings and nestings of matchings and set partitions in the larger context of the enumeration of fillings of Ferrers shape on which one imposes restrictions on their increasing and decreasing chains. While Chen et al. work with Robinson-Schensted-like insertion/deletion algorithms, we use the growth diagram construction of Fomin to obtain our results. We extend the results by Chen et al., which, in the language of fillings, are results about $0$-$1$-fillings, to arbitrary fillings. Finally, we point out that, very likely, these results are part of a bigger picture which also includes recent results of Jonsson on $0$-$1$-fillings of stack polyominoes, and of results of Backelin, West and Xin and of Bousquet-M'elou and Steingr'i msson on the enumeration of permutations and involutions with restricted patterns. In particular, we show that our growth diagram bijections do in fact provide alternative proofs of the results by Backelin, West and Xin and by Bousquet-M'elou and Steingr'i msson.

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

Recommendations

• Hecke insertion and maximal increasing and decreasing sequences in fillings of stack polyominoes
• Bijections between pattern-avoiding fillings of Young diagrams
• \(k\)-noncrossing and \(k\)-nonnesting graphs and fillings of Ferrers diagrams
• Growth diagrams, domino insertion and sign-imbalance
• Increasing and decreasing sequences in fillings of moon polyominoes

zbMATH Keywords

enumerationinteger partitionsmatchingsRobinson-Schensted correspondenceset partitionsKnuth correspondence

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Combinatorial aspects of representation theory (05E10) Combinatorial aspects of partitions of integers (05A17) Combinatorial identities, bijective combinatorics (05A19)

Cites Work

• Title not available (Why is that?)
• Combinatorics and commutative algebra.
• Permutations, matrices, and generalized Young tableaux
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Bell numbers, their relatives, and algebraic differential equations
• Crossings and nestings of matchings and partitions
• Schur operators and Knuth correspondences
• Schensted algorithms for dual graded graphs
• Generalized triangulations and diagonal-free subsets of stack polyominoes
• RSK insertion for set partitions and diagram algebras
• Title not available (Why is that?)
• Finite posets and Ferrers shapes
• An extension of Schensted's theorem
• Wilf-equivalence for singleton classes
• On Identities Concerning the Numbers of Crossings and Nestings of Two Edges in Matchings
• A spherical initial ideal for Pfaffians
• Matchings avoiding partial patterns
• Decreasing subsequences in permutations and Wilf equivalence for involutions
• Spin-preserving Knuth correspondences for ribbon tableaux
• The connection between the Robinson-Schensted correspondence for skew oscillating tableaux and graded graphs
• Four correspondences between graphs and generalized Young tableaux
• Prefix exchanging and pattern avoidance by involutions
• Generalized Robinson-Schensted-Knuth correspondence

Cited In (70)

• Promotion and growth diagrams for fans of Dyck paths and vacillating tableaux
• Uniform convergence to the Airy line ensemble
• Modified growth diagrams, permutation pivots, and the BWX map \(\phi^*\)
• Long increasing subsequences and non-algebraicity
• The oriented swap process and last passage percolation
• Posets and spaces of \(k\)-noncrossing RNA structures
• Inversion sequences avoiding a triple of patterns of 3 letters
• Growth diagrams and edge local rules
• Birational rowmotion and the octahedron recurrence
• Strictly increasing and decreasing sequences in subintervals of words and a conjecture of Guo and Poznanović
• Magic squares, the symmetric group and Möbius randomness
• Fillings of skew shapes avoiding diagonal patterns
• Positive and negative chains in charged moon polyominoes
• Sorting networks, staircase Young tableaux, and last passage percolation
• Increasing and decreasing sequences in fillings of moon polyominoes
• Chains of length 2 in fillings of layer polyominoes
• Some algebraic structures in KPZ universality
• Pattern-avoiding inversion sequences and open partition diagrams
• Generating-tree isomorphisms for pattern-avoiding involutions
• From Aztec diamonds to pyramids: Steep tilings
• Vincular patterns in inversion sequences
• Maximal 0-1-fillings of Moon polyominoes with restricted chain lengths and rc-graphs
• Ascents and descents in 01-fillings of moon polyominoes
• Restricted inversion sequences and enhanced 3-noncrossing partitions
• Modified growth diagrams, permutation pivots, and the BWX map \(\phi ^{\ast}\)
• Growth diagrams from polygons in the affine Grassmannian
• Bijections for inversion sequences, ascent sequences and 3-nonnesting set partitions
• A new perspective on \(k\)-triangulations
• Interlacing networks: birational RSK, the octahedron recurrence, and Schur function identities
• RSK in last passage percolation: a unified approach
• Major index for 01-fillings of moon polyominoes
• Hidden invariance of last passage percolation and directed polymers
• A COMBINATORIAL IDENTITY AND THE FINITE DUAL OF INFINITE DIHEDRAL GROUP ALGEBRA
• Avoiding a pair of patterns in multisets and compositions
• Rogers-Ramanujan identities and the Robinson-Schensted-Knuth correspondence
• Ascent sequences and 3-nonnesting set partitions
• k-noncrossing and k-nonnesting graphs and fillings of Ferrers diagrams
• Pattern avoidance in matchings and partitions
• Enumeration of bilaterally symmetric 3-noncrossing partitions
• Hecke insertion and maximal increasing and decreasing sequences in fillings of stack polyominoes
• On (shape-)Wilf-equivalence for words
• Maximal increasing sequences in fillings of almost-moon polyominoes
• An infinite family of inv-Wilf-equivalent permutation pairs
• Counting permutations with no long monotone subsequence via generating trees and the kernel method
• Muttalib-Borodin plane partitions and the hard edge of random matrix ensembles
• Vacillating Hecke tableaux and linked partitions
• A bijection between 2-triangulations and pairs of non-crossing Dyck paths
• A combinatorial bijection on \(k\)-noncrossing partitions
• From Dyck paths to standard Young tableaux
• Bijections between oscillating tableaux and (semi)standard tableaux via growth diagrams
• Patterns in column strict fillings of rectangular arrays
• Subword complexes, cluster complexes, and generalized multi-associahedra
• \(k\)-noncrossing and \(k\)-nonnesting graphs and fillings of Ferrers diagrams
• Lonesum and \(\Gamma\)-free \(0-1\) fillings of Ferrers shapes
• Equidistributed statistics on matchings and permutations
• Crossings and nestings for arc-coloured permutations and automation
• The \(m\)-cover posets and their applications
• Bijections for Weyl chamber walks ending on an axis, using arc diagrams and Schnyder woods
• Limiting distribution of maximal crossing and nesting of Poissonized random matchings
• Cyclic sieving, skew Macdonald polynomials and Schur positivity
• The geometric Burge correspondence and the partition function of polymer replicas
• Multitriangulations as complexes of star polygons
• Type-B generalized triangulations and determinantal ideals
• (2+2)-free posets, ascent sequences and pattern avoiding permutations
• Tableau sequences, open diagrams, and Baxter families
• Properties of border strips on Ferrers diagrams
• Transition between characters of classical groups, decomposition of Gelfand-Tsetlin patterns and last passage percolation
• The combinatorics of associated Hermite polynomials
• Gröbner geometry for skew-symmetric matrix Schubert varieties
• A simple bijection for enhanced, classical, and 2-distant \(k\)-noncrossing partitions

This page was built for publication: Growth diagrams, and increasing and decreasing chains in fillings of Ferrers shapes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q863323)