Counting smaller elements in the Tamari and m-Tamari lattices

Abstract : We introduce new combinatorial objects, the interval- posets, that encode intervals of the Tamari lattice. We then find a combinatorial interpretation of the bilinear operator that appears in the functional equation of Tamari intervals described by Chapoton. Thus, we retrieve this functional equation and prove that the polynomial recursively computed from the bilinear operator on each tree T counts the number of trees smaller than T in the Tamari order. Then we show that a similar m + 1-linear operator is also used in the functionnal equation of m-Tamari intervals. We explain how the m-Tamari lattices can be interpreted in terms of m+1-ary trees or a certain class of binary trees. We then use the interval-posets to recover the functional equation of m-Tamari intervals and to prove a generalized formula that counts the number of elements smaller than or equal to a given tree in the m-Tamari lattice.
Type de document :
Article dans une revue
Journal of Combinatorial Theory, Series A, Elsevier, 2015, 134 (58-97), pp.39. 〈http://www.sciencedirect.com/science/article/pii/S0097316515000321〉. 〈10.1016/j.jcta.2015.03.004〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01284728
Contributeur : Viviane Pons <>
Soumis le : mardi 8 mars 2016 - 09:13:49
Dernière modification le : jeudi 11 janvier 2018 - 06:27:11

Identifiants

Citation

Viviane Pons, Grégory Chatel. Counting smaller elements in the Tamari and m-Tamari lattices. Journal of Combinatorial Theory, Series A, Elsevier, 2015, 134 (58-97), pp.39. 〈http://www.sciencedirect.com/science/article/pii/S0097316515000321〉. 〈10.1016/j.jcta.2015.03.004〉. 〈hal-01284728〉

Partager

Métriques

Consultations de la notice

157