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
  • Guests : Éric Fusy, LIX, Ecole Polytechnique
  • Organisers : 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