\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}[1]{\begin{array}{#1}}
\newcommand{\earr}{\end{array}}
\newcommand{\Ord}[1]{{\cal O}\left(#1\right)} 
\newcommand{\rcp}[1]{\frac{1}{#1}}
%\renewcommand{\qedsymbol}{$\Box$}
\newcommand{\E}[1]{{\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 $<p$.

Now, let $w_{p,k,n}$ be the number of binary trees with $n$ nodes, 
register function $p$, and  YM--parameter $k$, and let
\beq \label{bas_rec}
W_p(z,y)=\sum_{n,k\ge0}w_{p,k,n}\,y^kz^n
\end{equation}
be its bivariate generating function.

 To find the expected values, we have to work with
$T_p(z)=\frac{\partial}{\partial y}W_p(z,y)|_{y=1}$ and
\begin{equation}
T(z)=\sum_{p \ge 1 }T_p(z).
\end{equation}
The coefficient of $z^n$ in $T(z)$, divided by $\frac{1}{n+1}\binom{2n}{n}$,
is the expected value sought by Yekutieli and Mandelbrot.

We can find an equation for $W_p(z,y)$ by considering 3 cases. Either
both subtrees have register function $p-1$, then we have $y^2$, since
the YM--parameter is 2. Or, we have to go down recursively. If the smaller
subtree (with 
respect to the register function!)
of the root has register function $p-1$, 
we have to label by a $y$, if it is even smaller, we do not label. 
Observe that there is a unique path from the root to a node with both
successors having register function $p-1$.
Hence we have for $p\ge1$
\begin{equation}
W_p(z,y)=zy^2R_{p-1}^2(z)+2zyW_p(z,y)R_{p-1}(z)+2zW_p(z,y)\big(B(z)-
S_{p-1}(z)\big),
\end{equation}
and therefore (since $R_{p-1}(z)+B(z)-S_{p-1}(z)=B(z)-S_{p}(z)$)
\begin{equation*}
T_p(z)=2zR_{p-1}^2(z)+2zR_p(z)R_{p-1}(z)+2zT_p(z)\big(B(z)-
S_{p}(z)\big),
\end{equation*}
or
\begin{equation}\label{Teq}
T_p(z)=\frac{2zR_{p-1}(z)\big( R_{p-1}(z)+R_{p}(z)\big)}
{1-2z\big(B(z)-
S_{p}(z)\big)}.
\end{equation}
One may now use the definitions (\ref{defs}) to easily verify
\begin{equation*}1-2z\big(B(z)-
S_{p}(z)\big)=\frac{1-u}{1+u}\, \frac{1+u^{2^p}}{1-u^{2^p}}.
\end{equation*}
Therefore (\ref{Teq}) may be rewritten as
\begin{align}\begin{split}\label{eq6}
T_p(z)&=\frac{1+u}{1-u}\frac{1-u^{2^p}}{1+u^{2^p}}
\frac{2u}{(1+u)^2}\left(\frac{1-u^2}{u}\right)^2
\frac{u^{2^{p-1}}}{1-u^{2^p}}\left[
\frac{u^{2^{p-1}}}{1-u^{2^p}}+\frac{u^{2^{p}}}{1-u^{2^{p+1}}}\right]\\
&=2\frac{1-u^2}{u}\left[
\frac{u^{2^{p}}}{1-u^{2^{p+1}}}+
\frac{u^{3\cdot2^{p-1}}}{(1+u^{2^{p}})(1-u^{2^{p+1}})}\right].
\end{split}\end{align}
Hence we get, upon summing on $p$ and performing some easy simplifications,
\begin{align}\begin{split}\label{teqq}
T(z)&=2\frac{1-u^2}{u}\sum_{p\ge1}
\left[
\frac{u^{2^{p}}}{1-u^{2^{p+1}}}+
\frac{u^{3\cdot2^{p-1}}}{(1+u^{2^{p}})(1-u^{2^{p+1}})}\right]\\
&=2\frac{1-u^2}{u}
\left[
\frac{u^2}{1-u^2}+\sum_{p\ge1}
\frac{u^{3\cdot2^{p-1}}}{(1+u^{2^{p}})(1-u^{2^{p+1}})}\right]\\
&=2u+2\frac{1-u^2}{u}
\sum_{p\ge1}
\frac{u^{3\cdot2^{p-1}}}{{(1+u^{2^{p}})}^2(1-u^{2^{p}})}.
\end{split}
\end{align}
Let us concentrate on the series
\begin{equation}
\sigma=\sum_{p\ge1}
\frac{u^{3\cdot2^{p-1}}}{{(1+u^{2^{p}})}^2(1-u^{2^{p}})}
=\sum_{p\ge1,\, i,j\ge0}u^{3\cdot2^{p-1}+(i+j)2^p}(-1)^i(i+1)
\end{equation}
appearing in (\ref{teqq}), since the other terms in (\ref{teqq}) are easy.
Now
\begin{equation*}
\sum_{i=0}^k(-1)^i(i+1)=(-1)^k\left({\left\lfloor\tfrac k2
\right\rfloor}+1
\right),
\end{equation*}
and thus
\begin{align}\begin{split}
\sigma&=\sum_{p\ge0, k\ge0}u^{3\cdot2^p+k2^{p+1}}
(-1)^k\left(\left\lfloor\tfrac k2\right\rfloor+1
\right)\\
&=\sum_{p\ge0, k\ge1}u^{2^p(2k+1)}(-1)^{k-1}\left\lfloor\tfrac{k+1}{2}
\right\rfloor\\
&=-\sum_{p,k\ge0}
ku^{2^p(4k+1)}+\sum_{p,k\ge0}
(k+1)u^{2^p(4k+3)}.
\end{split}\end{align}


The further methodology is to find the behavior of $T\big(z(u)\big)$ 
as $u\to1$, 
itself giving the local expansion of $T(z)$
about the singularity $z=\frac14$.
Since elementary methods fail, we proceed as follows.
Setting $u=e^{-t}$, we are interested in $t\to0$. As it is now standard, 
and described in \cite{Fl_Pr, Fl_Od, P3}, we compute the {\sl Mellin 
transform} (see the survey \cite{FGD}) of the series
\begin{equation*}
\sigma=-\sum_{p,k\ge0}
ke^{-t2^p(4k+1)}+\sum_{p,k\ge0}
(k+1)e^{-t2^p(4k+3)}.
\end{equation*}
Since $e^{-at}$ maps into $a^{-s}\Gamma(s)$, $\sigma$ maps into
$\Gamma(s)$ times
\begin{equation*}
-\sum_{p,k\ge0}k2^{-ps}(4k+1)^{-s}+\sum_{p,k\ge0}(k+1)2^{-ps}(4k+3)^{-s}.
\end{equation*}
These series are easily evaluated by means of the {\sl Hurwitz
zeta function} (\cite{WW})
\begin{equation*}
\zeta(s,a)=\sum_{n\ge0}\frac{1}{(n+a)^s}.
\end{equation*}
We just mention that the so-called {\sl fundamental strip\/} is $\langle2,
\infty\rangle$.
We find
\begin{equation*}
\sum_{k\ge0}k(4k+1)^{-s}=4^{-s}\sum_{k\ge0}k(k+\tfrac14)^{-s}
=4^{-s}\left(\zeta(s-1,\tfrac14)-\frac14\zeta(s,\tfrac14)\right)
\end{equation*}
and
\begin{equation*}
\sum_{k\ge0}(k+1)(4k+3)^{-s}=4^{-s}\sum_{k\ge0}(k+1)(k+\tfrac34)^{-s}
=4^{-s}\left(\zeta(s-1,\tfrac34)+\frac14\zeta(s,\tfrac34)\right).
\end{equation*}
Also, 
\begin{equation*}
\zeta(s,\tfrac14)+\zeta(s,\tfrac34)=4^s(1-2^{-s})\zeta(s).
\end{equation*}
Hence $\sigma$ maps into
\begin{align}\begin{split}
&
\frac{\Gamma(s)}{1-2^{-s}}\left[
-4^{-s}\left(\zeta(s-1,\tfrac14)-\zeta(s-1,\tfrac34)\right)+
\frac14(1-2^{-s})\zeta(s)\right]\\
&=-\frac{\Gamma(s)}{2^s(2^{s}-1)}\left(\zeta(s-1,\tfrac14)-\zeta(s-1,\tfrac34)\right)
+\frac14\Gamma(s)\zeta(s).
\end{split}\end{align}

To find the asymptotic behavior of $\sigma$, we must consider the residues
of the last quantity
times $t^{-s}$ left to the line $\Re s=\frac52$. As already stated, more
information about this methodology can be found in \cite{Fl_Pr, Fl_Od,
P1, P2, P3}.

The Hurwitz zeta functions have  simple poles at $s=2$, but they cancel
out. The zeta function has a simple pole at $s=1$, and the 
corresponding residue is
$\frac{1}{4t}$. At $s=0$, at the first glance, it looks like a second
order pole. However, according to \cite {WW}, we have the following.
Write $\beta(s)=\zeta(s,\tfrac14)-\zeta(s,\tfrac34)$, then 
\begin{equation}\label{beta_eq}
\beta(s)=4 (8\pi)^{s-1}\Gamma(1-s)\cos\frac{s\pi }{2}\beta(1-s).
\end{equation}
The presence of the cosine gives the value $\beta(-1)=0$. We also need
$\beta'(-1)$. Deriving the product, only the term with the cosine derived
survives, and we find
\begin{equation*}
\beta'(-1)=\frac{1}{32\pi}\beta(2).
\end{equation*}
The series
\begin{equation}
{\cal C}=\sum_{k\ge0}\frac{(-1)^k}{(2k+1)^2}=\frac{1}{16}
\beta(2)=0.9159655942\dots
\end{equation}
is called {\sl Catalan's constant} \cite{Ab_St}.
Hence as $s\to 0$,\quad $\beta(s-1)\sim s\cdot \frac{{\cal C}}{2\pi}$.

Therefore the corresponding residue is
\begin{equation*}
-\frac{1}{\log2}\frac{{\cal C}}{2\pi}-\frac18.
\end{equation*}
There are also simple poles at $s=\chi_k=\frac{2k\pi i}{\log2}$\quad ($k\ne0$)
with
residue
\begin{equation*}
-\frac{\Gamma(\chi_k)}{\log2}\beta(\chi_k-1)t^{-\chi_k}.
\end{equation*}
The other residues at the negative integers (originating from the
$\Gamma$--function) lead to 
smaller order terms and will be neglected.

Therefore the contribution of the series $\sigma$ is
\begin{equation}
\frac{1}{4t}-\frac{1}{\log2}\frac{{\cal C}}{2\pi}-\frac18-
\frac{1}{\log2}\sum_{k\ne0}{\Gamma(\chi_k)}\beta(\chi_k-1)t^{-\chi_k}
\end{equation}
Let us recall that we want the expansion of $T(z)$ in terms of
$1-4z$. First, we give it in terms of $t$\quad ($t\to 0$).
\begin{equation}
T(z)\sim 2-2t+ 4t\left[
\frac{1}{4t}-\frac{1}{\log2}\frac{{\cal C}}{2\pi}-\frac18-
\frac{1}{\log2}\sum_{k\ne0}{\Gamma(\chi_k)}\beta(\chi_k-1)t^{-\chi_k}
\right].
\end{equation}
And, since 
\begin{equation*}
t\sim 2\sqrt{1-4z},
\end{equation*}
we obtain
\begin{equation}
T(z)\sim 3 -\left(\frac{4{\cal C}}{(\log2)\pi}+5\right)\sqrt{1-4z}-
\frac{8}{\log2}\sum_{k\ne0}{\Gamma(\chi_k)}\beta(\chi_k-1)
(1-4z)^{(1-\chi_k)/2}.
\end{equation}
Now, according to   \cite{Fl_Od}, we can go over to the asymptotics
of the coefficients, using the rule
\begin{equation*}
[z^n](1-z)^\alpha\sim \frac{n^{-\alpha-1}}{\Gamma(-\alpha)}\ .
\end{equation*}
For the sake of simplicity, we stated all the asymptotic expansions in
terms of  `$\sim$' (asymptotic equivalence). However, in all instances,
${\cal O}$--terms are available (decreasing the readability),
 and  a 
``${\cal O}$--transfer''\cite{Fl_Od} is possible; we only
state a ${\cal O}$--result in our main theorem. In this way we get
\begin{align}\begin{split}
[z^n]T(z)&\sim \frac{1}{2\sqrt\pi}\left(\frac{4{\cal C}}{(\log2)\pi}+5\right)
4^nn^{-3/2}\\ & -\frac{2}{(\log2)\sqrt\pi}\sum_{k\ne0}
(\chi_k-1)\Gamma\big(\frac{\chi_k}{2}\big)\beta(\chi_k-1)4^nn^{-3/2}
e^{\log_4n\cdot 2k\pi i}\ .
\end{split}\end{align}
Since
\begin{equation*}
\frac{1}{n+1}\binom{2n}{n}\sim \frac{1}{\sqrt\pi}4^nn^{-3/2},
\end{equation*}
we get the desired result by dividing these two quantities.

The value 
\begin{equation*}
 \frac{2{\cal C}}{(\log2)\pi}+\frac 52=3.341266\dots
\end{equation*}
is the value around which the expected value of the  
YM--parameter fluctuates,
in agreement with the numerical observations in \cite{Y_M}.

\begin{theo} The average value of the Yekutieli--Mandelbrot 
parameter, if all binary trees of size $n$
 are considered to be equally likely, is given by
\begin{equation}
\frac{2{\cal C}}{(\log2)\pi}+\frac 52+\delta(\log_4n)+{\cal O}\Big(
\frac 1n\Big).
\end{equation}
The periodic function $\delta(x)$ has mean value 0 and admits the
following representation as a Fourier series,
\begin{equation}
\delta(x)=-
\frac{2}{\log2}\sum_{k\ne0}
(\chi_k-1)\Gamma\big(\frac{\chi_k}{2}\big)\beta(\chi_k-1)
e^{ 2k\pi ix};
\end{equation}
the function $\beta(x)$ is defined in (\ref{beta_eq}) and $\chi_k=\frac
{2k\pi i}{\log2}$.
\end{theo}



\begin{rem} Although it is not needed for the solution of the present
problem, it is possible to get an {\sl exact\/} formula for
$[z^n]T(z)$. For that, we use Cauchy's integral formula.
\begin{align*}
[z^n]T(z)&=\frac{1}{2\pi i}\oint\frac{dz}{z^{n+1}}T(z)\\
&=2\cdot \frac{1}{2\pi i}\oint\frac{du (1-u)(1+u)^{2n-1}}{u^{n+1}}
\left[u+\frac{1-u^2}{u}\sigma\right]\\
&=2[u^n](1-u)(1+u)^{2n-1}\left[u+\frac{1-u^2}{u}\sigma\right]\\
&=2\binom{2n-1}{n-1}-2\binom{2n-1}{n-2}
+2[u^{n+1}](1-u)^2(1+u)^{2n}\sigma\\
&=\frac{2}{n+1}\binom{2n}{n}+2\Big(
[u^{n+1}]-2[u^{n}]+[u^{n-1}]
\Big)(1+u)^{2n}\sum_{m\ge1}\psi(m)u^m,
\end{align*}
where the arithmetical function $\psi(m)$ is defined by
\begin{equation}
\psi(m)=\begin{cases} 
	-k\qquad &\text{if } m=2^i(4k+1)
		\text{\quad for some $i$ and $k$}\\
        k+1\qquad &\text{if } m=2^i(4k+3)\text{\quad for some $i$ and $k$}
        \end{cases}
\end{equation}
for convenience. 
Note that each integer has a unique representation as $2^i(4k+1)$ or
$2^i(4k+3)$. 
Hence (apart from a normalization factor $\frac1{n+1}\binom{2n}{n}$\ )
an exact value of the expected value of the YM--parameter in an
$n$--node binary tree is
\begin{equation}
[z^n]T(z)=\frac{2}{n+1}\binom{2n}{n}+2\sum_{m\ge1}\psi(m)
\left[
\binom{2n}{n+1-m}-2\binom{2n}{n-m}+\binom{2n}{n-1-m}
\right].
\end{equation}
One could also work out the asymptotics from this formula, but
it is less recommended because of more involved computations.
\end{rem}

\section {The variance}  

The variance can be analyzed in the same style. We give the key steps.

Let $U_p(z)=\frac{\partial^2}{\partial y^2}W_p(z,y)|_{y=1}$ be the
\textsl{second factorial moment}. We find from the basic recursion (\ref{bas_rec})
\begin{align}\begin{split}
U_p(z)&=\frac{2zR_{p-1}^2(z)+4zT_p(z)R_{p-1}(z)}{{1-2z\big(B(z)-
S_{p}(z)\big)}}\\
&=2\frac{1-u^2}{u}\left[
\frac{u^{2^p}}{1-u^{2^{p+1}}}+4\frac{u^{3\cdot2^{p-1}}}{{(1+u^{2^{p}})}^2
(1-u^{2^{p}})}+4\frac{u^{2^{p+1}}}{{(1+u^{2^{p}})}^3
(1-u^{2^{p}})}
\right],
\end{split}\end{align}
and
\begin{equation}\label{U_def}
U(z):=\sum_{p\ge1}U_p(z)=2u+8\frac{1-u^2}{u}\sigma+8\frac{1-u^2}{u}\tau-
8\frac{u}{(1+u)^2}
\end{equation}
with
\begin{equation}
\tau:=\sum_{p\ge0}\frac{u^{2^{p+1}}}{{(1+u^{2^{p}})}^3(1-u^{2^{p}})}.
\end{equation}
We compute

\begin{align}\begin{split}
\tau&=\sum_{p,i,j\ge0}u^{2^p(2+i+j)}\binom{-3}{i}\\
&=\sum_{p,k\ge0}u^{2^p(k+2)}(-1)^k
\left\lfloor\tfrac{k+2}{2}\right\rfloor
\left\lfloor\tfrac{k+3}{2}\right\rfloor\\
&=\sum_{p,k\ge0}u^{2^pk}(-1)^k
\left\lfloor\tfrac{k}{2}\right\rfloor
\left\lfloor\tfrac{k+1}{2}\right\rfloor\\
&=\sum_{p,k\ge1}u^{2^pk
}k^2-\sum_{p,k\ge0}u^{2^p(2k+1)}k(k+1)\\
&=:\sigma_1-\sigma_2
\end{split}
\end{align}
We set $u=e^{-t}$ and compute the Mellin transform of $\sigma_1$;
\begin{equation*}
\frac{\Gamma(s)}{2^s-1}\zeta(s-2)
\end{equation*}
and of $\sigma_2$;
\begin{equation*}
\Gamma(s)\zeta(s-2)\frac{2^{s-2}-1}{2^s-1}-\frac14\Gamma(s)\zeta(s),
\end{equation*}
so that $\tau$ maps into
\begin{equation*}
2\Gamma(s)\zeta(s-2)\frac{1-2^{s-3}}{2^s-1}+\frac14\Gamma(s)\zeta(s).
\end{equation*}
We must find the residues of this times $t^{-s}$, which yields, 
apart from the fluctuating terms
\begin{equation}
\sim\frac{1}{4t}+\frac{7\zeta'(-2)}{4\log2}-\frac18.
\end{equation}
Inserting this into
(\ref{U_def}) and using the results about $\sigma$, we are
led to the local expansion of $U(z)$ (no fluctations
are given);
\begin{equation}
U(z)\sim 8-\left(
12+\frac{16{\cal C}}{(\log2)\pi}-\frac{56\zeta'(-2)}{\log2}
\right)\sqrt{1-4z}
\end{equation}
To get the ``mean'' of the fluctuating function we have to take
the coefficient of $\sqrt{1-4z}$ and divide it by $-2$, which gives
a numerical value $10.595047\dots$. 

This is consistent with explicit
computations performed with {\sc Maple}: For that, we computed the first
10 values of $W_p(z,y)$ and differentiated this function twice w.r.t. $y$,
followed by $y=1$. The resulting function was expanded as a series in $z$,
and for instance, the coefficient of $z^{30}$, divided by the $30$--th
Catalan number $b_{30}$, gives a value $11.2763828$; a similar computation
gives $3.263013186$ in the instance of the expectation (again $n=30$).
  

 The fluctuations are not too small in 
amplitude
(usually, in the ``register" context, they are of the order
$10^{-2}$, which originates from $\chi_1/2=\pi i/\log2$ and the
value of the $\Gamma$--function at this point, see \cite{FRV});
 however, 
with the first few Fourier coefficients, they could be approximated very 
well. Since this was only the second factorial moment, we have to add the 
expectation (mean term) $3.341266\dots$ and subtract the square of it. The 
resulting numerical value is $2.7722547\dots\,$.
 This does not match with the 
plot in \cite{Y_M}, and we are not able to reproduce the computations done 
in this paper. One
should furthermore be aware of the fact that, when squaring the
expectation, the square of the periodic function $\delta(x)$ which
is involved does
no longer have mean zero. Since this function is not too small in
amplitude, the numerical value $2.7722547\dots$ is not too meaningful either.
Since we find it difficult to get explicit numerical values for
the Fourier coefficients of $\delta^2(x)$, we do not pursue this further.



\section{Higher bifurcation rates}  

This section indicates that the machinery used in the previous sections to 
deal with the original YM--parameter is powerful enough to deal with more
general situations ({\sl higher bifurcation rates\/}). Since the necessary
computations become quite messy, we confine ourselves with a sketch of
the key steps of one particular case.
\medskip

We want to count into how many maximal subtrees of register function
$p-2$ the maximal subtrees of register function $p-1$ bifurcate, if the whole tree
has register function $p$ for some $p$.
In the example of Figure 1, only the first tree contributes 4, and the other
ones 0. For the tree in
 Figure~2, the value is 7, which might be seen more easily 
from Figure~3.
To formulate it differently, this parameter
counts the number of
 maximal subtrees of register function 2 less than the whole tree.
\smallskip





We can use essentially the same decomposition as in the earlier case. 
Let us label all those maximal subtrees of register function    
$p-2$ by the variable $y$ and use (as an {\sl  ad hoc\/} notation)     
the generating function $D_p(z,y)$. We obtain (for $p\ge2$) 
\begin{equation}
D_p(z,y)=zW_{p-1}^2(z,y)+2zD_p(z,y)W_{p-1}(z,y)+
2zD_p(z,y)\big(B(z)-S_{p-1}(z)\big).
\end{equation}
Set $T_p^{(2)}(z)=\frac{\partial}{\partial y}D_p(z,y)|_{y=1}$, then we get
\begin{equation}
T_p^{(2)}(z)=2zT_{p-1}(z)\frac{R_{p-1}(z)+R_p(z)}{1-2z\big(B(z)-S_p(z)\big)}
.\end{equation}
We computed already that (cf. (\ref{Teq}) and (\ref{eq6})\,)
\begin{equation*}
2z\frac{R_{p-1}(z)+R_p(z)}{1-2z\big(B(z)-S_p(z)\big)}
=2u^{2^{p-1}}\frac{1+u^{2^{p-1}}+u^{2^{p}}}{\big(1+u^{2^p}\big)^2}
\end{equation*}
and
\begin{equation*}
T_{p}(z)=\frac{2(1-u^2)}{u}\frac{u^{2^p}\big(1-u^{2^p}\big)
\big(1+u^{2^{p-1}}+u^{2^{p}}\big)}{\big(1-u^{2^{p+1}}\big)^2}
.\end{equation*}
Therefore
\begin{equation}
T_{p}^{(2)}(z)=\frac{4(1-u^2)}{u}\frac{u^{2^p}\big(1-u^{3\cdot2^{p-1}}\big)
\big(1+u^{2^{p-2}}+u^{2^{p-1}}\big)}{\big(1-u^{2^{p+1}}\big)^2}
\end{equation}
and
\begin{equation}\label{forgotten}
T^{(2)}(z):=\sum_{p\ge2}T_{p}^{(2)}(z)=
\frac{4(1-u^2)}{u}
\sum_{p\ge0}
\frac{u^{2^{p+2}}\big(1-u^{3\cdot2^{p+1}}\big)
\big(1+u^{2^{p}}+u^{2^{p+1}}\big)}{\big(1-u^{2^{p+3}}\big)^2}
.\end{equation}
Let us forget about the factor $\frac{4(1-u^2)}{u}$ for the moment and
set $u=e^{-t}$ in the remaining sum $\sigma^{(2)}$. Its
 {\sl Mellin transform\/} is
\begin{equation*}
\frac{1}{1-2^{-s}}
\end{equation*}
times the {\sl Mellin transform\/} of
\begin{equation*}
\frac{e^{-4t}\big(1-e^{-6t}\big)
\big(1+e^{-t}+e^{-2t}\big)}{\big(1-e^{-8t}\big)^2}
=\sum_{k\ge0}(k+1)e^{-8kt}e^{-4t}\big(1-e^{-6t}\big)
\big(1+e^{-t}+e^{-2t}\big)
,\end{equation*}
which is

\begin{align*}
&\Gamma(s)\sum_{k\ge0}(k+1)\left(\frac{1}{{(8k+4)}^s}+
\frac{1}{{(8k+5)}^s}+\frac{1}{{(8k+6)}^s}\right.\\
&\qquad\qquad\qquad\qquad\left.-\frac{1}{{(8k+10)}^s}
-\frac{1}{{(8k+11)}^s}
-\frac{1}{{(8k+12)}^s}
\right)\\
&=\frac{\Gamma(s)}{8^s}
\sum_{k\ge0}(k+1)\left(\frac{1}{{(k+\frac{1}{2})}^s}
+\frac{1}{{(k+\frac{5}{8})}^s}
 +\frac{1}{{(k+\frac{3}{4})}^s}\right)\\ & -
\frac{\Gamma(s)}{8^s}
\sum_{k\ge0}k\left(\frac{1}{{(k+\frac{1}{4})}^s}
+\frac{1}{{(k+\frac{3}{8})}^s}
 +\frac{1}{{(k+\frac{1}{2})}^s}\right)\\
&=\frac{\Gamma(s)}{8^s}\bigg(
-\zeta(s-1,\tfrac14)+\zeta(s-1,\tfrac34)
-\zeta(s-1,\tfrac38)+\zeta(s-1,\tfrac58)
\\
&\qquad\qquad+\zeta(s,\tfrac12)
+\tfrac14\zeta(s,\tfrac14)+\tfrac14\zeta(s,\tfrac34)+
\tfrac38\zeta(s,\tfrac38)+\tfrac38\zeta(s,\tfrac58)
\bigg)\ .
\end{align*}
Altogether the Mellin transform of the sum $\sigma^{(2)}$ is
\begin{align}\begin{split}
\frac{\Gamma(s)}{8^s(1-2^{-s})}
\bigg(&
-\zeta(s-1,\tfrac14)+\zeta(s-1,\tfrac34)
-\zeta(s-1,\tfrac38)+\zeta(s-1,\tfrac58)
\\
&+\zeta(s,\tfrac12)
+\tfrac14\zeta(s,\tfrac14)+\tfrac14\zeta(s,\tfrac34)+
\tfrac38\zeta(s,\tfrac38)+\tfrac38\zeta(s,\tfrac58)
\bigg),
\end{split}
\end{align}
and we have to find the residues of this quantity times $t^{-s}$ at
the points $s=1$, $s=0$,  and $s=\chi_k$. 
We will not explicitly exhibit the 
periodic term, so we stick to $s=1$ and $s=0$.

Using properties such as \cite{WW}
\begin{gather*}
\zeta(s,a)\sim \frac{1}{s-1}\quad (s\to1),\qquad \zeta(0,a)=\tfrac12-a
,\\
\zeta(-1,a)=\tfrac{a^2}2-\tfrac a2-\tfrac1{12}, 
\qquad \zeta'(0,a)=\log\Gamma(a)-\tfrac12\log(2\pi)
\end{gather*}
and the functional equation of the Hurwitz' $\zeta$--function, an
extremely boring computation gives 
the residue at $s=1$ as $\frac{9}{16t}$ and
the residue at $s=0$ as
\begin{align}\begin{split}
\frac{1}{\log2}\Bigg(&-\frac{{\cal C}}{2\pi}
-\frac{1}{256\pi}\bigg(\sqrt2\, \zeta(2,\tfrac18)-
2\, \zeta(2,\tfrac14)
+\sqrt2\, \zeta(2,\tfrac38)
-\sqrt2\, \zeta(2,\tfrac58)
\\&+2\, \zeta(2,\tfrac34)-\sqrt2\, \zeta(2,\tfrac78)\bigg)
-\tfrac38\log\pi-\log2+\tfrac38\log\Gamma(\tfrac38)+
\tfrac38\log\Gamma(\tfrac58)
\Bigg)\ .
\end{split}\end{align}

Its numerical value is $-1.287$.

Now we bring the `forgotten factor' $\frac{4(1-u^2)}{u}$ 
(see eq. (\ref{forgotten}))
again into the picture and have
\begin{align*}
T^{(2)}(z)&\sim \Big(8t+{\cal O}(t^3)\Big)\cdot 
\Big(\frac{9}{16t}-1.287+\dots\Big)\\
&\sim\frac{9}{2}-10.298\, t+\dots\\
&\sim\frac{9}{2}-10.298\cdot2\sqrt{1-4z}+\dots
\end{align*}
Hence, apart from the ubiquitous fluctuations,
\begin{equation}
\frac{[z^n]\, T^{(2)}(z)}{[z^n]\, B(z)}\sim 10.298.
\end{equation}
Thus, apart from fluctuations, the expected number of maximal subtrees
2 less than the register function of the entire tree is asymptotic to
10.298.


\qquad({\footnotesize With Maple, we get for instance the value
$\displaystyle{\frac{[z^{30}]\, T^{(2)}(z)}{[z^{30}]\, B(z)}= 
10.01241483}$.})

\noindent
This must be put into perspective by the previous value 
$3.341$, and the quotient
\begin{equation*}
\frac{10.298}{3.341}=3.082
\end{equation*}
is the asymptotic bifurcation ratio considered in this section (up to
fluctuations, as always).

It is somehow surprising that we get a value 3.082 which is {\sl smaller\/}
then the previous values 3.341. However, the bifurcation  ratio at the 
root is tending to 4, as was obtained in \cite{Y_M}. So we might be tempted
to believe in a {\sl higher\/} value. One 
should note for instance 
that all trees $t$ with register function
$=1$ do not contribute at all to this ``2--bifurcation rate''!


\medskip

The considerations of this section can still be extended to higher {\sl 
bifurcation ratios}. With an obvious notation, we have
\begin{equation}
T_p^{(d)}(z)=2zT_{p-1}^{(d-1)}(z)\frac{R_{p-1}(z)+R_p(z)}{1-2z\big(B(z)-S_p(z)\big)}
.\end{equation}
It seems clear,                that the explicit expressions for these 
quantities become quite unpleasant when $d$ gets larger. The derivations 
presented in this paper should convince the reader however, that even in such 
a general case the asymptotic bifurcation ratio can be computed in principle.


\section{Conclusion}

We demonstrated that by the use of appropriate 
{\sl generating functions, Mellin transforms and singularity
analysis\/} problems which look very hard at first sight 
are reduced to more or less routine computations. The pattern is 
already described in the literature, and a forthcoming book of Flajolet
and Sedgewick \cite{anacom} will deal with it in much more
detail.
\smallskip

It is somehow amusing that {\sl Catalan numbers\/} and 
{\sl Catalan's constant\/} appear in the same problem! It is the
first time that the present author has seen that.









\bigskip
\noindent
{\sc Acknowledgment.}
 The comments of one referee helped to improve this paper in
many ways.




















\bigskip


\begin{thebibliography}{99}
\addcontentsline{toc}{chapter}{References}

\bibitem {Ab_St}  {\sc M.~Abramowitz, I.~A.~Stegun,}  Handbook of 
Mathematical Functions,   Dover,    New York  (1970). 



\bibitem {deBKR} {\sc N.~G.~de Bruijn, D.~E.~Knuth, S.~O.~Rice,} 
 The average height of planted plane trees,   Graph Theory and Computing 
 (R.~C.~Read, ed.), Academic Press,   New York,
(1972)
pp. 15--22.
      
\bibitem {Krus} {\sc L.~Devroye, P.~Kruszewski,}
	A note on the Horton--Strahler number for  random trees,
{\it Information Processing Letters 52}  (1994), pp. 155--159.
Reprinted in:  
{\it Information Processing Letters 56}  (1995), pp. 95--99.
    
 \bibitem {FGD} {\sc P.~Flajolet, X.~Gourdon, P.~Dumas,}
	Mellin transforms and asymptotics: Harmonic sums,
{\it Theor. Comput. Sci. 144}  (1995), pp. 3--58.        
        

\bibitem {FRV} {\sc P.~Flajolet, J.-C.~Raoult, J.~Vuillemin,}
         The number of registers required for evaluating
        arithmetic expressions,
{\it Theor. Comput. Sci. 9}  (1979), pp. 99--125. 
        
\bibitem {Fl_Pr}   {\sc P.~Flajolet and H.~Prodinger,} 
 Register allocation for unary--binary trees,
{\it SIAM Journal on Computing 
 15} (1986), pp.  629--640.


\bibitem {Fl_Od}  {\sc P.~Flajolet and A.~Odlyzko,} 
Singularity analysis of generating functions,
{\it SIAM J. Disc. Math. 3} (1990) pp.  216--240.

\bibitem {anacom}  {\sc P.~Flajolet and R.~Sedgewick,} 
Analytic Combinatorics,
Addison Wesley, in preparation (to appear ($\ge 1996$)). 

\bibitem {Kemp} {\sc R.~Kemp,} 
The average number of registers to evaluate a binary tree
        optimally,
{\it Acta Informatica 11} (1979), pp. 
363--372. 
         


\bibitem {MMP} {\sc A.~Meir, J.~W.~Moon and J.~A.~Pounder,}
On the order of random channel         networks,
 {\it SIAM J. on 
Alg. Disc. Meth. 1}
         (1980) pp. 25--33.  



\bibitem{P1} {\sc H.~Prodinger,}
 Die Bestimmung gewisser Parameter von 
bin\"aren  B\"aumen mit Hilfe analytischer Methoden,
 Lecture Notes in Mathematics 1114 (E.~Hlawka, Ed.),  Springer Verlag
   (1985) pp. 118--133. 




\bibitem {P2}     {\sc H.~Prodinger,}
 Some recent results on the register function of a binary tree,
 Proceedings      of the Second Conference on Random Graphs, 
Posen 1985, {\it Annals of Discrete      Mathematics 
 33}  (1987) pp. 241--260. 


\bibitem{P3}{\sc H.~Prodinger,}     
 Quelques techniques analytiques pour l'\'etude asymptotique des 
param\`etres dans les arbres,
{\it (Lecture notes for the summer school in  Ile de R\'e 1983),
English version in: EATCS Bulletin 47} (1992), 180--199.

\bibitem{hor_conf}{\sc H.~Prodinger,}     
Solution of a problem of {Y}ekutieli and {M}andelbrot, 
In: {\sc Latin '95} (R. Baeza-Yates, E. Goles, P.V. Poblete (Eds.),
\textit{Lecture Notes in Computer Science 911} (1995)
pp. 461--468.

\bibitem {WW} {\sc E.~T.~Whittaker, G.~N.~Watson,}  A course in modern 
analysis, 
          Cambridge University Press  (1930).

\bibitem {Y_M}  {\sc I.~Yekutieli and B.~Mandelbrot,} Horton--Strahler
ordering of random binary trees, {\it J. Phys. A: Math. Gen., 27}
 (1994) pp. 
285--293.

\end{thebibliography}

\bigskip\noindent
{\sc Helmut Prodinger\\
Department for Algebra and Discrete Mathematics \\
TU Wien \\
Wiedner Hauptstrasse 8--10/118 \\
A-1040 Wien\\
 Austria \\
\rm email: proding@@rsmb.tuwien.ac.at}





\end{document}
