The Vertical Profile of Embedded Trees

Source 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 \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.