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
  • http://hal.archives-ouvertes.fr/hal-00598840
  • oai:hal.archives-ouvertes.fr:hal-00598840
  • From: Mireille Bousquet-Mélou <>
  • Submitted on: Tuesday, 7 June 2011 17:11:58
  • Updated on: Wednesday, 8 June 2011 09:49:48