The vertical profile of embedded trees

Mireille Bousquet-Mélou¹ ; Guillaume Chapuy²

¹CNRS, LaBRI, Université Bordeaux 1, 351 cours de la Libération, 33405 Talence, France
²CNRS, LIAFA, Université Paris 7, 175 rue du Chevaleret, 75203 Paris, France

The electronic journal of combinatorics, Tome 19 (2012) no. 3

Résumé

Consider a rooted binary tree with $n$ nodes. Assign with the root the abscissa 0, and with the left (resp. right) child of a node of abscissa $i$ the abscissa $i-1$ (resp. $i+1$). We prove that the number of binary trees of size $n$ having exactly $n_i$ nodes at abscissa $i$, for $l \leq i \leq r$ (with $n = \sum_i n_i$), is $$ \frac{n_0}{n_l n_r} {{n_{-1}+n_1} \choose {n_0-1}} \prod_{l\le i\le r \atop i\not = 0}{{n_{i-1}+n_{i+1}-1} \choose {n_i-1}}, $$ with $n_{l-1}=n_{r+1}=0$. The sequence $(n_l, \dots, n_{-1};n_0, \dots n_r)$ is called the vertical profile of the tree. The vertical profile of a uniform random tree of size $n$ is known to converge, in a certain sense and after normalization, to a random mesure called the integrated superbrownian excursion, which motivates our interest in the profile. We prove similar looking formulas for other families of trees whose nodes are embedded in $Z$. We also refine these formulas by taking into account the number of nodes at abscissa j whose parent lies at abscissa $i$, and/or the number of vertices at abscissa i having a prescribed number of children at abscissa $j$, for all $i$ and $j$. Our proofs are bijective.

Détail

DOI : 10.37236/2150

Classification : 05C30, 05A15, 05C05, 05C80
Mots-clés : enumeration, embedded trees