21734 articles – 15570 references  [version française]

hal-00598840, version 1

## The number of intervals in the m-Tamari lattices

Mireille Bousquet-Mélou () 1, Eric Fusy 2, Louis-François Préville Ratelle 3

Abstract: 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, which generalizes the usual Tamari lattice 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 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.

• 1:  Laboratoire Bordelais de Recherche en Informatique (LaBRI)
• CNRS : UMR5800 – Université Sciences et Technologies - Bordeaux I – École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB) – Université Victor Segalen - Bordeaux II
• 2:  Laboratoire d'informatique de l'école polytechnique (LIX)
• CNRS : UMR7161 – Polytechnique - X
• 3:  LACIM, Université du Québec à Montréal
• Université du Québec à Montréal
• Domain : Mathematics/Combinatorics
• Keywords : Enumeration – Lattice paths – Tamari lattices
• Comment : 19 pages
• Available versions :  v1 (2011-06-08) v2 (2011-12-20)

• hal-00598840, version 1
• oai:hal.archives-ouvertes.fr:hal-00598840
• From:
• Submitted on: Tuesday, 7 June 2011 17:11:58
• Updated on: Wednesday, 8 June 2011 09:49:48