\documentclass[reqno,11pt]{amsart}

\usepackage{oldlfont}
\usepackage{epsfig}
	



\setlength{\arraycolsep}{0pt} 
\addtolength{\oddsidemargin}{-1.5cm} 
\addtolength{\evensidemargin}{-1.5cm} 
\addtolength{\textwidth}{2.2cm} 
\addtolength{\medskipamount}{3pt} 

\hfuzz=10pt

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

\newtheorem{ncor}{Corollary}



\newtheorem{df}{Definition}[section]
\newtheorem{ex}{Example}
\renewcommand{\theex}{}
\def\comp#1#2{C_{#1,#2}}
\def\compp#1#2{{\cal C}_{#1,#2}(v)}
\def\mom#1#2{D_{#1,#2}}
\def\dilog{\operatorname{dilog}}
\def\var{\operatorname{Var}}
%def\rho{\varrho}
\def\ca{{\cal{C}}}
\def\hot{heap ordered tree}
\def\wh{\widehat{H}}
\def\stir#1#2{\left[#1\atop#2\right]}
\def\poch#1#2{#1^{\underline{#2}}}
\def\eps{\epsilon}






\newcommand{\ackno}{\subsection*{\acknoname}}
\newcommand{\acknoname}{Acknowledgement}
\def\endackno{\par}

\makeatletter
\def\ps@headings{\ps@empty
  \def\@evenhead{\normalfont\scriptsize \hfil
      \leftmark{}{}\hfil\llap{\thepage}}%
  \def\@oddhead{\normalfont\scriptsize \hfil
      \rightmark{}{}\hfil\llap{\thepage}}%
  \let\@mkboth\markboth}
\makeatother
\pagestyle{headings}



\begin{document}
\title[{\sc\lowercase{the electronic journal of combinatorics 3} (1996), \#R29\hfill}]
{\Large\bf{Descendants in heap ordered trees\\
or\\
a triumph of computer algebra}
}

\maketitle
\begin{center}
{\large {\sc Helmut Prodinger}}\\

\medskip

  Institut f\"ur Algebra und Diskrete Mathematik\\
Technical University of Vienna\\
Wiedner Hauptstrasse 8--10\\ A-1040 Vienna, Austria.\\
email: \texttt{{Helmut.Prodinger@@tuwien.ac.at}}\\
www: \texttt{{http://info.tuwien.ac.at/theoinf/proding.htm}}\\
\bigskip

{Submitted: June 8, 1996; Accepted: September 16, 1996.} 

\bigskip

{\it I dedicate this paper to Doron Zeilberger and his program {\sc Ekhad}.}
\end{center}

\begin{abstract} A  heap ordered tree with $n$ nodes (``size $n$'')
is a  planted plane tree
together with a bijection from the nodes to the set $\{1,\dots,n\}$
which is  monotonically increasing
 when going from the root to the leaves.
We consider the number of descendants  of the node $j$ in a (random)
heap ordered tree  of size $n\ge j$. 
 Precise expressions are derived for 
the probability distribution and all (factorial) moments.
\end{abstract} 

\medskip
\noindent
{\bf AMS Subject Classification.} 05A15 (primary) 05C05 (secondary) 

\bigskip

\section{Heap ordered trees}

\pagestyle{myheadings}
\thispagestyle{empty}


A {\sl heap ordered tree\/} with $n$ nodes (``size $n$'')
might be described as a {\sl planted plane tree\/}
together with a bijection from the nodes to the set $\{1,\dots,n\}$
which is {\sl monotonically increasing\/}
 when going from the root to the leaves.
\begin{figure}[h]
\begin{center}
   \epsfig{file=hoty1.eps}
\end{center}
\end{figure}


\begin{figure}[h]
\begin{center}
   \epsfig{file=hoty2.eps}
\end{center}
\caption{All 15 heap ordered trees with 4 nodes}
\end{figure}



In this note, we want to concentrate on the 
\textsf{number of descendants}
 of the node $j$ in a (random)
{\sl heap ordered tree\/}  of size $n\ge j$. 
By convention, we say that  the node $j$ is a descendant of itself.
 For instance, node $1$ always has $n$ descendants and node $n$ has 1 descendant.

The interest in the number of descendants stems from the Ph.\,D. thesis
of Janice Lent \cite{Lent96}; compare also \cite{LenMah95}.
In \cite{MarPro96}, Conrado Mart\'{\i}nez and myself
are currently investigating this
parameter (and several others) for binary search trees and some variants.


 For more information about 
heap ordered trees the reader is referred to \cite{ChenNi94},
\cite{Prodinger96a}, \cite{Prodinger96b}.
\medskip  

We will get explicit formul{\ae} for all factorial moments, as well as for 
the probability generating functions. Finally, even the probabilities
themselves can be computed ex\-pli\-cit\-ly.

Methodologically, we first got the results for the moments by guessing with
{\sc Maple}. Then the proofs of the obtained formul{\ae} are done mechanically
with Zeilberger's algorithm {\sc Ekhad}, compare \cite{GrKnPa94} and \cite{PeWiZe96}.
We assume that the reader is familiar with this very important new feature.

\medskip







The enumeration of the numbers $a_n$ of  heap ordered trees of size $n$
is easy and appears already in \cite{ProUrb83}.
The recursion is
\begin{equation}\label{rec1}   
a_{n+1}=\sum_{m\ge1}\sum_{h_1+\dots+h_m=n}
\binom{n}{h_1,\dots,h_m} \, a_{h_1}\dots a_{h_m}\quad\hbox{for}\ {n\ge1}, \ \ a_1=1\;;
\end{equation} 
hence the exponential generating function $A(z):=\sum_{n\ge0}a_n\frac
{z^n}{n!}$ fulfills the differential equation
$$
A'(z)=\frac1{1-A(z)}\qquad\hbox{with}\quad A(0)=0\;,
$$
with the solution
$$
A(z)=1-\sqrt{1-2z}\;,
$$
so that
$$
a_n=n!\,2^{1-n}\,\ca_n=1\cdot3\cdot5\dots(2n-3)\;,
$$
with a (shifted) {\sl Catalan number}
$\ca_n=\frac1n\binom{2n-2}{n-1}$.

This formula can be extended to the complex plane by means of {\sc Gamma} functions.
Then it turns out that $a_0=-1$ is the {\it natural\/} value. We will work with this
redefined value in the sequel.

\smallskip

We want the probability that $j$ lies in a subtree of size $k$.
 For that  purpose we first note the alternative recursion
\begin{equation*}
a_{n+1}=\sum_{m\ge1}\sum_{h_1+\dots+h_m=n}
m\, \binom{n-1}{h_1-1,h_2,\dots,h_m} \,
 a_{h_1}\dots a_{h_m}\quad\hbox{for}\ {n\ge1}, \ \ a_1=1\;.
\end{equation*} 
It is obtained by forcing the node $j$ to be in the first subtree, thus restricting
the generality, which is restored by introducting a factor $m$.
 From this we get the desired probability as
\begin{equation*}   
\sum_{m\ge1}\sum_{h_2+\dots+h_m=n-k}
m\, \binom{n-1}{k-1}\, \binom{n-k}{h_2,\dots,h_m} \, \frac{a_{k}a_{h_2}\dots a_{h_m}}{a_{n+1}}\;.
\end{equation*}   
 %We want to fix the subtree which contains $j$ 
%and say that it is the first subtree. However, $j$  can be in any of the $m$ subtrees.
%So we introduce a factor $m$.  (Of course, we assume $j\ge2$.)
%But then, we cannot choose $h_1$ numbers out of 
%$\{2,\dots, n+1\}$, since we know already that $j$ is there!   
We can pull out the factor
$\binom{n-1}{k-1}\frac{a_k}{a_{n+1}}$; the exponential generating function of the 
remaining sum  
 is amazingly simple:
\begin{equation*}   
\frac{d}{du}\frac{u}{1-u\, A(z)}\bigg|_{u=1}=\frac{1}{1-2z}~,
\end{equation*}
whence our sought probability that $j$ lies in a subtree of size $k$ turns out to be
\begin{equation*}   
\binom{n-1}{k-1}\,\frac{a_k}{a_{n+1}}\, 2^{n-k}\, (n-k)!~.
\end{equation*}

\section{Results}

Now, let $F_{n,j}(v)$ be the 
probability generating function of the number of descendants, i.e. the coefficient
of $v^m$ in $F_{n,j}(v)$ is the probability that 
node $j$ in a random heap ordered tree with $n $ nodes has $m$ descendants.

We must take care of the fact that in its subtree, `$j$' does not mean `$j$'  any 
further. The numbers in the subtree are to be replaced by $1,2,\dots$, according to their
relative order. Let us compute the probability that $j$ will be $i$   after this procedure,
or, what is the same, that $j$ is the $i$th largest number in its subtree. It is
\begin{equation*}   
\frac{\binom{j-2}{i-1}\binom{n+1-j}{k-i} }{\binom{n-1}{k-1} }~,
\end{equation*} 
since $i-1$ numbers have to be chosen from $\{2,3,\dots,j-1\}$ and
$k-i$ numbers from \linebreak $\{j+1,\dots, n+1\}$.

Hence we get our recursion for the probability generating functions.


\begin{equation}   \label{rec3}     
F_{n+1,j}(v)=\sum_{k=1}^{n}
\binom{n-1}{k-1}\,\frac{a_k}{a_{n+1}}\, 2^{n-k}\, (n-k)!
\sum_{i=1}^k
\frac{\binom{j-2}{i-1}\binom{n+1-j}{k-i} }{\binom{n-1}{k-1} }\, F_{k,i}(v)~.
\end{equation} 
This holds for $n\ge1$ and $j\ge2$;
the initial conditions are $F_{n,1}(v)=v^n$.  
The recursion should be self-explanatory.

\smallskip

After one sunday afternoon with {\sc Maple},  I found this
explicit form of the probability generating functions 
(by some sort of creative guessing).
\begin{theorem}
{\sl The probability generating function of the parameter
{\rm \textsf{number of descendants}}  of node $j$ in a random heap ordered tree
of size $n$ is given by
\begin{equation}\label{pgf}   
F_{n,j}(v)=\sum_{s=0}^{n+1-j}\frac{a_s\,a_j}{a_{s+j}}
\Big((2s-1)n+j-1\Big)\, \poch{(n-j)}{s-1} \,\frac{(v-1)^s}{s!}\;,
\end{equation}
where $\poch xn=x(x-1)\dots(x-n+1)$, which is the notation for the falling
factorials from \cite{GrKnPa94}. 

}\end{theorem}





Before we go to the proof, we get expectation and variance as a corollary.
The expectation is the coefficient of $(v-1)$ in  $F_{n,j}$, i.e.
\begin{equation*}
\frac{n+j-1}{2j-1}\;.
\end{equation*} 
The second factorial moment
 is  twice the coefficient of $(v-1)^2$ in  $F_{n,j}$, i.e.
\begin{equation*}
\frac{a_2\,a_j}{a_{2+j}}\big(3n+j-1\big)\, \poch{(n-j)}{1}
=\frac{(3n+j-1)(n-j)}{(2j+1)(2j-1)}
\;.
\end{equation*}


\begin{theorem}{\sl The expectation and the variance of the parameter
{\rm \textsf{number of descendants}}  of node $j$ in a random heap ordered tree
of size $n$ is given by
\begin{align*}
\text{{\rm \textsf{Expectation}}}&=\frac{n+j-1}{2j-1}\;,\\
\text{{\rm \textsf{Variance}}}&=\frac{2(j-1)(2n-1)(n-j)}{(2j+1)(2j-1)^2}\;.
\end{align*}}

\end{theorem}  

 First a quick check that the announced formula is true for $j=1$:
\begin{align*}
 F_{n,1}(v)&=\sum_{s\ge0}\frac{a_s}{a_{s+1}}
\,(2s-1)n\, \poch{(n-1)}{s-1}\,\frac{(v-1)^s}{s!}\\
&=\sum_{s\ge0} \poch{n}{s}\,\frac{(v-1)^s}{s!}\\
&=\sum_{s\ge0}\binom{n}{s}(v-1)^s=v^n\;.
\end{align*} 
Now we assume $j\ge2$, so that the recursion formula (\ref{rec3}) is
applicable. If we compare coefficients, we have to prove the following:
\begin{multline}\label{identity}
\frac{a_s\,a_j}{a_{s+j}}
\Big((2s-1)(n+1)+j-1\Big)\, \poch{(n+1-j)}{s-1}=\\ =
\sum_{k=1}^{n}
\frac{a_k}{a_{n+1}}\, 2^{n-k}\, (n-k)!
\sum_{i=1}^k
{\binom{j-2}{i-1}\binom{n+1-j}{k-i} }
\,
\frac{a_s\,a_i}{a_{s+i}}
\Big((2s-1)k+i-1\Big)\, \poch{(k-i)}{s-1}\;.
\end{multline}
This looks definitely frightening, but 
in order to go on it is natural to interchange
the summation on the right hand side, viz.
\begin{equation}\label{inner}
\frac{a_s}{a_{n+1}}
\sum_{i=1}^{n}\binom{j-2}{i-1}
\frac{a_i}{a_{s+i}}
\sum_{k=i}^n {a_k}\, 2^{n-k}\, (n-k)!
{\binom{n+1-j}{k-i} }
\Big((2s-1)k+i-1\Big)\, \poch{(k-i)}{s-1}\;.
\end{equation}
In the next section we will prove the {\it combinatorial identity\/}
(\ref{identity}).


\section{Proof of  identity (\ref{identity})}

\begin{lemma}
\begin{gather*}
\sum_{k=i}^n {a_k}\, 2^{n-k}\, (n-k)!
{\binom{n+1-j}{k-i} }
\Big((2s-1)k+i-1\Big)\, \poch{(k-i)}{s-1}\\
=
{\frac {2^{2j-2i-n-1}  \big((n+1)(2s-1)+j-1\big) (2n )!
 (j-i-1 )! (2i+2s-3 )! (n+1-j )! (j+s-2 )!}{ n!(i+s-2 )! (n+2-j-s )! (2j+2s-3 )!}}\;.
\end{gather*}
\end{lemma}


\begin{proof}   
As announced earlier, we use Zeilberger's algorithm. We might note that the actual range
of summation is $i+s-1\le k\le n+1+i-j$. 
This sum, if given to {\sc Ekhad}, produces a first order recursion, and is therefore
expressible in closed form.
\end{proof}
\smallskip

Remark. The sum can be separated naturally into two sums, according to
\begin{equation*}   
\Big((2s-1)k+i-1\Big)=\big((2s-1)k\big)+\big(i-1\big)\;.
\end{equation*}
Both sums are also expressible in closed form. (When I prepared the  first draft
of this paper, I used an older version of {\sc Ekhad} that produced only
a second order recursion, so my strategy was to study the two sums separately.)


%\noindent
%\textsf{First sum.}
%\begin{gather*}
%\sum_k{ a_k{2}^{n-k}(n-k)!{n+1-j\choose k-i}\big((2s-1 )k\big)
%\poch{(k-i)}{s-1}}
%\\
%=
%\frac{{2}^{n}(n-{\tfrac12} )!(2ni+2ns-3n+i+j+2s-3 ) (n+1-j )!}{(n-j-s+2 )!}
%\frac {(2s-1)\Gamma (j-i)\Gamma (i-{\tfrac32}+s)}{4\sqrt {\pi }\,\Gamma (j+s-{\tfrac12})}\;.
%\end{gather*}
%\textsf{Second sum.}
%\begin{gather*}
%\sum_k{ a_k{2}^{n-k}(n-k)!{n+1-j\choose k-i}(i-1)
%\poch{(k-i)}{s-1}}
%\\
%=
%\frac
%{2^n(n-j+1)!(n-{\tfrac12})!}{(n-j-s+2)!}
%{\frac {\Gamma (i-{\tfrac32}+s)\Gamma (j-i)(i-1 )}{2\Gamma 
%(j-{\tfrac32}+s)\sqrt {\pi }}}\;.
%\end{gather*}
%The announced formula is a cleaned up version of the collection of both sums.


With this lemma, the inner sum of (\ref{inner}) 
has been evaluated, and we can turn to the whole sum (\ref{inner}).
Define
\begin{gather*}   
 F(n,i):=\binom{j-2}{i-1} \frac{a_i}{a_{s+i}}\times\\
\times
{\frac {2^{2j-2i-n-1}  \big((n+1)(2s-1)+j-1\big) (2n )!
 (j-i-1 )! (2i+2s-3 )! (n+1-j )! (j+s-2 )!}{ n!(i+s-2 )! (n+2-j-s )! (2j+2s-3 )!}}\;.
\end{gather*}
Zeilberger's algorithm shows that it is {\sl Gosper summable}, or, to be concrete,
if
\begin{equation*}   
G(n,i):=2(i-1)\,F(n,i)
\end{equation*}
then
\begin{equation*}   
 F(n,i)=G(n,i+1)-G(n,i)\;.
\end{equation*}
The range of summation is actually from $i=1$ to $i=j-1$, so our desired sum is
$\frac{a_s}{a_{n+1}}G(n,j)$. 

 Finally, we ask {\sc Maple} to simplify this  minus the predicted result;
\begin{equation*}   
\frac{a_s}{a_{n+1}}\,G(n,j)-\frac{a_s\,a_j}{a_{s+j}}
\Big((2s-1)(n+1)+j-1\Big)\, \poch{(n+1-j)}{s-1}
\end{equation*}
and we get 
 zero, so that  the proof is finished.

\section{Explicit probabilities}

Now we can even get an explicit expression for the probability $p_{n,j;m}$ that node $j$ 
in a random heap ordered tree of size $n$ has $m$ descendants, since this quantity is
given by
\begin{equation*}   
[v^m]F_{n,j}(v)=
\sum_{s=m}^{n+1-j}
\frac{a_s\,a_j}{a_{s+j}}
\Big((2s-1)n+j-1\Big)\, \poch{(n-j)}{s-1}\, \frac{   \binom{s}{m}(-1)^{s-m} 
}{s!}\:.
\end{equation*}
Giving this sum to Zeilberger's algorithm we see that we get a recursion of order one.
Consequently, the sum is of closed form (or rather: can be brought into); the result is
the following. 



\begin{theorem}\label{theo3}
{\sl
The probability $p_{n,j;m}$ that node $j\ge2$ 
in a random heap ordered tree of size $n$ has $m$ descendants is given by
\begin{equation*} 
 p_{n,j;m}=
{\frac {{4}^{n-m+1-j}\, (n-j )! \,(2m-2 )!\, (2j-2 )! \,(n-m-1 )!\, (n-1 )!}
{  (m-1 )! ^{2} \,(2n-2 )! \,(j-1 )!\, (j-2 )! \,(n-j-m+1 )!}}\;.
\end{equation*}
 For $j=1 $ we have
\begin{equation*}   
 p_{n,1;m}=\delta_{n,m}\;.
\end{equation*}
The extra case $j=1 $ can be considered to be a limiting case, since
\begin{equation*}   
\lim_{\eps\to 0}p_{n,1+\eps;m-\eps}=\delta_{n,m}\;.
\end{equation*}}
\end{theorem}
The fact that probabilities sum to 1 leads to the identity
\begin{equation*}   
\sum_{0<m<n}4^{-m}\binom{2m-2}{m-1}\binom{n-1-m}{j-2}=4^{-n-1+j}\binom{2n-2}{n-1}
\binom{n-1}{j-1}    \binom{2j-2}{j-1} ^{-1}\;.
\end{equation*}
This, too, is easy to prove directly by Zeilberger's algorithm.

\section{Combinatorial derivation of the probabilities}

The existence of the relatively simple formula for the probabilities as in Theorem
\ref{theo3} makes us optimistic to find a direct (combinatorial) proof for it.
Here it is:

 First, the formula
\begin{equation*}   
a_{n+1}={a_n}\,(2n-1)~,
\end{equation*} 
can be seen like this.
 From each tree with $n$ nodes, we get $2n-1$ new trees
by inserting the new node $n+1$. We can attach this new node to every node, but the 
relative order in the plane is important, so if a certain node has $i$ outgoing branches,
it gives us $i+1$ possibilities, namely to the left of all, between first and second edge, etc.
Denoting by $d(k)$     the number of outgoing branches of node $k$, we have altogether
\begin{equation*}   
 \sum_{k=1}^n\Big(1+d(k)\Big)=n+\text{number of edges}=2n-1~,
\end{equation*}
as desired. 

\begin{figure}[h]
\begin{center}
   \epsfig{file=hoty3.eps}
\end{center}
\caption{A heap ordered tree with 3 nodes and the 5 trees obtained by inserting a fourth node}
\end{figure}

Now we can use this idea to count the number of descendants of node $j$. We start with a
(fixed) tree of size $j$  and throw in new nodes at random. For instance, there is a probability $\frac{1}{2j-1}$  that the subtree with root $j$ ``catches'' node $j+1$.
It is a little bit like the cookie monster, described in \cite{GreKnu82}: the larger the monster
is already, the likelier will it catch the next thrown cookie. We have collected the appropriate
transition probabilities in a diagram 
({\sc Figure 3})
that resembles Pascal's triangle. Each node has two
entries, the first one being the current total size, and 
the second one being the size of
the subtree with root $j$. We start in state $j\big\vert1$ and can go left or right in each
step. We are interested in the weight of all the paths leading to  
node  $n\big\vert m$, since it
means simply the probability that a random tree of size $n$  has a
subtree rooted at $j$ of size $m$. That we start with a fixed tree does not matter, as can be
easily seen. 
\begin{figure}[t]
\begin{center}
   \epsfig{file=hoty4.eps}
\end{center}
\caption{The beginning of the Pascal like grid}
\end{figure}
Now, regardless as we walk, we will ``collect'' a denominator
\begin{equation*}   
(2j-1)\cdot(2j+1)\dots (2n-3)=\frac{a_n}{a_j}
\end{equation*}  
and a numerator
\begin{equation*}   
(2j-2)\cdot(2j)\dots(2n-2m-2)\, \cdot\, 1\cdot3\dots(2m-3)
=\frac{(n-m-1)!\, 2^{n-m-j+1}}{(j-2)!}
\, a_m~.
\end{equation*}
Having taken care of that factor, we 
only have to {\sl count\/} the number of paths in question.
It is easy to see that we get $\binom{n-j}{m-1} $ paths from state $j\big\vert1$
to state $n\big\vert m$. Altogether we find
\begin{equation*}   
p_{n,j;m}=\frac{(n-m-1)!\, 2^{n-m-j+1}}{(j-2)!}\, \binom{n-j}{m-1}\, \frac{a_m\, a_j}{a_n}~.
\end{equation*}
It is easy to see that this formula is equivalent to the previous one.

\section{Binary trees}

 For the sake of completeness and comparison we briefly sketch the corresponding
considerations for the instance of binary trees. 
They are considerably easier and we only list the results.
\smallskip

The recursion for the increasing binary trees is
\begin{equation*}   
a_{n+1}=\sum_{k=0}^n\binom{n}{k}a_ka_{n-k} 
\end{equation*}
with the obvious solution $a_n=n!$. The probability that $j$  lies in a subtree of
size $k$ is
\begin{equation*}   
2\binom{n-1}{k-1}\frac{k!(n-k)!} {(n+1)!}=\frac{2k}{n(n+1)}\;.
\end{equation*}
The recursion for the probability generating functions is
\begin{equation*}   
F_{n+1,j}(v)=\sum_{k=1}^n\frac{2k}{n(n+1)}\sum_{i=1}^k\frac{\binom{j-2}{i-1}\binom{n+1-j}
{k-i}  }{\binom{n-1}{k-1} }F_{k,i}(v)\;.
\end{equation*}
The solution is
\begin{equation*}  
F_{n,j}(v)=\sum_{s=0}^{n+1-j}\frac{s!\,j!}{(s+j)!}
\Big((s+1)n-(j-1)\Big)\, \poch{(n-j)}{s-1}\, \frac{(v-1)^s}{s!}\;.
\end{equation*}
Expectation and variance are given by
\begin{align*}
\text{{\rm \textsf{Expectation}}}&=\frac{2n-(j-1)}{j+1}\;,\\
\text{{\rm \textsf{Variance}}}&=\frac{2(j-1)(n+1)(n-j)}{(j+2)(j+1)^2}\;.
\end{align*}
The probabilities are given by
\begin{equation*} 
 p_{n,j;m}=j(j-1)m\,\frac{(n-m-1)!(n-j)!}{n!(n-j-m+1)!}\;.
\end{equation*}

\begin{ackno} The insightful comments of an anonymous referee are gratefully
ack\-nowledged.
\end{ackno}

\bibliographystyle{plain} 


%\bibliography{pro_bib}
\begin{thebibliography}{10}

\bibitem{ChenNi94}
W.-C. Chen and W.-C. Ni.
\newblock On the average altitude of heap--ordered trees.
\newblock {\em International Journal of Foundations of Computer Science},
  15:99--109, 1994.

\bibitem{GrKnPa94}
R.~L. Graham, D.~E. Knuth, and O.~Patashnik.
\newblock {\em Concrete Mathematics (Second Edition)}.
\newblock Addison Wesley, 1994.

\bibitem{GreKnu82}
D.~H. Greene and D.~E. Knuth.
\newblock {\em Mathematics for the analysis of algorithms}.
\newblock Birkhauser, Boston, second edition, 1982.

\bibitem{Lent96}
J.~Lent.
\newblock {\em Probabilistic Analysis of some searching and sorting
  algorithms}.
\newblock PhD thesis, George Washington University, 1996.

\bibitem{LenMah95}
J.~Lent and H.~M. Mahmoud.
\newblock Average--case analysis of multiple quickselect: An algorithm for
  finding order statistics.
\newblock {\em Statistics and Probability Letters}, 28:299--310, 1996.

\bibitem{MarPro96}
C.~Mart\'{\i}nez and H.~{P}rodinger.
\newblock On the number of descendants and ascendants in random search trees.
\newblock {\em In preparation}, 1996.

\bibitem{PeWiZe96}
M.~Petkovsek, H.~Wilf, and D.~Zeilberger.
\newblock {\em $A=B$}.
\newblock A.K. Peters, Ltd., 1996.

\bibitem{Prodinger96b}
H.~{P}rodinger.
\newblock The level of nodes in heap ordered trees.
\newblock {\em submitted}, 1996.

\bibitem{Prodinger96a}
H.~Prodinger.
\newblock Depth and path length of heap ordered trees.
\newblock {\em International Journal of Foundations of Computer Science}, 1996
  (to appear).

\bibitem{ProUrb83}
H.~Prodinger and F.J. Urbanek.
\newblock On monotone functions of tree structures.
\newblock {\em Discrete Applied Mathematics}, 5:223--239, 1983.

\end{thebibliography}





\end{document}