The vertical profile of embedded trees

Abstract : 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 =< i =< 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, ... , n_{-1};n_0, ..., 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.
Keywords :
Document type :
Reports

https://hal.archives-ouvertes.fr/hal-00680428
Contributor : Mireille Bousquet-Mélou <>
Submitted on : Monday, March 19, 2012 - 2:28:32 PM
Last modification on : Thursday, March 26, 2020 - 9:17:48 PM
Long-term archiving on: : Wednesday, June 20, 2012 - 2:27:00 AM

Files

profil.pdf
Files produced by the author(s)

Identifiers

• HAL Id : hal-00680428, version 1
• ARXIV : 1203.4148

Citation

Mireille Bousquet-Mélou, Guillaume Chapuy. The vertical profile of embedded trees. 2012. ⟨hal-00680428v1⟩

Record views