The number of intervals in the \(m\)-Tamari lattices

Mireille Bousquet-Mélou ; Éric Fusy ; Louis-François Préville-Ratelle

The electronic journal of combinatorics, The Zeilberger Festschrift volume, Tome 18 (2011) no. 2

Résumé

An $m$-ballot path of size $n$ is a path on the square grid consisting of north and east steps, starting at $(0,0)$, ending at $(mn,n)$, and never going below the line $\{x=my\}$. The set of these paths can be equipped with a lattice structure, called the $m$-Tamari lattice and denoted by $\mathcal{T}_n^{(m)}$, which generalizes the usual Tamari lattice $\mathcal{T}_n$ obtained when $m=1$. We prove that the number of intervals in this lattice is $$ \frac {m+1}{n(mn+1)} {(m+1)^2 n+m\choose n-1}. $$ This formula was recently conjectured by Bergeron in connection with the study of diagonal coinvariant spaces. The case $m=1$ was proved a few years ago by Chapoton. Our proof is based on a recursive description of intervals, which translates into a functional equation satisfied by the associated generating function. The solution of this equation is an algebraic series, obtained by a guess-and-check approach. Finding a bijective proof remains an open problem.

Détail

DOI : 10.37236/2027

Classification : 05A15, 52C99
Mots-clés : Tamari lattices, generating functions, binary trees