Inria
Inria.fr
Inria Channel
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
