\documentstyle[a4ams,righttag,ctagsplt,emlines2,11pt]{amsart}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
\makeatletter
\def\@theoremfont{\it}
\def\slanttheorems{\def\@theoremfont{\sl}}

\def\@begintheorem#1#2[#3]{%
\@theoremfont\trivlist \global\setbox0=\hbox{\bf
 #1}\global\setbox1=\hbox{\bf #2}\item[\hskip \labelsep{\bf #1\ #2.}]}
\let\@opargbegintheorem\relax
\makeatother
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\slanttheorems

\hfuzz=10pt

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

\newtheorem{df}{Definition}[section]
\newtheorem{ex}{Example}
\renewcommand{\theex}{}

\def\U{{\cal{U}}}
\def\E{{\cal{E}}}
\def\T{{\cal{T}}}
\def\P{{\cal{P}}}
\def\a{{\bold{a}}}
\def\p{{\bold{p}}}
\def\mcirc{{\bigcirc}}
%\newcommand{\mcirc}{\unitlength=1mm
%\special{em:linewidth 0.4pt}
%\linethickness{0.4pt}
%\begin{picture}(3.00,3.00)
%\put(1.50,1.50){\circle{2.83}}
%\end{picture}}
%

\RequirePackage{theorem}



\newtheorem{rem}{Remark}
\renewcommand{\therem}{}
\newtheorem{nrem}{Remark}

% Acknowledgements
% Entorno para escribir agradecimientos; similar al entorno abstract
% \begin{ackno} We thank Menganito Smith for ... \end{ackno}

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


\begin{document}
\title[Descendants and Ascendants in binary trees]
{Descendants and Ascendants in binary trees}
\author[A. Panholzer and H.~Prodinger]
{Alois Panholzer and Helmut Prodinger}
\address{  Institut f\"ur Algebra und Diskrete Mathematik\\
Technical University of Vienna\\
Wiedner Hauptstrasse 8--10\\ A-1040 Vienna, Austria.}
\email{e9125354@@fbma.tuwien.ac.at
 ({\sc Alois Panholzer})
}\vskip0pt
\email{Helmut.Prodinger@@tuwien.ac.at\vskip0pt
{\it WWW-address{\rm :\ }}\texttt{http://info.tuwien.ac.at/theoinf/proding.htm}
}



\date{\today}
\begin{abstract} 
There are 3 classical algorithms to visit all the nodes of a binary tree,
\hbox{preorder--,} {inorder--,} and postorder traversal. From this one
gets a natural labelling
of the $n$ internal nodes of a binary tree by the numbers $1,2,\dots,n$, 
indicating the sequence in which the nodes are visited. For given $n$
(size of the tree) and $j$ (a number between 1 and $n$) we consider the statistics
{\it number of ascendants of node $j$\/}
and
 {\it number of descendants of node $j$\/}.

By appropriate trivariate generating functions we are able to find {\sl explicit\/}
formul{\ae} for the expectation and the variance in all instances.
The heavy computations that are necessary are facilitated by {\sc Maple}
and Zeilberger's algorithm.

A similar problem comes from labelling the leaves from left to right by
$0,1,\dots,n$ and considering the statistic 
{\it number of ascendants (=height) of leaf $j$}. For this, Kirschenhofer
\cite{Kirschenhofer83} has computed the average. With our approach, we are
able to get the variance, too.

In a last section, a table with asymptotic equivalents is provided for the
reader's convenience.
\end{abstract} 


\maketitle

  
   \section{Introduction }



Binary trees are not only interesting for combinatorialists, but also for
	 computer scientists, 
since they constitute a basic data structure. As such, naturally, 
one needs {\sl traversal algorithms}, which visit every node of the tree. Basically,
there are 3 traversal algorithms, termed {\sl inorder}, {\sl preorder},
 and {\sl postorder} traversal.
They are all recursive, the left subtree being treated before the right subtree, and
they differ with respect to the visit of the root: first (preorder), 
middle (inorder), and last (postorder). As general references, we cite
\cite{Knuth68, Sedgewick91, SeFl96}.

The performance of such algorithms is directly related to the following
parameters, which are discussed in this paper: The number of ascendants of a node $j$, 
which is the number of nodes between the root and the node $j$, and
the number of descendants of a node $j$, 
which is the number of nodes of the subtree rooted at node $j$. 
(The sum of the numbers of ascendants, over all $j$, is the so called {\sl path length},
a quantity that is traditionally used to measure the complexity of tree algorithms. 
Clearly, it is independent of the labelling.)


The 3 traversal algorithms induce different labellings of the nodes with the natural
numbers $1,2,\dots$; the first node visited gets number 1, and so on. Thus, if we
have a binary tree with $n$   internal nodes, it makes sense to speak about node $j$, 
for $1\le j\le n$.  Compare with figures Fig.~\ref{in-fig},
  Fig.~\ref{pre-fig}, and Fig.~\ref{post-fig}.


  \begin{figure}[t]
      \begin{center}
      %\input{pbinin.pic} 
\unitlength=0.50mm
\special{em:linewidth 0.4pt}
\linethickness{0.4pt}
\begin{picture}(137.00,71.19)
\tiny
\put(5.00,3.00){\framebox(5.00,5.00)[cc]{}}
\put(15.00,3.00){\framebox(5.00,5.00)[cc]{}}
\put(25.00,3.00){\framebox(5.00,5.00)[cc]{}}
\put(35.00,3.00){\framebox(5.00,5.00)[cc]{}}
\put(45.00,3.00){\framebox(5.00,5.00)[cc]{}}
\put(55.00,3.00){\framebox(5.00,5.00)[cc]{}}
\put(65.00,3.00){\framebox(5.00,5.00)[cc]{}}
\put(75.00,3.00){\framebox(5.00,5.00)[cc]{}}
\put(12.67,18.33){\circle{5.73}}
\emline{7.67}{8.00}{1}{11.33}{15.67}{2}
\emline{17.67}{8.00}{3}{14.67}{15.67}{4}
\put(25.00,3.00){\framebox(5.00,5.00)[cc]{}}
\put(35.00,3.00){\framebox(5.00,5.00)[cc]{}}
\put(32.67,18.33){\circle{5.73}}
\emline{27.67}{8.00}{5}{31.33}{15.67}{6}
\emline{37.67}{8.00}{7}{34.67}{15.67}{8}
\put(45.00,3.00){\framebox(5.00,5.00)[cc]{}}
\put(55.00,3.00){\framebox(5.00,5.00)[cc]{}}
\put(65.00,3.00){\framebox(5.00,5.00)[cc]{}}
\put(75.00,3.00){\framebox(5.00,5.00)[cc]{}}
\put(52.67,18.33){\circle{5.73}}
\emline{47.67}{8.00}{9}{51.33}{15.67}{10}
\emline{57.67}{8.00}{11}{54.67}{15.67}{12}
\put(65.00,3.00){\framebox(5.00,5.00)[cc]{}}
\put(75.00,3.00){\framebox(5.00,5.00)[cc]{}}
\put(72.67,18.33){\circle{5.73}}
\emline{67.67}{8.00}{13}{71.33}{15.67}{14}
\emline{77.67}{8.00}{15}{74.67}{15.67}{16}
\put(22.67,33.33){\circle{5.73}}
\put(52.67,18.33){\circle{5.73}}
\put(72.67,18.33){\circle{5.73}}
\put(62.67,33.33){\circle{5.73}}
\put(43.67,52.33){\circle{5.73}}
\put(89.67,68.33){\circle{5.73}}
\put(102.00,16.00){\framebox(5.00,5.00)[cc]{}}
\put(112.00,16.00){\framebox(5.00,5.00)[cc]{}}
\put(122.00,16.00){\framebox(5.00,5.00)[cc]{}}
\put(132.00,16.00){\framebox(5.00,5.00)[cc]{}}
\put(102.00,16.00){\framebox(5.00,5.00)[cc]{}}
\put(112.00,16.00){\framebox(5.00,5.00)[cc]{}}
\put(122.00,16.00){\framebox(5.00,5.00)[cc]{}}
\put(132.00,16.00){\framebox(5.00,5.00)[cc]{}}
\put(109.67,33.33){\circle{5.73}}
\emline{104.67}{21.67}{17}{108.33}{30.67}{18}
\emline{114.67}{21.67}{19}{111.67}{30.67}{20}
\put(122.00,16.00){\framebox(5.00,5.00)[cc]{}}
\put(132.00,16.00){\framebox(5.00,5.00)[cc]{}}
\put(129.67,33.33){\circle{5.73}}
\emline{124.67}{21.67}{21}{128.33}{30.67}{22}
\emline{134.67}{21.67}{23}{131.67}{30.67}{24}
\put(109.67,33.33){\circle{5.73}}
\put(129.67,33.33){\circle{5.73}}
\put(118.67,52.33){\circle{5.73}}
\emline{14.00}{21.67}{25}{20.67}{30.67}{26}
\emline{25.00}{30.67}{27}{32.00}{21.67}{28}
\emline{54.00}{21.67}{29}{60.67}{30.67}{30}
\emline{64.67}{30.67}{31}{72.00}{21.67}{32}
\emline{25.00}{36.33}{33}{41.33}{50.33}{34}
\emline{45.67}{50.33}{35}{61.67}{36.33}{36}
\emline{110.67}{36.33}{37}{117.00}{50.33}{38}
\emline{120.67}{50.33}{39}{129.00}{36.33}{40}
\emline{46.33}{54.00}{41}{87.00}{66.67}{42}
\emline{92.33}{66.67}{43}{116.67}{54.00}{44}
\put(12.67,18.33){\makebox(0,0)[cc]{1}}
\put(23.00,33.33){\makebox(0,0)[cc]{2}}
\put(33.00,18.33){\makebox(0,0)[cc]{3}}
\put(43.67,52.33){\makebox(0,0)[cc]{4}}
\put(52.67,18.33){\makebox(0,0)[cc]{5}}
\put(62.67,33.33){\makebox(0,0)[cc]{6}}
\put(72.67,18.33){\makebox(0,0)[cc]{7}}
\put(90.00,68.33){\makebox(0,0)[cc]{8}}
\put(109.67,33.33){\makebox(0,0)[cc]{9}}
\put(118.67,52.33){\makebox(0,0)[cc]{10}}
\put(129.67,33.33){\makebox(0,0)[cc]{11}}
\put(7.33,5.33){\makebox(0,0)[cc]{0}}
\put(17.67,5.33){\makebox(0,0)[cc]{1}}
\put(27.67,5.33){\makebox(0,0)[cc]{2}}
\put(37.33,5.33){\makebox(0,0)[cc]{3}}
\put(47.33,5.33){\makebox(0,0)[cc]{4}}
\put(57.67,5.33){\makebox(0,0)[cc]{5}}
\put(67.67,5.33){\makebox(0,0)[cc]{6}}
\put(77.33,5.33){\makebox(0,0)[cc]{7}}
\put(104.33,18.33){\makebox(0,0)[cc]{8}}
\put(114.33,18.33){\makebox(0,0)[cc]{9}}
\put(124.67,18.33){\makebox(0,0)[cc]{10}}
\put(134.67,18.33){\makebox(0,0)[cc]{11}}
\normalsize
\end{picture}      
\caption{A binary tree with 11 internal nodes, that are labelled by
	inorder traversal. Node 4 has 7 descendants and 2
       ascendants, leave 6 has the height 5. \label{in-fig}}
      \end{center}
        \end{figure}

   \begin{figure}[ht]
      \begin{center}
      %\input{pbinpre.pic} 
\unitlength=0.50mm
\special{em:linewidth 0.4pt}
\linethickness{0.4pt}
\begin{picture}(139.67,59.19)
\tiny
\put(12.67,6.33){\circle{5.73}}
\put(32.67,6.33){\circle{5.73}}
\put(52.67,6.33){\circle{5.73}}
\put(72.67,6.33){\circle{5.73}}
\put(22.67,21.33){\circle{5.73}}
\put(52.67,6.33){\circle{5.73}}
\put(72.67,6.33){\circle{5.73}}
\put(62.67,21.33){\circle{5.73}}
\put(43.67,40.33){\circle{5.73}}
\put(89.67,56.33){\circle{5.73}}
\put(109.67,21.33){\circle{5.73}}
\put(109.67,21.33){\circle{5.73}}
\put(129.67,21.33){\circle{5.73}}
\put(118.67,40.33){\circle{5.73}}
\emline{14.00}{9.33}{1}{20.67}{18.67}{2}
\emline{25.00}{18.67}{3}{32.00}{9.33}{4}
\emline{54.00}{9.33}{5}{60.67}{18.67}{6}
\emline{64.67}{18.67}{7}{72.00}{9.33}{8}
\emline{25.00}{24.00}{9}{41.33}{38.33}{10}
\emline{45.67}{38.33}{11}{61.67}{24.33}{12}
\emline{110.67}{24.33}{13}{117.00}{38.33}{14}
\emline{120.67}{38.33}{15}{129.00}{24.33}{16}
\emline{46.33}{42.00}{17}{87.00}{54.67}{18}
\emline{92.33}{54.67}{19}{116.67}{42.00}{20}
\put(12.67,6.33){\makebox(0,0)[cc]{4}}
\put(23.00,21.33){\makebox(0,0)[cc]{3}}
\put(33.00,6.33){\makebox(0,0)[cc]{5}}
\put(43.67,40.33){\makebox(0,0)[cc]{2}}
\put(52.67,6.33){\makebox(0,0)[cc]{7}}
\put(62.67,21.33){\makebox(0,0)[cc]{6}}
\put(72.67,6.33){\makebox(0,0)[cc]{8}}
\put(90.00,56.33){\makebox(0,0)[cc]{1}}
\put(109.67,21.33){\makebox(0,0)[cc]{10}}
\put(119.00,40.33){\makebox(0,0)[cc]{9}}
\put(129.67,21.33){\makebox(0,0)[cc]{11}}
\normalsize
\end{picture}      
\caption{A binary tree with 11 internal nodes, that are labelled by
	preorder traversal. Node 3 has 7 descendants and 3
       ascendants.      \label{pre-fig}}
      \end{center}
   \end{figure}
   
   \begin{figure}[ht]
      \begin{center}
%      \input{pbinpos.pic} 
\unitlength=0.50mm
\special{em:linewidth 0.4pt}
\linethickness{0.4pt}
\begin{picture}(139.67,59.19)
\tiny
\put(12.67,6.33){\circle{5.73}}
\put(32.67,6.33){\circle{5.73}}
\put(52.67,6.33){\circle{5.73}}
\put(72.67,6.33){\circle{5.73}}
\put(22.67,21.33){\circle{5.73}}
\put(52.67,6.33){\circle{5.73}}
\put(72.67,6.33){\circle{5.73}}
\put(62.67,21.33){\circle{5.73}}
\put(43.67,40.33){\circle{5.73}}
\put(89.67,56.33){\circle{5.73}}
\put(109.67,21.33){\circle{5.73}}
\put(109.67,21.33){\circle{5.73}}
\put(129.67,21.33){\circle{5.73}}
\put(118.67,40.33){\circle{5.73}}
\emline{14.00}{9.33}{1}{20.67}{18.67}{2}
\emline{25.00}{18.67}{3}{32.00}{9.33}{4}
\emline{54.00}{9.33}{5}{60.67}{18.67}{6}
\emline{64.67}{18.67}{7}{72.00}{9.33}{8}
\emline{25.00}{24.33}{9}{41.33}{38.33}{10}
\emline{45.67}{38.33}{11}{61.67}{24.33}{12}
\emline{110.67}{24.33}{13}{117.00}{38.33}{14}
\emline{120.67}{38.33}{15}{129.00}{24.33}{16}
\emline{46.33}{42.00}{17}{87.00}{54.67}{18}
\emline{92.33}{54.67}{19}{116.67}{42.00}{20}
\put(12.67,6.33){\makebox(0,0)[cc]{1}}
\put(23.00,21.33){\makebox(0,0)[cc]{3}}
\put(33.00,6.33){\makebox(0,0)[cc]{2}}
\put(43.67,40.33){\makebox(0,0)[cc]{7}}
\put(52.67,6.33){\makebox(0,0)[cc]{4}}
\put(62.67,21.33){\makebox(0,0)[cc]{6}}
\put(72.67,6.33){\makebox(0,0)[cc]{5}}
\put(90.00,56.33){\makebox(0,0)[cc]{11}}
\put(109.67,21.33){\makebox(0,0)[cc]{8}}
\put(118.67,40.33){\makebox(0,0)[cc]{10}}
\put(129.67,21.33){\makebox(0,0)[cc]{9}}
\normalsize
\end{picture}
      \caption{A binary tree with 11 internal nodes, that are labelled by
	 post\-order traversal. Node 5 has 1 descendant and 4
       ascendants.\label{post-fig}}
      \end{center}
   \end{figure}

From a probabilistic point of view, there are different models, e.g. the 
binary search trees, see e.g. \cite{MarPro96}. In this paper, we concentrate on 
Catalan statistics, i.e. we assume that each binary tree with $n$ internal nodes is
equally likely. 

   
   We denote by $\cal B$ the family of  binary trees, sometimes called
   extended binary trees, which is defined by the formal identity

  \begin{equation}   
\input{pbingg.pic}\hfill
       \label{fgg1}
\end{equation}    

	


\noindent   where $\mcirc$ is the symbol for an internal node and $\Box$ is the symbol
   for a leaf or external node.
   
   The family of objects from $\cal B$ with exactly $n$ internal nodes is
   denoted by ${\cal B}_{n}$. Further we write $B_{n}$ for the number of
   elements from ${\cal B}_{n}$. Finally we denote with $B(z) = \sum_{n \ge
    0} B_{n} z^{n}$ the ordinary generating function of the $B_{n}$'s.
   


We are considering exact formul{\ae} for the expectation and variance of 
the number of ascendants resp. descendants of
node $j$ in a random binary tree with $n$ internal nodes (`of size $n$'),   
for all 3 traversal algorithms. 

A similar problem, namely the number of ascendants of the leaves (labelled from
left to right by $0,1,\dots,n$) was considered by Kirschenhofer \cite{Kirschenhofer83,
Kirschenhofer83b}; he obtained an explicit formula for the expected value of leaf $j$.
 (Kirschenhofer's definition of `height' differs by 1 from our quantity.)

We rederive this and compute the variance additionally.

Apart from Kirschenhofer's formula, all results seem to be new to the best of
our know\-ledge. The reason that people were not considering such problems earlier
might be related to the fact that we  used the computer algebra system 
{\sc Maple} quite heavily in this paper, and also the powerful algorithm of Zeilberger
\cite{PeWiZe96,GrKnPa94}, tools that were not generally available in the eighties.
This approach might be less elegant than some clever {\sl ad hoc\/} arguments, but
it is definitely more flexible.

Except for two instances, we always get closed formul{\ae}, although sometimes
of a quite complicated nature. Therefore we give asymptotic equivalents in the last section.
In these two cases, the answer is given in terms of a sum, which cannot be evaluated
in closed form, which might be seen for instance from the asymptotic equivalent or also
with Petkov\v{s}ek's algorithm \cite{PeWiZe96}. 

The labelling by inorder traversal is equivalent to the sequence of {\sc min}--turns;
the $j$--th  {\sc min}--turn is defined to be the root of the smallest subtree containing
the leaves labelled $j-1$ and $j$. Some results about {\sc min}--turns in the context
of planted plane (=ordered) trees can be found in \cite{ Kemp82, KiPr82b, KiPr82}. 


We would like to emphasize, however, that the spirit of this paper is on 
{\sl exact enumeration,} not on asymptotics. Questions about limiting distributions,
as treated in \cite{GuPf92} (related to Kirschenhofer's analysis) are not considered here
and referred to further research.

\medskip

Now we sketch the methodology that we use:
   We always translate the symbolic equation (\ref{fgg1}) directly into an
	 algebraic equation
   for the (ordinary) trivariate generating functions 
   \begin{equation}\label{F_def}
      F(z,u,v) = \sum_{j \ge 1 \, (0)} \sum_{n \ge j} \sum_{l \ge 0}
      f_{n,j,l} \, z^{n} u^{j} v^{l} \, ,
   \end{equation}
   where the coefficients $f_{n,j,l}$ are defined as the number of objects
   from ${\cal B}_{n}$, where the node with label $j$ has exactly $l$
   ascendants (or descendants, respectively). 
	In short, 
	 we do not need to set up recurrences, but we use the 
   symbolic method \cite{SeFl96} to
   get the functions $F(z,u,v)$ immediately. In general, when we are interested
	in a certain node $j$, we distinguish 3 cases, namely whether the root is
this node or whether it lies in the left or right subtree. Consequently, the functional
equations of later sections have 3 terms on the right hand side. In the instance of the
next section, where we consider leaves, things are similar but slightly different. 
   
   To obtain the expectation $E_{n,j}$, the second factorial moment 
	$M_{n,j}^{(2    )}$ 
	and the variance $V_{n,j}$ of
   the number of ascendants (or descendants, respectively) of the node with
   label $j$ in a tree with $n$ internal nodes (`of size $n$')  we use the relations
   \begin{align}\begin{split}
       E_{n,j} &= \frac{1}{B_n}[z^{n}u^{j}] \frac{\partial}{\partial v}F
       (z,u,v) \bigg|_{v=1} \, ,  \\ 
       M_{n,j}^{(2)} &= \frac{1}{B_n}[z^{n}u^{j}]  \frac{
        \partial^{2}}{\partial v^{2}}F(z,u,v) \bigg|_{v=1} \, ,
       \\
       V_{n,j} &= M_{n,j}^{(2)} + E_{n,j} - E_{n,j}^{2} \, . 
      \label{rgg1}
   \end{split}\end{align}
   
	Using the symbolic method, the formal equation (\ref{fgg1})  translates
   into an equation of the generating function $B(z)$;
   \begin{equation}
      B(z) = 1 + z B^{2}(z) \, .
   \end{equation}
   From the solution
   \begin{equation}
       B(z) = \frac{1-\sqrt{1-4z}}{2z}
   \end{equation}
   we get  the coefficients of $B(z)$, the so called Catalan
   numbers
   \begin{equation}
      B_{n} = \frac{1}{n+1} {2n \choose n} \, .
      \label{rgg2}
   \end{equation}

\noindent   To shorten the presentation, we will use  the following
   abbreviations throughout the whole paper;
   \begin{gather*}
      X = \sqrt{1-4z}\, , \qquad       Y = \sqrt{1-4zu} \, , \\
       G_{1}(z,u) 
	=  \frac{\partial}{\partial v}F(z,u,v) \bigg|_{v=1} 
	\, , \qquad
       G_{2}(z,u) =  \frac{\partial^{2}}{\partial v^{2}}F(z,u,v)
      \bigg|_{v=1} \, . 
   \end{gather*}
  
   \section{The height of  leaves}
   
   We begin by reviewing and extending the results given by Kirschenhofer, but with
   the method  mentioned above. We will translate the formal identity
   (\ref{fgg1}) into a functional equation for
   the trivariate generating function of the desired parameter. 
   
   In this section, $f_{n,j,l}$ denotes the number of binary trees of size $n$,
	 where the leaf labelled with $j$ has  height $l$.
   Then we get for the trivariate generating function $F(z,u,v)$ of the
   $f_{n,j,l}$, defined as in (\ref{F_def})
	 the functional equation     
   \begin{equation}
       F(z,u,v) = v + zv F(z,u,v) B(z) + z u v F(z,u,v) B(z u) \, .
    \end{equation}
   This leads immediately to the solution
   \begin{equation}
      F(z,u,v) = \frac{v}{1-zvB(z)-zuvB(zu)} \, .
      \label{rgg4}
   \end{equation}
      By differentiating (\ref{rgg4}) we get with the  use of the abbreviations
   from  above
   \begin{equation} 
       G_{1}(z,u) = \frac{4}{(\sqrt{1-4z}+\sqrt{1-4zu}\,)^{2}} = \frac{4}{(X+Y
        )^{2}} \, .
   \end{equation}
      To find the coefficients in the expansion of $\frac{1}{(X+Y)^{2}}$,
   we can expand this expression about $u=1$. This leads to
   \begin{displaymath}
      \frac{1}{(X+Y)^{2}} = \sum_{k \ge 0} \frac{1}{4 (k+2)} {2 (k+1) \choose
       k+1} \frac{z^{k}}{(1-4z)^{k +1}} (u-1)^{k} \; .
   \end{displaymath}
      The coefficients are then given by the following sum
   \begin{equation}
      [z^{n}u^{j}] \frac{1}{(X+Y)^{2}} = \sum_{k=j}^{n} \frac{1}{4(k+2)} {2(k
       +1) \choose k+1} {n \choose k} {k \choose j} (-1)^{k-j} 4^{n-k} \, .
   \end{equation}
      We find a closed form of this sum by using Zeilberger's algorithm
   \cite{PeWiZe96, GrKnPa94}:
   We write 
   \begin{displaymath}
      F(n,j,k) = \frac{1}{4(k+2)} {2(k+1) \choose k+1} {n \choose k} {k
       \choose j} (-1)^{k-j} 4^{n-k} \; ,
   \end{displaymath}
   then Zeilberger's algorithm finds the relation
   \begin{equation*}
       -2(n+1)(2n-2j+3) F(n,j,k) + (n+3)(n-j+1) F(n+1,j,k) 
       = G(n,j,k+1)-G(n,j,k)
\end{equation*}
with
 \begin{equation}   
G(n,j,k) = R(n,j,k) F(n,j,k) \quad \text{and} \quad 
	R(n,j,k) = -      \frac{4(n+1)(k+2)(k-j)}{n+1-k} \; .
\end{equation}
       To find an expression for the  coefficients
   \begin{equation}
      [z^{n}u^{j}] \frac{1}{(X+Y)^{2}} = f(n,j) = \sum_{k \in {\Bbb{Z}}} F(n,j,k) \,
      ,
   \end{equation}  
   we sum the above equation over all $k \in {\Bbb{Z}}$.
   
   The right side of the equation telescopes and we get the linear recurrence
(for $n\ge j$)    
\begin{equation}
       (n+3)(n-j+1) f(n+1,j) = 2 (n+1) (2n-2j+3) f(n,j) 
\end{equation}
and the initial condition
\begin{equation*}   
f(j,j) = \frac{1}{4(j+2)} {2(j+1) \choose j+1} \, .
\end{equation*}
    This gives the desired result (for $0\le j \le n$)
   \begin{equation}
      [z^{n}u^{j}] \frac{1}{(X+Y)^{2}} = f(n,j) = \frac{(2j+1)(2n-2j+1)}{2(n
       +1)(n+2)} {2j \choose j} {2(n-j) \choose n-j} \, .
      \label{rgg3}
   \end{equation}
      Combining the equations (\ref{rgg1}), (\ref{rgg2}) and (\ref{rgg3}) 
we find again Kirschenhofer's result \cite{Kirschenhofer83}.
   
   \begin{theorem}
   The expectation $E_{n,j}$ of the height of the leaf with label $j$ in a
   binary tree of size $n$, is given by
      \begin{equation}
         E_{n,j} = \frac{2(2j+1)(2n-2j+1)}{n+2}\frac{{2j \choose j} {2n-2j
                \choose n-j}}{{2n \choose n}} \qquad \text{{\rm for} } \ 0 \le j
              \le n \, .\qed
      \end{equation}
   \end{theorem}
     Differentiating equation (\ref{rgg4}) twice and evaluating at $v=1$
   leads to 
   \begin{equation}
       G_{2}(z,u) = \frac{16}{(X+Y)^{3}} - \frac{8}{(X+Y)^{2}} \; .
   \end{equation}
      For this, we also need the coefficients of $\frac{1}{(X+Y)^{3}}$. To get them
   we make the following rearrangements;
   \begin{align}\begin{split}
      &  \frac{1}{(X+Y)^{3}} = \frac{(X-Y)^{3}}{(X^{2}-Y^{2})^{3}} =
      \frac{X^{3}-3X^{2}Y+3XY^{2}-Y^{3}}{-64z^{3}(1-u)^{3}}  \\
      & = \frac{\sqrt{1-4z}}{(1-u)^{3}} \left(-\frac{1}{16z^{3}}+
      \frac{1}{16z^{2}}+ \frac{3u}{16z^{2}}\right) + \frac{\sqrt{1-4zu}}{(1-u
       )^{3}}\left( \frac{1}{16z^{3}}-\frac{3}{16z^{2}}-\frac{u}{16z^{2}}
      \right) \; .
   \end{split}
	\end{align}
      From this we see that
   \begin{equation}
      [z^{n}u^{j}] \frac{1}{(X+Y)^{3}} = [z^{n}u^{j}] \frac{\sqrt{1-4z}}{(1-u
       )^{3}}\left(-\frac{1}{16z^{3}}+\frac{1}{16z^{2}}+\frac{3u}{16z^{2}}
      \right) \qquad \text{for} \ 0 \le j \le n \, ,
   \end{equation}
   which finally leads to
   \begin{equation}
      [z^{n}u^{j}] \frac{1}{(X+Y)^{3}} = \frac{3}{4}\frac{(2n+1)(j+1)(n-j+1
      )}{(n+1)(n+2)(n+3)} {2n \choose n} \quad \text{for} \ 0 \le j
     \le n \, .
     \label{rgg5}
   \end{equation}
   
   With the relations (\ref{rgg1}), (\ref{rgg2}), (\ref{rgg3}) and (\ref{rgg5}) we get
   \begin{lemma}
   The second factorial moment $M_{n,j}^{(2)}$ of the height of the leaf with
   label $j$ in a binary tree of size $n$ is given for all\/
$0\le j\le n$ by
      \begin{equation}
         M_{n,j}^{(2)} = \frac{12(2n+1)(j+1)(n-j+1)}{(n+2)(n+3)}-\frac{4(2j+1)
                     (2n-2j+1)}{n+2}\frac{{2j \choose j} {2n-2j \choose
                      n-j}}{{2n \choose n}} \; .\qed
      \end{equation}
   \end{lemma}
   
   Observing (\ref{rgg1}) we get as a consequence
   \begin{theorem}
   The variance $V_{n,j}$ of the height of the leaf with
   label $j$ in a binary tree of size $n$, is given by
      \begin{align}\begin{split}
          V_{n,j} &= \frac{12(j+1)(2n+1)(n-j+1)}{(n+2)(n+3)}-\frac{2(2j+1)
                     (2n-2j+1)}{n+2}\frac{{2j \choose j} {2n-2j \choose
                      n-j}}{{2n \choose n}}  \\
           & - \frac{4(2j+1)^{2} (2n-2j+1)^{2}}{(n+2)^{2}}\frac{{2j
                      \choose j}^{2} {2n-2j \choose n-j}^{2}}{{2n \choose
                      n}^{2}} \qquad \text{{\rm for}} \ 0 \le
                    j \le n \, .\qed
      \end{split}\end{align}
   \end{theorem}





   \section{The number of descendants of nodes labelled by inorder traversal}
   
   Now we label the nodes of the tree 
by $1,2,\dots,n$ as we  visit them  by    inorder traversal.
   Then $f_{n,j,l}$ denotes the number of binary trees of size $n$,
	 where the node with label $j$ has exactly $l$ descendants. The
   trivariate generating function $F(z,u,v)$ (compare (\ref{F_def}))
   fulfills the algebraic equation
      \begin{equation}
       F(z,u,v) = zuv B(zuv) B(zv) + z F(z,u,v)  B(z) + zuB(z u)  F(z,u,v) \,,
          \end{equation}
   which can be found by translating the formal equation (\ref{fgg1}) 
	appropriately.
   
   Therefore we have the following explicit formula
      \begin{equation}
      F(z,u,v) = \frac{zuvB(zv)B(zuv)}{1-zB(z)-zuB(zu)} \; .
      \label{rgg6}
   \end{equation}
   From this we get by differentiating
   \begin{equation}
       G_{1}(z,u) = \frac{1}{4z} \left( \frac{1}{XY} - \frac{1}{X} -
       \frac{1}{Y} + 1 \right) \; .
   \end{equation}
      The expansion of the coefficients  is easy and we get
   \begin{equation}
      [z^{n}u^{j}] G_{1}(z,u) = [z^{n}u^{j}]  \frac{1}{4zXY} =
      \frac{1}{4} {2j \choose j} {2(n+1-j) \choose n+1-j} \qquad 
	\text{for} \ 1 \le j \le n \, .
      \label{rgg7}
   \end{equation}   
   
   This gives with the relations (\ref{rgg1}), (\ref{rgg2}) and (\ref{rgg7})
   \begin{theorem} 
      The expectation $E_{n,j}$ of the number of descendants of the node with
      label $j$, where the nodes are labelled by
	inorder traversal, in a binary tree of size $n$,  is given by
      \begin{equation}
          E_{n,j} = \frac{n+1}{4}\frac{{2j \choose j} {2(n+1-j) \choose n
                      +1-j}}{{2n \choose n}} \qquad \text{{\rm for}} \ 1 \le
                    j \le n \, .\qed
      \end{equation}
   \end{theorem}
   
   Further we get from (\ref{rgg6}) the equation
   \begin{align}\begin{split}
       G_{2}(z,u) &= \frac{(1-X)(-4X^{2}Y^{2}+3X^{2}Y^{3}+X^{2}-XY^{3}
       +2XY^{2}-XY+Y^{2}-Y^{3})}{8zX^{3}Y^{3}}  \\
      & = \frac{1}{8z}\left(-3+\frac{4}{X}-\frac{1}{X^{3}}\right)+
      \frac{1}{8zY}\left(4-\frac{6}{X}+\frac{1}{X^{2}}+\frac{1}{X^{3}}\right)
      +\frac{1}{8zY^{2}}\left(\frac{1}{X}-\frac{1}{X^{2}}\right)  \\
       & + \frac{1}{8zY^{3}}\left(-1+\frac{1}{X}\right) \, .
      \label{rgg8}
\end{split}
   \end{align}   
   With the relations
   \begin{equation}
      [z^{n}u^{j}]\frac{1}{X^{p}Y^{q}} = [z^{j}u^j]\frac{1}{Y^{q}} \,
      [z^{n-j}] \frac{1}{X^{p}} = [z^{j}]\frac{1}{X^{q}} \, [z^{n-j}]
      \frac{1}{X^{p}}\qquad \text{for} \ p,q \in {\Bbb{N}}
   \end{equation}
   and
   \begin{equation}
      [z^{n}] \frac{1}{X} = {2n \choose n} \; , \quad [z^{n}] \frac{1}{X^{2}} =
      4^{n} \; , \quad [z^{n}] \frac{1}{X^{3}} = (2n+1) {2n \choose n} 
   \end{equation}   
   the expansion of (\ref{rgg8}) is also easy to do (preferably with the 
	use of a
   computer algebra system like {\sc Maple}) and we get for $1 \le j \le n$ 
   \begin{equation}
       [z^{n}u^{j}]G_{2}(z,u) = \frac{n-1}{4}{2j \choose j} {2n+2-2j
       \choose n+1-j} - \frac{1}{2} 4^{n} + \frac{1}{8} 4^{j} {2n+2-2j
       \choose n+1-j} + \frac{1}{8} 4^{n+1-j} {2j \choose j} \; .
   \end{equation}   
  
   This leads to 
   \begin{lemma}
      The second factorial moment $M_{n,j}^{(2)}$ of the number of
      descendants of the node with label $j$, where the nodes are labelled by	
	 inorder traversal, in a binary tree of size $n$, 	 is given by
      \begin{align}\begin{split}
          M_{n,j}^{(2)} &= \frac{(n-1)(n+1)}{4}\frac{{2j \choose j} {2n
           +2-2j \choose n+1-j}}{{2n \choose n}} 
 \\
           & + \frac{n+1}{{2n \choose n}} \left[- \frac{1}{2} 4^{n} +
          \frac{1}{8} 4^{j} {2n+2-2j \choose n+1-j} + \frac{1}{8} 4^{n +1-j}
          {2j \choose j} \right] \quad \text{{\rm for}} \ 1 \le j \le n \, .\qed
        \end{split}\end{align}
   \end{lemma}
   
   So we get with (\ref{rgg1})
   \begin{theorem}
       The variance $V_{n,j}$ of the number of
      descendants of the node with label $j$, where the nodes are labelled by
	inorder traversal, in a binary tree of size $n$,	is given by
      \begin{align}\begin{split}
          V_{n,j} &= \frac{n(n+1)}{4}\frac{{2j \choose j} {2n+2-2j
              \choose n+1-j}}{{2n \choose n}} - \frac{(n+1)^{2}}{16}\frac{{2j
              \choose j}^{2}{2n+2-2j \choose n+1-j}^{2}}{{2n \choose n}^{2}} 
           \\
         &   + \frac{n+1}{{2n \choose n}} {\left[-
                \frac{1}{2} 4^{n} + \frac{1}{8} 4^{j} {2n+2-2j \choose n+1-j}
                + \frac{1}{8} 4^{n +1-j} {2j \choose j} \right]
                } \qquad \text{{\rm for}} \ 1 \le j \le n \, .\qed
      \end{split}\end{align}
   \end{theorem}
   
   \section{The number of ascendants of nodes labelled by
	inorder traversal}
   
   Here we denote by $f_{n,j,l}$ the number of binary trees of size $n$,
	 where the node labelled $j$ by inorder traversal
	has exactly $l$ ascendants.
   
   For the usual trivariate generating function $F(z,u,v)$ 
   we get from (\ref{fgg1}) the functional equation
   \begin{equation}
       F(z,u,v) = zuv B(zu) B(z) + zv F(z,u,v)  B(z) + zuvB(z u)  F(z,u,v)
       \, , 
   \end{equation}
   and thus
   \begin{equation}
      F(z,u,v) = \frac{zuvB(z)B(zu)}{1-zvB(z)-zuvB(zu)} \, .
      \label{rgg9}
   \end{equation}
       Hence it follows by differentiation from (\ref{rgg9}) that
   \begin{equation}
       G_{1}(z,u) = \frac{(1-X)(1-Y)}{z(X+Y)^{2}} = \frac{1}{z(X+Y)^{2}} -
       \frac{1}{z(X+Y)} + \frac{XY}{z(X+Y)^{2}} \; .
       \label{rgg10}
   \end{equation}
      Therefore we need the coefficients of
   \begin{align}\begin{split}
       [z^{n}u^{j}]\frac{1}{X+Y} &= [z^{n}u^{j}] \frac{X-Y}{X^{2}-Y^{2}} =
      [z^{n}u^{j}] \frac{\sqrt{1-4z}-\sqrt{1-4zu}}{-4z(1-u)}  \\
      &  = [z^{n}u^{j}] \left(- \frac{\sqrt{1-4z}}{4z(1-u)}\right) =
      \frac{1}{2(n+1)}{2n \choose n} \qquad \text{for} \ 1 \le j \le n\,,
      \label{rgg11}
   \end{split}\end{align}   
   and of
   \begin{align}\begin{split}
       [z^{n}u^{j}]\frac{XY}{(X+Y)^{2}} &= 2 [z^{n-1}u^{j}] \frac{1}{(X+Y
       )^{2}} + 2 [z^{n-1}u^{j-1}]\frac{1}{(X+Y)^{2}}-[z^{n}u^{j}]\frac{1}{(X
       +Y)^{2}}
       \\
      &  = - \frac{(n-1)(n-8j)+8j(j-1)}{2n(n+1)(n+2)} {2j \choose
       j} {2n-2j \choose n-j} \quad \text{for} \ 1 \le j \le n\,.
      \label{rgg12}
   \end{split}\end{align}
      Combining the equations (\ref{rgg3}), (\ref{rgg11}) and (\ref{rgg12}) we
   get for $1 \le j \le n$

\begin{equation*}   
[z^{n}u^{j}] G_{1}(z,u) = \frac{4jn+n-4j^{2}+4j+1}{2(n+1)(n+2)}{2j
       \choose j} {2n+2-2j \choose n+1-j} - \frac{2n+1}{(n+1)(n+2)} { 2n
       \choose n}  \, .
\end{equation*}
   
   This leads to

   \begin{theorem}
       The expectation $E_{n,j}$ of the number of
      ascendants of the node with label $j$, where the nodes are labelled by
	inorder traversal, in a binary tree of size $n$,		is given by
      \begin{equation}
         E_{n,j} = \frac{4jn+n-4j^{2}+4j+1}{2(n+2)} \frac{{2j \choose j} {2n
           +2-2j \choose n+1-j}}{{2n \choose n}} - \frac{2n+1}{n+2} \qquad
           \text{{\rm for}} \ 1 \le j \le n \, .\qed
      \end{equation}
   \end{theorem}
   
   For $G_{2}(z,u)$ we get from (\ref{rgg9}) by differentiating twice and
   evaluating at $v=1$
   \begin{align}\begin{split}
      G_{2}(z,u) &= -2 \frac{(1-X)(1-Y)(X+Y-2)}{z(X+Y)^{3}}  \\
       &  = \frac{4XY}{z(X+Y)^{3}}+\frac{4}{z(X+Y)^{3}}-\frac{6}{z(X+Y
        )^{2}}-\frac{2XY}{z(X+Y )^{2}}+\frac{2}{z(X+Y)} \; .
     \label{rgg13}  
   \end{split}\end{align}
      To expand this expression we  need additionally
   \begin{align}\begin{split}
      &  [z^{n}u^{j}] \frac{XY}{(X+Y)^{3}}  \\
      & = \frac{1}{2} [z^{n}u^{j}] \frac{1}{X+Y} - [z^{n}u^{j}]\frac{1}{(X
       +Y)^{3}} + 2[z^{n-1}u^{j}] \frac{1}{(X+Y)^{3}} + 2 [z^{n-1}u^{j-1}]
      \frac{1}{(X+Y)^{3}}  \\
       & = - \frac{2n^{2}-15jn-5n+15j^{2}-3}{4(n+1)(n+2)(n+3)} {2n
       \choose n} \qquad \text{for} \ 1 \le j \le n \, .
     \label{rgg14} 
   \end{split}\end{align}   
      With the relations (\ref{rgg13}), (\ref{rgg5}), (\ref{rgg11}), 
   (\ref{rgg12}) and (\ref{rgg14}) we get (for $1\le j\le  n$) 
   \begin{multline}
       [z^{n}u^{j}]G_{2}(z,u) = \frac{2(2n+1)(6jn+5n-6j^{2}+6j+9)}{(n+1)(n
       +2)(n+3)} { 2n \choose n}  \\
       - \frac{12jn^{2}+5n^{2}-12j^{2}n+32jn +14n-20j^{2}+20j+9}{(n+1)
      (n+2)(n+3)} {2j \choose j} {2n+2-2j \choose n +1-j}        \, .
   \end{multline}
      From that we obtain
   \begin{lemma}
   The second factorial moment $M_{n,j}^{(2)}$ of the number of ascendants
   of the node with label $j$,
	where the nodes are labelled by inorder traversal, 
	 in a binary tree of size $n$, is	
	for all\/ $1\le j \le n$ given by
   \begin{align}\begin{split}
 M_{n,j}^{(2)} &= \frac{2(2n+1)(6jn+5n-6j^{2}+6j+9)}{(n
       +2)(n+3)} \\
      & - \frac{12jn^{2}+5n^{2}-12j^{2}n+32jn+14n-20j^{2}+20j
       +9}{ (n +2)(n+3)} \frac{{2j \choose j} {2n+2-2j \choose n
                     +1-j}}{{2n \choose n}} \, .  \qed
   \end{split}\end{align}
   \end{lemma}
 Thus we have
   \begin{theorem}
   The variance $V_{n,j}$ 
of the number of ascendants
   of the node with label $j$,
	where the nodes are labelled by inorder traversal,
	 in a binary tree of size $n$, is	
	for all\/ $1\le j \le n$ given by
   \begin{align}\begin{split}
       V_{n,j} &= \frac{(2n+1)(12jn^{2}+7n^{2}-12j^{2}n+36jn+26n-24j^{2}+24j+27
               )}{(n+2)^{2}(n+3)}  \\
           & -\textstyle{\frac{4jn^{3}+5n^{3}-4j^{2}n^{2}+16jn^{2}+24n^{2}-12j^{2}n+44jn
              +43n -32j^{2}+32j+24}{\displaystyle{2(n+2)^{2}(n+3)}}}
	\displaystyle{          \frac{{2j \choose j}{2n+2-2j \choose n+1-j}}{{2n \choose
                n}}  }\\
    & - {\frac{(4jn+n-4j^{2}+4j+1)^{2}}{4(n+2)^{2}}} \frac{{2j \choose
       j}^{2}{2n+2-2j \choose n+1-j}^{2}}{{2n \choose n}^{2}}    \; .\qed
      \end{split}\end{align}
   \end{theorem}
   
   \section{The number of descendants of nodes labelled by preorder traversal}
   
   The following results are obtained by the same methods that we used in
   the instance of inorder traversal. So we can omit the details and only sketch
   the main steps  to get  analogous results in the case of
   preorder  traversal (and postorder traversal, in later sections).
   
   The trivariate  generating function $F(z,u,v)$ of the numbers
   $f_{n,j,l}$,  counting the trees of size $n$, where the node with label $j$
	(labelled by preorder traversal) has
   exactly $l$ descendants, is given by the functional equation
   \begin{equation}
      F(z,u,v) = zuv B^{2}(zv) + zu F(z,u,v)  B(z) + zu B(zu)  F(z,u,v) \, ,
   \end{equation}
   and explicitly by
   \begin{equation}
      F(z,u,v) = \frac{zuvB^{2}(zv)}{1-zuB(z)-zuB(zu)} \; .
      \label{rgg15}
   \end{equation}
      From (\ref{rgg15}) we get
   \begin{equation}
      G_{1}(z,u) = \frac{2(1-Y)}{X(1+X)(X+Y)} = \frac{2}{X(X+Y)} + \frac{2}{1
       +X} - \frac{2}{X} \; .
   \end{equation}
   
   For $1 \le j \le n$ only the first summand contributes a nonzero coefficient.
	 At first we get the sum
   \begin{equation}\label{rgg16a}
      [z^{n}u^{j}]\frac{1}{X(X+Y)} = \sum_{k=j}^{n} [z^{k}u^{j}] \frac{1}{X
       +Y} [z^{n-k}] \frac{1}{X} = \sum_{k=j}^{n} \frac{1}{2(k+1)} {2k
      \choose k} {2n-2k \choose n-k} \; ,
   \end{equation}
   which we evaluate as before with Zeilberger's algorithm and obtain   
   \begin{equation}
      [z^{n}u^{j}]\frac{1}{X(X+Y)} =
	 \frac{2n+1-2j}{2(n+1)} {2j \choose j} {2n-2j \choose
       n-j} \, .
      \label{rgg16}
   \end{equation}
     This gives us 
   \begin{equation}
      [z^{n}u^{j}] G_{1}(z,u) = \frac{2n+1-2j}{n+1} {2j \choose j} {2n-2j
       \choose n-j} \, ,
   \end{equation}
   and furthermore
   \begin{theorem}
      The expectation $E_{n,j}$ of the number of descendants of the node with
      label $j$, where the nodes are labelled by
	preorder traversal, in a binary tree of size $n$,  is given by
      \begin{equation}
          E_{n,j} = (2n+1-2j)\frac{{2j \choose j}{2n-2j \choose n-j}}{{2n
            \choose n}} \; .\qed
      \end{equation}
   \end{theorem}
   
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


For $G_{2}(z,u)$ we get the following expression:
   \begin{align}\begin{split}
      G_{2}(z,u) &= \frac{(1-Y)(1-X)(1+3X)}{X^{3}(1+X)(X+Y)}  \\
      &  = \frac{1}{X^{3} (X+Y)}+\frac{2}{X^{2}(X+Y)}-\frac{3}{X(X+Y)}+
      \frac{4}{X}- \frac{1}{X^{2}}-\frac{1}{X^{3}}-\frac{4}{X+1} \, .
	\end{split}
   \end{align}
   
   To read off  the coefficients in  this expression, we still need
   to expand $\frac{1}{X^{2}(X+Y)}$ and $\frac{1}{X^{3}(X+Y)}$.
   From the equation
   \begin{equation*}
      \frac{1}{X^{2}(X+Y)} = \frac{1}{X^{2}Y}+\frac{1}{4z(1-u)Y}-\frac{1}{4z
       (1-u)X}
   \end{equation*}
   we get the coefficients from $\frac{1}{X^{2}(X+Y)}$:
   \begin{equation}
      [z^{n}u^{j}] \frac{1}{X^{2}(X+Y)} = 4^{n-j} {2j \choose j} -
      \frac{1}{4} { 2(n+1) \choose n+1} \, .
   \end{equation}
      For the coefficients from $\frac{1}{X^{3}(X+Y)}$ we first get the
   following sum
   \begin{align*}
       [z^{n}u^{j}] \frac{1}{X^{3}(X+Y)} &= \sum_{k=j}^{n} \frac{1}{2(k+1
       )}{2k \choose k} (2(n-k)+1){2(n-k) \choose n-k} \\
      &  = (2n+3)\sum_{k=j}^{n}
      \frac{1}{2(k+1)}{2k \choose k} {2(n-k) \choose n-k} - \sum_{k=j}^{n}
      {2k \choose k} {2(n-k) \choose n-k} \; ,
   \end{align*}
   which can be simplified  using  (\ref{rgg16a}) and (\ref{rgg16}),
yielding
   \begin{equation}
      [z^{n}u^{j}] \frac{1}{X^{3}(X+Y)} = \frac{(2n+3)(2n+1-2j)}{2(n+1)} {2j
       \choose j} {2(n-j) \choose n-j} - \sum_{k=j}^{n} {2k \choose k} {2(n-k
       ) \choose n-k} \; .
   \end{equation}
   It can be shown that the remaining sum cannot be
   brought into a closed form; see the general comment from the introduction.
   
   Combining these results we get
   \begin{align}\begin{split}
       [z^{n}u^{j}] G_{2}(z,u) & =  \frac{n(2n-2j+1)}{n+1} {2j \choose j}
      {2n-2j \choose n-j} + 2 \cdot 4^{n-j} {2j \choose j} - \frac{1}{2} {2n+2
       \choose n +1}  \\
      &  - \sum_{k=j}^{n} {2k \choose k} {2n-2k \choose n-k} 
\end{split}  \end{align}
   and thus
   \begin{lemma}
      The second factorial moment $M_{n,j}^{(2)}$
	 of the number of descendants of the node with
      label $j$, where the nodes are labelled by
	preorder traversal, in a binary tree of size $n$  is given by
      \begin{align}\begin{split}
          M_{n,j}^{(2)} & =  n(2n-2j+1) \frac{ {2j \choose j} {2n-2j \choose
            n-j}}{ {2n \choose n}} + 2 (n+1) \frac{4^{n-j} {2j \choose
            j}}{{2n \choose n}} -2n -1 \\
          &  - \frac{n+1}{{2n \choose n}} \sum_{k
           =j}^{n} {2k \choose k} {2n-2k \choose n-k} \qquad \text{{\rm for}}
          \ {1 \le j \le n} \, .\qed
      \end{split}\end{align}
   \end{lemma}   
   
   This leads immediately to
   \begin{theorem}
      The variance $V_{n,j}$
of the number of descendants of the node with
      label $j$, where the nodes are labelled by
	preorder traversal, in a binary tree of size $n$,  is given by
      \begin{align}\begin{split}
           V_{n,j} & =  (n+1)(2n-2j+1) \frac{ {2j \choose j} {2n-2j \choose
            n-j}}{ {2n \choose n}} + 2 (n+1) \frac{4^{n-j} {2j \choose
            j}}{{2n \choose n}} -2n -1  \\
          &  -(2n+1-2j)^{2}\frac{{2j \choose j}^{2}{2n-2j \choose
            n-j}^{2}}{{2n \choose n}^{2}} \nonumber  - \frac{n
           +1}{{2n \choose n}} \sum_{k =j}^{n} {2k \choose k} {2n-2k \choose
           n-k} \qquad \text{{\rm for}}
          \ {1 \le j \le n}  \, .\qed
     \end{split} \end{align}
   \end{theorem}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



We remark that the full sum can be easily evaluated;
\begin{equation}   
\sum_{k=0}^{n} {2k \choose k} {2n-2k \choose n-k}=4^n\;.
\end{equation}
This relation might be useful if $j$ is rather small; the sum can always be rewritten
so that it has not more than roughly $n/2$ terms.











   \section{The number of ascendants of nodes labelled by preorder traversal}
   
   Now $f_{n,j,l}$ counts the number of binary trees of size $n$,
	 where  the node with label $j$ has exactly $l$ ascendants.
   
   For the usual trivariate generating function we get the relation
   \begin{equation}
      F(z,u,v) = zuv B^{2}(z) + zuvF(z,u,v)  B(z) + zuvB(zu)  F(z,u,v) \; ,
   \end{equation}
   from which we obtain
   \begin{equation}
      F(z,u,v) = \frac{zuvB^{2}(z)}{1-zuvB(z)-zuvB(zu)} \, .
      \label{rgg18}
   \end{equation}   
    To expand the quantity
   \begin{equation}
       G_{1}(z,u) = \frac{4(1-Y)}{(1+Y)(X+Y)^{2}} = \frac{2}{zu(X+Y)^{2}}-
      \frac{4}{(X+Y)^{2}}-\frac{2Y}{zu(X+Y)^{2}} 
      \label{rgg19}
   \end{equation}
   we still need the following expansion;
   \begin{align}\begin{split}
        [z^{n}u^{j}] \frac{Y}{(X+Y)^{2}} &= [z^{n}u^{j}]\frac{XY}{(X+Y)^{3}}
      +[z^{n}u^{j}]\frac{1}{(X+Y)^{3}}-4[z^{n-1}u^{j-1}]\frac{1}{(X+Y
       )^{3}}  \\
       & = \frac{2n+1-3j}{2(n+1)(n+2)}{2n \choose n} \, .
      \label{rgg20}
   \end{split}\end{align}
   Hence we have
\begin{equation*}   
      [z^{n}u^{j}] G_{1}(z,u)  =  \frac{(jn+2n-j)(2n-2j+1)}{(n+1)(n+2)(n+3
       )}{2 j+2 \choose j+1} {2n-2j \choose n-j}  
       - \frac{2n-3j}{(n+2)(n+3)}{2n+2\choose n+1} \;,
\end{equation*}
   which proves 
   \begin{theorem}
      The expectation $E_{n,j}$ of the number of ascendants of the node with
      label $j$, where the nodes are labelled by
      preorder traversal, in a binary tree of size $n$, is given\/ 
	for all $1\le j \le n$ by
      \begin{equation}
         E_{n,j} = \frac{(jn+2n-j)(2n-2j+1)}{(n+2)(n+3)}\frac{{2
               j+2 \choose j+1} {2n-2j \choose n-j}}{{2n \choose n}} - 
             \frac{2(2n+1)(2n-3j)}{(n+2)(n+3)} \; .\qed
      \end{equation}       
    \end{theorem}
   
   To get the coefficients in the expansion of
   \begin{align}\begin{split}
       G_{2}(z,u) &= 8\frac{(1-Y)^{2}(X+Y+2)}{(X+Y)^{3}(1+Y)^{2}}  \\
       & = \frac{8(1-4uz+2u^{2}z^{2})}{u^{2}z^{2}}\frac{1}{(X+Y)^{3}}-
      \frac{8(1-2uz)}{u^{2}z^{2}}\frac{Y}{(X+Y)^{3}}  \\
      &  + \frac{4(1-4uz
       +2u^{2}z^{2})}{u^{2}z^{2}}\frac{1}{(X+Y)^{2}}-\frac{4(1-2uz
       )}{u^{2}z^{2}}\frac{Y}{(X+Y)^{2}} 
      \label{rgg21}
   \end{split}\end{align}
   we still have to compute the coefficients $[z^{n}u^{j}]\frac{Y}{(X+Y)^{3}}$\,.
   
   As a first step, we get them as a sum;
   \begin{align}\begin{split}
       [z^{n}u^{j}]&\frac{Y}{(X+Y)^{3}} = \sum_{k=0}^{j} [z^{k}u^k] Y\
      [z^{n-k}u^{j-k}] \frac{1}{(X+Y)^{3}}  \\
       & = -\frac{3}{2}\sum_{k=0}^{j}  
      \frac{(2k-2)!}{k! (k-1)!}\frac{(2(n-k)+1)(j-k+1)(n-j+1)}{(n-k+1)(n-k+2)
       (n-k+3)}{2(n-k) \choose n-k} \; ,
   \end{split}\end{align}
   that is valid by observing the limiting relation
     $ \frac{(-2)!}{(-1)!}  = - \frac{1}{2}$\,.


  Zeilberger's algorithm evaluates this sum as before, and we obtain
   \begin{equation}
        [z^{n}u^{j}] \frac{Y}{(X+Y)^{3}} = \frac{(2j+1)(2n
        +1-2j)(3n-4j+3)}{4(n+1)(n+2)(n+3)}{2j \choose j}{2n-2j \choose n-j} \,
       .
       \label{rgg22}
   \end{equation}
   Hence we get 
   \begin{align}\begin{split}
      &  [z^{n}u^{j}] G_{2}(z,u) = \textstyle{ \frac{4(2n+1)(3jn^{3}
      +23n^{3}-3j^{2}n^{2}-51jn^{2} +18n^{2}+33j^{2}n-42jn 
	 +19n+30j^{2}-30j)}{\displaystyle{(n+1)(n+2)(n+3)(n+4)(n +5)}}
      }\displaystyle{{ 2n \choose n}  }\\
      & -  \textstyle{\frac{(n-j+1)
      (11j^{2}n^{3}+47jn^{3} +46n^{3}-16j^{3}n^{2}-68j^{2}n^{2}-44jn^{2}
      +36n^{2}-35j^{2}n   -35jn+38n +16j^{3}+20j^{2}-16j)}{\displaystyle{(j+2)(n+1)(n
       +2)(n+3)(n+4)(n+5)}}}\times  \\
	&\qquad\times{2j+2 \choose j+1} {2n+2-2j \choose n+1-j}
   \end{split}\end{align}
   and thus
   \begin{lemma}
      The second factorial moment $M_{n,j}^{(2)}$ of the number of ascendants
      of the node with label $j$, where the nodes are labelled by
	 preorder traversal, in a binary tree of size $n$  is given by
      \begin{align}\begin{split}
           & M_{n,j}^{(2)} = \textstyle{\frac{4(2n+1)(3jn^{3}+23n^{3}-3j^{2}n^{2}-51jn^{2}
                 +18n^{2}+33j^{2}n-42jn    +19n+30j^{2}-30j)}{\displaystyle{(n+2)(n+3)(n+4)(n+5)}}}
           \\     
            & - \textstyle
           {\frac{(n-j+1) (11j^{2}n^{3}+47jn^{3}
                +46n^{3}-16j^{3}n^{2}-68j^{2}n^{2}-44jn^{2}
                +36n^{2}-35j^{2}n-35jn   +38n +16j^{3}+20j^{2}-16j)}
	{\displaystyle{(j+2)(n+2)(n+3)(n+4)(n+5)}}}
\times\\&\qquad\times		\frac{{2j+2 \choose j+1}
                  {2n+2-2j \choose n+1-j}}{{2n \choose n}} \, .\qed
       \end{split}\end{align}
   \end{lemma}
   
   This leads to the following
   \begin{theorem}
      The variance $V_{n,j}$ of the number of ascendants
      of the node with label $j$, where the nodes are labelled by
	 preorder traversal, in a binary tree of size $n$, is given by
      \begin{align}\begin{split}
           V_{n,j} &=  \textstyle
                {\frac{2n(2n+1)(6n^{4}j+28n^{4}-6n^{3}j^{2}-21n^{3}j
                  +86n^{3}-60jn^{2}-40n^{2}    +12j^{2}n+297jn-62n-186j^{2}
                  +138j-12)}{\displaystyle{(n+2)^{2}(n+3)^{2}(n+4)(n+5)}}}  \\
         &  -{\frac{\Psi
}{(j+1)(j+2)(n+2)^{2}(n+3)^{2}
                 (n+4)(n+5)}}\frac{{2j \choose j}{2n-2j \choose n-j}}{{2n
                  \choose n}}  \\ 
          & - \frac{4(jn+2n-j
                   )^{2}(2n-2j+1)^{2}}{(n+2)^{2}(n+3)^{2}}\frac{{2j+2 \choose
                 j+1}^{2}{2n-2j \choose n-j}^{2}}{{2n \choose n}^{2}} \; ,
      \end{split}\end{align}
with

\noindent
$  
\Psi=2(2j+1)                  (2n-2j+1)(5j^{2}n^{5}+26jn^{5}
                  +24n^{5}-8j^{3}n^{4}-79j^{2}n^{4}   -152jn^{4}-132n^{4}
+44j^{3}n^{3}-51j^{2}n^{3}-554jn^{3}-864n^{3}+200j^{3}n^{2}
  +919j^{2}n^{2}+1112jn^{2}-444n^{2}-188j^{3}n
                 -242j^{2}n+528jn-24n -48j^{3}   -120j^{2}+48j)
$\;.\qed

   \end{theorem}
   
   \section{The number of descendants of nodes labelled by postorder traversal}
   

   Now $f_{n,j,l}$ counts the number of binary trees of size $n$,
	 where  the node with label $j$ (labelled by postorder traversal)
	has exactly $l$ descendants.
   
   For the trivariate generating function we get the relation
   \begin{equation}
      F(z,u,v) = zuv B^{2}(zuv) + zF(z,u,v)  B(z) + zB(zu)  F(z,u,v) \; ,
   \end{equation}
   from which we obtain
    \begin{equation}
      F(z,u,v) = \frac{zuvB^{2}(zuv)}{1-zB(z)-zB(zu)} \, .
   \end{equation}
   
   From the expression 
   \begin{equation}
      G_{1}(z,u) = \frac{2(1-Y)}{Y(1+X)(X+Y)} = \frac{1}{2zXY} - \frac{2}{X(X
       +Y)} - \frac{1}{2zY} 
   \end{equation}
   we get the coefficients
   \begin{equation}
      [z^{n}u^{j}] G_{1}(z,u) = \frac{1}{2}[z^{n+1}u^{j}]\frac{1}{XY} - 2
      [z^{n}u^{j}] \frac{1}{X(X+Y)} =\frac{j}{2(n+1)}{2j \choose j}
      {2n+2-2j \choose n+1-j} \, .
   \end{equation}
   
   This leads to
   \begin{theorem}
      The expectation $E_{n,j}$ of the number of descendants of the node with
      label $j$, where the nodes are labelled by
      postorder traversal, in a binary tree of size $n$,  is given
      by
      \begin{equation}
         E_{n,j} = \frac{j}{2}\frac{{2j \choose j}{2n+2-j \choose n
                   +1-j}}{{2n \choose n}} \; .\qed
      \end{equation}
   \end{theorem}
   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   Furthermore we get for $G_{2}(z,u)$
   \begin{align}\begin{split}
       G_{2}(z,u) &= \frac{(1-Y)^{2}(1+3Y)}{Y^{3}(1+X)(X+Y)}  \\
      &  = 3\frac{1}{X(X+Y)} + 2 \frac{1}{X^{2}(X+Y)} - \frac{1}{X^{3}(X+Y)}
      - \frac{3}{4}\frac{X}{zY}+\frac{1}{2}\frac{X}{zY^{2}}+\frac{1}{4}
      \frac{X}{zY^{3}}  \\
      &  -3\frac{1}{XY}-2\frac{1}{X^{2}Y}+\frac{1}{X^{3}Y}+2
      \frac{1}{XY^{2}}-\frac{1}{X^{2}Y^{2}}+\frac{1}{XY^{3}}+\frac{3}{4}
      \frac{1}{zY}-\frac{1}{2}\frac{1}{zY^{2}}-\frac{1}{4}\frac{1}{zY^{3}} \,
      .
   \end{split}\end{align}
Combining the earlier results
    we get for the coefficients
   \begin{align}\begin{split}
       [z^{n}u^{j}] G_{2}(z,u) & =  \frac{nj}{2(n+1)}{2j \choose j}{2n+2-2j
        \choose n+1-j} + \frac{1}{2} 4^{j} {2n +2 -2j \choose n+1-j} -
       \frac{1}{2} {2n+2 \choose n+1}  \\
       &  - 4^{n} + \sum_{k=j}^{n} {2k \choose k} {2n-2k \choose n-k} \, .
      \end{split}\end{align}
   
   This leads to
\begin{lemma}
      The second factorial moment $M_{n,j}^{(2)}$
	 of the number of descendants of the node with
      label $j$, where the nodes are labelled by
	postorder traversal, in a binary tree of size $n$  is given by
      \begin{align}\begin{split}
              M_{n,j}^{(2)} & =  \frac{nj}{2} \frac{{2j \choose j}{2n+2-2j
            \choose n+1-j}}{{2n \choose n}} + \frac{n+1}{2} \frac{4^{j} {2n
            +2-2j \choose n+1-j}}{{2n \choose n}} - (n+1) \frac{4^{n}}{{2n
            \choose n}}-2n -1 \\
          &  + \frac{n+1}{{2n \choose n}} \sum_{k=j}^{n} {2k
           \choose k} {2n-2k \choose n-k} 
	\qquad \text{{\rm for}}
          \ {1 \le j \le n} \, .\qed
      \end{split}\end{align}
   \end{lemma}   
   
   This leads immediately to
   \begin{theorem}
      The variance $V_{n,j}$
of the number of descendants of the node with
      label $j$, where the nodes are labelled by
	postorder traversal, in a binary tree of size $n$,  is given by
      \begin{align}\begin{split}
 V_{n,j} & =  \frac{(n+1)j}{2} \frac{{2j \choose j}{2n+2-2j
             \choose n+1-j}}{{2n \choose n}} + \frac{n+1}{2} \frac{4^{j}{2n
             +2-2j \choose n+1-j}}{{2n \choose n}} - (n+1) \frac{4^{n}}{{2n
             \choose n}} -2n -1  \\
           &  - \frac{j^{2}}{4}\frac{{2j \choose j}^{2}{2n
             +2-2j \choose n+1-j}^{2}}{{2n \choose n}^{2}} + \frac{n+1}{{2n
             \choose n}} \sum_{k=j}^{n} {2k \choose k} {2n-2k \choose n-k}
                     \qquad \text{{\rm for}}
          \ {1 \le j \le n}  \, .\qed
     \end{split} \end{align}
   \end{theorem}
     

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


   \section{The number of ascendants of nodes labelled by   postorder traversal}
   
 Here we denote by $f_{n,j,l}$ the number of binary trees of size $n$,
	 where the node labelled $j$ by postorder traversal
	has exactly $l$ ascendants.
   
   
   For the trivariate generating function $F(z,u,v)$ we get the relation
   \begin{equation}
      F(z,u,v) = zuv B^{2}(zu) + zvF(z,u,v)  B(z) + zvB(zu)  F(z,u,v) \, ,
   \end{equation}
   and explicitly
   \begin{equation}
      F(z,u,v) = \frac{zuvB^{2}(zu)}{1-zvB(z)-zvB(zu)} \, .
   \end{equation}   
   From this equation we derive
   \begin{equation}
      G_{1}(z,u) = \frac{4(1-Y)(1+Y)}{(1+X)^{2}(X+Y)^{2}} = \frac{2u}{z(X
       +Y)^{2}}-\frac{4u}{(X+Y)^{2}}-\frac{2u}{z}\frac{X}{ (X+Y)^{2}} \; .
   \end{equation}
      In order to get the coefficients in the expansion of the above expression we need
   \begin{equation}
      [z^{n}u^{j}]\frac{X}{(X+Y)^{2}}=[z^{n}u^{j}]\frac{1}{X+Y}-[z^{n}u^{j}]
      \frac{Y}{(X+Y)^{2}} = -\frac{n-1-3j}{2(n+1)(n+2)}{2n \choose
       n} \, .
      \label{rgg24}
   \end{equation}
      With this we get
   \begin{equation}
      [z^{n}u^{j}] G_{1}(z,u) = \frac{n+3-3j}{(n+2)(n+3)}{2n+2 \choose n
       +1} + \frac{j(n^{2}-jn+2n+j-1)}{2(n+1)(n+2)(n+3)}{2j \choose
       j} {2(n+2-j) \choose n+2-j} 
   \end{equation}
   and
   \begin{theorem}
      The expectation $E_{n,j}$ of the number of ascendants of the node with
      label $j$, where the nodes are labelled by
      postorder traversal, in a binary tree of size $n$, is given
	for all\/ $1\le j\le n$       by
      \begin{equation}
            E_{n,j}  =  \frac{2(2n+1)(n+3-3j)}{(n+2)(n+3)} 
             + \frac{j(n^{2}-jn +2n+j-1)}{2(n+2)(n+3)}\frac{{2j
                   \choose j}{2(n+2-j) \choose n+2-j}}{{2n \choose n}} \; . \qed
      \end{equation}
   \end{theorem}
   
   Furthermore we consider the coefficients of
   \begin{align}\begin{split}
       G_{2}(z,u) &= 8 \frac{(1-Y)(1+Y)(1-X)(X+Y+2)}{(1+X)^{3}(X+Y)^{3}}
       \\
      &  = -\frac{8(1-2z)u}{z^{2}}\frac{X}{(X+Y)^{3}}+
      \frac{8(1-4z+2z^{2})u}{z^{2}}\frac{1}{(X+Y)^{3}}  \\
      &  -\frac{4(1-2z)u}{z^{2}}\frac{X}{(X+Y)^{2}}+\frac{4(1-4z
       +2z^{2})}{z^{2}}\frac{1}{(X+Y )^{2}} \; .
   \end{split}\end{align}
      To do this we need
   \begin{align}\begin{split}
      [z^{n}u^{j}]\frac{X}{(X+Y)^{3}}  &=  [z^{n}u^{j}]\frac{1}{(X+Y
       )^{2}}-[z^{n}u^{j}]\frac{Y}{(X+Y)^{3}}  \\
      & =  -\frac{(2j+1) (2n-2j+1)(n-4j-3)}{4(n+1)(n+2)(n+3)}{2j
       \choose j}{2(n-j) \choose n-j} \, .
   \end{split}\end{align}
      Then we get
   \begin{align}\begin{split}
      [z^{n}u^{j}] G_{2}(z,u) & =  {\frac{\Psi
}{(n+3-j)(n+1 )(n+2)(n+3)(n+4)(n+5)} } {2j \choose j}{2(n+2-j) \choose n+2-j}  \\
       & + \textstyle{\frac{4(2n+1)(3jn^{3} +2n^{3}-3j^{2}n^{2}-9jn^{2} +18n^{2}+33j^{2}n-84jn
        +40n+30j^{2}-30j)}{{\displaystyle(n+1)(n+2)(n+3)(n+4)(n +5)}}}\displaystyle{{2n \choose
       n}} \, ,
   \end{split}\end{align}
where $\Psi$ is given in Lemma \ref{Le_num}, whence we have
   \begin{lemma}\label{Le_num}
      The second factorial moment $M_{n,j}^{(2)}$ of the number of ascendants
      of the node with label $j$, where the nodes are labelled by
	postorder traversal, in a binary tree of size $n$ is given by
      \begin{align}\begin{split}
              M_{n,j}^{(2)} &= \textstyle{
	\frac{4(2n+1)(3jn^{3}+2n^{3}-3j^{2}n^{2}-9jn^{2}
                +18n^{2} +33j^{2}n-84jn  +40n+30j^{2}-30j)}
	{\displaystyle{(n+2)(n+3)(n+4)(n+5)}}  }
             \\
             &  +\frac{\Psi}{(n+3-j)(n+2)(n+3)(n+4)(n+5)}\frac{{2j
                   \choose j}{2(n+2-j) \choose n+2-j}}{{2n \choose n}} 
       \end{split}\end{align}
with $\Psi=j(5n^{5}-26jn^{4}+47n^{4}+37j^{2}n^{3}-163jn^{3}
                 +143n^{3}-16j^{3}n^{2} 
           +116j^{2}n^{2}-250jn^{2}+129n^{2}-13j^{2}n
            +31jn-40n +16j^{3}-68j^{2}  
            +72j-20)$\;.\qed
   \end{lemma}
   
   Also we get
   \begin{theorem}
      The variance $V_{n,j}$ of the number of ascendants
      of the node with label $j$, where the nodes are labelled by
	 postorder traversal, in a binary tree of size $n$, is given by
      \begin{align}\begin{split}
           V_{n,j} &= \textstyle{\frac{2n(2n+1)(6jn^{4}+n^{4}+11n^{3}+33jn^{3}-6j^{2}n^{3}
                 +36jn^{2} +35n^{2}+12j^{2}n  
           +51jn+13n-186j^{2}+234j-60)}
	{\displaystyle{(n+2)^{2}(n+3)^{2}(n+4)(n+5)}} }  \\           
          & + \frac{\Psi}{2(n+3-j)(n+2)^{2}(n+3)^{2}(n+4)
          (n+5)}\frac{{2j \choose j}{2(n+2-j) \choose n+2-j}}{{2n \choose n}}
          \\
          &  -\frac{j^{2}(n^{2}-jn+2n+j-1
                 )^{2}}{4}\frac{{2j \choose j}^{2}{2(n+2-j) \choose n
                   +2-j}^{2}}{{2n \choose n}^{2}}
       \end{split}\end{align}
   \end{theorem}
\noindent
with $\Psi=
j(3n^{7}-14jn^{6}+23n^{6}
                 +19j^{2}n^{5}-38jn^{5}-2n^{5}-8j^{3}n^{4}-29j^{2}n^{4}
            +428jn^{4}-436n^{4}+44j^{3}n^{3}-681j^{2}n^{3}
                 +1950jn^{3}-1271n^{3}
                +200j^{3}n^{2}-955j^{2}n^{2}  
  +1794jn^{2}-1003n^{2}-188j^{3}n+950j^{2}n
                -1048jn+262n-48j^{3}+264j^{2}    -336j+120)$\;.\qed

\section{Asymptotics}

In this section we evaluate our findings asymptotically, under the assumptions
$j$ fixed;  $j\sim\rho n$, with $0<\rho <1$;  $n-j$ fixed. 
All formul\ae\ are easy to obtain, thus we only collect them in a table.

\begin{table}
\tabcolsep1mm
\arraycolsep0mm

\begin{tabular}{ | c | c | c | c | c | c | }
%
% 1. Zeile
%
   \cline{4-6}
   \multicolumn{3}{c|}{ \rule[-1.65ex]{0mm}{4.2ex} } 
   & 
   $j$ fixed 
   & 
   $j \sim \rho n$ 
   & $l := n-j$ fixed 
   \\
%
% 2. Zeile
%
   \cline{2-6}
   \multicolumn{1}{c|}{ \rule[-2.25ex]{0mm}{6ex} }   
   &
   &
   $E_{n,j}$ %Expectation 
   & 
   $ \scriptstyle (2j+1) {2j \choose j} 4^{-j +1}$ 
   & 
   $8 \frac{\sqrt{\rho (1-\rho)}}{\sqrt{\pi}}\sqrt{n}$ 
   & 
   $ \scriptstyle (2l +1) {2l \choose l} 4^{-l+1}$ 
   \\
%
% 3. Zeile
%
   \cline{3-6}
   \multicolumn{1}{c|}{ \rule[-4.5ex]{0mm}{10ex} }
   & 
   \raisebox{2.5ex}[-2.5ex]{ \begin{tabular}{@{}c@{}} Ascendants \\ of leaf
      \end{tabular} } 
   &
   $V_{n,j}$ % Variance 
   & 
   $ \begin{array}{l} \scriptstyle 24(j+1) \\ \scriptstyle - 16 (2j+1)^{2}
    {2j \choose j}^{2} 4^{-2j} \\ \scriptstyle - (2j+1 ) {2j \choose j} 4^{-j
     +1} \end{array} $
   & 
   $8 \frac{ \rho (1-\rho) (3\pi-8 )}{\pi} n$ 
   & 
   $ \begin{array}{l} \scriptstyle 24 (l+1) \\ \scriptstyle -16(2l+1
    )^{2}{2l \choose l}^{2}4^{-2 l} \\ \scriptstyle -(2l+1
    ){2l \choose l} 4^{-l+1} \end{array} $  
   \\ 
%
% 4. Zeile
%   
   \hline
   \rule[-2.55ex]{0mm}{5.7ex}
   &
   &
   $E_{n,j}$
   &
   $ {2j \choose j} 4^{-j} n$ 
   &
   $\frac{1}{\sqrt{\pi}\sqrt{\rho (1-\rho)}} \sqrt{n}$
   &
   ${2(l+1) \choose l+1} 4^{-(l+1)} n$
   \\
%
% 5. Zeile
%
   \cline{3-6}
   \rule[-4.05ex]{0mm}{9ex}
   &
   \raisebox{2.5ex}[-2.5ex]{Descendants}
   &
   $V_{n,j}$
   &
   $ \scriptstyle \left({2j \choose j} 4^{-j} - {2j \choose j}^{2} 4^{-2j}
   \right) n^{2}$
   &
   $ \scriptstyle \left(\frac{1}{\sqrt{\pi}\sqrt{\rho (1-\rho)}}-\frac{\sqrt{
     \pi}}{2} \right)n^{ 3/2}$
   &
   $ \begin{array}{l} \scriptstyle \left( \rule{0mm}{2ex} {2(l+1) \choose l+1} 4^{-(l+1)}
    \right. \\
     \scriptstyle \left. \hspace{3mm}- {2(l+1) \choose l +1}^{2} 4^{-2(l+1)}\right) n^{2}
     \end{array}$
   \\
%
% 6. Zeile
%   
   \cline{2-6}
   \rule[-2.25ex]{0mm}{6ex}
   \raisebox{2.5ex}[-2.5ex]{Inorder}
   &
   &
   $E_{n,j}$
   &
   $ \scriptstyle 2(4j+1){2j \choose j} 4^{-j} -2$
   &
   $8 \frac{\sqrt{\rho (1-\rho)}}{\sqrt{\pi}}\sqrt{n}$
   &
   $ \scriptstyle 2(4(l+1)+1){2(l+1) \choose l+1} 4^{-(l+1)} -2$
   \\   
%
% 7. Zeile
%
   \cline{3-6}
   \rule[-5ex]{0mm}{10ex}
   &
   \raisebox{2.5ex}[-2.5ex]{Ascendants}   
   &
   $V_{n,j}$
   &
   $ \begin{array}{l} \scriptstyle 24j+14 \\
     \scriptstyle -2(4j+5){2j \choose j} 4^{-j} \\
     \scriptstyle -4(4j+1)^{2}{2j \choose j}^{2}4^{-2j} \end{array}$
   &
   $8 \frac{\rho (1-\rho)(3\pi-8)}{\pi}n$
   &
   $ \begin{array}{l} \scriptstyle 24(l+1)+14 \\
     \scriptstyle -2(4(l+1)+5){2(l+1) \choose l+1} 4^{-(l+1)} \\
     \scriptstyle - 4(4 (l+1)+1)^{2} {2(l+1) \choose l+1}^{2} 4^{-2(l+1)}
     \end{array}$
   \\
%
% 8. Zeile
%   
   \hline
   \rule[-2.25ex]{0mm}{5.4ex}
   &
   &
   $E_{n,j}$
   &
   $\scriptstyle 2 {2j \choose j} 4^{-j} n$
   &
   $2 \frac{\sqrt{1-\rho}}{\sqrt{\pi}\sqrt{\rho}}\sqrt{n}$
   &
   $\scriptstyle (2l+1){2l \choose l} 4^{-l}$
   \\
%
% 9. Zeile
%
   \cline{3-6}
   \rule[-4.05ex]{0mm}{9ex}
   &
   \raisebox{2.5ex}[-2.5ex]{Descendants}
   &
   $V_{n,j}$
   &
   $ \begin{array}{l} \scriptstyle \hspace{-0mm}\left( \rule{0mm}{2ex} 2 {2j \choose j}
     4^{-j} \right. \\ 
     \scriptstyle \hspace{3mm} \left. - {2j \choose j}^{2} 4^{-2j +1}
     \right) n^{2}
     \end{array}$
   &
   $ \begin{array}{l} \scriptstyle \frac{2}{\sqrt{\pi}} \left( \frac{\sqrt{1-
      \rho}}{\sqrt{ \rho}} \right. \\
     \scriptstyle \left. - \arcsin \sqrt{1-\rho} \rule{0mm}{2ex} \right) n^{
      3/2}
     \end{array}$
   &
   $ \begin{array}{l} \scriptstyle \frac{2}{3} l (l+1) {2(l+1) \choose l+1}
     4^{-(l+1)}+l+1 \\
     \scriptstyle -4(l+1)^{2}{2(l+1) \choose l+1}^{2} 4^{-2(l+1)} \end{array}$
   \\
%
% 10. Zeile
%
   \cline{2-6}
   \rule[-1.95ex]{0mm}{5.7ex}
   \raisebox{2.5ex}[-2.5ex]{Preorder}         
   &
   &
   $E_{n,j}$
   &
   $\scriptstyle 2(j+2){2(j+1) \choose j+1} 4^{-j} -8$
   &
   $8 \frac{\sqrt{\rho (1-\rho)}}{\sqrt{\pi}} \sqrt{n}$
   &
   $\scriptstyle 4(2l+1){2l \choose l}4^{-l} +4$
   \\
%
% 11. Zeile
%
   \cline{3-6}
   \rule[-5ex]{0mm}{10ex}
   &
   \raisebox{2.5ex}[-2.5ex]{Ascendants}         
   &
   $V_{n,j}$
   &
   $ \begin{array}{l} \scriptstyle 24j +112 \\
     \scriptstyle - 4 (j+2)^{2} {2(j+1) \choose j+1}^{2} 4^{-2j} \\
     \scriptstyle - \frac{2(j+4)(5j+6)}{j+2}{2(j+1) \choose j+1} 4^{-j}
     \end{array}$
   &
   $8\frac{\rho(1-\rho)(3\pi-8)}{\pi}n$
   &
   $ \begin{array}{l} \scriptstyle 24l+28 \\
     \scriptstyle -16(2l+1)^{2}{2l \choose l}^{2}4^{-2l} \\
     \scriptstyle +12(2l+1){2l \choose l} 4^{-l} \end{array}$
   \\
%
% 12. Zeile
%
   \hline
   \rule[-2.25ex]{0mm}{5.4ex}
   &
   &
   $E_{n,j}$
   &
   $\scriptstyle 2j {2j \choose j} 4^{-j}$
   &
   $2 \frac{\sqrt{\rho}}{\sqrt{\pi}\sqrt{1-\rho}}\sqrt{n}$
   &
   $\scriptstyle 2 {2(l+1) \choose l+1} 4^{-(l+1)} n$
   \\
%
% 13. Zeile
%
   \cline{3-6}
   \rule[-4.05ex]{0mm}{9ex}
   &
   \raisebox{2.5ex}[-2.5ex]{Descendants}
   &
   $V_{n,j}$
   &
   $ \begin{array}{l} \scriptstyle \frac{2j(j-1)}{3}{2j \choose j}4^{-j} +j \\
     \scriptstyle -4j^{2}{2j \choose j}^{2} 4^{-2j} \end{array}$
   &
   $ \begin{array}{l} \scriptstyle \frac{2}{\sqrt{\pi}}\left(\frac{\sqrt{
      \rho}}{\sqrt{1-\rho}} \right. \\
     \scriptstyle \left. +\arcsin \sqrt{1-\rho}-\frac{\pi}{2} \rule{0mm}{2ex}
     \right)n^{ 3/2} \end{array}$
   &
   $ \begin{array}{l} \scriptstyle \left( \rule{0mm}{2ex} 2 {2(l+1) \choose l
     +1} 4^{-(l+1)} \right. \\
     \scriptstyle \left. \hspace{3mm}- 4 {2(l+1) \choose l+1}^{2} 4^{-2(l+1)} \right)
     n^{2} \end{array}$
   \\
%
% 14. Zeile
%
   \cline{2-6}
   \rule[-2.25ex]{0mm}{6ex}
   \raisebox{2.5ex}[-2.5ex]{Postorder}
   &
   &
   $E_{n,j}$
   &
   $\scriptstyle 8j{2j \choose j} 4^{-j} +4$ 
   &
   $8 \frac{\sqrt{\rho (1-\rho)}}{\sqrt{\pi}} \sqrt{n}$
   &
   $\scriptstyle 2(l+3){2(l+2) \choose l+2}4^{-(l+1)} -8$
   \\
%
% 15. Zeile
%
   \cline{3-6}
   \rule[-5ex]{0mm}{10ex}
   &
   \raisebox{2.5ex}[-2.5ex]{Ascendants}      
   &
   $V_{n,j}$
   &
   $ \begin{array}{l} \scriptstyle 24j+4 \\
     \scriptstyle +24j{2j \choose j} 4^{-j} \\
     \scriptstyle - 64 j^{2} {2j \choose j}^{2} 4^{-2j} \end{array}$
   &
   $8 \frac{\rho (1-\rho) (3\pi-8)}{\pi} n$
   &
   $ \begin{array}{l} \scriptstyle 24l+136 \\
     \scriptstyle -4(l+3)^{2}{2(l+2) \choose l+2}^{2}4^{-2(l+1)} \\
     \scriptstyle - \frac{2(l+5)(5l+11 )}{l+3}{2(l+2) \choose l+2} 4^{-(l+1)}
     \end{array}$
   \\
   \hline
\end{tabular}   







\bigskip
\caption{Asymptotic results related to all the explicit formulae in the paper}
\end{table}


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

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

\bibitem{GuPf92}
W.~Gutjahr and G.~Pflug.
\newblock The asymptotic contour process of a binary tree is a {B}rownian
  excursion.
\newblock {\em Stochastic processes and their applications}, 41:69--89, 1992.

\bibitem{Kemp82}
R.~Kemp.
\newblock On the average oscillation of a stack.
\newblock {\em Combinatorica}, 2:157--176, 1982.

\bibitem{Kirschenhofer83}
P.~Kirschenhofer.
\newblock On the height of leaves in binary trees.
\newblock {\em Journal of Combinatorics, Information and System Sciences}, 8:44
  --60, 1983.

\bibitem{Kirschenhofer83b}
P.~Kirschenhofer.
\newblock Some new results on the average height of binary trees.
\newblock {\em Ars Combinatoria}, {16} {A}:255--260, 1983.

\bibitem{KiPr82b}
P.~Kirschenhofer and H.~{Prodinger}.
\newblock On the average hyperoscillations of planted plane trees.
\newblock {\em Combinatorica}, 2:177--186, 1982.

\bibitem{KiPr82}
P.~Kirschenhofer and H.~Prodinger.
\newblock On the average oscillation of the contour of monotonically labelled
  ordered trees.
\newblock In {\em Proceedings of the Second World Conference on Mathematics at
  the Service of Man (Las Palmas)}, pages 394--399, 1982.

\bibitem{Knuth68}
D.~E. Knuth.
\newblock {\em The Art of Computer Programming}, volume 1: Fundamental
  Algorithms.
\newblock Addison-Wesley, 1968.
\newblock Second edition, 1973.

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

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

\bibitem{Sedgewick91}
R.~Sedgewick.
\newblock {\em Algorithms}.
\newblock Addison-Wesley, 1991.

\bibitem{SeFl96}
R.~Sedgewick and P.~Flajolet.
\newblock {\em An Introduction to the Analysis of Algorithms}.
\newblock Addison-Wesley, 1996.

\end{thebibliography}
\end{document}
