On a problem of Yekutieli and Mandelbrot about the bifurcation ratio of
binary trees
Abstract.
Concerning the Horton--Strahler number (or Register function) of
binary trees, Yekutieli and Mandelbrot posed the problem of analyzing
the bifurcation 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, than the average value of this number
of subtrees is asymptotic to $3.341266 +\delta(\log_4n)$, where
an analytic expression for the numerical constant is available and
$\delta(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.
This paper is the journal version of an
older paper .
helmut@gauss.cam.wits.ac.za,
This paper is available in the Tex, Dvi, and PostScript format.
(Back to List of Papers)