Sur le nombre d'intervalles dans les treillis de Tamari.

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}.

---

Virginie Collette
Last modified: Tue Oct 4 16:22:52 CEST 2011