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

\usepackage{emlines2}
\usepackage{latexsym}

\marginparwidth 0pt 
\oddsidemargin -0.4 in 
\evensidemargin -0.4 in 
\marginparsep 0pt
\topmargin -0.3 in 
\textwidth 7 in 
\textheight 9 in 


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
\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=30pt

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

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

\newcommand\U{{\mathcal{U}}}
\newcommand\E{{\mathbb{E}}}
\newcommand\V{{\mathbb{V}}}
\newcommand\T{{\mathcal{T}}}
\renewcommand\P{{\mathcal{P}}}
\renewcommand\a{{\bold{a}}}
\newcommand\p{{\bold{p}}}
\newcommand\mcirc{{\bigcirc}}

\newcommand\C{{\mathcal C}}

\newcommand\bl{\operatorname{L}}

\newcommand{\floor}[2]{\genfrac{\lfloor}{\rfloor}{}{}{#1}{#2}}
\newcommand{\ceil}[2]{\genfrac{\lceil}{\rceil}{}{}{#1}{#2}}


\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[Level numbers in binary trees]
{Moments of level numbers of leaves in binary trees}\footnote{This research was supported by 
the Austrian Research Society (FWF) under the project number \textup{P12599-MAT}}
\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{March 17, 1998}
\begin{abstract} 
For the random variable ``height of leaf $j$ in a binary tree of
size $n$'' we derive closed formul{\ae} for all moments. The more general
case of $t$--ary trees is also considered. 
\end{abstract} 


\maketitle

  \section{Introduction}

We reexamine the heights of leaves (enumerated from left to right) in 
binary trees and, more generally, $t$--ary trees.  

The expectations go back to Kirschenhofer \cite{Kirschenhofer83}, 
and the variance to Gutjahr \cite{Gutjahr92}. For higher moments, Gutjahr had to
resort to analytic techniques. However, we are able to produce an explicit formula
for the $s$--th moment, for general $s$. The result is ``closed form,'' as  it
comprised only a number of summands that depends on $s$, not on $n$  or $j$,
where $n$ denotes the size of the tree and $j$ the number of the leaf in consideration.

From this explicit result, asymptotic formul{\ae}, as given by Gutjahr, are of course
corollaries for which we don't need more than Stirling's approximation for the
factorials. 

\medskip

In a follow--up paper to \cite{Kirschenhofer83}, Kirschenhofer considered
in \cite{Kirschenhofer85} also $t$--ary trees (binary trees are the instance
$t=2$). He treated the expectation with a complicated analytic technique
(``diagonalization method'') because he believed that explicit enumeration is
not feasible. However, we disproof this claim by giving an exact formula for
the $s$-th (factorial) moment.    This time, it is not ``closed form,'' 
but we can get asymptotics for the expectations by rather elementary techniques
(Stirling's formula and approximation of a sum by an integral). 





 



   \section{The height of  leaves in binary trees}
   
   
   We denote by $\mathcal B$ the family of  binary trees, sometimes called
   extended binary trees, which is defined by the formal identity

  \begin{equation}   
%\input{pbingg.pic}
%TexCad Options
%\grade{\on}
%\emlines{\on}
%\beziermacro{\off}
%\reduce{\on}
%\snapping{\off}
%\quality{2.00}
%\graddiff{0.01}
%\snapasp{1}
%\zoom{0.50}
\special{em:linewidth 0.4pt}
\unitlength 0.50mm
\linethickness{0.4pt}
\begin{picture}(78.33,23.29)
\put(64.33,20.00){\circle{6.57}}
\emline{62.00}{17.67}{1}{51.67}{7.33}{2}
\emline{66.67}{17.67}{3}{77.00}{7.33}{4}
\emline{21.00}{11.00}{5}{21.00}{17.00}{6}
\emline{21.00}{17.00}{7}{27.00}{17.00}{8}
\emline{27.00}{17.00}{9}{27.00}{11.33}{10}
\emline{27.00}{11.33}{11}{21.00}{11.33}{12}
\put(42.00,14.33){\makebox(0,0)[cc]{+}}
\put(50.33,1.67){\makebox(0,0)[cc]{$\mathcal{B}$}}
\put(78.33,1.67){\makebox(0,0)[cc]{$\mathcal{B}$}}
\put(1.67,14.67){\makebox(0,0)[cc]{$\mathcal{B}\quad=\quad$}}
\end{picture}
\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 $\mathcal B$ with exactly $n$ internal nodes is
   denoted by ${\mathcal B}_{n}$. Further we write $B_{n}$ for the number of
   elements from ${\mathcal 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.

Let us state the following classic results that we will need in the sequel:
\begin{equation*}   
B(z)=1+zB^2(z)=\frac{1-\sqrt{1-4z}}{2z};\qquad B_n=\frac{1}{n+1}\binom{2n}{n}.
\end{equation*}


   
Assume that the leaves are labelled with the numbers $0,1,\dots,n$ from left to right
and that the distance (depth, height) of a leaf is given by the number of internal nodes
on the path from the root to the leaf. This defines random variables $X_{n,j}$ assuming
that all binary trees of size $n$ are equally likely.

Kirschenhofer \cite{Kirschenhofer83, Kirschenhofer83b} has obtained the following
explicit formula for the expectations (see \cite{PaPr97} for more results);
\begin{equation*}   
       \E(X_{n,j}) = \frac{2(2j+1)(2n-2j+1)}{n+2}\frac{\binom{2j}{j} 
\binom{2n-2j}{n-j}}{\binom{2n}{n}} -1\qquad \text{{\rm for} } \ 0 \le j
              \le n \, .
\end{equation*}
 
  

Gutjahr obtained the variance $\V(X_{n,j})$ in \cite{Gutjahr92};
unfortunately, this paper was overlooked during the preparation of our
paper \cite{PaPr97}.

Studying the higher moments, Gutjahr writes:

\medskip
\textit{``There is little hope to find a closed expression for the \textsf{third}
moment.''}
\medskip

This statement is too pessimistic, since we will find explicit formul{\ae} 
for {\it all \/}(factorial) moments in the sequel. 
Since the usual moments can be obtained from them
by linear combinations with Stirling numbers as coefficients, we have also
explicit formul{\ae} for all usual moments. 



Let $f_{n,j,l}$ denote 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 by $\sum_{n,j,l}f_{n,j,l}z^nu^jv^l$ 
	 the functional equation     
   \begin{equation}
       F(z,u,v) = 1 + 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{1}{1-zvB(z)-zuvB(zu)} \, .
      \label{rgg4}
   \end{equation}

This appears in \cite{PaPr97} and in \cite{Gutjahr92}.
The $s$--th factorial moment $\E^{\underline{s}}(X_{n,j})$  is given by
\begin{equation*}   
\E^{\underline{s}}(X_{n,j})=\frac{1}{B_n}[z^nu^j]
\frac{\partial^s}{\partial v^s}F(z,u,v)\bigg\vert_{v=1}.
\end{equation*}
Now, a routine calculation (that is easy to verify by induction) shows that
\begin{equation*}   
\frac{\partial^s}{\partial v^s}F(z,u,v)\bigg\vert_{v=1}=
2s!\frac{\big(2-(X+Y)\big)^s}{(X+Y)^{s+1}}=
2s!\sum_{l=0}^s
\binom{s}{l}(-1)^{s-l}2^l\frac{1}{(X+Y)^{l+1}},
\end{equation*}
with
\begin{equation*}   
 X = \sqrt{1-4z} \qquad\text{and}\qquad       Y = \sqrt{1-4zu},
\end{equation*}
so that our task is reduced to find explicit formul{\ae} for
\begin{equation*}   
[z^nu^j]\frac{1}{(X+Y)^{q}}.
\end{equation*}

First we compute the coefficients of $1/(1+\sqrt{1-4x}\,)^q$; for that, we use
the substitution $x=t/(1+t)^2$  and the Lagrange inversion formula:
\begin{align*}
[x^k]\frac{1}{(1+\sqrt{1-4x}\,)^q}&=\frac{1}{k}[t^{k-1}](1+t)^{2k}
\frac{d}{dt}\frac{1}{\left(1+\sqrt{1-\frac{4t}{(1+t)^2}}\,\right)^q}\\
&=\frac{1}{k}[t^{k-1}](1+t)^{2k}\frac{d}{dt}\left(\frac{1+t}{2}\right)^q\\
&=\frac{q}{2^q}\frac{1}{k+q}\binom{2k+q-1}{k}.
\end{align*}
Hence
\begin{align*}
\frac{1}{(X+Y)^q}&=
\frac{1}{(1-4z)^{q/2}\left(1+\sqrt{1-\frac{4z(u-1)}{1-4z}}\,\right)^q}\\
&=\sum_{k\ge0}\frac{q}{2^q}\frac{1}{k+q}\binom{2k+q-1}{k}
\frac{z^k(u-1)^k}{(1-4z)^{k+\frac q2}}.
\end{align*}
Thus
\begin{equation*}   
[z^nu^j]\frac{1}{(X+Y)^q}=
\sum_{j\le k\le n}(-1)^{k-j}\binom{k}{j}\frac{q}{2^q}\frac{1}{k+q}\binom{2k+q-1}{k}
4^{n-k}\binom{n-1+\frac{q}{2}}{n-k}.
\end{equation*}
To evaluate the remaining sum we use Zeilberger's algorithm \cite{GrKnPa94, PeWiZe96}.
(Alternative proofs, e.\;g. by the use of hypergeometric series, would also
be possible.)
Let
\begin{equation*}   
F(n,k)=(-1)^{k-j}\binom{k}{j}\frac{q}{2^q}\frac{1}{k+q}\binom{2k+q-1}{k}
4^{n-k}\binom{n-1+\frac{q}{2}}{n-k},
\end{equation*}
then we find
\begin{equation*}   
(n-j+1)(n+q+1)F(n+1,k)-(2n+q)(2n+q-2j+1)F(n,j) = G(n,k+1)-G(n,k)
\end{equation*}
with
\begin{equation*}   
R(n,k)=-\frac{2(2n+q)(k+q)(k-j)}{n+1-k}\qquad\text{and}\qquad G(n,k)=F(n,k)R(n,k).
\end{equation*}
Now set
\begin{equation*}   
f(n)=\sum_{k\in\mathbb Z}F(n,k),
\end{equation*}
then we obtain by summing (since the right side telescopes)
\begin{equation*}   
(n-j)(n+q)f(n)=(2n+q-2)(2n+q-2j-1)f(n-1),
\end{equation*}
with the initial value
\begin{equation*}   
f(j)=\frac{q}{2^q}\frac{1}{j+q}\binom{2j+q-1}{j},
\end{equation*}
which gives by iteration
\begin{align*}   
f(n)&=\frac{q}{2^q}\frac{1}{j+q}\binom{2j+q-1}{j}
\prod_{k=j+1}^n
\frac{(2k+q-2)(2k+q-2j-1)}{(k-j)(k+q)}\\
&=\frac{q}{2^q}\frac{1}{j+q}\binom{2j+q-1}{j}\frac{(j+q)!}{(n-j)!(n+q)!}
\prod_{k=j+1}^n (2k+q-2)(2k+q-2j-1)\\
&={q\,2^{2n-2j-q}}\frac{(2j+q-1)!}{j!(n-j)!(n+q)!}
\frac{\Gamma\big(n+\frac{q}{2}\big)\Gamma\big(n-j+\frac{q+1}{2}\big)}
{\Gamma\big(j+\frac{q}{2}\big)\Gamma\big(\frac{q+1}{2}\big)}.
\end{align*}
Of course, these $\Gamma$--functions can always be written by factorials
(or binomial coefficients), by distinguishing the cases $q$ even and odd.
Summarizing,
\begin{equation*}   
[z^nu^j]\frac{1}{(X+Y)^q}=		
{q\,2^{2n-2j-q}}\frac{(2j+q-1)!}{j!(n-j)!(n+q)!}
\frac{\Gamma\big(n+\frac{q}{2}\big)
\Gamma\big(n-j+\frac{q+1}{2}\big)}
{\Gamma\big(j+\frac{q}{2}\big)\Gamma\big(\frac{q+1}{2}\big)}
\end{equation*}
or citing the cases $q$ even and odd explicitly 
\begin{align*}
   [z^{n}u^{j}] \frac{1}{(X+Y)^{2p}} & = \frac{2p (p-1)! (j+2p)! (2n-2j+2p-1)! 
   (2j+2p-1)! (n+p-1)!}{2^{2p} (2p-1)! (j+p-1)! (n-j)! (n-j+p-1)! j! 
   (j+2p)! (n+2p)!} , \\
   [z^{n}u^{j}] \frac{1}{(X+Y)^{2p+1}} & = \frac{(2p+1) (j+p)! (2n+2p-1)! (n-j+p)!}
   {2^{2p} p! j! (n+p-1)! (n-j)! (n+2p+1)!}.
\end{align*}

Hence we have the following theorem.
\begin{theorem}
The $s$--th factorial moment $\E(X^{\underline{s}}_{n,j})$  is given by
the following explicit formula.
\begin{align}   
& \E(X^{\underline{s}}_{n,j})
=
\frac{s!}{B_n}\sum_{l=0}^s
\binom{s}{l}(-1)^{s-l}
{4^{n-j}}\frac{(l+1)\,(2j+l)!}{j!(n-j)!(n+l+1)!}
\frac{\Gamma\big(n+\frac{l+1}{2}\big)\Gamma\big(n+1-j+\frac{l}{2}\big)}
{\Gamma\big(j+\frac{l+1}{2}\big)\Gamma\big(1+\frac{l}{2}\big)}. \\
& \hspace{38em} \qed \notag
\end{align}			
\end{theorem}

With Stirling's asymptotic formula for the factorials, we get for a fixed ratio
$\rho = j/n$
\begin{equation*}
   \frac{(l+1)\,(2j+l)!}{j!(n-j)!(n+l+1)!}
   \frac{\Gamma\big(n+\frac{l+1}{2}\big)\Gamma\big(n+1-j+\frac{l}{2}\big)}
   {\Gamma\big(j+\frac{l+1}{2}\big)\Gamma\big(1+\frac{l}{2}\big)}
   = 4^{\rho n} n^{\frac{l-3}{2}} \frac{(1-\rho)^{\frac{l}{2}} \rho^{\frac{l}{2}}
   2^{l} (l+1)}{\sqrt{\pi}\; \Gamma\big(1+\frac{l}{2}\big)} 
   \left(1+\mathcal{O}\Big(\frac{1}{n}\Big)\right).
\end{equation*}

 From this we see that
 the summand with $l=s$ gives the main term in the asymptotic expansion
of the factorial moments. Using the reflection law of the Gamma function we get
\begin{equation*}
\E(X^{\underline{s}}_{n,j}) = \frac{(s+1)! (1-\rho)^{\frac{s}{2}} \rho^{\frac{s}{2}}
   2^{s}}{\Gamma\big(1+\frac{s}{2}\big)} n^{\frac{s}{2}} + 
   \mathcal{O}\left(n^{\frac{s-1}{2}}\right) = 
   \frac{2}{\sqrt{\pi}} \,4^{s} \rho^{\frac{s}{2}} (1-\rho)^{\frac{s}{2}} 
   \Gamma\left(\frac{s+3}{2}\right) n^{\frac{s}{2}} 
   + \mathcal{O}\left(n^{\frac{s-1}{2}}\right) .
\end{equation*}

Thus we have the following corollary.
\begin{cor}
The $s$--th factorial moment $\E(X^{\underline{s}}_{n,j})$ (and thus also the 
ordinary $s$--th moment $\E(X^{s}_{n,j})$) is asymptotically 
for $n \to \infty$ given by
\begin{equation*}
   \E(X^{\underline{s}}_{n,j}) = 
   \frac{2}{\sqrt{\pi}} \,4^{s} \rho^{\frac{s}{2}} (1-\rho)^{\frac{s}{2}} 
      \Gamma\left(\frac{s+3}{2}\right) n^{\frac{s}{2}} 
   + \mathcal{O}\left(n^{\frac{s-1}{2}}\right)
\end{equation*}
\end{cor}

Together with the theorem of Fr\'echet and Shohat (second central limit theorem) 
\cite{Fisz63}
and the fact, that the Maxwell distribution is uniquely determined by its moments,
we get the following result, which was first proved in \cite{GuPf92b}.
\begin{cor}
   The limiting distribution of the normalized height $\frac{X_{n,j}}{\sqrt{n}}$
   is for a fixed ratio $\rho=\frac{j}{n}$ with $0 < \rho <1$ 
   a Maxwell distribution with parameter $\sigma = \sqrt{8 \rho (1-\rho)}$. 
   That means it has for $x > 0$ the density function
   \begin{equation}
      f_{\rho}(x) = \frac{x^{2}}{16 \sqrt{\pi} 
	\big(\rho(1-\rho)\big)^{\frac{3}{2}}} 
	  e^{-\frac{x^{2}}{16\rho(1-\rho)}}.
   \end{equation}
\end{cor}
For the reader's convenience we mention that
the Maxwell distribution with parameter $\sigma$ is defined 
as the distributions
$Y = \sqrt{X_{1}^{2}+X_{2}^{2}+X_{3}^{2}}$, where the $X_{i}$ are independently 
normally distributed random variables $\mathcal{N}(0,\sigma^{2})$ with mean $0$
and variance $\sigma^{2}$. It has the following density function $f(x)$ and 
moments $M_{s} = \mathbb{E}(Y^{s})$
\begin{equation*}
   f(x) = \frac{\sqrt{2} x^{2}}{\sqrt{\pi} \sigma^{3}} 
   e^{-\frac{x^{2}}{2 \sigma^{2}}} \quad \text{for} \enspace x > 0 \, ; \quad
   M_{s} = \frac{2}{\sqrt{\pi}} 2^{\frac{s}{2}} \sigma^{s} 
      \Gamma\left(\frac{s+3}{2}\right).
\end{equation*}

\section{$t$--ary trees }

Let us consider $t$--ary trees for general $t\ge2$. In this instance, we can 
also report some progress, although the results are not so nice. The random variable
$X_{n,j}$ is again defined as the height of the leaf $j$ in a $t$--ary tree
of size $n$, where the leaves are labelled with the numbers $0,1,\dots,(t-1)n$ from
left to right and all trees are equally likely.

Recall that the generating function of $t$--ary trees satisfies
$T(z)=1+zT^t(z)$, and that
\begin{equation*}   
T_n:=[z^n]T(z) = \frac{1}{(t-1)n+1}\binom{tn}{n}\quad
\text{and}\quad
T^{(p)}_n:=[z^n]T^{p}(z) = \frac{p}{(t-1)n+p}\binom{tn+p-1}{n},
\end{equation*}  
which is classical and easy to see by means of Lagrange's 
inversion formula: With $T(z)=1+U(z)$ we get
\begin{equation*}
   [z^{n}] T^{p}(z) = [z^{n}] \big(1+U(z)\big)^{p} 
	= \frac{p}{n} [U^{n-1}] (1+U)^{tn+p-1}
   = \frac{p}{(t-1)n+p} \binom{tn+p-1}{n}.
\end{equation*}


The trivariate generating function 
\begin{equation*}
   F(z,u,v) = \sum_{n,j,l} \Big[
\text{\textsf{Number of trees of size $n$ with leaf $j$ on level $l$}}
\Big]
 z^{n} u^{j} v^{l}
\end{equation*}
is now given by
\begin{equation*}   
F(z,u,v)=\frac{1}{1-zv\sum_{k=0}^{t-1}u^k\,T^{t-1-k}(z)\,T^k(zu^{t-1})}.
\end{equation*}

Let us define the following abbreviations:
$X=T(z)$ and $Y=T(zu^{t-1})$ (in the previous section $X$ and $Y$  
had a slightly different meaning).
Now note that
\begin{equation*}   
z\sum_{k=0}^{t-1}u^kX^{t-1-k}Y^k=
z\frac{X^t-u^tY^t}{X-uY}=\frac{X-uY-(1-u)}{X-uY}=1-\frac{1-u}{X-uY}
\end{equation*}
so that we have
\begin{equation}   
F(z,u,v)=\frac{1}{1-v\big(1-\frac{1-u}{X-uY}\big)}.
\label{eqn1}
\end{equation}

\subsection{The Expectation}

At first we want to find an explicit expression for the expectations $\E(X_{n,j})$. 
Here Kirschenhofer writes \cite{Kirschenhofer85}:

\medskip
{\it ``For general $t \ge 2$,  the method, that led to an explicit expression for
$t=2$, is not feasible.''}
\medskip

Again, this statement is too pessimistic; in
 the following we will find an explicit formula for the expectations, from which
it is also possible to get an asymptotic result without the laborious
``diagonalization method,'' by only using very elementary techniques. 

Introducing 
\begin{equation*}
   G_{1}(z,u) = \left.\frac{\partial}{\partial v} F(z,u,v)\right|_{v=1}
\end{equation*}
we get by differentiating \eqref{eqn1} w.r.t. $v$ and evaluating at $v=1$ the
following result, which appeared in \cite{Kirschenhofer83}.
\begin{equation*}
   G_{1}(z,u) = \left(\frac{X-uY}{1-u}\right)^{2} - \frac{X-uY}{1-u} .
\end{equation*}

Extracting the coefficients for $0 \le j \le (t-1)n$ leads immediately to
\begin{equation*}
   [z^{n}u^{j}] \frac{X-uY}{1-u} = T_{n} \quad \text{and} \quad
   [z^{n}u^{j}] \left(\frac{X-uY}{1-u}\right)^{2} 
   = [z^{n}u^{j}] \frac{X^{2}}{(1-u)^{2}} - 2 [z^{n}u^{j}] \frac{XuY}{(1-u)^{2}}.
\end{equation*}

For $0 \le j \le (t-1) n$ we get then
\begin{equation*}
   [z^{n}u^{j}] \frac{X^{2}}{(1-u)^{2}} = \frac{2 (j+1)}{(t-1)n+2} 
   \binom{tn+1}{n}
\end{equation*}
and
\begin{align*}
   & [z^{n}u^{j}] \frac{XuY}{(1-u)^{2}} = \sum_{0 \le k \le \floor{j-1}{t-1}} 
   \frac{1}{(t-1)k+1} \binom{tk}{k} \frac{1}{(t-1)(n-k)+1}
   \binom{t(n-k)}{n-k} \big(j-(t-1)k\big).
\end{align*}

Combining these results leads to
\begin{equation}
\begin{split}
   [z^{n}u^{j}] \left(\frac{X-uY}{1-u}\right)^{2} 
   & = \frac{2 (j+1)}{(t-1)n+2} \binom{tn+1}{n} \\
   & \quad {} - 2 \sum_{0 \le k \le \floor{j-1}{t-1}} \frac{j-(t-1)k}{\big((t-1)k+1\big)
   \big((t-1)(n-k)+1\big)} \binom{tk}{k} \binom{t(n-k)}{n-k}.
\end{split}   
\end{equation}

To get asymptotic equivalents it is helpful to manipulate this expression in the 
following way. Partial fraction expansion leads to
\begin{align*}
   [z^{n}u^{j}] \left(\frac{X-uY}{1-u}\right)^{2} & = 
   \frac{2(j+1)}{(t-1)n+2} \binom{tn+1}{n} 
   - \frac{2(j+1)}{(t-1)n+2}\sum_{0 \le k \le \floor{j-1}{t-1}} 
   \frac{1}{(t-1)k+1} \binom{tk}{k} \binom{t(n-k)}{n-k} \\
   & \quad {} + \frac{2\big((t-1)n-j+1\big)}{(t-1)n+2} \sum_{0 \le k \le \floor{j-1}{t-1}} 
   \frac{1}{(t-1)(n-k)+1} \binom{tk}{k} \binom{t(n-k)}{n-k}.
\end{align*}

In the following we use the identity
\begin{equation*}
   \sum_{k=0}^{n} \frac{1}{(t-1)k+1}\binom{tk}{k} \binom{t(n-k)}{n-k} = 
   \binom{tn+1}{n} \, .
\end{equation*}
This is easy to prove, when considering the equation
\begin{equation*}
   (t-1)z T'(z) + T(z) = \sum_{n \ge 0} \binom{tn}{n} z^{n}.
\end{equation*}
The sum can then be simplified by extracting the coefficients of 
a convolution of two functions:
\begin{align*}
   & \sum_{k=0}^{n} \frac{1}{(t-1)k+1}\binom{tk}{k} \binom{t(n-k)}{n-k} =
   [z^{n}] \,T(z) \left((t-1)z T'(z) + T(z)\right) \\
   & \quad = [z^{n}]\, T^{2}(z) + 
   \frac{t-1}{2} [z^{n-1}] \left(T^{2}(z)\right)' = \left(1+\frac{t-1}{2}n\right)
   [z^{n}] \, T^{2}(z) = \binom{tn+1}{n}.
\end{align*}

When the first sum is running over the whole range from $0$ to $n$ it cancels
the extra summand, which is asymptotically of higher order. Adding the remaining
summands leads to the following expression
\begin{align*}
   & [z^{n}u^{j}] \left(\frac{X-uY}{1-u}\right)^{2} = 
   \frac{2(j+1)}{(t-1)n+2}\sum_{\floor{j-1}{t-1}+1 \le k \le n} 
   \frac{1}{(t-1)k+1} \binom{tk}{k} \binom{t(n-k)}{n-k} \\
   & \quad {} + \frac{2\big((t-1)n-j+1\big)}{(t-1)n+2}
	 \sum_{0 \le k \le \floor{j-1}{t-1}} 
   \frac{1}{(t-1)(n-k)+1} \binom{tk}{k} \binom{t(n-k)}{n-k}.
\end{align*}

This leads to the following exact formula for the expectation 
$\E\left(X_{n,j}\right) 
= \frac{1}{T_{n}} [z^{n}u^{j}]\, G_{1}(z,u)$.
\begin{theorem}
The expectation $\E\left(X_{n,j}\right)$ of the height of leaf $j$ in 
a $t$--ary tree with $n$ internal nodes is given by
\begin{align}
\begin{split}
   & \E\left(X_{n,j}\right) = \frac{2 \, (j+1) \, \big((t-1)n+1\big)}
   {\big((t-1)n+2\big) \binom{tn}{n}}
   \sum_{\floor{j-1}{t-1}+1 \le k \le n} \frac{1}{(t-1)k+1}
   \binom{tk}{k} \binom{t(n-k)}{n-k} \\
   & \quad {} +
   \frac{2 \, \big((t-1)n-j+1\big) \, \big((t-1)n+1\big)}{\big((t-1)n+2\big)
	 \binom{tn}{n}}
   \sum_{0 \le k \le \floor{j-1}{t-1}} \frac{1}{(t-1)(n-k)+1} 
   \binom{tk}{k} \binom{t(n-k)}{n-k} - 1 \, . 
\end{split} \\
& \hspace{38em} \qed \notag
\end{align}
\end{theorem}

In the following we will obtain an asymptotic equivalent of this expression.
First we want to evaluate the sum
\begin{equation*}
   \frac{2 \, (j+1) \, \big((t-1)n+1\big)}{\big((t-1)n+2\big) \binom{tn}{n}}
   \sum_{\floor{j-1}{t-1}+1 \le k \le n} \frac{1}{(t-1)k+1} \binom{tk}{k}
   \binom{t(n-k)}{n-k}
\end{equation*}
asymptotically for a fixed ratio $\rho = \frac{j}{(t-1)n}$. 
With Stirling's asymptotic formula for the binomial coefficients
\begin{equation*}
   \binom{t n}{n} = \frac{\sqrt{t} \left(\frac{t^{t}}{(t-1)^{t-1}}\right)^{n}}
   {\sqrt{t-1} \sqrt{2} \sqrt{\pi}} n^{-\frac{1}{2}} 
   \left(1+\mathcal{O}\Big(\frac{1}{n}\Big)\right)
\end{equation*}
we obtain the following expansion for the summands from $k=\rho n$ to $n-1$;
\begin{align*}
   & \frac{1}{(t-1)k+1} \binom{t k}{k} \binom{t(n-k)}{n-k} \\
   & = \frac{t} {2 \pi (t-1)} \left(\frac{t^{t}}{(t-1)^{t-1}}\right)^{n} 
   \frac{1}{(t-1)k+1} \frac{1}{\sqrt{k} \sqrt{n-k}} 
   \left(1+\mathcal{O}\Big(\frac{1}{k}\Big)\right) 
   \left(1+\mathcal{O}\Big(\frac{1}{n-k}\Big)\right) \\
   & = \frac{t} {2 \pi (t-1)} \left(\frac{t^{t}}{(t-1)^{t-1}}\right)^{n} 
   \frac{1}{(t-1)k+1} \frac{1}{\sqrt{k} \sqrt{n-k}}
    + \frac{t}{2 \pi (t-1)} \left(\frac{t^{t}}{(t-1)^{t-1}}\right)^{n} 
   \frac{1}{(t-1)k+1} \frac{c_{t}}{\sqrt{k} (n-k)^{\frac{3}{2}}}.
\end{align*}
In the last expression, the
constant $c_{t}$ is independent from $k$ and $n$.

Therefore we get
\begin{align*}
   & \frac{2 \, (j+1) \, \big((t-1)n+1\big)}{((t-1)n+2) \binom{tn}{n}}
   \sum_{\floor{j-1}{t-1}+1 \le k \le n} \frac{1}{(t-1)k+1} \binom{tk}{k}
   \binom{t(n-k)}{n-k} \\
   & \quad = \sum_{k=\rho n}^{n-1} \frac{t} {2 \pi (t-1)} 
   \left(\frac{t^{t}}{(t-1)^{t-1}}\right)^{n} 
   \frac{1}{(t-1)k+1} \frac{1}{\sqrt{k} \sqrt{n-k}} \\
   & \qquad {} + \sum_{k=\rho n}^{n-1} \frac{t}{2 \pi (t-1)} 
   \left(\frac{t^{t}}{(t-1)^{t-1}}\right)^{n} 
   \frac{1}{(t-1)k+1} \frac{c_{t}}{\sqrt{k} (n-k)^{\frac{3}{2}}} 
   + \mathcal{O}(1) .
\end{align*}

Interpreting the first sum as a Riemann sum, we obtain the following expansion;
\begin{align*}
   & \frac{2 (j+1) \big((t-1)n+1\big)}{((t-1)n+2) \binom{tn}{n}} \sum_{k=\rho n}^{n-1}
   \frac{t}{2 \pi (t-1)} \left(\frac{t^{t}}{(t-1)^{t-1}}\right)^{n} 
   \frac{1}{(t-1)k+1} \frac{1}{\sqrt{k} \sqrt{n-k}} \\
   & = \frac{\sqrt{2} \sqrt{t} \rho \sqrt{n}}{\sqrt{\rule{0mm}{1.5ex}\pi}
   \sqrt{t-1}} \sum_{\frac{k}{n}=\rho}^{1-\frac{1}{n}} 
   \frac{1}{n \left(\frac{k}{n}\right)^{\frac{3}{2}}
   \sqrt{1-\frac{k}{n}}} \left(1+ \mathcal{O}\Big(\frac{1}{n}\Big)\right)
   = \frac{\sqrt{2} \sqrt{t}
   \rho \sqrt{n}}{\sqrt{\rule{0mm}{1.5ex}\pi} \sqrt{t-1}} 
   \int_{x=\rho}^{1} \frac{dx}{x^{\frac{3}{2}} \sqrt{1-x}} + \mathcal{O}(1) \\
   & = \frac{\sqrt{2} \sqrt{t}
   \rho \sqrt{n}}{\sqrt{\pi} \sqrt{t-1}} \left.
   \left(-\frac{2\sqrt{1-x}}{\sqrt{x}}\,\right)\right|_{x=\rho}^{1} + \mathcal{O}(1) =
   \frac{2 \sqrt{2} \sqrt{t} \sqrt{\rule{0mm}{1.5ex}\rho} \sqrt{\mathstrut1-\rho}}
   {\sqrt{\rule{0mm}{1.5ex}\pi} \sqrt{t-1}} \sqrt{n} + \mathcal{O}(1).
\end{align*}

The remainder term leads to the following order estimation;
\begin{align*}
   & \frac{2 (j+1) \big((t-1)n+1\big)}{\big((t-1)n+2\big)
	 \binom{tn}{n}} \sum_{k=\rho n}^{n-1}
   \frac{t}{2 \pi (t-1)} \left(\frac{t^{t}}{(t-1)^{t-1}}\right)^{n} \frac{1}{(t-1)k+1}
   \frac{c_{t}}{\sqrt{k} (n-k)^{\frac{3}{2}}} \\
   & = c n^{\frac{3}{2}} \sum_{k=\rho n}^{n-1}
   \frac{1}{k^{\frac{3}{2}} (n-k)^{\frac{3}{2}}} = c \sum_{k=\rho n}^{n-1}
   \left(\frac{1}{k} + \frac{1}{n-k}\right)^{\frac{3}{2}} 
   \le 2 c \sum_{k=1}^{\frac{n}{2}} 
   \left(\frac{1}{k}+\frac{1}{n-k}\right)^{\frac{3}{2}} 
   \le 2 c \sum_{k=1}^{\frac{n}{2}} 
   \left(\frac{1}{k}+\frac{2}{n}\right)^{\frac{3}{2}} \\
   & \le 2c \sum_{k=1}^{\frac{n}{2}} \left(\frac{2}{k}\right)^{\frac{3}{2}}
   = \mathcal{O}(1).
\end{align*}   

So we have the asymptotic expansion
\begin{equation*}
\frac{2 \, (j+1) \, \big((t-1)n+1\big)}{\big((t-1)n+2\big) \binom{tn}{n}}
   \sum_{\floor{j-1}{t-1}+1 \le k \le n} \frac{1}{(t-1)k+1} 
   \binom{tk}{k} \binom{t(n-k)}{n-k} = 
   \frac{2 \sqrt{2} \sqrt{t} \sqrt{\rule{0mm}{1.5ex}\rho} 
   \sqrt{\mathstrut1-\rho}}{\sqrt{\rule{0mm}{1.5ex}\pi} \sqrt{t-1}}\sqrt{n} 
   + \mathcal{O}(1).
\end{equation*}

An analogous procedure leads to
\begin{align*}
   & \frac{2 \, \big((t-1)n -j +1\big) \, \big((t-1)n+1\big)}
	{\big((t-1)n+2\big) \binom{tn}{n}}
   \sum_{0 \le k \le \floor{j-1}{t-1}} \frac{1}{(t-1)(n-k)+1} 
   \binom{tk}{k} \binom{t(n-k)}{n-k} \\
   & = \frac{2 \sqrt{2} \sqrt{t} \sqrt{\rule{0mm}{1.5ex}\rho} \sqrt{\mathstrut1-\rho}}
   {\sqrt{\rule{0mm}{1.5ex}\pi} \sqrt{t-1}} \sqrt{n} + \mathcal{O}(1).
\end{align*}

So we get finally the asymptotic result for the expectations of the leaf heights in
$t$--ary trees, as it was stated in \cite{Kirschenhofer85}.
\begin{theorem}
   The expectation $\E\left(X_{n,j}\right)$ of the height of the leaf $j$ in a 
   $t$--ary tree with $n$ internal nodes is asymptotically for a fixed ratio
   $\rho = \frac{j}{(t-1)n}$ with $0 < \rho < 1$ for $n \to \infty$ given as
   \begin{equation}
   \E\left(X_{n,j}\right) = \frac{4 \sqrt{2} \sqrt{t} 
   \sqrt{\rule{0mm}{1.5ex}\rho}
   \sqrt{\mathstrut1-\rho}}
	{\sqrt{\rule{0mm}{1.5ex}\pi} \sqrt{t-1}} \sqrt{n} + \mathcal{O}(1).
   \end{equation}
\end{theorem}

\subsection{Higher Moments}

We are also able to find explicit expressions for the higher factorial moments, 
although they are not so nice.

Differentiating $F(z,u,v)$ $s$-times w.r.t. $v$ and evaluating at $v=1$ leads to
\begin{equation*}
   \left.\frac{\partial^{s}}{\partial v^{s}}F(z,u,v)\right|_{v=1} = 
   \frac{s! \big(1-\frac{1-u}{X-uY}\big)^{s}}
   {\big(\frac{1-u}{X-uY}\big)^{s+1}} = 
   \sum_{p=1}^{s+1} (-1)^{s+1-p} s! \binom{s}{p-1} 
   \left(\frac{X-uY}{1-u}\right)^{p}.
\end{equation*}

The coefficients from $\left(\frac{X-uY}{1-u}\right)^{p}$ are obtained as follows.
\begin{align*}
   [z^{n}u^{j}] \left(\frac{X-uY}{1-u}\right)^{p} & = \sum_{l=0}^{p} [z^{n}u^{j}]
   (-1)^{l} \binom{p}{l} \frac{(uY)^{l} X^{p-l}}{(1-u)^{p}} \\
   & = T_{n}^{(p)} \binom{j+p-1}{p-1} + \sum_{l=1}^{p-1} (-1)^{l} \binom{p}{l}
   \sum_{0 \le k \le \floor{j-l}{t-1}} T_{k}^{(l)}\,  T_{n-k}^{(p-l)} 
   \binom{j-l-(t-1)k+p-1}{p-1} .
\end{align*}

Therefore we get
\begin{align*}
  \left.\frac{\partial^{s}}{\partial v^{s}}F(z,u,v)\right|_{v=1} & = 
  \sum_{p=1}^{s+1} (-1)^{s+1-p} s! \binom{s}{p-1} \Bigg[
  T_{n}^{(p)} \binom{j+p-1}{p-1} \\
  & \quad {} + \sum_{l=1}^{p-1} (-1)^{l} \binom{p}{l}
     \sum_{0 \le k \le \floor{j-l}{t-1}} T_{k}^{(l)}\,  T_{n-k}^{(p-l)} 
   \binom{j-l-(t-1)k+p-1}{p-1}
  \Bigg] .
\end{align*}

Hence the higher moments are given by the following theorem.
\begin{theorem}
   The $s$--th factorial moment $\E(X^{\underline{s}}_{n,j})$ of the height
   of the leaf $j$ in a $t$--ary tree with $n$ internal nodes is given by
   \begin{equation}
   \begin{split}
      \E(X^{\underline{s}}_{n,j}) & = \frac{1}{T_{n}}
	    \sum_{p=1}^{s+1} (-1)^{s+1-p} s! \binom{s}{p-1} \Bigg[
	    T_{n}^{(p)} \binom{j+p-1}{p-1} \\
		& \quad {} + \sum_{l=1}^{p-1} (-1)^{l} \binom{p}{l}
	       \sum_{0 \le k \le \floor{j-l}{t-1}} T_{k}^{(l)}\, T_{n-k}^{(p-l)} 
	     \binom{j-l-(t-1)k+p-1}{p-1}
	    \Bigg] .
   \end{split}
   \end{equation}
\end{theorem}

One could work out the asymptotics from this formula, at least for the variance, 
but the computational effort would be considerable, because of the alternating
sign in the inner sum. Since according formul{\ae} are already stated in
\cite{Gutjahr92}, we refrain from doing that. 







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

\bibitem{Fisz63}
M.~Fisz.
\newblock {\em Probability Theory and Mathematical Statistics}.
\newblock John Wiley, 1963.

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

\bibitem{Gutjahr92}
W.~Gutjahr.
\newblock The variance of level numbers in certain families of trees.
\newblock {\em Random Structures and Algorithms}, 3:361--374, 1992.

\bibitem{GuPf92b}
W.~Gutjahr and G.~Pflug.
\newblock The asymptotic distribution of leaf heights in binary trees.
\newblock {\em Graphs and Combinatorics}, 8:243--251, 1992.

\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{Kirschenhofer85}
P.~Kirschenhofer.
\newblock Asymptotische {U}ntersuchungen zur durchschnittlichen {G}estalt
  gewisser {G}raphenklassen.
\newblock In E.~Hlawka, editor, {\em {Z}ahlentheoretische {A}nalysis}, volume
  1114 of {\em Lecture Notes in Mathematics}, pages 40--54, 1985.

\bibitem{PaPr97}
A.~Panholzer and H.~{P}rodinger.
\newblock Descendants and ascendants in binary trees.
\newblock {\em Discrete Mathematics and Theoretical Computer Science},
  1:247--266, 1997.

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

\end{thebibliography}  
\end{document}

