A recursion on maximal chains in the Tamari lattices

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 $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$. In this note, we treat vertices in the lattice as Young diagrams and identify maximal chains as certain tableaux. For each $i\ge -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 $\#{\mathcal{C}}_i(n)$ 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 $\#{\mathcal{C}}_0(n)=\left(\genfrac{}{}{0ex}{}{n}{3}\right)$. The formula has a combinatorial interpretation in terms of a special property of maximal chains.

20 pages, 17 figures

References in corpus (1)

• Quiver mutation and combinatorial DT-invariants