\input amstex
\documentstyle{amsppt}
\magnification=\magstep1



\headline=               
{\ifnum\pageno=1\hfil
 \else\vbox{\line {\sl 
Summerschool Ile de R\'e (English version)
\hfil   \folio}
\vskip 2pt\hrule}\fi}
\footline={\hfil}
\catcode`\@=11
\redefine\logo@{}
\firstpage@false
\catcode`\@=13







\def\erfc{\operatorname{erfc}}
\define\reg{\operatorname{reg}}
\define\coeff#1{\left[z^{#1}\right]}
\define\coeffu#1{\left[u^{#1}\right]}
\define\GG{\Gamma}
\redefine\ll{\lambda}

\font\super=cmbx10 scaled \magstep 2

\document
{\super 
\centerline{Some Analytic Techniques }
\medskip
\centerline{for the Investigation of the}
\medskip
\centerline{Asymptotic Behaviour of }
\medskip
\centerline{Tree Parameters}}

\bigskip
\centerline{{\smc Helmut Prodinger}}
\bigskip
\font\klein=cmr8
\klein
\centerline{Department of Algebra and Discrete Mathematics}
\centerline{Technical University of Vienna}
\centerline{Wiedner Hauptstra\ss e 8--10}
\centerline{A--1040, Vienna, Austria}
\bigskip
\rm
\rightline{{\sl Written for the Proceedings of the Summerschool
 in Ile de R\'e 1983 (in French)}}
\rightline{{\sl Retyped 1991}}
\rightline{{\sl Translated into English January 1992}}




\heading
1. Introduction
\endheading

The structure of a tree is one of the most common data structures
in Computer Science. There exist many algorithms for the manipulation
of trees.
The analysis of these  algorithms in the sense
of Knuth leads often to combinatorial problems of the
enumeration of  configurations; the following step
consists of the asymptotic analysis of these numbers.
See e.g. \cite 4, \cite{15}, \cite{16}.

The study of Flajolet and Odlyzko \cite 7 is a paradigm for a slightly
different point of view: Instead of extracting the coefficients
of generating functions 
and approximating them
by methods of real analysis, the singularities of the generating functions
are studied. More precisely, one tries to establish the local behaviour
of the generating functions around their singularities next to the
origin. After that, some translation lemmas allow to translate
this behaviour into the asymptotic behaviour of the (Taylor-)coefficients
of the generating function in question.
For instance, if
$f(z)=\sum_{n\ge 0}f_nz^n$ has its singularity next to the
origin at 1, with
$$
f(z)\sim A-B\sqrt{1-z}+\dots ,
$$
then one concludes that
$$
\coeff n f(z):=f_n\sim\frac{B}{2\sqrt \pi}n^{-3/2}.
$$
Similarily if
$$
f(z)\sim -A\log(1-z)+\dots,
$$
then
$$
[z^n]f(z)\sim\frac{A}{n},\quad\text{etc}.
$$
Also, the more terms we know from the local behaviour of the generating
function, the more terms we know from the asymptotic behaviour of
the (Taylor-)coefficients.

This translation is a rather automatic process. The principle problem
is  thus to find the local behaviour around the (dominant)
singularities.
In a lot of cases one can use the Mellin transform, a very popular
method within the french school of the analysis of algorithms.

The main interest of this paper is to explain this general strategy
in 3 particular cases: the problem of register allocation for the
evaluation of arithmetic expressions; then the height of leaves in
planted plane trees. The third problem is the asymptotic study of a
certain expression (that is similar to one occurring in the register
problem); this value is of interest in the analysis of a particular
sorting algorithm
(see \cite 6, \cite{21}).

Before we engage ourselves into technical problems, we would like
to formulate some fundamental concepts:

The family $\Cal B$ of binary trees might be defined
recursively by the (symbolic) equation
$$ $$
which means that a binary tree is either  an external node
(``leaf'') or built by a root and 2 binary trees (the left and right
subtree).
Let $B(z)=\sum_{n\ge 0}b_nz^n$ 
denote the generating function 
where $b_n$ is the number of binary trees of size
$n$ (the size is measured in termes of internal nodes);
one can see immediately that
$$
B(z)=1+z\left(B(z)\right)^2,
$$
and thus
$$
B(z)=\frac{1-\sqrt{1-4z}}{2z}\quad \text{and} \quad 
b_n=\frac{1}{n+1}\binom{2n}n.
$$
The numbers $b_n$ are {\sl Catalan} numbers.

In an analogous way, the family
$\Cal P$ of planted plane trees is defined by
%\vskip 2 cm
$$$$
form which one deduces the generating function
$P(z)=\sum_{n\ge 1}
t_nz^n$ of planted plane trees:
$$
P(z)=\frac{z}{1-P(z)}
\ \text{ and thus } \ 
P(z)=\frac{1-\sqrt{1-4z}}{2}\ \text{  and  }\ 
 t_n=\frac{1}{n}\binom{2n-2}{n-1}
.$$
In these 2 cases, the above mentioned singularity is $z=\frac 14$, and
$$
B(z)\sim 2 -2\sqrt{1-4z},\ \text{ thus }\ 
b_n\sim\frac{1}{\sqrt \pi}4^nn^{-3/2}
$$
or
$$
P(z)\sim \frac 12 -\frac 12\sqrt{1-4z},\ \text{ thus }\ 
t_n\sim\frac{1}{\sqrt \pi}4^{n-1}n^{-3/2}.
$$
\pagebreak
\heading
2. The average number of registers to evaluate a binary tree of size
 $n$
\endheading

Before we start the discussion, let's cite the references on this
subject:
 \cite 4, \cite 5, \cite8, \cite{11}, \cite{17}, \cite{19}.
We won't go into a description of the Computer Science problem.
For this we advise the gentle reader to consult the thesis of
P. Flajolet
\cite 4.

The function ``number of registers'' {\it reg} 
is given recursively by
$$
\reg(\square)=0
$$
$$
\reg\bigg(\quad
%\hbox{
\kern-.3cm\raise-.38cm\hbox{}
%}
\bigg)=
\cases
\max\{\reg(t_1), \reg(t_2)\} \quad&\text{if } \reg(t_1)\ne \reg(t_2)\\
1+\reg(t_1) \quad&\text{otherwise. }
\endcases
$$
The problem is the evaluation of
$R_n$, the average value of the function
{\it reg}, based on the set of binary trees of size $n$.
We have
$$
R_n=\frac{1}{b_n}\cdot [z^n]E(z),
$$
with
$$
E(z)=\sum_{n\ge 0}z^n\sum_{ \text{$t$ of size $n$}}\reg(t).
$$

Let $\Cal R_p$ be the family of trees $t$ with $\reg(t)=p$. 
From the definition of {\it reg} we easily see that
$$
$$
Let $\Cal S_p$ be the family of trees $t$ with $\reg(t)\ge p$,
that means
$$
\Cal S_p=\Cal R_p+\Cal R_{p+1}+\dots\ .
$$
We can write
$$
\sum_{j<p-1}\Cal R_j=\Cal B \setminus \Cal S_{p-1}.
$$
We obtain a recursion for the families $\Cal S_{p}$ in a very
similar fashion:
$$
 $$
The functions $S_p(z)$ are defined by
$$
S_p(z):=\sum_{n\ge 0}z^n\sum_{t \text{ of size }n,\  \reg(t)\ge p}1.
$$
It is clear that
$$
E(z)=\sum_{p\ge 1}S_p(z).
$$
The functions $S_p(z)$ may be described by the immediate recursions
$$
S_0=B; \quad
S_p=zS_{p-1}^2+2zS_p\left(B-S_{p-1}\right).
$$
It is convenient to define $\varepsilon:=\sqrt{1-4z}$ and $z=u/(1+u)^2$.
Thus
$$
S_p=\frac{zS_{p-1}^2}{1-2zB+2zS_{p-1}},
$$
or
$$
\frac{1}{S_p}=\frac{\varepsilon}{zS_{p-1}^2}+\frac{2}{S_{p-1}}.
$$
This finally gives us
$$
\aligned
1+\frac{\varepsilon}{z}\frac{1}{S_p}&=
1+\frac{\varepsilon^2}{z^2S_{p-1}^2}+\frac{2\varepsilon}{z}\frac{1}{S_{p-1}}
=\left(1+\frac{\varepsilon}{z}\cdot\frac{1}{S_{p-1}}\right)^2\\
&=\dots=\left(1+\frac{\varepsilon}{z}\cdot\frac{1}{S_0}\right)^{2^p}.
\endaligned
$$
From this we derive the equation
$$
S_p=\frac{\varepsilon}{z}\left(\left(1+\frac{\varepsilon}{zB}\right)
^{2^p}-1
\right)^{-1}.
$$
Now we see at once that
$$
\frac{\varepsilon}{z}=\frac{1-u^2}{u},\quad\text{and}\quad
1+\frac{\varepsilon}{zB}=\frac 1u,
$$
so that
$$
S_p=\frac{1-u^2}{u}\frac{1}{u^{-2^p}-1}=\frac{1-u^2}{u}
\frac{u^{2^p}}{1-u^{2^p}}.
$$
For the function $E(z)$ we have therefore the following  expression
$$
\aligned
E(z)&=\frac{1-u^2}{u}\sum_{p\ge 1}\frac{u^{2^p}}{1-u^{2^p}}\\
&=\frac{1-u^2}{u}\sum_{p\ge 1}
\sum_{\lambda \ge 1}u^{\lambda 2^p}\\
&=\frac{1-u^2}{u}\sum_{n\ge 2}v_2(n)u^n,
\endaligned
$$
where $v_2(n)$ is the exponent of 2 in the prime number  decomposition of
 $n$:
$$
v_2(n)=\sum_{n=\lambda 2^p,\ \lambda, p\ge 1}1.
$$
If we write in a unique way $n=2^m(1+2i)$, ($m\ge1$, 
$i\ge 0$), we have
$$
v_2(n)=\sum_{p=1}^m1=m.
$$
The quantity $v_2(n)$ is often called ``dyadic valuation'',
for obvious reasons.
As it was announced in the Introduction, we will finally show that in
a neighbourhood of
$z=\frac 14$ (which means $u=1$):
$$
E(z)\sim 2\varepsilon\log_2\varepsilon+A\varepsilon+
4\sum_{k\ne 0}c_k\varepsilon^{1-\chi_k}+\dots,
$$
with
$$
A=3-2\log_22\pi+\frac{2\gamma}{\log 2},\quad (\gamma 
\text{ is Euler's constant})
$$
and
$$
\chi_k=\frac{2k\pi i}{\log 2}\quad\text{and}\quad
c_k=\frac{1}{\log 2}\Gamma(\chi_k)\zeta(\chi_k)
$$
($\Gamma$ is Euler's gamma function, $\zeta$ is
Riemann's zeta funtion).

Let us mention the following expansion (\cite{10})
$$
\coeff n\log(1-z)(1-z)^\alpha\sim \frac{-n^{-\alpha-1}\log n}{\GG(-\alpha)}
+n^{-\alpha-1}\frac{\GG(-\alpha)}{(\GG(-\alpha))^2},
$$
which gives us as a special instance
$$
\coeff n\varepsilon\log\varepsilon\sim
\frac 124^nn^{-3/2}\left(
\frac{\log n}{2\sqrt\pi}+\frac{\gamma+2\log2-2}{2\sqrt\pi}\right).
$$
We will also use the result
$$
\coeff n\varepsilon^{1-\chi_k}\sim4^nn^{(\chi_k-3)/2}\Big/\GG
\left(\frac{\chi_k-1}{2}\right).
$$
We observe that we can simplify the expression
$$
c_k\Big/\GG
\left(\frac{\chi_k-1}{2}\right)=
\frac{\zeta(\chi_k)\GG\big(\frac{\chi_k}{2}\big)(\chi_k-1)}{4\sqrt\pi\log2};
$$
for this we use the duplication formula of {\sl Legendre-Gauss\/}
(see e.g. \cite2)
$$
\GG\left(\frac{z}{2}\right)\GG\left(\frac{z+1}{2}\right)=
\sqrt\pi2^{1-z}\GG(z).
$$
Finally, if we collect everything, we find that
$$
\align
\coeff nE(z)&\sim
\frac{4^nn^{-3/2}}{2\sqrt\pi\log2}\left(\log n+\gamma+2\log2-2\right)\\
&-A\frac{4^n}{2\sqrt\pi}n^{-3/2}+
\sum_{k\ne0}
\frac{4^nn^{(\chi_k-3)/2}\zeta(\chi_k)\GG(\chi_k/2)(\chi_k-1)}{\sqrt\pi
\log2}.
\endalign
$$
If we take into consideration that
$$
b_n\sim\frac{4^n}{\sqrt\pi}n^{-3/2}\qquad\text{and}
\qquad
n^{\chi_k/2}=\varepsilon^{\log_4n\cdot2k\pi i}, 
$$
we  obtain

\proclaim{Theorem 1}
The average number $R_n$ 
of registers to evaluate a binary tree of size
$n$ verifies
$$
R_n=\log_4n+D(\log_4n)+o(1),
$$
where $D(x)$
is a continuous periodic function of period 1; this function
can be expanded in a  Fourier series as
$$
D(x)=\sum_{k\in\Bbb Z}d_ke^{2k\pi ix},
$$
with
$$
d_0=\frac 12-\frac{\gamma}{2\log2}
-\frac{1}{\log 2}+\log_2\pi
$$
and
$$
d_k=\frac{1}{\log2}\zeta(\chi_k)\GG(\frac{\chi_k}{2})(\chi_k-1),
\quad k\ne 0, \quad \chi_k=\frac{2k\pi i}{\log2}.
$$
\endproclaim


The remainder of this section ist devoted to the study of the expansion of
the function $E(z)$.

To study $E(z)$ for $z\to \frac 14$, i.e. for $u\to 1$, we set
$u=e^{-t}$ and consider $E(z)$ for $t\to 0$. 
We easily  obtain that
$$
\frac{1-u^2}{u }\sim2t+\dots \ .
$$
Let us turn to the second factor of $E(z)$, which we denote by $V(t)$; the
Mellin transform of $V(t)$ is denoted by $V^*(s)$:
$$
V(t)=\sum_{k\ge 1}v_2(k)e^{-kt}; \qquad
V^*(s)=\int_0^\infty x^{s-1}V(x)dx
$$
$$
\align
V^*(s)&=\int_0^\infty x^{s-1}\sum_{k\ge 1}v_2(k)e^{-kx}dx\\
&=\sum_{k\ge 1}v_2(k)k^{-s}\int_0^\infty x^{s-1}e^{-x}dx
\endalign
$$
We have
$$
\sum_{k\ge 1}v_2(k)k^{-s}=2^{-s}\sum_{k\ge 1}v_2(2k)k^{-s}
=2^{-s}\sum_{k\ge 1}\big[1+v_2(k)\big]k^{-s},
$$
and thus
$$
V^*(s)=\frac{\GG(s)\zeta(s)}{2^s-1}.
$$
The Mellin inversion formula gives us
$$
V(t)=\frac{1}{2\pi i}\int\limits_{2-i\infty}^{2+i\infty}V^*(s)t^{-s}ds.
$$

We can shift the line of integration to the left, provided we
take the residues of the
integrand $V^*(s)t^{-s}$ into account. There are
poles at $s=1$ (originating from the Riemann $\zeta$- function)
, at $s=0, -1, -2,\dots$ (coming from the function $\GG$)  and at
$s=\chi_k$, $k\in\Bbb Z$ (from $(2^s-1)^{-1}$). We use the classical
expansions to get
$$
\align
V(t)&\sim \frac 1t +\frac 12\log_2t-\frac 12\log_22\pi +\frac 14
+\frac{\gamma}{2\log 2}\\
&+\frac{1}{\log 2}\sum_{k\ne 0}\GG(\chi_k)\zeta(\chi_k)t^{-\chi_k}+\dots
\endalign
$$
which gives us the announcedc  formula for $E(z)$, after having multiplied
the last 2 expansions and noting that
$$
t\sim 2\varepsilon+\dots \ .
$$
\bigskip

\head 3. A similar problem:  odd-even merge \endhead

In the analysis of a sorting algorithm (odd-even merge) one has
to consider the quantity
$$
B_n=\sum_{k\ge 1}\frac{\binom{2n}{n-k}}{\binom{2n}n}\Big(2F(k)+k\Big),
$$
representing the number of exchanges in the odd-even merge
of
$2n$ elements. In this equation,
$$
F(k)=\sum_{0\le j<k}f(j)
$$
and $f(j)$ is the number of digits ``1'' in the Gray code representation
of $j$  (see \cite6, \cite{21}). Below we see the first few numbers
in this representation:
\vskip 1 cm

\hfil
\vbox{
\settabs 
\+ \hskip 2 cm&\hskip 1 cm&\hskip 3 cm&\hskip 1 cm&\cr
\+ \hfill 0 & \hfill 0 & \hfill 1100 &\hfill 8 &\cr
\+ \hfill 1 & \hfill 1 & \hfill 1101 &\hfill 9 &\cr
\+ \hfill 11 & \hfill 2 & \hfill 1111 &\hfill 10 &\cr
\+ \hfill 10 & \hfill 3 & \hfill 1110 &\hfill 11 &\cr
\+ \hfill 110 & \hfill 4 & \hfill 1010 &\hfill 12 &\cr
\+ \hfill 111 & \hfill 5 & \hfill 1011 &\hfill 13 &\cr
\+ \hfill 101 & \hfill 6 & \hfill 1001 &\hfill 14 &\cr
\+ \hfill 100 & \hfill 7 & \hfill 1000 &\hfill 15 &\cr
\+ &  & \hfill 11000 &\hfill 16 &\cr}
\hfil
\vskip 1 cm
   
The numbers 
$$\vartheta(j):=f(j)-f(j-1)$$
equal $\pm1$: if $k$ is of the form $k=2^m(4i+1)$, $\vartheta
(k)=1$; if $k$ is of the form $k=2^m(4i+3)$, $\vartheta(k)=-1$.
We might recognize a great similarity between $\vartheta(k)$ and $v_2(k)$
from Section 2. The Dirichlet generating function of the sequence
$\vartheta(k)$ is
$$
\align
\sum_{k\ge 1}\vartheta(k)k^{-s}
&=\sum_{m\ge 0}\sum_{i\ge 0}2^{-ms}(4i+1)^{-s}
-\sum_{m\ge 0}\sum_{i\ge 0}2^{-ms}(4i+3)^{-s}\\
&=\frac{1}{1-2^{-s}}
\cdot\frac{1}{4^s}
\left(\zeta\big(s,\frac 14\big)-\zeta\big(s,\frac 34\big)
\right),
\endalign
$$
where the Hurwitz $\zeta(s,a)$-function  is defined by
$$
\zeta(s,a)=\sum_{n\ge 0}(n+a)^{-s}\qquad\text{for}\ \ \Re (s)>1.
$$
We can write
$$
B_n=\frac n2 +\frac{2}{\binom{2n}n}C_n,
$$
with
$$
C_n=\sum_{k\ge 1}F(k)\binom{2n}{n-k}.
$$
We want to find an analogous function to $E(z)$ (Section 2). 
Thus we write
$$
\align
C_n&=\sum_{k\ge 1}F(k)\coeffu{n-k}(1+u)^{2n}\\
&=\coeffu n \sum_{k\ge 1}F(k)u^k(1+u)^{2n}\\
&=\coeffu n \sum_{k\ge 1}\sum_{0\le j<k}f(j) \ u^k(1+u)^{2n}\\
&=\coeffu n \sum_{j\ge 0}f(j)  u^j\frac{u}{1-u}(1+u)^{2n}\\
&=\coeffu n \sum_{j\ge 0}\sum_{0\le i\le j} \vartheta(i)
 u^j\frac{u}{1-u}(1+u)^{2n}\\
&=\coeffu n \sum_{i\ge 0} \vartheta(i)
 u^i\frac{u}{(1-u)^2}(1+u)^{2n}.
\endalign
$$
In general, if we have a series $\Psi(z)$, and if we set $z=u/(1+u)^2$,
we have by Cauchy's theorem
$$\align
\coeff n \Psi(z)&=
\frac{1}{2\pi i}\oint\frac{dz}{z^{n+1}}\Psi(z)\\
&=\frac{1}{2\pi i}\oint \frac{du(1-u)}{(1+u)^3}\frac{(1+u)^{2n+2}}{u^{n+1}}
\Psi\Big(\frac{u}{(1+u)^2}\Big)\\
&=\coeffu n (1-u)(1+u)^{2n-1}\Psi\Big(\frac{u}{(1+u)^2}\Big).
\endalign
$$
Thus we can write
$$
C_n=\coeffu n \frac{u(1+u)}{(1-u)^3}
\sum_{i\ge 1}\vartheta(i)u^i.
$$
The function appearing in the right hand side of this equation
is the analogue of
$E(z)$ of Section  2. We easily find that
$$
\frac{u(1+u)}{(1-u)^3}\sim\frac{2}{t^3}+\dots\ .
$$
If we set
$$
V(t)=\sum_{k\ge 1}\vartheta(k)e^{-kt},
$$
then we have
$$
V^*(s)=\GG(s)\cdot \frac{1}{2^s}\cdot\frac{1}{2^s-1}
\left(\zeta\big(s,\frac 14\big)-\zeta\big(s,\frac 34\big)
\right).
$$
As a consequence we find
$$
V(t)=\frac{1}{2\pi i}\int\limits_{2-i\infty}^{2+i\infty}
\GG(s)\cdot \frac{1}{2^s}\cdot\frac{1}{2^s-1}
\left(\zeta\big(s,\frac 14\big)-\zeta\big(s,\frac 34\big)
\right)t^{-s}dt.
$$
The difference of the Hurwitz $\zeta$-functions is an entire function;
the integrand has poles at $s=\chi_k$ and $s=0, -1, -2,\dots$ .
We have (see \cite {22})
$$
\zeta\big(s,\frac 14\big)-\zeta\big(s,\frac 34\big)
\sim \frac 12 +s\left(2\log\GG\big(\frac 14\big)-\frac 12\log2-\log\pi
\right)+\dots
$$
for $s\to0$. Also,
$$
\gather
\GG(s)\sim \frac 1s -\gamma+\dots\\
\frac{1}{2^s-1}\sim \frac{1}{\log2}\cdot \frac 1s -\frac 12 +\dots\\
(2t)^{-s}\sim 1-s\cdot \log(2t)+\dots
\endgather
$$
which gives us the residue at $s=0$
$$
-\frac 54 -\frac{\gamma}{2\log2}+2\log_2\GG(\frac 14)-\log_2\pi
-\frac 12\log_2t.
$$
The residue at $s=\chi_k$ for $k\ne 0$ is simply
$$
\frac{1}{\log2}\GG(\chi_k)
\left(\zeta\big(\chi_k,\frac 14\big)-\zeta\big(\chi_k,\frac 34\big)
\right)t^{-\chi_k}.
$$
We can simplify, because
$$
\zeta\big(\chi_k,\frac 34\big)=-\zeta\big(\chi_k,\frac 14\big).
$$
Thus we obtain
$$\align
C_n\sim\coeff n \frac{2}{t^3}\bigg(&-\frac 12\log_2t-\frac 54
-\frac{\gamma}{2\log2}
+2\log_2\GG\big(\frac14\big)-\log_2\pi\\
&+\frac{2}{\log2}\sum_{k\ne 0}\GG(\chi_k)\zeta\big(\chi_k,\frac14\big)
t^{-\chi_k}\bigg),
\endalign
$$
where, with $t\sim 2\varepsilon$
$$\align
C_n\sim\coeff n \bigg(&-\frac 18\varepsilon^{-3}\log_2\varepsilon
-\varepsilon^3\Big(
\frac{7}{16}+\frac{\gamma}{8\log2}
-\frac12\log_2\GG\big(\frac14\big)+\frac14\log_2\pi\Big)\\
&+\frac{1}{2\log2}\sum_{k\ne 0}\GG(\chi_k)\zeta\big(\chi_k,\frac14\big)
\varepsilon^{-3-\chi_k}\bigg).
\endalign
$$
We find, as in Section 2,
$$\gather
\coeff n\varepsilon^3\log\varepsilon\sim
\frac{4^n\sqrt n}{\sqrt\pi}\Big(-\log n+(2-\gamma-2\log2)\Big),\\
\coeff n\varepsilon^{-3}\sim \frac{2\cdot4^n\sqrt n}{\sqrt\pi},\\
\coeff n\varepsilon^{-3-\chi_k}\sim4^n\frac{n^{(1+\chi_k)/2}}
{\GG\left(\frac{3+\chi_k}{2}\right)}.
\endgather
$$
By regrouping the preceeding results we obtain
$$\align
C_n&\sim\frac{4^n\sqrt n}{\sqrt\pi}\log n\cdot\frac{1}{8\log2}\\
&+\frac{4^n\sqrt n}{\sqrt\pi}
\left(-\frac{1}{4\log2}-\frac{\gamma}{8\log2}-\frac 58+
\log_2\GG\big(\frac14\big)-\frac 12\log_2\pi
\right)\\
&+\frac124^n\sqrt n \frac{1}{\log 2}
\sum_{k\ne 0}\GG(\chi_k)\zeta\big(\chi_k,\frac14\big)
\frac{n^{\chi_k/2}}
{\GG\left(\frac{3+\chi_k}{2}\right)}.
\endalign
$$
We have by the  duplication formula
$$
\GG(\chi_k)\Big/ \GG\left(\frac{3+\chi_k}{2}\right)=
\frac{1}{1+\chi_k}
\frac{1}{\sqrt\pi}\GG\left(\frac{\chi_k}{2}\right).
$$
With
$$
\binom{2n}n\sim\frac{4^nn^{-1/2}}{\sqrt\pi}
$$
we find
$$
\align
\frac{D_n}{\binom{2n}n}\cdot\frac{1}{n}&\sim\frac 18\log_2n\\
&-\frac{1}{4\log2}-\frac{\gamma}{8\log2}-\frac 58+\log_2\Gamma\big(\frac14
\big)-\frac12\log_2\pi\\
&+\frac{1}{2\log2}\sum_{k\ne0}\zeta\big(\chi_k,\frac 14\big)\frac
{\Gamma(\chi_k/2)}{1+\chi_k}n^{\chi_k/2}.
\endalign
$$
Finally we have obtained the

\proclaim{Theorem 2} The average number of exchanges in the odd-even merge
of $2n$ elements verifies
$$
B_n\sim\frac 14n\log_2n+nB\big(\log_4n\big),
$$
where $B(x)$ is a continuous periodic function of period 1; this
function can be expanded as a Fourier series
$$
B(x)=\sum_{k\in \Bbb Z}b_ke^{2k\pi ix},
$$ 
with
$$
b_0=-\frac{1}{2\log 2}
-\frac{\gamma}{4\log 2}-\frac 34+2\log_2\Gamma\big(\frac14
\big)-\log_2\pi
$$
and for $k\ne 0$
$$
b_k=\frac{1}{\log 2}\zeta\big(\chi_k,\frac 14\big)\frac
{\Gamma(\chi_k/2)}{1+\chi_k}.
$$
\endproclaim

\newpage

\head 4. The height of leaves in planted plane trees \endhead

We can understand the problem of this section most easily
by considering the following example of a planted plane tree:

$$$$

This tree has 4 leaves of height (from left to right) $3, 3, 4, 2$. 
We remark that the height of the tree is given
by the height of the highest leaf
We imagine now that the leaves are ordered with respect to their
heights. In our example,
the sequence of heights of leaves is
$4,3,3,2$. 
Let us remark that there might be more leaves with the same height.
To simplify the computations, we complete this sequence by an
infinity of zeroes. 
Now it makes sense to speak about the $d$-th
highest leaf for each $d$, even if the tree has less than $d$ leaves.

Now we consider $h_n^{(d)}$, the average height of the $d$-th highest leaf
where we remark again that $h_n^{(1)}$ is simply the average height
of a tree of size $n$.

Some technical lemmas have appeared already in several papers,
see
\cite{1}, \cite{12}, \cite{13}, \cite{14}, \cite{20}.

\proclaim{Lemma 1} Let $F(z,y)$ be the generating function where
$\left[z^ny^m\right]F$ is the number of trees of size $n$ with $m$
leaves (the tree $\circ$ has zero leaves); we have for each
$p\ge 0$
$$
F^p(z,y)=z^p+p\sum_{0\le\lambda<n}
z^ny^{n-\lambda}\frac 1n \binom n\lambda\binom{n-p-1}{\lambda-p}.
$$
\endproclaim
\demo{Idea of proof} (See \cite{12}) We introduce
$G(z,y)$, the analogous quantity, where
$\circ$ has a leaf; translating 
the symbolic equation for the family of planted plane trees as usual
we obtain
$$
G(z,y)=z\bigg(y+\sum_{r\ge 1}G^r(z,y)\bigg)=
\big(1-z(1-y)\big)P\left(\frac{zy}{\big(1-z(1-y)\big)^2}\right).
$$
We use the classical expansion
$$
P^m(z)=\sum_{k\ge 0}\left[\binom{2k+m-1}{k}-\binom{2k+m-1}{k-1}\right]
z^{k+m}.
$$
After this we use the binomial theorem 3 times and use the
identity
$$
\sum_{k\ge 0}\binom rk\binom{s+k}p(-1)^k=(-1)^r\binom s{p-r}
$$
to obtain
$$
G^p(z,y)=z^py^p+p\sum_{p\le\lambda\le n}
z^ny^\lambda\frac 1n \binom n\lambda\binom{n-p-1}{\lambda-p}.
$$
Finally we can observe that
$$
F(z,y)=G(z,y)-zy+z=G(zy,y^{-1}),
$$
and obtain thus the announced formula.
\enddemo

\proclaim{Lemma 2} Let $A_k(z)$ be the generating function of trees of
height $\le k$ and set, as before, $z=u/(1+u)^2$.
We have
$$
A_k(z)=\frac{u}{1+u}\cdot\frac{1-u^k}{1-u^{k+1}}.
$$
\endproclaim
\demo{Proof} Translating the symbolic equation for the  family
$\Cal P$, we obtain
$$
A_k=\frac{z}{1-A_{k-1}}
,\qquad k\ge 1, \quad A_0=0;
$$
from this we can prove the formula easily by induction
. \qed
\enddemo

\proclaim{Lemma 3} Let $Q_k(z,y)$ be the generating function,
where $[z^ny^m]Q_k$ is the number of trees of size  $n$ with $m$
nodes at level $k$, which is the maximal level. (This means that,
if $m\ge 1$, the height of the tree is  exactly $k$.) We have for $k\ge 1$
and $d\ge 1$
$$
[y^d]Q_k(z,y)=A_{k-1}^{d+1}(z)-A_{k-1}^{d}(z)+zA_{k-1}^{d-1}(z).
$$
\endproclaim
\demo{Proof} Translating as usual, we obtain
$$
Q_1=zy\qquad\text{and}\qquad Q_k=\frac{z}{1-Q_{k-1}}\quad
\text{for $k\ge 2$.}
$$
Since we have
$$
[y^0]Q_k(z,y)=A_{k-1}(z),
$$
it is  sufficient to show that
$$
\align
Q_k(z,y)&=A_{k-1}(z)+\sum_{d\ge 1}y^d\Big(
A_{k-1}^{d+1}(z)-A_{k-1}^{d}(z)+zA_{k-1}^{d-1}(z)\Big)\\
&=\frac{A_{k-1}}{1-yA_{k-1}}-\frac{yA_{k-1}}
{1-yA_{k-1}}+\frac{zy}{1-yA_{k-1}}\\
&=\frac{(1-y)A_{k-1}+zy}{1-yA_{k-1}};
\endalign
$$
this is a simple exercise, using the recurrence for the
$A_k$'s.
\enddemo

Let $B_{d,k}(z)$ be the generating function
where $[z^n]B_{d,k}$ is the number of trees of size $n$ with
$d$ leaves having a height $>k$ and all the others having a height
$\le k$. We can observe that $B_{0,k}+B_{1,k}+\dots+
B_{d-1,k}$ is the generating function of trees where $d$-th highest leaf
(in the sense described above) has a height $\le k$.
Thus the quantity $h_n{(d)}$
is given by
$$
h_n^{(d)}=\frac{\coeff n \sum_{k\ge 0}\Big(P(z)-B_{0,k}(z)-B_{1,k}(z)-\dots-
B_{d-1,k}(z)\Big)
}{\coeff n P(z)}.
$$
\proclaim{Lemma 4} The average height of a planted plane tree of size
$n$ verifies
$$
\frac{\coeff n \sum_{k\ge 0}\Big(P(z)-B_{0,k}(z)\Big)
}{\coeff n P(z)}\sim\sqrt{\pi n}-\frac 12+\dots\ .
$$
\endproclaim
\demo{Idea of proof} We find that
$$
\align
\sum_{k\ge 0}\Big(P(z)-B_{0,k}(z)\Big)
&=\sum_{k\ge 0}\Big(P(z)-A_{k}(z)\Big)\\
&=\frac{1-u}{1+u}\sum_{k\ge1}\frac{u^k}{1-u^k}
=\frac{1-u}{1+u}\sum_{k\ge1}d(k)u^k
\endalign
$$
where $d(k)$ is the number of divisors of $k$. We observe that
$$
\sum_{k\ge1}d(k)k^{-s}=\zeta^2(s),
$$
and use the Mellin transform as in Section 2.
\enddemo

As is the Sections 2 and 3 we are going to show that
$$
\sum_{k\ge 0}B_{s+1,k}(z)\sim A_s-B_st+\dots,
$$
where $A_s$ and $B_s$ are constants and $u=e^{-t}$. Since
$$
P(z)=\frac{u}{1+u}\sim\frac 12-\frac 14t+\dots,
$$
we can  conclude that
$$
\coeff n \sum_{k\ge 0}B_{s+1,k}(z)\bigg/t_n\sim4B_s.
$$
\proclaim{Lemma 5} We have for $s\ge 0$
$$
\sum_{n\ge p}z^n\binom ns\binom{n-p}s=
\sum_{j=0}^s\frac{z^{s+p+j}}{(1-z)^{s+1+j}}
\frac{(p+s)!(s+j)!}{j!(s-j)!(p+j)!s!}.
$$
\endproclaim
\demo{Proof} With $D=d/dz$ and $(n)_d=n(n-1)\dots(n-d+1)$ we have
$$\align
\sum_{n\ge p}z^n\binom ns\binom{n-p}s&=
\frac{1}{(s!)^2}
\sum_{n\ge 0}(n)_sz^sD^sz^{n+p}\\
&=\frac{1}{(s!)^2}
z^sD^sz^{p+s}\sum_{n\ge 0}z^n\\
&=\frac{1}{s!}z^sD^s\frac{z^{p+s}}{(1-z)^{s+1}}\\
&=\frac{1}{s!}z^s\sum_{j=0}^s\binom sj\big[D^{s-j}z^{p+s}\big]
\big[D^{j}(1-z)^{-s-1}\big].\qed
\endalign
$$
\enddemo
\proclaim{Lemma 6} We have for $s\ge 0$ and $k\ge 1$
$$\align
B_{s+1,k}(z)&=\sum_{j=0}^s
\frac{(s+j)!}{j!(s-j)!(s+1)!}\left(\frac{u}{1+u+u^2}\right)^{s+1+j}\\
&\times\frac{(1-u)^2}{1+u}
\frac{u^{k-1}}{(1-u^{k-1})(1-u^k)}
\sum_{p\ge 1}\frac{p(p+s)!}{(p+j)!}A_{k-1}^p.
\endalign
$$
\endproclaim

\demo{Proof}
We replace each leaf at maximal level $k$ (marked by $y$ in
$Q_k(z,y)$) by an arbitrary tree whose leaves are marked by
$y$. Now
$$\align
B_{s+1,k}&=\left[y^{s+1}\right]Q_k\Big(z,\frac 1zF(z,y)\Big)\\
&=\left[y^{s+1}\right]
\sum_{p\ge1}\Big[\frac 1zF(z,y)\Big]^p
\Big[A_{k-1}^{p+1}-A_{k-1}^{p}+zA_{k-1}^{p-1}\Big]\\
&=\sum_{p\ge1}z^{-p}p\sum_{n\ge 1}z^n
\frac 1n\binom{n}{s+1}\binom{n-p-1}{s}A_{k-1}^p
\big[A_{k-1}-1+zA_{k-1}^{-1}\big].
\endalign
$$
The announced formula is now obtained by remarking that
$$
\gather
A_{k-1}-1+zA_{k-1}^{-1}=
\frac{u^{k-1}}{(1-u^{k-1})(1-u^k)}\frac{(1-u)^2}{1+u},\\
\frac{z}{1-z}=\frac{u}{1+u+u^2}
\endgather
$$
and using Lemma 5.
\enddemo

\proclaim{Lemma 7} The generating function $B_{s+1,k}(z)$ is given by
$$
\align
B_{s+1,k}(z)&=\sum_{j=0}^s\sum_{i=0}^{s-j}
\frac{(s+j)!(i+1)}{j!(s-j-i)!(j+i+1)!}\times\\&\times
\left(\frac{u}{1+u+u^2}\right)^{s+1+j}
(1-u)^2u^{i+1}u^{k-1}\frac{(1-u^{k-1})^i}{(1-u^{k+1})^{i+2}}.
\endalign
$$
\endproclaim
\demo{Proof} We use the formula
(being a consequence of the {\sl Vandermonde} formula)
$$
\frac{p(p+s)!}{(s-j)!(s+1)!(p+j)!}=
\sum_{i=0}^{s-j}
(i+1)\binom{p}{i+1}\frac{1}{(s-j-i)!(j+i+1)!}
$$
and also the equations
$$
\frac{A_k}{z}=\frac{1}{1-A_{k-1}}
$$
and
$$
\sum_{p\ge1}\binom{p}{i+1}A_{k-1}^p=
\frac{A_{k-1}^{i+1}}{\big(1-A_{k-1}\big)^{i+2}}.
$$
Now we are ready to  attack the local expansion
of $\sum_{k\ge0}B_{s+1,k}$. We easily see that
$$
\frac{u}{1+u+u^2}\sim\frac 13;\qquad
(1-u)^2\sim t^2(1-t);\qquad u^{i+1}\sim 1-(i+1)t.
$$
\enddemo

\proclaim{Lemma 8} We have the local expansion
$$\align
&\sum_{k\ge 0}u^{k-1}\frac{(1-u^{k-1})^i}{(1-u^{k+1})^{i+2}}\\
&\sim
t^{-2}(1+2t)\bigg(
\sum_{l=0}^i\binom il (-2)^l(1+lt)\Big(
\zeta(l+2)-\frac l2\zeta(l+1)t
\Big)-\frac 12t
\bigg).
\endalign
$$
\endproclaim
\demo{Proof}
We can write
$$
\align
\sum_{k\ge 0}u^{k-1}\frac{(1-u^{k-1})^i}{(1-u^{k+1})^{i+2}}
&=u^{-2}\sum_{k\ge1}\frac{u^k}{(1-u^k)^2}\bigg(1+
\frac{(1-u^{-2})u^k}{1-u^k}\bigg)^i\\
&=u^{-2}\sum_{l=0}^i\binom il \big(1-u^{-2}\big)^l\sum_{k\ge1}
\frac{u^{k(l+1)}}{(1-u^k)^{l+2}}.
\endalign
$$
It is easy to see that
$$
u^{-2}\sim1+2t\qquad\text{and}\qquad(1-u^{-2})^l\sim(-2)^lt^l(1+lt).
$$
We use again the Mellin transform:
$$
\align
\Cal M \sum_{k\ge1}\frac{e^{-tk(l+1)}}{(1-e^{tk})^{l+2}}
&= \sum_{k\ge1}k^{-s}\Cal M\frac{e^{-t(l+1)}}{(1-e^{t})^{l+2}}\\
&=\zeta(s)\GG(s)\sum_{\ll\ge0}\binom{\ll}{l+1}\ll^{-s}\\
&=\zeta(s)\GG(s)\sum_{\ll\ge0}\frac{1}{(l+1)!}
\sum_{i=0}^{l+1}s_{l+1,i}\ll^i\ll^{-s}\\
\intertext{
(where the $s_{l+1,j}$ are  {\sl Stirling} numbers of the first kind)}
&=\frac{1}{(l+1)!}\zeta(s)\GG(s)\sum_{i=0}^{l+1}s_{l+1,i}\zeta(s-i).
\endalign
$$
As in Secion 2 we use the Mellin inversion formula; change the line
of integration and take the residues into account.
In our problem is sufficient to consider the terms
where $i=s+1$ and $i=s$. We note that
$$
s_{l+1,l+1}=1\qquad\text{and}\qquad s_{l+1,l}=-\binom{l+1}2.
$$
\enddemo

\proclaim{Lemma 9} The sum of the $B_{s+1,k}(z)$ 
has to local expansion
$$
\sum_{k\ge0}B_{s+1,k}(z)\sim\text{const}-
\frac 12t\sum_{j=0}^s\sum_{i=0}^{s-j}
\frac{(s+j)!(i+1)}{j!(s-j-i)!(j+i+1)!}3^{-s-1-j}.
$$
\endproclaim
\demo{Idea of proof}
$$
\align
\sum_{k\ge0}B_{s+1,k}(z)&\sim\sum_{j=0}^s\sum_{i=0}^{s-j}
\frac{(s+j)!(i+1)}{j!(s-j-i)!(j+i+1)!}3^{-s-1-j}
t^2(1-t)\big(1-(i+1)t\big)\times\\
&\times t^{-2}(1+2t)\bigg(
\sum_{l=0}^i\binom il (-2)^l(1+lt)\Big(
\zeta(l+2)-\frac l2\zeta(l+1)t
\Big)-\frac 12t
\bigg)
\endalign
$$
We want to obtain the coefficient of $t$ in this expression. This is
a simple thing; after some 
manipulations there are luckily of lot of 
simplifications . \qed
\enddemo

From the  preceeding equations we deduce
$$
\coeff n B_{s+1,k}(z)\Big/ t_n
\sim 
4\cdot \frac 12\sum_{j=0}^s\sum_{i=0}^{s-j}
\frac{(s+j)!(i+1)}{j!(s-j-i)!(j+i+1)!}3^{-s-1-j}.
$$
For the quantity $h_n^{(d)}$ we have to sum up:
$$
\sum_{s=0}^{d-2}2\sum_{j=0}^s\sum_{i=0}^{s-j}
\frac{(s+j)!(i+1)}{j!(s-j-i)!(j+i+1)!}3^{-s-1-j}.
$$
We can rewrite this  quantity as
$$
\sum_{s=0}^{d-2}\frac{2}{(s+1)3^{s+1}}
\left[x^s\right]
\frac{1}{(1-x)^2}
\left(\frac{1+x}{1-\frac x3}\right)^{s+1}.
$$
Thus we have finally obtained

\proclaim{Theorem 3} The average height of the {$d$-th} highest leaf
of a planted plane tree of size
$n$, has the following asymptotic expansion
(for $d$ fixed and $n
\to\infty$)
$$
h_n^{(d)}=\sqrt{\pi n}-\frac 12-
\sum_{s=0}^{d-2}\frac{2}{(s+1)3^{s+1}}
\left[x^s\right]
\frac{1}{(1-x)^2}
\left(\frac{1+x}{1-\frac x3}\right)^{s+1}
+\ o(1).
$$
\endproclaim

\head 5. Some remarks concerning the technique of the extraction of 
 coefficients
\endhead

If one follows the strategy mentioned in the title, the enumeration
 problems
for trees often involve the evaluation
of sums of the type
$$
\sum_{k\ge1}\omega(k)
\frac{\binom{2n}{n+k+1}-2\binom{2n}{n+k}+\binom{2n}{n+k-1}}{\binom{2n}{n}}.
$$
where $\omega(k)$ might be, for example, $v_2(k)$ or $\vartheta(k)$
or $d(k)$ as  in Sections 2, 3 and 4.

One needs to approximate certain binomial coefficients 
in a central region
(e.g. $|k|\le \sqrt n\log n$). We obtain, for instance by
{\sl Stirling}'s formula,
$$
\frac{\binom{2n}{n+k}}{\binom{2n}{n}}\sim
e^{-k^2/n}\cdot\left(
1+\frac{k^2}{2n^2}-\frac{k^4}{6n^3}+\dots\right)
$$
(see \cite 9 for a general formula). Quite often
{$r$-th} differences of binomal coefficients appear, viz.
$$
\xi=\coeffu n
u^k(1-u)^r(1+u)^{2n}\bigg/\binom{2n}n
=\sum_{\ll=0}^r
(-1)^\ll\binom r\ll \binom{2n}{n+k+r}\bigg/\binom{2n}n.
$$
Let us recall the difference operator $\Delta$:
$$
\Delta^r \binom{2n}{n+k}=\sum_{\ll=0}^r
\binom r\ll(-1)^{r-\ll} \binom{2n}{n+k+\ll}
$$
Let us consider $\Delta^re^{-k^2/n}$. For this, we need the
{\sl Hermite} polynomials. Here are the necessary properties \cite 3:
$$
\gather
e^{2zt-t^2}=\sum_{n\ge0}H_n(z)\frac{t^n}{n!}\\
H_0=1,\quad H_1=2z,\quad H_{n+1}=2zH_n-2nH_{n-1}\\
H_n(z)=\sum_{k\ge0}\frac{n!}{k!(n-2k)!}(-1)^k(2z)^{n-2k}\\
H_n(-z)=(-1)^nH_n(z)
\endgather
$$
Thus
$$
\align
\Delta^re^{-k^2/n}&=\sum_{\ll=0}^r(-1)^{r-\ll}
\binom r\ll e^{-(k+\ll)^2/n}\\
&=e^{-k^2/n}\sum_{\ll=0}^r(-1)^{r-\ll}
\binom r\ll e^{-\frac{2k\ll}{n}-\frac{\ll^2}{n}}\\
&=e^{-k^2/n}\sum_{\ll=0}^r(-1)^{r-\ll}
\binom r\ll 
\sum_{m\ge0}H_m\left(-\frac{k}{\sqrt n}\right)\left(\frac{\ll}{\sqrt n}
\right)^m\frac{1}{m!}.
\endalign
$$
We know (with {\sl Stirling\/} numbers of the second kind) that
$$
\sum_{\ll=0}^r(-1)^{r-\ll}
\binom r\ll \ll^m=r!S_{m,r}.
$$
Hence
$$
(-1)^r\Delta^re^{-k^2/n}\sim
e^{-k^2/n}\left[
H_{r}\left(\frac{k}{\sqrt n}\right)\frac{1}{n^{r/2}}-
H_{r+1}\left(\frac{k}{\sqrt n}\right)\frac{1}{n^{(r+1)/2}}\frac r2+\dots
\right].
$$
Therefore we have
$$
\xi\sim e^{-k^2/n}H_{r}\left(\frac{k}{\sqrt n}\right)\frac{1}{n^{r/2}},
$$
which was already announced in \cite 5.
\medskip

To obtain more terms we have to consider $\displaystyle{
\Delta^rk^te^{-k^2/n}}$.

We can use the general formula (of {\sl Leibniz} type):
$$
\Delta^rf(k)g(k)  =\sum_{\ll=0}^r\binom r\ll \Big(\Delta^{r-\ll}f(k+\ll)
\Big) \Big(\Delta^{\ll}g(k)\Big)
$$
with $f(k)=k^t$ and $g(k)=e^{-k^2/n}$.
\medskip

If we have to consider (for a  certain polynomial $p$)
$$
\coeffu n u^kp(u)(1+u)^{2n},
$$
we can  developp $p(u)$ in powers of $1-u$ and use the just described
machinery.
\medskip

In a lot of other cases we must investigate
the quantities
$$
\coeffu n u^k\frac{1}{1-u} (1+u)^{2n};
$$
for this we have to consider
$$
\sum_{j\ge k}e^{-j^2/n}\sim\sqrt n \erfc\Big(\frac{k}{\sqrt n}\Big)
+\frac 12 e^{-k^2/n}+\dots,
$$ 
which comes for {\sl Euler\/}'s summation formula and the error function
$$
\erfc(z):=\int_z^\infty e^{-t^2}dt.
$$
\medskip

To obtain more terms, we must consider
$$
I_m(z)=\int_z^\infty t^m e^{-t^2}dt;
$$
we can  evaluate this integral by partial integration:
$$
\gather
I_m(z)=\frac{m-1}{2}I_{m-2}(z)+\frac 12z^{m-1}e^{-z^2},\\
I_1(z)=\frac 12e^{-z^2},\qquad I_0(z)=\erfc(z).
\endgather
$$
Finally a more general problem of the same nature appears in the
evaluation of sums of the type
$$
\coeffu n u^k\frac{1}{(1-u)^a} (1+u)^{2n}
$$
where $a$ is an integer $\ge1$.










\Refs

\ref \no 1\by de Bruijn, Knuth, Rice\jour \yr 1972\pages 15--22
        \vol \paper The average height of planted plane trees
        \inbook Graph Theory and Computing \eds R.C. Read
        \publ Academic Press \publaddr New York\endref

\ref \no 2\by Dieudonne \yr 1968\book Calcul Infinitesimal
         \publ Hermann \publaddr Paris\endref

\ref \no 3\by Erdelyi, Magnus, Oberhettinger,
        Tricomi \yr 1955\book Higher Transcendental Functions
        \publ Mc-Graw-Hill \endref

\ref \no 4\by Flajolet\jour Cahiers du BURO\yr 1981
        \pages 1--209\vol 34--35\paper Analyse d'algorithmes
        d'arbres and de fichiers\endref

\ref \no 5\by Flajolet, Raoult, Vuillemin
        \jour Theor. Comput. Sci. \yr 1979\pages 99--125\vol 9
        \paper The number of registers required for evauluating
        arithmetic expressions\endref

\ref \no 6\by Flajolet, Ramshaw\jour SIAM J. on Computing
        \yr 1980\pages 142--158\vol 9\paper A note on Gray Code and
        odd-even merge\endref

\ref \no 7\by Flajolet, Odlyzko\jour J. Comput. Syst. Sci.
        \yr 1982\pages 171--213\vol 25\paper The average height of binary
        trees and other simple trees\endref

\ref \no 8\by Flajolet, Prodinger\jour SIAM J. on Computing
        \yr 1986\pages 629--640\vol 15\paper Register Allocation
        for unary-binary Trees\endref

\ref \no 9\by Greene, Knuth\book Mathematics for the 
        Analysis of Algorithms \yr 1981 \publ Birkh\"auser \endref

\ref \no 10\by Jungen\jour Commentarii Math. Helvetici
        \yr 1931\pages 266--306\vol 3\paper Sur les series de Taylor
        n'ayant que des singularites algebro-logarithmiques sur
        leur cercle de convergence\endref

\ref \no 11\by Kemp\jour Acta. Inf.\yr 1979\pages 363--372\vol 11
        \paper The average number of registers to evaluate a binary tree
        optimally\endref

\ref \no 12\by Kemp\jour Combinatorica\yr 1982\pages 157--176\vol 2
        \paper On the average oscillation of a stack\endref

\ref \no 13\by Kemp\jour Journal of Combinatorial Theory Ser. B\yr 1983
        \pages 191--208\vol B 34\paper The average height of planted
        plane trees with $m$ leaves\endref

\ref \no 14\by Kemp\jour Discrete Mathematics\yr 1990\pages 247--258
        \vol 81\paper 
        On the number of deepest nodes in ordered trees\endref

\ref \no 15\by Knuth\book The Art of Computer Programming,Vol.1 
        \publ Addison-Wesley\yr 1968\endref

\ref \no 16\by Knuth\book The Art of Computer Programming,Vol.3 
        \publ Addison-Wesley\yr 1968\endref

\ref \no 17\by Meir, Moon and Pounder\jour SIAM J. on Alg. Disc. Meth.
        \yr 1980\pages 25--33\vol 1\paper On the order of random channel
        networks\endref

\ref \no 18\by Prodinger\jour Europ. J. on Combinatorics
        \yr 1984\pages 351--357\vol 5\paper The average height of 
        the second highest leaf of a
        planted plane trees\endref

\ref\no 19
        \paper Die Bestimmung gewisser Parameter von 
        bin\"aren  B\"aumen mit Hilfe analytischer Methoden
        \jour Lecture Notes in Mathematics  (E.Hlawka, Ed.)
        \vol 1114 \yr 1985\pages 118--133\by Prodinger
        \endref

\ref \no 20  
        \paper The Average Height of the d-th Highest Leaf of a 
        Planted Plane Tree
        \jour Networks \vol 16 \yr 1985\pages  67--75 \by Prodinger
        \endref

\ref \no 21\by Sedgewick\jour SIAM J. on Computing\yr 1978\pages 239--272
        \vol 7\paper Data movement in odd-even merge\endref

\ref \no 22\by Whittaker, Watson\book A course in modern analyis \yr 1930
        \publ Cambridge University Press \endref


\endRefs











\enddocument


