A recursion on maximal chains in the Tamari lattices

DOI10.1016/J.DISC.2016.11.030MaRDI QIDQ507487zbMATH OpenOpenAlexFDO

Authors Luke Nelson

Publication date 6 February 2017

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

enumerationrecursiontableauxTamari latticenumber of maximal chains

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Combinatorial aspects of representation theory (05E10) Combinatorics of partially ordered sets (06A07)

Abstract: The Tamari lattices have been intensely studied since their introduction by Dov Tamari around 1960. However oddly enough, a formula for the number of maximal chains is still unknown. This is due largely to the fact that maximal chains in the $n$-th Tamari lattice $mathcal{T}_n$ range in length from $n-1$ to $nchoose2$. In this note, we treat vertices in the lattice as Young diagrams and identify maximal chains as certain tableaux. For each $igeq-1$, we define $mathcal{C}_i(n)$ as the set of maximal chains in $mathcal{T}_n$ of length $n+i$. We give a recursion for $$ and an explicit formula based on predetermined initial values. The formula is a polynomial in $n$ of degree $3i+3$. For example, the number of maximal chains of length $n$ in $mathcal{T}_n$ is $$. The formula has a combinatorial interpretation in terms of a special property of maximal chains.

Recommendations

• Chains of maximum length in the Tamari lattice.
• Chain lengths in the Tamari lattice
• On the number of intervals in Tamari lattices
• The number of intervals in the \(m\)-Tamari lattices
• On Tamari lattices

Cites work

• scientific article; zbMATH DE number 6016068 (Why is no real title available?)
• scientific article; zbMATH DE number 3149991 (Why is no real title available?)
• scientific article; zbMATH DE number 3178652 (Why is no real title available?)
• scientific article; zbMATH DE number 3995692 (Why is no real title available?)
• Balanced tableaux
• Cambrian lattices.
• Chains of maximum length in the Tamari lattice.
• Counting smaller elements in the Tamari and \(m\)-Tamari lattices
• Higher trivariate diagonal harmonics via generalized Tamari posets
• Intervals in Catalan lattices and realizers of triangulations
• Mappings of acyclic and parking functions
• Multichains, non-crossing partitions and trees
• On cluster theory and quantum dilogarithm identities
• On the number of intervals in Tamari lattices
• On the number of reduced decompositions of elements of Coxeter groups
• Parking functions and noncrossing partitions
• Primes, irreducibles and extremal lattices
• Problèmes d'associativité: Une structure de treillis finis induite par une loi demi-associative
• Shellable nonpure complexes and posets. II
• Sur les partitions non croisées d'un cycle. (The non-crossed partitions of a cycle)
• The Hook Graphs of the Symmetric Group
• The number of intervals in the \(m\)-Tamari lattices
• Two bijections on Tamari intervals

Cited in

(5)

• A catalanization map on the symmetric group
• Chains of maximum length in the Tamari lattice.
• Ungarian Markov chains
• Chain lengths in the Tamari lattice
• The Tamari block lattice: an order on saturated chains in the Tamari lattice

This page was built for publication: A recursion on maximal chains in the Tamari lattices

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