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.
Keywords :
Document type :
Reports
Complete list of metadata

https://hal.archives-ouvertes.fr/hal-00621252
Contributor : Mireille Bousquet-Mélou <>
Submitted on : Friday, March 23, 2012 - 9:58:36 AM
Last modification on : Tuesday, October 6, 2020 - 10:56:02 AM
Long-term archiving on: : Sunday, June 24, 2012 - 2:21:31 AM

Files

parking.pdf
Files produced by the author(s)

Identifiers

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

Citation

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