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

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

2011-09-12

arxiv.org/abs/1109.2398v2

Mathematics

Combinatorics

21 pp. This paper is now subsumed by arXiv:1202.5925, and will not be submitted to any journal

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Tamari lattices and parking functions: proof of a conjecture of F. Bergeron does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Tamari lattices and parking functions: proof of a conjecture of F. Bergeron, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Tamari lattices and parking functions: proof of a conjecture of F. Bergeron will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-59632