arXiv Analytics

Sign in

arXiv:1109.2398 [math.CO]AbstractReferencesReviewsResources

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

Mireille Bousquet-Mélou, Guillaume Chapuy, Louis-François Préville Ratelle

Published 2011-09-12, updated 2012-04-17Version 2

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.

Comments: 21 pp. This paper is now subsumed by arXiv:1202.5925, and will not be submitted to any journal
Categories: math.CO
Related articles: Most relevant | Search more
arXiv:math/0009230 [math.CO] (Published 2000-09-26)
The conjecture cr(C_m\times C_n)=(m-2)n is true for all but finitely many n, for each m
arXiv:math/0508537 [math.CO] (Published 2005-08-26)
On a conjecture of Widom
arXiv:math/0610977 [math.CO] (Published 2006-10-31)
New results related to a conjecture of Manickam and Singhi