\documentclass[11pt,a4paper,reqno]{amsart}

\usepackage{epsfig}

%\renewcommand{\baselinestretch}{1.5}

\setlength{\textwidth}{6in}
\setlength{\textheight}{9in}
\setlength{\topmargin}{0cm}
\setlength{\oddsidemargin}{5mm}
\setlength{\evensidemargin}{5mm}

\newtheorem{theorem}{Theorem}%[section]
\newtheorem{proposition}[theorem]{Proposition}%[section]
\newtheorem{lemma}[theorem]{Lemma}%[section]
\newtheorem{example}[theorem]{Example}%[section]
\newtheorem{cor}[theorem]{Corollary}

\sloppy
\allowdisplaybreaks

\begin{document}

\title[Spanning tree size in Random Binary Search Trees]{Spanning tree size in Random Binary Search Trees}
\author[A.~Panholzer and H.~Prodinger]
{Alois Panholzer$^{\dag}$ and Helmut Prodinger$^{\ddag}$}

\address{${}^{\dag}$Institut f\"ur Algebra und Computermathematik\\ 
Technische Universit{\"a}t Wien\\ Wiedner Hauptstra{\ss}e 8--10\\ A-
1040 Wien\\ Austria.}
\email{Alois.Panholzer@tuwien.ac.at}\vskip0pt
\address{${}^{\ddag}$The John Knopfmacher
Centre for Applicable Analysis and Number Theory\\ 
School of Mathematics\\ 
University of the Witwatersrand\\ P.O. Wits\\ 2050
Johannesburg\\ South Africa.}
\email{helmut@staff.ms.wits.ac.za\vskip0pt {\it WWW-address{\rm:
}}\texttt{http://www.wits.ac.za/helmut/index.htm}}

% \date{April 2, 2002}

\begin{abstract}
   This paper deals with the size of the spanning tree of $p$ randomly chosen nodes in a 
   binary search tree. It is shown via generating functions methods, that for fixed $p$, 
   the (normalized) spanning tree size converges in law to the Normal distribution. 
   The special case $p=2$ reproves  the recent
   result     (obtained by the contraction method in \cite{MahNei01}), 
   that the distribution of distances in random binary search trees has a Gaussian limit law.
   In the proof we use the fact that the spanning tree size is closely related to the number of
   passes in Multiple Quickselect.
This parameter, in particular its first two moments were studied 
   earlier in \cite{PanPro98}. Here we show also that this normalized 
parameter has for  fixed    $p$ 
order statistics 
a Gaussian limit law. For 
$p=1$ this gives the well known
   result that the depth of a randomly selected node in a random binary search tree 
   converges in law to the Normal distribution.
\end{abstract}

\maketitle

\section{Introduction}

In the papers \cite{MahNei01} and \cite{Dob96} the distances between nodes in 
random search trees resp.\  random recursive trees were studied.
It was proven in \cite{MahNei01} that the (edge) distances $\Delta_{n}$ between two 
randomly selected nodes in random binary search trees of size $n$ are asymptotically 
normally (Gaussian) distributed, where  the so called 
random permutation model was used as the model of randomness for the trees. This 
 means that every permutation of length $n$ is assumed to be
equally likely when  generating a binary search tree;
furthermore, for selecting  nodes, all $\binom{n}{2}$ pairs of nodes
are assumed to be equally likely.

In \cite{Dob96} it was shown that the distribution of the distance 
$\Delta(i,n)$ between 
a fixed node $i$ and the node $n$ in a random recursive tree of size $n$ is 
(for a fixed ratio $\rho:=\frac{i}{n}$ with $0 < \rho < 1$)
 asymptotically normally distributed.
A related parameter to the distance between two randomly
 selected nodes is the \emph{Wiener index\/}
of a graph, which is defined to be the  sum of all  distances between pairs of nodes
in the considered graph. The Wiener index was studied for certain families of graphs,
and although the scaled mean of this parameter must coincide with the mean distance of 
two randomly selected nodes, 
it turned out that the Wiener index was 
asymptotically \emph{not\/} normally distributed 
for random recursive trees and random binary search trees
(see \cite{Nei01, Jan01}).

In this paper we concentrate on 
random binary search trees and study a natural extension of the distance between 
two randomly selected nodes, namely the 
size of the spanning tree of $p$ randomly chosen nodes 
in the tree. Again, we use the random permutation model for the 
generation of the binary search trees
and also that all $\binom{n}{p}$ possibilities to select $p$ nodes in the tree of size $n$ are
equally likely. The random variable $Y_{n,p}$, which counts the size of the spanning tree 
of $p$ selected nodes in a random binary search tree of size $n$, is then a direct extension
of $\Delta_{n}$, since the edge distance between two nodes is nothing else than the size of 
the spanning tree of these two nodes minus one and thus 
$\Delta_{n} \overset{\mathcal{L}}{=} Y_{n,2}-1$, 
where $\overset{\mathcal{L}}{=}$ denotes equality in distribution.

In the mathematical analysis of $Y_{n,p}$ we use the fact that it is
closely related to the random variable $X_{n,p}$, which counts the number of passes 
required 
in the Multiple Quickselect algorithm to find a random $p$--order statistic in a data file of 
length $n$ (see \cite{PanPro98} and the  references cited therein
for a description of this 
divide and conquer algorithm); the natural
 probability model for the data is, that their
ranks form a random permutation of $\{1, \dots, n\}$ and we 
assume further that all $\binom{n}{p}$ sets of $p$ 
order statistics $\{1\le i_1<\ldots<i_p\le n\}$ are equally likely.
Then by well known relations between binary search trees and Quicksort-like algorithms,
$X_{n,p}$ is equal to the number of ascendants of $p$ randomly
 chosen nodes in a random 
binary search tree of size $n$ or, equivalently,
 to the size of the spanning tree, spanned
by the root and $p$ randomly chosen nodes (where of course the root
could have been chosen as well) 
in a random binary search tree of size $n$. 
See Figure~\ref{fig1} for a comparison of
both  parameters.

\begin{figure}[ht]
\caption{A binary search tree with the two  parameters
under consideration.\label{fig1}}
\begin{minipage}[t]{15.2cm}
\mbox{}\\
\begin{minipage}{7.5cm}
\begin{center}
\epsfig{file=w1.eps,height=3.5cm}\\
Spanning tree of the nodes $7$, $9$ and $10$ is of size $4$.
\end{center}
\end{minipage}
\begin{minipage}{7.5cm}
\begin{center}
\epsfig{file=w2.eps,height=3.5cm}\\
$5$ passes of the Multiple Quickselect algorithm to find 
the ranks $7$, $9$ and $10$.
\end{center}
\end{minipage}
\end{minipage}
\end{figure}

The parameter
$X_{n,p}$ was studied already in \cite{PanPro98}, where exact formul{\ae} for the
expectation and the variance were given. Here we show additionally
that $X_{n,p}$ is, for fixed $p \ge 1$,
 asymptotically normally distributed.%
\footnote{Philippe Flajolet mentioned that to H.~P. in 1998 without working
out the details.}


For $Y_{n,p}$ we also derive  exact formul{\ae} for the expectation and the variance
and show, that $Y_{n,p}$ is,
 for fixed $p \ge 2$,
 asymptotically normally distributed, where the special case $p=2$
 reproves that the distances $\Delta_{n}$ between two 
randomly selected nodes in random binary search trees of size $n$ are asymptotically 
normally distributed. Our approach uses generating functions, 
singularity analysis and
a central limit theorem for combinatorial structures due to Hwang and avoids the
difficulties which occur in \cite{MahNei01} when showing the asymptotic
normality for $\Delta_{n}$
using the contraction method which arises due to the degenerate nature of the 
distributional limit equation for $X_{n,1}$ (that was studied there to obtain the 
result for $\Delta_{n}$).

\section{Passes in Multiple Quickselect and spanning tree size in\\ 
binary search trees}

First we want to translate the close relation between $X_{n,p}$ and $Y_{n,p}$ into an
equation for suitable generating functions as described below.

Here we denote with $\varphi_{n,p,m}:=\mathbb{P}\{X_{n,p}=m\}$ the probability
that exactly $m$ passes of the
Multiple Quickselect algorithm are required, in order to find a random set of 
$p$ order statistics in a data file of length $n$, and with 
$F_{n,p,m}:=\mathbb{P}\{Y_{n,p}=m\}$ the probability
that the size of the spanning tree of $p$ randomly chosen nodes in a binary search tree 
of size $n$ is exactly $m$. 
Using the recursive structure of the search trees, we obtain for the generating functions
$\phi_{p}(z,v) = \sum_{n,m \ge 0} \binom{n}{p} \varphi_{n,p,m} z^{n} v^{m}$ resp.\
$F_{p}(z,v) = \sum_{n,m \ge 0} \binom{n}{p} F_{n,p,m} z^{n} v^{m}$ for 
\hbox{$p \ge 1$}
the recurrences
\begin{equation}
   \frac{\partial}{\partial z} \phi_{p}(z,v) = v \sum_{i=0}^{p} \phi_{i}(z,v) \phi_{p-i}(z,v)
   + v \sum_{i=0}^{p-1} \phi_{i}(z,v) \phi_{p-1-i}(z,v)
   \label{eqn1}
\end{equation}
and 
\begin{equation}
   \frac{\partial}{\partial z} F_{p}(z,v) = v \sum_{i=1}^{p-1} \phi_{i}(z,v) \phi_{p-i}(z,v)
   + v \sum_{i=0}^{p-1} \phi_{i}(z,v) \phi_{p-1-i}(z,v) +
   2 F_{0}(z,v) F_{p}(z,v),
   \label{eqn2}
\end{equation}
with the initial functions $\phi_{0}(z,v) = F_{0}(z,v) = \frac{1}{1-z}$.
The difference
in the above recurrences reflects the difference 
between both parameters coming from the instance 
where the root is not selected and also the left ($i=0$\/) resp.
 right ($i=p$\/) subtree of the 
root does not contain a selected node.

Introducing the trivariate generating functions 
$\Phi(z,u,v) = \sum_{p \ge 0} \phi_{p}(z,v) u^{p}$ and\\
$F(z,u,v) = \sum_{p \ge 0} F_{p}(z,v) u^{p}$,
we obtain first from \eqref{eqn1} a Riccati differential equation:
\begin{equation}
   \frac{\partial}{\partial z} \Phi(z,u,v) = v (1+u) \Phi^{2}(z,u,v) + \frac{1-v}{(1-z)^{2}},
\end{equation}
with the initial value $\Phi(0,u,v) = 1$.
The solution of this equation is already given in \cite{PanPro98}:
\begin{equation}
   \Phi(z,u,v) = \frac{\Omega+1-2v+(1-z)^{\Omega} (\Omega-1+2v)}
   {\big(\Omega+1-2v(1+u)+(1-z)^{\Omega}(\Omega-1+2v(1+u))\big)(1-z)},
   \label{eqn3}
\end{equation}
with 
\begin{equation}
   \Omega=\sqrt{1-4(1+u)v(1-v)}.
   \label{eqn9}
\end{equation}

For $F(z,u,v)$ we get from \eqref{eqn2} the differential equation
\begin{equation*}
   \frac{\partial}{\partial z}F(z,u,v) = v (1+u) \Phi^{2}(z,u,v) 
   - \frac{2v}{1-z} \Phi(z,u,v) + \frac{2}{1-z} F(z,u,v) + \frac{v-1}{(1-z)^{2}}
\end{equation*}
or
\begin{equation*}
\frac{\partial}{\partial z}F(z,u,v) = \frac{\partial}{\partial z}\Phi(z,u,v)
- \frac{2v}{1-z}\Phi(z,u,v) + \frac{2}{1-z} F(z,u,v) + \frac{2 (v-1)}{(1-z)^{2}},
\end{equation*}
with $F(0,u,v) = 1$.

This equation has then the solution 
\begin{equation}
   F(z,u,v) = \frac{1+2z(v-1)}{(1-z)^{2}} + \frac{1}{(1-z)^{2}} \int_{0}^{z} 
   \left[ \frac{\partial}{\partial t}\Phi(t,u,v) - \frac{2v}{1-t} \Phi(t,u,v) \right]
    (1-t)^{2} dt,
   \label{eqn4}
\end{equation}
with $\Phi(z,u,v)$ given by \eqref{eqn3}.

\section{Expectation and variance of the spanning tree size}

 From \eqref{eqn4} it is easy to obtain exact formul{\ae} for the expectation
$$
E_{n,p}=\mathbb{E}(Y_{n,p})=\frac{1}{\binom{n}{p}}[z^{n}u^{p}] 
\left.\frac{\partial}{\partial v} F(z,u,v)\right|_{v=1}
$$ 
and the second factorial moment
$$
M^{(2)}_{n,p}=\mathbb{E}\big(Y_{n,p}(Y_{n,p}-1)\big) = \frac{1}{\binom{n}{p}}[z^{n}u^{p}] 
\left.\frac{\partial^{2}}{\partial v^{2}} F(z,u,v)\right|_{v=1}
$$ 
(and thus also for the variance $V_{n,p}$) of $Y_{n,p}$, the size of the spanning tree 
of $p$ randomly selected nodes in a random binary search tree of size $n$.

Differentiating \eqref{eqn4} with respect to $v$ and evaluating at $v=1$ gives the following
equation for $E(z,u) := \left.\frac{\partial}{\partial v} F(z,u,v)\right|_{v=1}$:
\begin{equation}
   E(z,u) = \frac{2z}{(1-z)^{2}} + \frac{1}{(1-z)^{2}} \int_{0}^{z} 
   \left[ \frac{4(1-t)(1+u)u^{2}}{(1-t(1+u))^{3}} \log \frac{1}{1-t} + 
   \frac{X}{(1-t(1+u))^{3}} \right] dt,
\end{equation}
with
$X=(-2+u)+(6+3u-3{u}^{2}-4{u}^{3})t+(1+u)
 (2{u}^{2}-3u-6){t}^{2}+(2+u)(1+u)^{2}{t}^{3}$.

This can be simplified to
\begin{equation}
   \begin{split}
   E(z,u) & = \frac{2 u (1+u)}{(1-z(1+u))^{2}} \log \frac{1}{1-z} -
   \frac{2u}{(1-z)^{2} (1+u)^{2}} \log \frac{1}{1-z(1+u)} \\
   & {} + \frac{zu(1-2z-3u+z^2+uz-2u^2+2uz^2+3u^2z+u^2z^2)}{(1-z)^{2} (1+u) (1-z(1+u))^{2}}.
   \end{split}
\end{equation}

To extract coefficients we use here and in the sequel the general formul{\ae} 
(see e.~g. \cite{GreKnu82})
\begin{align*}
   [z^{n}] \frac{1}{(1-z)^{m+1}} \log \frac{1}{1-z} & = \binom{n+m}{n} 
   (H_{n+m}-H_{m}),  \\
   [z^{n}] \frac{1}{(1-z)^{m+1}} \log^{2} \frac{1}{1-z} & = \binom{n+m}{n} 
   \big((H_{n+m}-H_{m})^{2}-(H^{(2)}_{n+m}-H^{(2)}_{m})\big),
\end{align*}
where $H_{n}=\sum_{k=1}^{n}\frac{1}{k}$ and $H^{(2)}_{n}=\sum_{k=1}^{n}\frac{1}{k^{2}}$ 
denote the first and second order harmonic numbers.

By lengthy, but routine calculations,
 we finally get for $E_{n,p} = \frac{1}{\binom{n}{p}}
[z^{n}u^{p}] E(z,u)$ an exact formula, which is given in the next lemma:
\begin{lemma}
   The expectation $E_{n,p}=\mathbb{E}(Y_{n,p})$ of the size 
     of the spanning tree of $p$ randomly chosen nodes 
   in a random binary search tree of size $n$ is for $p \ge 1$ given by
   \begin{align*}
      E_{n,p} & = \frac{2p(n+1)^{2}}{(n+2-p)(n+1-p)} (H_{n} - H_{p}) +
	  \frac{2(2p-1)(n+1)}{(n+2-p)(n+1-p)} + 3 + 2p - \frac{2pn}{n+1-p} \\
	  & {} + \frac{2p(n+1) (-1)^{p}}{\binom{n}{p}} H_{n} 
	  + \frac{2p(n+1)(-1)^{p}}{\binom{n}{p}} 
	  \sum_{k=1}^{p-1} \frac{(-1)^{k}}{k} \binom{n}{k},
   \end{align*}
   and asymptotically for fixed $p \ge 2$ by
   \begin{equation*}
      E_{n,p} = 2p \log n + 2p \gamma -2p H_{p} +3 -2p - \frac{2p}{p-1} + 
	  \mathcal{O}\Big(\frac{\log n}{n}\Big).
   \end{equation*}
\end{lemma}
For $p=1$ the formula simplifies to $E_{n,1} = 1$ as it should.

We remark that 
\begin{equation*}
H_{n} =	  \sum_{k=1}^{n} \frac{(-1)^{k-1}}{k} \binom{n}{k},
\end{equation*}
and so one can give the alternative formula
   \begin{align*}
      E_{n,p} & = \frac{2p(n+1)^{2}}{(n+2-p)(n+1-p)} (H_{n} - H_{p}) +
	  \frac{2(2p-1)(n+1)}{(n+2-p)(n+1-p)} + 3 + 2p - \frac{2pn}{n+1-p} \\
	  & {} + \frac{2p(n+1)(-1)^{p}}{\binom{n}{p}}
         \sum_{k=p}^{n} \frac{(-1)^{k-1}}{k} \binom{n}{k}.
   \end{align*}



When we differentiate equation \eqref{eqn4} twice with respect to $v$ and evaluate at $v=1$, we
finally obtain the following formula for 
$M_{2}(z,u) := \left.\frac{\partial^{2}}{\partial v^{2}} F(z,u,v)\right|_{v=1}$:
\begin{align}
   M_{2}(z,u) & = - \frac{8u}{(1-z)^{2}} \int_{0}^{z} \frac{1}{1-t(1+u)} \log \frac{1}{1-t} dt
   + \frac{4u(1+u)^{2}(1-z+2u-uz)}{(1-z(1+u))^{3}} \log^{2} \frac{1}{1-z} \notag \\
   & {} + \frac{12u}{(1-z)^{2} (1+u)^{2}} \log \frac{1}{1-z(1+u)} 
   + \frac{4u \Psi_{1}}{(1-z)(1-z(1+u))^{3}}
   \log \frac{1}{1-z} \\
   & {} + \frac{2u^{2}z \Psi_{2}}{(1-z)^{2} (1-z(1+u))^{3} (1+u)}, \notag
\end{align}
with the abbreviations
\begin{align*}
   \Psi_{1} & = -z^{2}u^{2} - 3z^{2} -5z^{2}u+u^{3}z^{2}+6z+9zu+2u^{2}z-u^{3}z-3u^{2}-4u-3, \\
   \Psi_{2} & = -z^{3}u^{3}+3u^{3}z^{2}-2u^{3}z-19u^{2}z+22z^{2}u^{2}+6u^{2}-3z^{3}u^{2}
   +14u-3z^{3}u-46zu\\
   & {} +35z^{2}u+14-29z-z^{3}+16z^{2}.
\end{align*}

Extracting coefficients gives after a somewhat lengthy calculation 
an exact formula for the second factorial moment $M^{(2)}_{n,p} = \frac{1}{\binom{n}{p}}
[z^{n}u^{p}] M_{2}(z,u)$ and we get via $V_{n,p} = M^{(2)}_{n,p}+E_{n,p}-E_{n,p}^{2}$
the following result:
\begin{lemma}
   The variance $V_{n,p}=\mathbb{V}(Y_{n,p})$ of the size of the spanning tree of $p$ chosen nodes 
   in a random binary search tree of size $n$ is for $p \ge 2$ given by
   \begin{align*}
      V_{n,p} & = \frac{4 (-1)^{p} (n+1) (2 p H_{n}- 2 p H_{p} + 2 - 3p^{2})}{p \binom{n}{p}}
	  \sum_{k=1}^{p-1} \frac{(-1)^{k}}{k} \binom{n}{k} \\
	  & {} - \frac{8 (-1)^{p} (n+1)}{\binom{n}{p}} \sum_{k=1}^{p-1} \frac{(-1)^{k}}{k^{2}}
	  \binom{n}{k} 
	  + \frac{4 (-1)^{p} (n+1)}{\binom{n}{p}} (H_{n}^{2} - H_{n}^{(2)} - 2 H_{p} H_{n}) \\
	  & {} + \frac{4 (-1)^{p} (2-3p^{2}) (n+1)}{p \binom{n}{p}}  H_{n}
	  - \frac{4 \Psi_{3}}{(n+4-p)^{\underline{4}}} (H_{n}-H_{p}) \\
	  & {} + \frac{4 p (n+2) (n+1)^{3} (np+2+p)}{(n+4-p)^{\underline{4}}} 
	  \big((H_{n}-H_{p})^{2}-(H^{(2)}_{n}-H^{(2)}_{p})\big)
	  + \frac{2 \Psi_{4}}{(n+4-p)^{\underline{4}}} \\
	  & {} + E_{n,p} - E_{n,p}^{2},
   \end{align*}
   with
   \begin{align*}
      \Psi_{3} & = -2p^4-6n^2p^3+16p^3-2n^3p^3-45p^2n-58p^2-4n^2p^2+2p^2n^4+7n^3p^2+56p\\
	  & {} +78np+6n^3p+41pn^2-n^4p-8-20n-16n^2-4n^3, \\
	  \Psi_{4} & = -144-6p^5-3n^4-152p^3n+2p^4n^2+25p^4n-234n+78p+10np-5n^4p-39n^2p^3\\
	  & {} -4n^3p^3+250p^2n+119n^2p^2+2p^2n^4+25n^3p^2-\!22n^3p-35pn^2+155p^2-\!173p^3+58p^4\\
	  & {} -153n^2-42n^3.
   \end{align*}
   Further we have  $V_{n,1} = 0$ and the following asymptotic expansion
   for $n \to \infty$ and fixed $p \ge 2$:
   \begin{equation*}
      V_{n,p} = 2p \log n - 2p (H_{p}-\gamma) - 4p^{2} 
\Big(\frac{\pi^{2}}{6} - H^{(2)}_{p}\Big)
	  + \frac{2 (-2+7p-5p^{2}+2p^{3})}{(1-p)^{2}} + \mathcal{O}
       \Big(\frac{\log^{2} n}{n}\Big).
   \end{equation*}
\end{lemma}
Here we used the abbreviation $x^{\underline{m}} := x (x-1) \cdots (x-m+1)$ for the
falling factorials.

We remark again that an alternative representation of the variance would be
possible using the additional formula
\begin{equation*}
\frac12\Big(H_{n}^2+H_n^{(2)}\Big) =	
  \sum_{k=1}^{n} \frac{(-1)^{k-1}}{k^2} \binom{n}{k}.
\end{equation*}

\section{The limiting distribution of the number of passes in Multiple 
Quickselect\label{sec1}}

We will show that both  random variables $X_{n,p}$ and $Y_{n,p}$ satisfy, 
for fixed $p$, a Gaussian limit law. To do this, we will expand the coefficients at
$u^{p}$ (for fixed $p$) of the trivariate generating functions $\Phi(z,u,v)$ 
resp.\ $F(z,u,v)$ around their dominant singularity $z=1$, where the expansion holds uniformly 
for $|v-1| < \tau$, for $\tau > 0$. Singularity analysis (see \cite{FlaOdl90}) of 
generating functions allows then to translate these expansions into an asymptotic expansion 
of the moment generating function (the Laplace transform) of the considered random variables. 
Then we can apply the so called Quasi power theorem (see \cite{Hwa98}) to establish the weak 
convergence of the random variables to the normal distribution with certain convergence rates.

In this section we will treat the random variable $X_{n,p}$.
As described above, we are interested in an asymptotic expansion of 
$\frac{1}{\binom{n}{p}} [z^{n}u^{p}] \Phi(z,u,v)$ for $n \to \infty$ and fixed $p$ 
uniformly for $|v-1| \le \tau$, where $\Phi(z,u,v)$ is given by the exact formula \eqref{eqn3}.

To expand $\Phi(z,u,v)$ we will use some auxiliary expansions of
\begin{align}
f(u) & = \Omega +1 - 2v + (1-z)^{\Omega} (\Omega-1+2v), \label{eqn10} \\
g(u) & = \Omega +1 -2v(1+u)+(1-z)^{\Omega} (\Omega-1+2v(1+u)) \label{eqn11}
\end{align}
with $\Omega$ given by \eqref{eqn9}. 
All $\mathcal{O}$--terms in the expansions given below  are
uniform for $|v-1| \le \tau$, as required.
In the sequel, we will use the notations $D_{u}$ for the differential operator 
w.~r.~t. $u$ 
and $N_{u}$ for the evaluation operator at $u=0$.

Since
\begin{equation*}
   \Omega = (2v-1) \sum_{k \ge 0} \binom{\frac{1}{2}}{k} 
   \bigg(- \frac{4v(1-v)}{1-4v(1-v)}\bigg)^{k} u^{k},
\end{equation*}
we get
\begin{equation*}
   (1-z)^{\Omega} = e^{\Omega \log (1-z)} = (1-z)^{2v-1} 
   \exp\bigg[{(2v-1) \log (1-z) \sum_{k \ge 1} \binom{\frac{1}{2}}{k} 
   \bigg(- \frac{4v(1-v)}{1-4v(1-v)}\bigg)^{k} u^{k}}\bigg],
\end{equation*}
and thus 
\begin{equation}
   N_{u} D_{u}^{p} (1-z)^{\Omega}= \mathcal{O}\big((1-z)^{2v-1} \log^{p}(1-z) \big).
\end{equation}

We have
\begin{equation}
   f(0) = g(0) = (1-z)^{2v-1} 2 (2v-1)
\end{equation}
and we get further
\begin{subequations}
\begin{align}
   N_{u} D_{u} f(u) & = -\frac{4v(1-v)}{2 (2v-1)} + \mathcal{O}\big((1-z)^{2v-1} \log(1-z)\big), \\
   N_{u} D_{u} g(u) & = -\frac{2v^{2}}{2v-1} + \mathcal{O}\big((1-z)^{2v-1} \log(1-z)\big), \\
   N_{u} D_{u}^{p} f(u) & = (2v-1) p! \binom{\frac{1}{2}}{p} 
   \left(- \frac{4v(1-v)}{1-4v(1-v)}\right)^{p} + \mathcal{O}\big((1-z)^{2v-1} \log^{p}(1-z)\big), \\
   N_{u} D_{u}^{p} g(u) & = (2v-1) p! \binom{\frac{1}{2}}{p} 
   \left(- \frac{4v(1-v)}{1-4v(1-v)}\right)^{p} + \mathcal{O}\big((1-z)^{2v-1} \log^{p}(1-z)\big), 
\end{align}
\end{subequations}
for $p \ge 2$. Furthermore, 
we want to expand $D_{u}^{p} (g(u))^{-1}$ (for $p \ge 1$) in terms 
of falling powers of $(g(u))^{-1}$, which gives
\begin{align*}
   D_{u}^{p} (g(u))^{-1} & = (-1)^p p! (g(u))^{-p-1} (g'(u))^{p} + \frac{(-1)^{p-1} (p-1) p!}{2} 
   (g(u))^{-p} (g'(u))^{p-2} g''(u) \\
   & {} + \mathcal{O}((g(u))^{-p+1})
\end{align*}
and hence we obtain the expansion
\begin{align}
   N_{u} D_{u}^{p} (g(u))^{-1} & = (-1)^p p! \frac{\big(-\frac{2v^{2}}{2v-1} 
   + \mathcal{O}\big((1-z)^{2v-1} \log(1-z)\big)\big)^{p}}
   {(1-z)^{(p+1) (2v-1)} 2^{p+1} (2v-1)^{p+1}}
   + \mathcal{O}\Big(\frac{1}{(1-z)^{p(2v-1)}}\Big) \notag \\*
   & = \frac{(-1)^{p} p! \big(-\frac{2v^2}{2v-1}\big)^{p}}
   {(1-z)^{(p+1)(2v-1)}2^{p+1}(2v-1)^{p+1}}
   + \mathcal{O}\Big(\frac{\log(1-z)}{(1-z)^{p(2v-1)}}\Big).
\end{align}
%
This finally gives
\begin{align}
   & N_{u} D_{u}^{p} \Phi(z,u,v) = N_{u} D_{u}^{p} \frac{f(u)}{(1-z)g(u)} \notag \\
   & = \frac{1}{1-z} f(0) N_{u} D_{u}^{p} (g(u))^{-1} + \frac{1}{1-z} p f'(0) 
   N_{u} D_{u}^{p-1} (g(u))^{-1} 
   + \frac{1}{1-z} \mathcal{O}\Big(\frac{1}{(1-z)^{(p-1)(2v-1)}}\Big) \notag \\
   & = \frac{(1-z)^{2v-1} 2 (2v-1) (-1)^{p} p! \big(-\frac{2v^{2}}{2v-1}\big)^{p}}
   {(1-z)^{(p+1)(2v-1)+1} 2^{p+1} (2v-1)^{p+1}} 
   + \frac{p \big(-\frac{4v(1-v)}{2(2v-1)}\big) (-1)^{p-1} (p-1)! 
   \big(-\frac{2v^{2}}{2v-1}\big)^{p-1}}
   {(1-z)^{p(2v-1)+1} 2^{p} (2v-1)^{p}} \notag \\
   & \quad {} + \mathcal{O}\Big(\frac{\log(1-z)}{(1-z)^{(p-1)(2v-1)+1}}\Big)
 \notag  \\
&= \frac{p! \big(\frac{v}{2v-1}\big)^{2p-1}}{(1-z)^{p(2v-1)+1}}
   + \mathcal{O}\Big(\frac{\log(1-z)}{(1-z)^{(p-1)(2v-1)+1}}\Big).
   \label{eqn5}
\end{align}
%
Singularity analysis leads then directly to
\begin{align}
   [z^{n}] N_{u} D_{u}^{p} \Phi(z,u,v) & = p! \big(\frac{v}{2v-1}\big)^{2p-1} 
   \!\frac{n^{p(2v-1)}}{\Gamma(p (2v-1)+1)} 
   \Big(1+\mathcal{O}\big(\frac{1}{n}\big)\Big)
   \!+ \mathcal{O}\big((\log n) \, n^{(p-1)(2v-1)}\big) \notag \\
   & = \frac{p! \big(\frac{v}{2v-1}\big)^{2p-1}n^{p(2v-1)}}{\Gamma(p(2v-1)+1)} 
   \Big(1+\mathcal{O}\big(\frac{1}{n}\big)\Big) 
   \Big(1+\mathcal{O}\big(\frac{\log n}{n^{2v-1}}\big)\Big) \notag \\
   & = \frac{p! \big(\frac{v}{2v-1}\big)^{2p-1}n^{p(2v-1)}}{\Gamma(p(2v-1)+1)} 
   \Big(1+\mathcal{O}\big(\frac{1}{n^{1-\epsilon}}\big)\Big),
\end{align}
uniformly for $\epsilon > 0$ and $|v-1| \le \tau :=\frac{\epsilon}{3}$ and 
also to the following expansion, which is valid for fixed $p \ge 1$:
\begin{align}
   \frac{1}{\binom{n}{p}} [z^{n}u^{p}] \Phi(z,u,v) & = \frac{p!}{n^{p}} [z^{n}u^{p}]
   \Phi(z,u,v) \Big(1+\mathcal{O}\big(\frac{1}{n}\big)\Big)\\
    &= \frac{1}{n^{p}} [z^{n}] N_{u} D_{u}^{p} \Phi(z,u,v) 
\Big(1+\mathcal{O}\big(\frac{1}{n}\big)\Big) \notag \\
   & = \frac{p! \big(\frac{v}{2v-1}\big)^{2p-1}n^{p(2v-2)}}{\Gamma(p(2v-1)+1)} 
   \Big(1+\mathcal{O}\big(\frac{1}{n^{1-\epsilon}}\big)\Big) \notag \\
   & = \exp\bigg[{p (2v-2) \log n + \log\bigg(\frac{p! 
(\frac{v}{2v-1})^{2p-1}}{\Gamma(p(2v-1)+1)}\bigg)}\bigg]
   \Big(1+\mathcal{O}\big(\frac{1}{n^{1-\epsilon}}\big)\Big).
   \label{eqn6}
\end{align}

We give here the Quasi power theorem as proven in \cite{Hwa98}, which we want to apply
to our problem:
\begin{theorem} {\rm{[H.~K.~Hwang]}}
\label{the1}
Let $\{\Omega_{n}\}_{n \ge 1}$ be a sequence of integral random variables. Suppose that the
moment generating function satisfies the asymptotic expression
\begin{equation*}
   M_{n}(s) := \mathbb{E}\left(e^{\Omega_{n} s}\right) = \sum_{m \ge 0}
   \mathbb{P}\{\Omega_{n}=m\} e^{ms} = e^{H_{n}(s)} 
      \big(1+\mathcal{O}(\kappa_{n}^{-1})\big),
\end{equation*}
the $\mathcal{O}$--term being uniform for $|s| \le \tau$, $s \in \mathbb{C}$, $\tau>0$, where
\begin{itemize}
   \item[(i)] $H_{n}(s) = u(s) \phi(n) + v(s)$, with $u(s)$ and $v(s)$ analytic for
   $|s| \le \tau$ and independent of $n$;  $\ u''(0)\neq 0$,
   \item[(ii)] $\phi(n) \to \infty$,
   \item[(iii)] $\kappa_{n} \to \infty$.
\end{itemize}

Under these assumptions, the distribution of $\Omega_{n}$ is asymptotically Gaussian:
\begin{equation*}
   \mathbb{P}\bigg\{\frac{\Omega_{n}-u'(0)\phi(n)}{\sqrt{u''(0)\phi(n)}}<x\bigg\}
   = \Phi(x) + \mathcal{O}\bigg(\frac{1}{\kappa_{n}}+\frac{1}{\sqrt{\phi(n)}}\bigg),
\end{equation*}
uniformly with respect to $x$, $x \in \mathbb{R}$.
Here $\Phi(x)$ denotes the distribution function of the standard normal distribution
$\mathcal{N}(0,1)$.

Moreover, the mean and the variance of $\Omega_{n}$ satisfy
\begin{equation*}
   \mathbb{E}(\Omega_{n}) = u'(0) \phi(n) + v'(0) + \mathcal{O}(\kappa_{n}^{-1}), 
   \qquad
   \mathbb{V}(\Omega_{n}) = u''(0) \phi(n) + v''(0) + \mathcal{O}(\kappa_{n}^{-1}).
\end{equation*}
\end{theorem}
%
 From \eqref{eqn6} we get with the notations in Theorem~\ref{the1}:
\begin{equation*}
   u(s) = p (2e^{s}-2), \ \ v(s) = 
   \log\bigg(\frac{p! \big(\frac{e^{s}}{2e^{s}-1}\big)^{2p-1}}{\Gamma(p(2e^{s}-1)+1)}
\bigg),
   \ \ \phi(n) = \log n, \ \ \kappa_{n} = n^{1-\epsilon}.
\end{equation*}
%
We find
\begin{equation}
   u'(0)=2p, \qquad u''(0)=2p,
   \label{eqn7}
\end{equation}
and
\begin{align}
   v'(0) & = -2p+1-2p \Psi(p+1) = -2pH_{p}+2p \gamma +1 -2p, \notag \\
   v''(0) & = 2(2p-1)-2p\Psi(p+1)-4p^{2}\Psi'(p+1) \label{eqn8} \\
   & = 2(2p-1) -2pH_{p}+2p\gamma -\frac{2}{3}\pi^{2}p^{2} + 4p^{2} H^{(2)}_{p}, \notag
\end{align}
where $\Psi(x)$ denotes the digamma function: $\Psi(x):=\big(\log \Gamma(x)\big)'$. 

Hence, with equations \eqref{eqn7} and \eqref{eqn8}, we get from 
Theorem~\ref{the1} the following result:
\begin{theorem}
The distribution of the random variable $X_{n,p}$, which counts the number of passes in the 
Multiple Quickselect algorithm that are required to find a random order statistic of $p$ 
elements in a data file of size $n$, is for fixed $p \ge 1$ asymptotically Gaussian,
where the convergence rate is of order $\mathcal{O}\big(\frac{1}{\sqrt{\log n}}\big)$:
\begin{equation*}
   \mathbb{P}\left\{\frac{X_{n,p}-2p\log n}{\sqrt{2p\log n}}\right\} = \Phi(x) + 
   \mathcal{O}\Big(\frac{1}{\sqrt{\log n}}\Big),
\end{equation*}
and the expectation $E_{n,p}=\mathbb{E}(X_{n,p})$ and the variance 
$V_{n,p}=\mathbb{V}(X_{n,p})$ satisfy
\begin{align*}
   E_{n,p} & = 2p \log n +1 -2p - 2pH_{p} +2p \gamma + 
\mathcal{O}\big(\frac{1}{n^{1-\epsilon}}\big), \\
   V_{n,p} & = 2p \log n + 4p - 2 - 2pH_{p} + 2p \gamma + 4p^{2}H^{(2)}_{p} 
   - \frac{2}{3} \pi^{2} p^{2} + \mathcal{O}\big(\frac{1}{n^{1-\epsilon}}\big).
\end{align*}
\end{theorem}

The result for $E_{n,p}$ and $V_{n,p}$ already appeared in \cite{PanPro98},
but unfortunately there was a typo in the formula for $V_{n,p}$.

For the case $p=1$ we have that $X_{n,1}$ counts the number of 
comparisons encountered by a successful
search in a random binary search tree
 and this is, up to an additive constant, the same as the depth $D_{n}$
of a randomly selected node, $D_{n} \overset{\mathcal{L}}{=} X_{n,1}-1$.
The asymptotic normality of the distribution of $X_{n,1}$ is well known 
(see e.~g. \cite{Mah92}), 
and the convergence rate was recently established in \cite{MahNei01}.

\section{The limiting distribution of the spanning tree size in binary search trees}

In this section we will show, that the normalized random variable $Y_{n,p}$, as defined in 
Section~\ref{sec1}, has for fixed $p$ a Gaussian limiting distribution. 
Hence we are interested in an asymptotic expansion of 
$\frac{1}{\binom{n}{p}} [z^{n}u^{p}] F(z,u,v)$ for $n \to \infty$ and fixed $p$ 
uniformly for $|v-1| \le \tau$, where $F(z,u,v)$ is given by \eqref{eqn4}.

To do this, we will first
study  the behaviour near the singularity $z=1$ of the expression 
\begin{equation}
   \tilde{\Phi}(z,u,v) = \left(\frac{\partial}{\partial z} \Phi(z,u,v)
   -\frac{2v}{1-z}\Phi(z,u,v)\right) (1-z)^{2},
\end{equation}
which we can write as
\begin{equation}
   \tilde{\Phi}(z,u,v) = \frac{\tilde{f}(u)}{(g(u))^{2}},
\end{equation}
where the function $\tilde{f}(u)$ is defined by
\begin{equation}
   \tilde{f}(u) = -\Omega (\Omega-1+2v)(1-z)^{\Omega} g(u) + 
   \Omega (\Omega-1+2v(1+u)) (1-z)^{\Omega} f(u) + (1-2v) f(u) g(u),
\end{equation}
and $\Phi(z,u,v)$, $\Omega$, $f(u)$ and $g(u)$ are given by equations \eqref{eqn3}, 
\eqref{eqn9}, \eqref{eqn10} and \eqref{eqn11}, respectively.

The relevant expansions are now
\begin{align*}
   \tilde{f}(0) & = -4 (2v-1)^{3} (1-z)^{4v-2}, \\
   \tilde{f}'(0) & = 8v^{2} (2v-1) (1-z)^{2v-1} + 
   \mathcal{O}\big(\log(1-z) \, (1-z)^{4v-2}\big), \\
   \tilde{f}''(0) & = \frac{8(v-1) v^{3}}{2v-1} + 
   \mathcal{O}\big(\log(1-z)\, (1-z)^{2v-1}\big),
\end{align*}
and
\begin{equation*}
N_{u}D_{u}^{p} (g(u))^{-2} = (-1)^{p} (p+1)! \frac{(g'(0))^{p}}{(g(0))^{p+2}} + 
\mathcal{O}\Big(\frac{1}{(g(0))^{p+1}}\Big),
\end{equation*}
which leads for $p \ge 2$ eventually to
\begin{align}
   N_{u} D_{u}^{p} \tilde{\Phi}(z,u,v) & = \tilde{f}(0) N_{u} D_{u}^{p} (g(u))^{-2} 
   + p \tilde{f}'(0) N_{u} D_{u}^{p-1} (g(u))^{-2} \notag \\
   & \quad {} + \frac{p(p-1)}{2} \tilde{f}''(0) N_{u} D_{u}^{p-2}(g(u))^{-2} 
   + \mathcal{O}\Big(\frac{1}{(1-z)^{(p-1)(2v-1)}}\Big) \notag \\
   & = \frac{(p-1)p! v \big(\frac{v}{2v-1}\big)^{2p-2}}{(1-z)^{p(2v-1)}}
   + \mathcal{O}\Big(\frac{\log(1-z)}{(1-z)^{(p-1)(2v-1)}}\Big).
\end{align}
%
This gives then
\begin{align}
   & \frac{1}{\binom{n}{p}} [z^{n}u^{p}] F(z,u,v) = 
   \frac{1}{\binom{n}{p}} [z^{n}u^{p}] \frac{1}{(1-z)^{2}} \int_{t=0}^{z} 
   \tilde{\Phi}(t,u,v) dt \notag \\
   & = \frac{1}{n^{p}} [z^{n}] \frac{1}{(1-z)^{2}}
   \int_{t=0}^{z} N_{u} D_{u}^{p} \tilde{\Phi}(t,u,v) dt 
   \, \Big(1+\mathcal{O}\big(\frac{1}{n}\big)\Big) \label{eqn12} \\
   & = \frac{1}{n^{p}} [z^{n}] \frac{1}{(1-z)^{2}} 
   \int_{t=0}^{z} \left[ \frac{(p-1) p! v \big(\frac{v}{2v-1}\big)^{2p-2}}{(1-z)^{p(2v-1)}}
   + \mathcal{O}\Big(\frac{\log(1-z)}{(1-z)^{(p-1)(2v-1)}}\Big)\right] dt
   \, \Big(1+\mathcal{O}\big(\frac{1}{n}\big)\Big). \notag
\end{align}
%
We get via singularity analysis
\begin{align}
   & [z^{n}] \frac{1}{(1-z)^{2}} \int_{t=0}^{z} 
   \frac{(p-1) p! v \big(\frac{v}{2v-1}\big)^{2p-2}}{(1-z)^{p(2v-1)}} dt
   = [z^{n}] \frac{(p-1) p! v \big(\frac{v}{2v-1}\big)^{2p-2}}{(p(2v-1)-1)(1-z)^{p(2v-1)+1}} \notag \\
   & = \frac{(p-1) p! v \big(\frac{v}{2v-1}\big)^{2p-2} n^{p(2v-1)}}{(p(2v-1)-1)\Gamma(p(2v-1)+1)}
    \Big(1+\mathcal{O}\big(\frac{1}{n}\big)\Big) \label{eqn13}
\end{align}
and
\begin{align}
   & [z^{n}] \frac{1}{(1-z)^{2}} \int_{t=0}^{z}
   \mathcal{O}\Big(\frac{\log(1-t)}{(1-t)^{(p-1)(2v-1)}}\Big) dt \notag \\
   & = \mathcal{O}\bigg(\sum_{k=1}^{n} [z^{n-k}] \frac{1}{(1-z)^{2}} [z^{k}]
   \int_{t=0}^{z} \frac{\log(1-t)}{(1-t)^{(p-1)(2v-1)}} dt\bigg) \notag \\
   & = \mathcal{O}\left(n \max_{1 \le k \le n} [z^{n-k}] \frac{1}{(1-z)^{2}} \max_{1 \le k \le n} [z^{k}] 
   \int_{t=0}^{z} \frac{\log(1-t)}{(1-t)^{(p-1)(2v-1)}} dt\right) \notag \\
   & = \mathcal{O}\left(n^{2} [z^{n}] \int_{t=0}^{z} \frac{\log(1-t)}{(1-t)^{(p-1)(2v-1)}} 
   dt \right)
   = \mathcal{O}\left((\log n) \, n^{(p-1)(2v-1)}\right) \notag \\
   & = \mathcal{O}\Big(n^{p(2v-1)} \frac{1}{n^{1-\epsilon}}\Big), \label{eqn14}
\end{align}
uniformly for $\epsilon > 0$ and $|v-1| \le \tau:= \frac{\epsilon}{3}$.

Thus we obtain by combining the results \eqref{eqn12}, 
\eqref{eqn13} and \eqref{eqn14} 
for $p \ge 2$ the asymptotic expansion
\begin{align}
   & \frac{1}{\binom{n}{p}} [z^{n}u^{p}] F(z,u,v) = 
   \frac{(p-1) p! v \big(\frac{v}{2v-1}\big)^{2p-2} n^{p(2v-2)}}{(p(2v-1)-1)\Gamma(p(2v-1)+1)}
   \Big(1+\mathcal{O}\big(\frac{1}{n^{1-\epsilon}}\big)\Big).
   \label{eqn15}
\end{align}

To apply the Quasi power theorem, we write \eqref{eqn15} as
\begin{multline}
    \frac{1}{\binom{n}{p}} [z^{n}u^{p}] F(z,u,v) = 
   \exp\bigg[{p (2v-2) \log n + \log\bigg(\frac{(p-1) p! v 
     (\frac{v}{2v-1})^{2p-2}}
   {(p(2v-1)-1) \Gamma(p(2v-1)+1)}\bigg)}\bigg]
\\ \times   \Big(1+\mathcal{O}\big(\frac{1}{n^{1-\epsilon}}\big)\Big)
\end{multline}
and  then get, with the notations used in Theorem~\ref{the1},
\begin{align*}
   u(s) & = p (2e^{s}-2), \quad v(s) = 
   \log\bigg(\frac{(p-1) p! e^{s} \big(\frac{e^{s}}{2e^{s}-1}\big)^{2p-2}}
   {(p(2e^{s}-1)-1)\Gamma(p(2e^{s}-1)+1)}\bigg), \\
   \phi(n) & = \log n, \quad \kappa_{n} = n^{1-\epsilon}.
\end{align*}

We have
\begin{equation}
   u'(0)=2p, \quad u''(0)=2p,
   \label{eqn16}
\end{equation}
and
\begin{align}
   v'(0) & = -2p \Psi(p+1) +3 -2p -\frac{2p}{p-1}= -2pH_{p}+2p \gamma +3 -2p -\frac{2p}{p-1}, \notag \\
   v''(0) & = -2p\Psi(p+1)-4p^{2}\Psi'(p+1)+\frac{2(2p^{3}-5p^{2}+7p-2)}{(p-1)^{2}} \label{eqn17}\\
   & = -2pH_{p}+2p\gamma -\frac{2}{3}\pi^{2}p^{2} + 4p^{2} H^{(2)}_{p}
   +\frac{2(2p^{3}-5p^{2}+7p-2)}{(p-1)^{2}}, \notag
\end{align}
which leads now to the following result:
\begin{theorem}
The distribution of the random variable $Y_{n,p}$, 
which counts the size of the spanning tree
of $p$ randomly chosen  nodes in a binary search tree of size $n$ is for fixed $p \ge 2$ 
asymptotically Gaussian, where the convergence rate is of order
$\mathcal{O}\big(\frac{1}{\sqrt{\log n}}\big)$:
\begin{equation*}
   \mathbb{P}\left\{\frac{Y_{n,p}-2p\log n}{\sqrt{2p\log n}}\right\} = \Phi(x) + 
   \mathcal{O}\Big(\frac{1}{\sqrt{\log n}}\Big),
\end{equation*}
and the expectation $E_{n,p}=\mathbb{E}(Y_{n,p})$ and the variance 
$V_{n,p}=\mathbb{E}(Y_{n,p})$ satisfy
\begin{align*}
   E_{n,p} & = 2p \log n -2pH_{p}+2p \gamma +3 -2p -\frac{2p}{p-1} + 
        \mathcal{O}\big(\frac{1}{n^{1-\epsilon}}\big), \\*
   V_{n,p} & = 2p \log n -2pH_{p}+2p\gamma -\frac{2}{3}\pi^{2}p^{2} + 4p^{2} H^{(2)}_{p}
   +\frac{2(2p^{3}-5p^{2}+7p-2)}{(p-1)^{2}} + \mathcal{O}\big(\frac{1}{n^{1-\epsilon}}\big).
\end{align*}
\end{theorem}
Of course, the case $p=1$ is trivial, since we have $\mathbb{P}\{Y_{n,1}=1\}=1$ due to the fact
that the spanning tree of a single node is the node itself.

The case $p=2$ is of particular interest, since $Y_{n,2}$ is 
as described earlier, up to an 
additive constant, the distance $\Delta_{n}$ between two randomly selected nodes in a 
binary search tree of size $n$, viz. $\Delta_{n} \overset{\mathcal{L}}{=} Y_{n,2}-1$.
This parameter was studied already in \cite{MahNei01}, where the asymptotic normality of the 
distribution was shown by means of a refined contraction method.

\bibliographystyle{plain}
\begin{thebibliography}{1}

\bibitem{Dob96}
R.~Dobrow, On the distribution of distances in recursive trees, \emph{Journal of
Applied Probability} 33, 749--757, 1996.

\bibitem{FlaOdl90}
Ph.~Flajolet and A.~Odlyzko, Singularity Analysis of Generating Functions, 
\emph{SIAM Journal on Discrete Mathematics} 3, 216--240, 1990.

\bibitem{GreKnu82}
D.~Greene and D.~Knuth, \emph{Mathematics for the Analysis of Algorithms}, 2nd Ed., 
Birkh{\"a}user, Boston, 1982.

\bibitem{Hwa98}
H.-K.~Hwang, On Convergence Rates in the Central Limit Theorems for 
Combinatorial Structures, \emph{European Journal of Combinatorics} 19, 329--343, 1998.

\bibitem{Jan01}
S.~Janson,  The Wiener index of simply generated random trees,
 preprint, 2001.

\bibitem{Mah92}
H.~Mahmoud, \emph{Evolution of Random Search Trees}, Wiley, New York, 1992.

\bibitem{MahNei01}
H.~Mahmoud and R.~Neininger, Distribution of Distances in Random Binary Search Trees,
\emph{The Annals of Applied Probability}, accepted for publication, 2002. 

\bibitem{Nei01}
R.~Neininger, Wiener index of random trees, \emph{
Combinatorics, Probability \& Computing}, accepted for publication, 2002. 

\bibitem{PanPro98}
A.~Panholzer and H.~Prodinger, A Generating Functions Approach for the Analysis of Grand
Averages for Multiple \textsc{Quickselect},
\emph{Random Structures and Algorithms} 13, 189--209, 1998.

\end{thebibliography}

\end{document}


