A recursion on maximal chains in the Tamari lattices

DOI10.1016/J.DISC.2016.11.030zbMATH Open1355.05273arXiv1709.02987OpenAlexW2570185350MaRDI QIDQ507487FDOQ507487

Authors: Luke Nelson 

Publication date: 6 February 2017

Published in: Discrete Mathematics (Search for Journal in Brave)

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.

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

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

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)

Cites Work

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

Cited In (5)

• Ungarian Markov chains
• Chains of maximum length in the Tamari lattice.
• The Tamari block lattice: an order on saturated chains in the Tamari lattice
• A catalanization map on the symmetric group
• Chain lengths 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)