Mathematics – Combinatorics
Scientific paper
2012-03-19
Mathematics
Combinatorics
46 pages
Scientific paper
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.
Bousquet-Mélou Mireille
Chapuy Guillaume
No associations
LandOfFree
The vertical profile of embedded trees does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with The vertical profile of embedded trees, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The vertical profile of embedded trees will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-212889