\documentstyle[12pt]{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\comp#1#2{C_{#1,#2}}
\def\compp#1#2{{\cal C}_{#1,#2}(v)}
\def\mom#1#2{D_{#1,#2}}
\def\dilog{\operatorname{dilog}}
\def\var{\operatorname{Var}}
%def\rho{\varrho}
\def\Pr{\operatorname{Pr}}
\def\poch#1#2{#1^{\underline{#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
[types of nodes in uniform binary trees]
{A note on the distribution of the three types of nodes in uniform binary trees}
\author[H.~Prodinger]
{Helmut Prodinger}
\address{  Institut f\"ur Algebra und Diskrete Mathematik\\
Technical University of Vienna\\
Wiedner Hauptstrasse 8--10\\ A-1040 Vienna, Austria.}
\email{Helmut.Prodinger@@tuwien.ac.at\vskip0pt
{\it WWW-address{\rm :\ }}\texttt{http://info.tuwien.ac.at/theoinf/proding.htm}
}


\date{\today}
\begin{abstract}We use Zeilberger's algorithm to compute some sums that came up
in Mahmoud's analysis of the distribution of types of nodes in binary trees. 
\end{abstract} 

\maketitle




In \cite{Mahmoud95}, Mahmoud has considered uniform binary trees (counted by Catalan
numbers $b_n=\frac{1}{n+1}\tbinom{2n}{n} $)  and the three statistics $X_n^{(0)}$,
$X_n^{(1)}$, $X_n^{(2)}$, counting the numbers of internal nodes having 0, 1, 2 internal nodes
as successors, respectively. He obtained the following theorem 
(with  one typo removed):

\begin{theorem} []{\rm [Mahmoud]}
\begin{align*}
\Pr\left\{X_n^{(0)}=j\right\}&=\frac{1}{b_n}\sum_{i=0}^{n-j}(-1)^{n-j-i}b_i
\binom{i+1}{n-i}\binom{n-i}{j} \, ,  \\
\Pr\left\{X_n^{(1)}=j\right\}&=\frac{1}{b_n}\sum_{i=0}^{n-j}(-1)^{n-j-i}2^{n-i}b_i
\binom{n-1}{i-1}\binom{n-i}{j}\, ,\\
\Pr\left\{X_n^{(2)}=j\right\}&=\frac{1}{b_n}
\sum_{k=0}^j(-1)^{j-k}b_k\binom{n-k}{j-k} 
\sum_{i=0}^{n-k}2^{n-k-i}\binom{n-1}{k+i-1}\binom{k+1}{i} \, .
\end{align*}

\end{theorem}

Mahmoud used generating functions to get these results. For convenience, we sketch
how to do it.

The generating function $B(z)$ of the binary trees is normally obtained via
the equation $B=1+zB^2$. However, we can also get it via the equation
$B=1+z+2z(B-1)+z(B-1)^2$. Observe that $B(z)-1$   is the generating function for
the nonempty trees, and the recursion now distinguishes between zero, one, or two
successors. Now, we can use additional variables $u, v, w$ in order to count nodes
with zero, one, or two successors.  Then the equation is
\begin{equation*}   
B=1+zu+2zv(B-1)+zw(B-1)^2\, ,
\end{equation*}
with the solution
\begin{equation*}   
B(z;u,v,w)=\frac{1-2z(v-w)-\sqrt{1-4zv+4z^2(v^2-uw)}}{2zw}\,.
\end{equation*}
Now the probabilities from Theorem 1 are obtained by reading off appropriate coefficients:
\begin{align*}
\Pr\left\{X_n^{(0)}=j\right\}&=\frac{1}{b_n}[z^nu^j]B(z;u,1,1) \, ,  \\
\Pr\left\{X_n^{(1)}=j\right\}&=\frac{1}{b_n}  [z^nv^j]B(z;1,v,1)          \, ,\\
\Pr\left\{X_n^{(2)}=j\right\}&=\frac{1}{b_n}[z^nw^j]B(z;1,1,w)\, .
\end{align*}











With Zeilberger's algorithm {\sc Ekhad} (see \cite{PeWiZe96}), I found the following
explicit formul\ae:

\begin{theorem}
\begin{align*}
\Pr\left\{X_n^{(0)}=j\right\}&=
	 \frac{2^{n+1-2j}(n+1)!\,n!\,(n-1)!}{j!\,(j-1)!\,(n+1-2j)!\,(2n)!}\,,  \\
\Pr\left\{X_{2n+1}^{(1)}=2j\right\}&= 
\frac{2^{2j-1}(2n+2)!\,(2n)!\,(2n)!}{(2j)!\,(n-j+1)!\,(n-j)!\,(4n+1)!}\,,  \\
\Pr\left\{X_{2n}^{(1)}=2j+1\right\}&=
	 \frac{2^{2j+1}(2n+1)!\,(2n)!\,(2n-1)!}{(2j+1)!\,(n-j)!\,(n-j-1)!\,(4n)!}\,,\\  
\Pr\left\{X_n^{(1)}=j\right\}&= 0\quad \text{for $n+j$ even}\,,  \\
\Pr\left\{X_n^{(2)}=j\right\}&= \frac{2^{n-1-2j}(n+1)!\,n!\,(n-1)!}{(j+1)!\,j!\,(n-1-2j)!\,(2n)!}\,.
\end{align*}

\end{theorem}

The quantity 
$$\Pr\left\{X_n^{(0)}=j\right\}b_n=	 \frac{2^{n+1-2j}(n-1)!}{j!\,(j-1)!\,(n+1-2j)!}$$
 is the number of binary trees of size
$n$ and $j$  leaves. It is interesting to compare this quantity with the corresponding one
for planted plane trees; the number of planted plane trees of size $n$ with $j$  leaves is the
{\sl Narayana\/} number 
$$
\frac{1}{n}\binom{n}{j}\binom{n-2}{j-1}=\frac{(n-1)!\,(n-2)!}{j!\,(j-1)!\,(n-1-j)!^2}\,,  
$$ 
see \cite{Kreweras70}.

We provide a glimpse of what Zeilberger's algorithm does. Dealing with the first sum in 
Theorem 1, and setting
\begin{equation*}   
F(n,i):=\frac{1}{b_n}(-1)^{n-j-i}b_i\binom{i+1}{n-i}\binom{n-i}{j} \,,
\end{equation*}
where we treat $j$ as a parameter, the algorithm computes 
\begin{equation*}   
G(n,i):= \frac{(n+2)(n-2i)(n-2i-1)}{2(n+1-i-j)}\,     F(n,i)\,,
\end{equation*}
such that
\begin{multline*}   
(n-2j+2)(2n+1)\,F(n+1,i)-(n+2)n\,F(n,i)=\\
=G(n,i+1)-G(n,i)\,.
\end{multline*}
Denoting the sum on $i$ by $F(n)$ and summing up, the right hand side telescopes, and
we get
\begin{equation*}   
(n-2j+2)(2n+1)\,F(n+1)=(n+2)n\,F(n)\,.
\end{equation*}
Such a {\sl first order recursion\/} can always be solved by {\sl iteration}, leading to the
announced formula.

If we do the same thing for the second sum, we find the recursion
\begin{multline*}   
(2n+3)(2n+1)(n-j+3)(n-j+1)\,F(n+2)=\\
=(n+3)(n+2)(n+1)n\, F(n)\,
\end{multline*}
which is not of first order, but can, because of the lack of the term $F(n+1)$, 
still be solved by iteration.
It turns out that four cases ($n,j$ even or odd) have to be
 distinguished.

The third entry is a double sum and thus not so easily treatable. 
I recently showed it to F.~Chyzak, and he is able to handle it with his package
{\sc mgfun} (see \cite{Chyzak94}).
However, 
because of the following argument, the double sum is reducible to the other instances.
 We will show  that the three statistics are basically
the same. Assume that there are $i$ nodes with 0 successors, $j$ nodes with 1 successor, 
and
$k$ nodes with 2 successors. Then we have by an elementary argument the equations
\begin{align*}
i+j+k&=n\, ,\\
j+2k&=n+1\, ,
\end{align*}
whence $k=i+1$ and furthermore $j=n-2i-1$. Thus, with 

\begin{equation*}   
H(n,j):=\frac{2^{n+1-2j}(n+1)!\,n!\,(n-1)!}{j!\,(j-1)!\,(n+1-2j)!\,(2n)!}\;,
\end{equation*}
we get alternatively
\begin{align*}
\Pr\left\{X_{n}^{(0)}=j\right\}&=H(n,j)	\,,  \\
\Pr\left\{X_{n}^{(1)}=j\right\}&=H(n,\tfrac{n-j+1}{2}), \qquad\text{for $n+j$ is odd}
		 \,,\\  
\Pr\left\{X_n^{(1)}=j\right\}&= 0, \qquad \text{for $n+j$ even}\,,  \\
\Pr\left\{X_n^{(2)}=j\right\}&= H(n,j+1)\,.
\end{align*}

The fact, that the covariance matrix has rank 1 (see \cite{Mahmoud95}) becomes perhaps
a little bit more transparent by this combinatorial argument.

With Zeilberger's algorithm we can do even  more: We can compute the $s$--th factorial moments
explicitly. Let $\poch nk=n(n-1)\dots(n-k+1)$, and
\begin{equation*}   
M_{n;s}^{(i)}:=\sum_j\Pr\left\{X_n^{(i)}=j\right\}\poch js
\end{equation*}
denote the $s$--th factorial moments for $i=0,1,2$, then:
 
\begin{theorem}
\begin{align*}
M_{n;s}^{(0)}&=\frac{(n+1)!\,n!\,(2n-2s)!}{(2n)!\,(n+1-2s)!\,(n-s)!}\,,\\
M_{n;s}^{(1)}&=
\frac{2^{s}\,(n+1)!\,n!\,(n-1)!\,(2n-2s)!}{(2n)!\,(n-s+1)!\,(n-s)!\,(n-s-1)!}
\,,\\
M_{n;s}^{(2)}&=\frac{n!\,(n-1)!\,(2n-2s)!}{(2n)!\,(n-1-2s)!\,(n-s)!}\,.
\end{align*}

\end{theorem}

\bigskip We end this little note by citing two other papers 
(\cite{Kirschenhofer83}, \cite{Ruskey80})
dealing with binary
trees and statistics on the leaves.





\bibliographystyle{plain} 


%\bibliography{pro_bib}

\begin{thebibliography}{1}

\bibitem{Chyzak94}
F.~Chyzak.
\newblock Holonomic systems and automatic proofs of identities.
\newblock Research Report 2371, Institut National de Recherche en Informatique
  et en Automatique, October 1994.

\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{Kreweras70}
G.~Kreweras.
\newblock Sur les \ eventails de segments.
\newblock {\em Cahiers du B.U.R.O}, 15:255--261, 1970.

\bibitem{Mahmoud95}
H.~M. Mahmoud.
\newblock The joint distribution of the three types of nodes in uniform binary
  trees.
\newblock {\em Algorithmica}, 13:313--323, 1995.

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

\bibitem{Ruskey80}
F.~Ruskey.
\newblock On the average shape of binary trees.
\newblock {\em SIAM Journal on Algebraic and Discrete Methods}, 1:43 --50,
  1980.

\end{thebibliography}






\end{document}






