\documentstyle[oldlfont,a4ams,righttag,ctagsplt,emlines2,11pt]{amsart} \newtheorem{theo}{Theorem}%[section] \newtheorem{lemma}{Lemma}[section] \newtheorem{cor}{Corollary} \renewcommand{\thecor}{} \newtheorem{ncor}{Corollary} \theoremstyle{definition} \newtheorem{df}{Definition}[section] \newtheorem{ex}{Example} \renewcommand{\theex}{} \theoremstyle{remark} \newtheorem{rem}{Remark} \renewcommand{\therem}{} \newtheorem{nrem}{Remark} \newcommand{\A}{{\cal A}} \newcommand{\B}{{\cal B}} \newcommand{\C}{$C[0,1]$} \newcommand{\Ca}{$C[0,a]$} \newcommand{\Cinf}{$C[0,\infty)$} \newcommand{\p}{{\bf P}} \newcommand{\beq}{\begin{equation}} \newcommand{\eeq}{\end{equation}} \newcommand{\bal}{\begin{align}} \newcommand{\eal}{\end{align}} \newcommand{\bals}{\begin{align*}} \newcommand{\eals}{\end{align*}} \newcommand{\barr}{\begin{array}{#1}} \newcommand{\earr}{\end{array}} \newcommand{\Ord}{{\cal O}\left(#1\right)} \newcommand{\rcp}{\frac{1}{#1}} %\renewcommand{\qedsymbol}{$\Box$} \newcommand{\E}{{\bf E}#1} \newcommand{\N}{{\bf N}} \newcommand{\bth}{\begin{theo}} \newcommand{\eth}{\end{theo}} \newcommand{\bl}{\begin{lemma}} \newcommand{\el}{\end{lemma}} \newcommand{\bdf}{\begin{df}} \newcommand{\edf}{\end{df}} \newcommand{\brem}{\begin{rem}} \newcommand{\erem}{\end{rem}} \newcommand{\bnrem}{\begin{nrem}} \newcommand{\enrem}{\end{nrem}} \newcommand{\bex}{\begin{ex}} \newcommand{\eex}{\end{ex}} \newcommand{\bcor}{\begin{cor}} \newcommand{\ecor}{\end{cor}} \newcommand{\bncor}{\begin{ncor}} \newcommand{\encor}{\end{ncor}} \newcommand{\bpf}{\begin{pf}} \newcommand{\epf}{\end{pf}} %\newcommand{\implies}{\Longrightarrow} \newcommand{\eps}{\varepsilon} \newcommand{\ph}{\varphi} \newcommand{\cd}{\stackrel{d}{\longrightarrow}} \newcommand{\cw}{\stackrel{w}{\longrightarrow}} \newcommand{\X}{\hat X} \newcommand{\lo}{\hat l} \newcommand{\ggT}{\mbox{ggT}} \newcommand{\swz}{\frac{\sigma}{\sqrt2}} \newcommand{\fpsi}{\frac{\varphi_0}{\varphi(\tau)}} \newcommand{\fpsiinv}{\frac{\varphi(\tau)}{\varphi_0}} \newcommand{\D}{\displaystyle} \newcommand{\Sc}{\scriptstyle} %\numberwithin{equation}{section} \begin{document} \title[on a problem of Yekutieli and Mandelbrot]{ on a problem of Yekutieli and Mandelbrot\\ about the \\ bifurcation ratio of binary trees$^*$} \thanks{$^*$\,A preliminary version of this paper was presented at the conference {\sc Latin} 95 \ (\cite{hor_conf})} \date{\today} \author {Helmut Prodinger} \begin{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. \end{abstract} \maketitle \section{Introduction} This paper solves a problem that was left open (and attacked empirically) in \cite{Y_M}. It concerns binary trees and Horton--Strahler orderings. Here, we phrase everything in the equivalent notion of the {\sl register function}. The register function became famous among computer scientists in the late seventies when Flajolet and his team and Kemp independently determined the average number of registers needed to evaluate a binary tree of size $n$ \cite{FRV, Kemp, MMP, Krus}. If we have an extended binary tree, we label the leaves with 0, and, recursively, if the left subtree of a node is labeled with $a$ and the right subtree with $b$, we label the node with $\max\{a,b\}$ if $a\neq b$ and with $a+1$ otherwise. The value attached to the root is called the {\sl register function\/} of the tree $t$. The value attached to a particular node is the register function of the subtree having this node as its root. The authors in \cite{Y_M} consider the {\sl bifurcation ratio (at the root)}, which we will call the YM--parameter throughout. It is meant to be the {\sl number of maximal subtrees (which is not the same as the number of internal nodes (!)) having register function exactly 1 less than the register function of the entire tree}. See the original paper for a more elaborated problem statement and some motivation. Figure~1 lists all 5 trees with 3 nodes. The first tree in this list has YM--parameter 2, and the other four trees have YM--parameter 4. Hence, the average value of the YM--parameter is $18/5$ in this instance. The tree in Figure~2 has YM--parameter 3. \begin{figure}[t] %TexCad Options %\grade{\on} %\emlines{\on} %\beziermacro{\off} %\reduce{\on} %\snapping{\off} %\quality{2.00} %\graddiff{0.01} %\snapasp{1} %\zoom{0.50} \special{em:linewidth 0.4pt} \unitlength 0.50mm \linethickness{0.4pt} \begin{picture}(290.00,92.01) \put(10.33,19.67){\framebox(10.00,10.00)[cc]{0}} \put(25.00,46.00){\circle{10.02}} \put(30.00,19.67){\framebox(10.00,10.00)[cc]{0}} \emline{22.00}{42.00}{1}{15.00}{30.00}{2} \emline{27.67}{42.00}{3}{35.00}{29.67}{4} \put(25.00,45.67){\makebox(0,0)[cc]{1}} \put(44.62,19.67){\framebox(10.00,10.00)[cc]{0}} \put(59.29,46.00){\circle{10.02}} \put(64.28,19.67){\framebox(10.00,10.00)[cc]{0}} \emline{56.29}{42.00}{5}{49.29}{30.00}{6} \emline{61.95}{42.00}{7}{69.29}{29.67}{8} \put(59.29,45.67){\makebox(0,0)[cc]{1}} \put(42.96,69.33){\circle{10.02}} \emline{39.33}{65.67}{9}{28.00}{50.33}{10} \emline{28.00}{50.33}{11}{28.00}{50.33}{12} \emline{46.67}{65.67}{13}{58.00}{50.67}{14} \put(43.33,69.17){\makebox(0,0)[cc]{2}} \put(77.33,19.67){\framebox(10.00,10.00)[cc]{0}} \put(92.00,46.00){\circle{10.02}} \put(97.00,19.67){\framebox(10.00,10.00)[cc]{0}} \emline{89.00}{42.00}{15}{82.00}{30.00}{16} \emline{94.67}{42.00}{17}{102.00}{29.67}{18} \put(92.00,45.67){\makebox(0,0)[cc]{1}} \put(104.67,66.33){\circle{10.02}} \put(117.33,86.67){\circle{10.02}} \emline{101.67}{62.33}{19}{94.67}{50.33}{20} \emline{114.33}{82.67}{21}{107.33}{70.67}{22} \put(104.67,66.00){\makebox(0,0)[cc]{1}} \put(117.33,86.34){\makebox(0,0)[cc]{1}} \put(110.67,40.67){\framebox(10.00,10.00)[cc]{0}} \put(124.00,62.00){\framebox(10.00,10.00)[cc]{0}} \emline{108.34}{63.00}{23}{115.67}{50.67}{24} \emline{121.67}{84.33}{25}{129.00}{72.00}{26} \put(184.67,19.67){\framebox(10.00,10.00)[cc]{0}} \put(180.00,46.00){\circle{10.02}} \put(165.00,19.67){\framebox(10.00,10.00)[cc]{0}} \emline{183.00}{42.00}{27}{190.00}{30.00}{28} \emline{177.33}{42.00}{29}{170.00}{29.67}{30} \put(180.00,45.67){\makebox(0,0)[cc]{1}} \put(167.33,66.33){\circle{10.02}} \put(154.67,86.67){\circle{10.02}} \emline{170.33}{62.33}{31}{177.33}{50.33}{32} \emline{157.67}{82.67}{33}{164.67}{70.67}{34} \put(167.33,66.00){\makebox(0,0)[cc]{1}} \put(154.67,86.34){\makebox(0,0)[cc]{1}} \put(151.33,40.67){\framebox(10.00,10.00)[cc]{0}} \put(138.00,62.00){\framebox(10.00,10.00)[cc]{0}} \emline{163.66}{63.00}{35}{156.33}{50.67}{36} \emline{150.33}{84.33}{37}{143.00}{72.00}{38} \put(221.33,87.00){\circle{10.02}} \emline{218.33}{83.00}{39}{211.33}{71.00}{40} \put(221.33,86.67){\makebox(0,0)[cc]{1}} \put(228.00,62.34){\framebox(10.00,10.00)[cc]{0}} \emline{225.67}{84.67}{41}{233.00}{72.34}{42} \put(226.00,19.67){\framebox(10.00,10.00)[cc]{0}} \put(221.33,46.00){\circle{10.02}} \put(206.33,19.67){\framebox(10.00,10.00)[cc]{0}} \emline{224.33}{42.00}{43}{231.33}{30.00}{44} \emline{218.66}{42.00}{45}{211.33}{29.67}{46} \put(221.33,45.67){\makebox(0,0)[cc]{1}} \put(208.67,66.33){\circle{10.02}} \emline{211.67}{62.33}{47}{218.67}{50.33}{48} \put(208.67,66.00){\makebox(0,0)[cc]{1}} \put(192.67,40.67){\framebox(10.00,10.00)[cc]{0}} \emline{205.00}{63.00}{49}{197.67}{50.67}{50} \put(261.33,87.00){\circle{10.02}} \emline{264.33}{83.00}{51}{271.33}{71.00}{52} \put(261.33,86.67){\makebox(0,0)[cc]{1}} \put(244.67,62.34){\framebox(10.00,10.00)[cc]{0}} \emline{257.00}{84.67}{53}{249.67}{72.34}{54} \put(246.66,19.67){\framebox(10.00,10.00)[cc]{0}} \put(261.33,46.00){\circle{10.02}} \put(266.33,19.67){\framebox(10.00,10.00)[cc]{0}} \emline{258.33}{42.00}{55}{251.33}{30.00}{56} \emline{264.00}{42.00}{57}{271.33}{29.67}{58} \put(261.33,45.67){\makebox(0,0)[cc]{1}} \put(274.00,66.33){\circle{10.02}} \emline{271.00}{62.33}{59}{264.00}{50.33}{60} \put(274.00,66.00){\makebox(0,0)[cc]{1}} \put(280.00,40.67){\framebox(10.00,10.00)[cc]{0}} \emline{277.67}{63.00}{61}{285.00}{50.67}{62} \end{picture} \caption{All 5 trees with 3 internal nodes} \end{figure} It was observed empirically that the expected value of this parameter is asymptotically a periodic function of $\log_4n$ if all trees of size $n$ ($n$ internal nodes) are considered to be equally likely. Here we want to settle this problem by explicitly describing the periodic function in terms of the Fourier coefficients. In principle, a full asymptotic expansion could be given, but the computation of the lower order term becomes more and more complicated. \begin{figure}[t] %TexCad Options %\grade{\on} %\emlines{\on} %\beziermacro{\off} %\reduce{\on} %\snapping{\off} %\quality{2.00} %\graddiff{0.01} %\snapasp{1} %\zoom{0.50} \special{em:linewidth 0.4pt} \unitlength 0.50mm \linethickness{0.4pt} \begin{picture}(283.78,170.01) \put(10.33,19.67){\framebox(10.00,10.00)[cc]{0}} \put(25.00,46.00){\circle{10.02}} \put(30.00,19.67){\framebox(10.00,10.00)[cc]{0}} \emline{22.00}{42.00}{1}{15.00}{30.00}{2} \emline{27.67}{42.00}{3}{35.00}{29.67}{4} \put(25.00,45.67){\makebox(0,0)[cc]{1}} \put(44.62,19.67){\framebox(10.00,10.00)[cc]{0}} \put(59.29,46.00){\circle{10.02}} \put(64.28,19.67){\framebox(10.00,10.00)[cc]{0}} \emline{56.29}{42.00}{5}{49.29}{30.00}{6} \emline{61.95}{42.00}{7}{69.29}{29.67}{8} \put(59.29,45.67){\makebox(0,0)[cc]{1}} \put(42.96,69.33){\circle{10.02}} \emline{39.33}{65.67}{9}{28.00}{50.33}{10} \emline{28.00}{50.33}{11}{28.00}{50.33}{12} \emline{46.67}{65.67}{13}{58.00}{50.67}{14} \put(77.66,19.67){\framebox(10.00,10.00)[cc]{0}} \put(92.33,46.00){\circle{10.02}} \put(97.33,19.67){\framebox(10.00,10.00)[cc]{0}} \emline{89.33}{42.00}{15}{82.33}{30.00}{16} \emline{95.00}{42.00}{17}{102.33}{29.67}{18} \put(92.33,45.67){\makebox(0,0)[cc]{1}} \put(111.95,19.67){\framebox(10.00,10.00)[cc]{0}} \put(126.62,46.00){\circle{10.02}} \put(131.61,19.67){\framebox(10.00,10.00)[cc]{0}} \emline{123.62}{42.00}{19}{116.62}{30.00}{20} \emline{129.28}{42.00}{21}{136.62}{29.67}{22} \put(110.29,69.33){\circle{10.02}} \emline{106.67}{65.67}{23}{95.33}{50.33}{24} \emline{114.00}{65.67}{25}{125.33}{50.67}{26} \put(43.33,69.17){\makebox(0,0)[cc]{2}} \put(110.00,69.17){\makebox(0,0)[cc]{2}} \emline{81.11}{99.44}{27}{108.89}{73.89}{28} \put(167.40,69.33){\circle{10.02}} \put(202.11,19.67){\framebox(10.00,10.00)[cc]{0}} \put(216.78,46.00){\circle{10.02}} \put(221.78,19.67){\framebox(10.00,10.00)[cc]{0}} \emline{213.78}{42.00}{29}{206.78}{30.00}{30} \emline{219.45}{42.00}{31}{226.78}{29.67}{32} \put(216.78,45.67){\makebox(0,0)[cc]{1}} \put(236.40,19.67){\framebox(10.00,10.00)[cc]{0}} \put(251.07,46.00){\circle{10.02}} \put(256.06,19.67){\framebox(10.00,10.00)[cc]{0}} \emline{248.07}{42.00}{33}{241.07}{30.00}{34} \emline{253.73}{42.00}{35}{261.07}{29.67}{36} \put(234.73,69.33){\circle{10.02}} \emline{231.11}{65.67}{37}{219.78}{50.33}{38} \emline{238.44}{65.67}{39}{249.78}{50.67}{40} \put(167.78,69.17){\makebox(0,0)[cc]{1}} \put(234.44,69.17){\makebox(0,0)[cc]{2}} \put(201.40,103.22){\circle{10.02}} \emline{197.78}{100.00}{41}{171.11}{73.89}{42} \put(152.51,43.00){\framebox(10.00,10.00)[cc]{0}} \put(167.18,69.33){\circle{10.02}} \put(172.17,43.00){\framebox(10.00,10.00)[cc]{0}} \emline{164.18}{65.33}{43}{157.18}{53.33}{44} \emline{169.84}{65.33}{45}{177.18}{53.00}{46} \put(141.96,137.67){\circle{10.02}} \emline{137.78}{135.56}{47}{80.56}{107.78}{48} \emline{146.67}{135.00}{49}{198.33}{108.33}{50} \put(254.11,110.34){\framebox(10.00,10.00)[cc]{0}} \put(268.78,136.67){\circle{10.02}} \put(273.78,110.34){\framebox(10.00,10.00)[cc]{0}} \emline{265.78}{132.67}{51}{258.78}{120.67}{52} \emline{271.45}{132.67}{53}{278.78}{120.34}{54} \put(268.78,136.34){\makebox(0,0)[cc]{1}} \put(207.96,165.00){\circle{10.02}} \emline{203.33}{163.33}{55}{146.67}{141.33}{56} \emline{213.33}{163.33}{57}{265.33}{141.33}{58} \emline{265.33}{141.33}{59}{265.33}{141.33}{60} \put(142.00,137.33){\makebox(0,0)[cc]{3}} \put(201.33,103.33){\makebox(0,0)[cc]{2}} \put(251.33,46.00){\makebox(0,0)[cc]{1}} \put(208.00,165.33){\makebox(0,0)[cc]{3}} \emline{73.00}{100.00}{61}{46.33}{73.33}{62} \put(126.67,46.00){\makebox(0,0)[cc]{1}} \emline{205.33}{100.33}{63}{231.67}{73.67}{64} \put(78.63,103.00){\circle{10.02}} \put(78.67,102.66){\makebox(0,0)[cc]{3}} \end{picture} \caption{A binary tree of size 15 with register function 3 and 3 maximal subtrees with register function 2, which are displayed in Figure 3.} \end{figure} \begin{figure} %TexCad Options %\grade{\on} %\emlines{\on} %\beziermacro{\off} %\reduce{\on} %\snapping{\off} %\quality{2.00} %\graddiff{0.01} %\snapasp{1} %\zoom{0.50} \special{em:linewidth 0.4pt} \unitlength 0.5mm \linethickness{0.4pt} \begin{picture}(266.06,108.23) \put(10.33,19.67){\framebox(10.00,10.00)[cc]{0}} \put(25.00,46.00){\circle{10.02}} \put(30.00,19.67){\framebox(10.00,10.00)[cc]{0}} \emline{22.00}{42.00}{1}{15.00}{30.00}{2} \emline{27.67}{42.00}{3}{35.00}{29.67}{4} \put(25.00,45.67){\makebox(0,0)[cc]{1}} \put(44.62,19.67){\framebox(10.00,10.00)[cc]{0}} \put(59.29,46.00){\circle{10.02}} \put(64.28,19.67){\framebox(10.00,10.00)[cc]{0}} \emline{56.29}{42.00}{5}{49.29}{30.00}{6} \emline{61.95}{42.00}{7}{69.29}{29.67}{8} \put(59.29,45.67){\makebox(0,0)[cc]{1}} \put(42.96,69.33){\circle{10.02}} \emline{39.33}{65.67}{9}{28.00}{50.33}{10} \emline{28.00}{50.33}{11}{28.00}{50.33}{12} \emline{46.67}{65.67}{13}{58.00}{50.67}{14} \put(77.66,19.67){\framebox(10.00,10.00)[cc]{0}} \put(92.33,46.00){\circle{10.02}} \put(97.33,19.67){\framebox(10.00,10.00)[cc]{0}} \emline{89.33}{42.00}{15}{82.33}{30.00}{16} \emline{95.00}{42.00}{17}{102.33}{29.67}{18} \put(92.33,45.67){\makebox(0,0)[cc]{1}} \put(111.95,19.67){\framebox(10.00,10.00)[cc]{0}} \put(126.62,46.00){\circle{10.02}} \put(131.61,19.67){\framebox(10.00,10.00)[cc]{0}} \emline{123.62}{42.00}{19}{116.62}{30.00}{20} \emline{129.28}{42.00}{21}{136.62}{29.67}{22} \put(110.29,69.33){\circle{10.02}} \emline{106.67}{65.67}{23}{95.33}{50.33}{24} \emline{114.00}{65.67}{25}{125.33}{50.67}{26} \put(43.33,69.17){\makebox(0,0)[cc]{2}} \put(110.00,69.17){\makebox(0,0)[cc]{2}} \put(167.40,69.33){\circle{10.02}} \put(202.11,19.67){\framebox(10.00,10.00)[cc]{0}} \put(216.78,46.00){\circle{10.02}} \put(221.78,19.67){\framebox(10.00,10.00)[cc]{0}} \emline{213.78}{42.00}{27}{206.78}{30.00}{28} \emline{219.45}{42.00}{29}{226.78}{29.67}{30} \put(216.78,45.67){\makebox(0,0)[cc]{1}} \put(236.40,19.67){\framebox(10.00,10.00)[cc]{0}} \put(251.07,46.00){\circle{10.02}} \put(256.06,19.67){\framebox(10.00,10.00)[cc]{0}} \emline{248.07}{42.00}{31}{241.07}{30.00}{32} \emline{253.73}{42.00}{33}{261.07}{29.67}{34} \put(234.73,69.33){\circle{10.02}} \emline{231.11}{65.67}{35}{219.78}{50.33}{36} \emline{238.44}{65.67}{37}{249.78}{50.67}{38} \put(167.78,69.17){\makebox(0,0)[cc]{1}} \put(234.44,69.17){\makebox(0,0)[cc]{2}} \put(201.40,103.22){\circle{10.02}} \emline{197.78}{100.00}{39}{171.11}{73.89}{40} \put(152.51,43.00){\framebox(10.00,10.00)[cc]{0}} \put(167.18,69.33){\circle{10.02}} \put(172.17,43.00){\framebox(10.00,10.00)[cc]{0}} \emline{164.18}{65.33}{41}{157.18}{53.33}{42} \emline{169.84}{65.33}{43}{177.18}{53.00}{44} \put(201.33,103.33){\makebox(0,0)[cc]{2}} \put(251.33,46.00){\makebox(0,0)[cc]{1}} \put(126.67,46.00){\makebox(0,0)[cc]{1}} \emline{205.33}{100.33}{45}{231.67}{73.67}{46} \end{picture} \caption{The 3 maximal subtrees with register function 2.} \end{figure} \section{The average value of the Yekutieli--Mandelbrot parameter} We start our analysis with some notions and results from the literature. Let $b_n$, $r_{p,n}$, and $s_{p,n}$ denote the number of binary trees of size $n$, the number of binary trees of size $n$ and register function $=p$, and the number of binary trees of size $n$, and register function $\ge p$, respectively. Then \begin{gather}\begin{split}\label{defs} B(z)= \sum_{n\ge0}b_nz^n=\frac{1-\sqrt{1-4z}}{2z}= \sum_{n\ge0}\frac1{n+1}\binom{2n}{n}z^n=1+u, \quad\text{with}\quad z=\frac{u}{(1+u)^2} \\ R_p(z)=\sum_{n\ge0}r_{p,n}z^n= \frac{1-u^2}{u}\frac{u^{2^p}}{1-u^{2^{p+1}}},\qquad\text{with} \quad z=\frac{u}{(1+u)^2},\\ S_p(z)=\sum_{n\ge0}s_{p,n}z^n= \frac{1-u^2}{u}\frac{u^{2^p}}{1-u^{2^{p}}},\qquad\text{with} \quad z=\frac{u}{(1+u)^2}. \end{split} \end{gather} The first generating function is classical, and the other two appeared in \cite{FRV,Kemp, P1, P2, P3}. The substitution (cf. \cite{deBKR}) $z=u/(1+u)^2$ will be used throughout. Note that $B(z)-S_p(z)$ is the generating function of the binary trees with $n$ nodes and register function \$