Skip to Main content Skip to Navigation

Tamari lattices and parking functions: proof of a conjecture of F. Bergeron

Abstract : An m-ballot path of size n is a path on the square grid consisting of north and east unit 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 T_n^(m), which generalizes the usual Tamari lattice T_n obtained when m=1. This lattice was introduced by F. Bergeron in connection with the study of coinvariant spaces. He conjectured several intriguing formulas dealing with the enumeration of intervals in this lattice. One of them states that the number of intervals in T_n^(m) is $$ \frac {m+1}{n(mn+1)} {(m+1)^2 n+m\choose n-1}. $$ This conjecture was proved recently, but in a non-bijective way, while its form strongly suggests a connection with plane trees. Here, we prove another conjecture of Bergeron, which deals with the number of labelled, intervals. An interval [P,Q] of T_n^(m) is labelled, if the north steps of Q are labelled from 1 to n in such a way the labels increase along any sequence of consecutive north steps. We prove that the number of labelled intervals in T_n^(m) is $$ {(m+1)^n(mn+1)^{n-2}}. $$ The form of these numbers suggests a connection with parking functions, but our proof is non-bijective. It is based on a recursive description of intervals, which translates into a functional equation satisfied by the associated generating function. This equation involves a derivative and a divided difference, taken with respect to two additional variables. Solving this equation is the hardest part of the paper. Finding a bijective proof remains an open problem.
Document type :
Complete list of metadata
Contributor : Mireille Bousquet-Mélou Connect in order to contact the contributor
Submitted on : Friday, March 23, 2012 - 9:58:36 AM
Last modification on : Monday, December 20, 2021 - 4:50:11 PM
Long-term archiving on: : Sunday, June 24, 2012 - 2:21:31 AM


Files produced by the author(s)


  • HAL Id : hal-00621252, version 2
  • ARXIV : 1109.2398


Mireille Bousquet-Mélou, Guillaume Chapuy, Louis-François Préville Ratelle. Tamari lattices and parking functions: proof of a conjecture of F. Bergeron. 2012. ⟨hal-00621252v2⟩



Record views


Files downloads