Séminaire des équipes de recherche

Sur le nombre d'intervalles dans les treillis de Tamari

Entrée libre, à 10h30.

  • Date : 3/10/2011
  • Place : Inria Paris - Rocquencourt, salle de conférence du bâtiment 9
  • Guest(s) : Éric Fusy, LIX, Ecole Polytechnique
  • Organiser(s) : Equipe-projet ALGORITHMS

L'ensemble des arbres binaires de taille n  (ou mots de Dyck à n  pas montants) peut être muni d'une structure de treillis dite de Tamari , dont la relation de couverture correspond à une operation de rotation sur les arbres. Une jolie formule due à Chapoton assure que le nombre d'intervalles dans le treillis est \frac{2}{n (n +1)}{4n +1 \choose n -1}. Nous donnons différentes méthodes pour montrer cette formule et en proposons une généralisation à un certain treillis dit m-Tamari  qui opère sur les mots de Dyck dont les pas montants ont hauteur m  (le cas m =1 correspond au treillis de Tamari classique) et dont nous montrons que le nombre d'intervalles est \frac{m +1}{n (mn +1)}{(m +1)^2 n +m  \choose n -1}.

Keywords: Paris - Rocquencourt ALGORITHMS Séminaire

Top