On a problem of Yekutieli and Mandelbrot about the bifurcation ratio of binary trees

✍ Scribed by Helmut Prodinger

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 677 KB
• Volume: 181
• Category: Article
• ISSN: 0304-3975
• DOI: 10.1016/s0304-3975(96)00269-1

✦ Synopsis

Concerning the Horton-Strahler number (or register function) of binary trees, Yekutieli and Mandelbrot posed the problem of analyzing the bihtrcation ratio of the root, which means how many maximal subtrees of register function one less than the whole tree are present in the tree. We show that if all binary trees of size n are considered to be equally likely, then the average value of this number of subtrees is asymptotic to 3.341266+6 (log, n), where an analytic expression for the numerical constant is available and S(x) is a (small) periodic function of period 1, which is also given explicitly. Additionally, we sketch the computation of the variance and also of higher bifurcation ratios.