Enumeration of (uni- or bicolored) plane trees according to their degree distribution

✍ Scribed by Gilbert Labelle; Pierre Leroux

• Publisher: Elsevier Science
• Year: 1996
• Tongue: English
• Weight: 1021 KB
• Volume: 157
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/s0012-365x(96)83017-2

✦ Synopsis

The main object of this paper is to give explicit formulas for the number of unlabelled bicolored (unrooted) plane trees with given degree distributions (1'12iz., . ; 1/12'2.1 ,). These trees are closely related to the Shabat polynomials, i.e., ~1~~~s over 8: having at most two critical values (cf. . In the case of planted trees (i.e., rooted at a leaf), this problem was solved by Tutte in 1964, using multivariate &range inversion. Here the key to the solution is the dissymmetry theorem for enriched trees which takes a particularly simple form in the bicolored case and which allows one to get rid of the rooting. We also enumerate those trees in the labelled case, in the unicolored case, as well as when the au~o~~~ group (necessarily cyclic) is of order h equal to (or a multiple of) a given integer R3 1.

L'objectif principal de ce texte est de dormer des formules explicites pour le nombre de types d'isomorphie d'arbres plans bicolor6s ayant une double ~s~bution ( 1'12'2.. . ; 1" 2'2.. .) de &g&s domn5s a l'avance. Ces arbres sont en &t&e relation avec les poly&mes de Shabat, c'est-i-dire les polynomes sur C ayant au plus deux valeurs critiques (cf. . Dans le cas des arbres enracines (point&r en une feuille), ce probl&me a et6 r6solu par Tutte en 1964 ii l'aide de l'inversion de Lagrange multivariee. Ici la cl& de la solution reside dans le theoreme de dissym&rie pour les arbres enrichis qui, dans le cas bicolor6, prend une fbrme particuli&rement simple et qui permet de se d6fah-e du pointage. Nous d6nombrons CgaIement ces arbres dam le cas etiquet6, dans le cas unicolo&, ainsi que lorsque le groupe ~au~rno~~~s, night cyclique, est d'un ordre h &gal P (ou multiple de) un entier k z 1 donne.