\documentclass[reqno,11pt]{amsart}

\marginparwidth 0pt 
\oddsidemargin 0 in 
\evensidemargin 0 in 
\marginparsep 0pt
\topmargin -0.3 in 
\textwidth 6in 
\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



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

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

\newcommand\U{{\mathcal{U}}}
\newcommand\E{{\mathcal{E}}}
\newcommand\T{{\mathcal{T}}}
\renewcommand\P{{\mathcal{P}}}
\renewcommand\a{{\bold{a}}}
\newcommand\p{{\bold{p}}}
\newcommand\mcirc{{\bigcirc}}
\newcommand\dilog{\operatorname{dilog}}
\newcommand\C{{\mathcal C}}
\newcommand{\stwo}[2]{\genfrac{\{}{\}}{0pt}{}{#1}{#2}}
\newcommand{\sone}[2]{\genfrac{[}{]}{0pt}{}{#1}{#2}}


\def\cauchy{\frac{1}{2i\pi}}
\def\H{{\mathcal{H}}}
\def\B{{\mathcal{B}}}


\newcommand\bl{\operatorname{L}}


\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}{\section*{\acknoname}}
\newcommand{\acknoname}{Acknowledgement}
\def\endackno{\par}

\renewcommand{\thefootnote}{}

\begin{document}

\author{Alois Panholzer and Helmut Prodinger}
\title[A more precise analysis of an algorithm to generate
binary trees]
{Towards a more precise analysis of an algorithm to generate
binary trees : A tutorial}\footnote{This research was supported by 
the Austrian Research Society (FWF) under the project number \textup{P12599-MAT}}

\date{\today}
\begin{abstract}
For the analysis of an algorithm to generate binary trees 
\cite{XiTaUs97}, the behaviour of a certain sequence of numbers
is essential. In the original paper, it was expressed by a recursion.

Here, we show how to solve this (and similar) recursions, both, 
explicitly and asymptotically.  Some additional information about
useful mathematical software is also provided.
\end{abstract}


\maketitle

%Filename: C:$\backslash$texfiles$\backslash$chinese.tex

\section{Introduction}  

In the analysis of an algorithm to generate binary trees the authors of
\cite{XiTaUs97} came up with a double sequence $g_{n,k}$ and gave a
recursion for it (Theorem 9, with notation changed). The sequence
 $g_{n,0}$ was of particular interest. 

Since there was no analysis provided we think that it is appropriate
to explain here how such recursions can be  treated properly. 
Especially we want to discuss generating functions, explicit forms, 
asymptotic expansions, and convenient Computer software.

It is a little bit nicer to explain things for a slightly modified recursion
that seems to be more natural. However, the original one can be treated
in the same way, as we will also demonstrate.

Here is the recursion:
\begin{equation}   
g_{n,k}=g_{n-1,k-1}+2g_{n-1,k}+g_{n-1,k+1}+1\qquad\text{for }0\le k\le n 
\end{equation}
with the assumption that all values $g_{n,k}$
 outside the range $0\le k\le n $  are zero.

\section{Generating functions}

As in Knuth \cite[page 537]{Knuth68} we set up the generating function
\begin{equation*}   
G(x,z)=\sum_{0\le k\le n }g_{n,k}x^kz^n.
\end{equation*}

Summing up the recursion (multiplied by $x^kz^n$) we find 
\begin{equation*}   
G(x,z)=zxG(x,z)+2zG(x,z)+\frac{z}{x}\big(G(x,z)-g(z)\big)
+\sum_{0\le k\le n }x^kz^n,
\end{equation*}
with $g(z)=G(0,z)$. Note that 

\begin{equation*}   
\sum_{0\le k\le n }x^kz^n=
\sum_{k\ge0}\sum_{j\ge0}x^kz^{k+j}=\frac{1}{1-z}
\sum_{k\ge0}(zx)^k=\frac{1}{(1-z)(1-zx)}.
\end{equation*}
Hence
\begin{equation*}   
G(x,z)=\frac{zg(z)-\frac{x}{(1-z)(1-zx)}}
{zx^2+(2z-1)x+z}
\end{equation*}
Now note that 
\begin{equation*}   
zx^2+(2z-1)x+z=z\big(1-xr_1(z)\big)\big(1-xr_2(z)\big)
\end{equation*}
with
\begin{equation*}   
r_{1,2}(z)=-1+\frac{1\pm\sqrt{1-4z}}{2z}.
\end{equation*}
Now, again as Knuth, we argue that $G(x,z)$ has a power series expansion
in $z$ and $x$. Since the denominator vanishes for
$x=r_2(z)$, the numerator should also vanish, which means
\begin{equation*}   
zg(z)=\frac{r_2(z)}{(1-z)(1-zr_2(z))},
\end{equation*}  
which leads already to the solution
\begin{equation}\label{g_loes}   
g(z)=\frac{r_2(z)}{z(1-z)(1-zr_2(z))}.
\end{equation}  

\section{Explicit expressions}

As it is perhaps not too surprising, there are some close connections with
{\it Catalan numbers}, since
\begin{equation*}   
B(z)=\frac{1-\sqrt{1-4z}}{2z}=\sum_{n\ge0}\frac{1}{n+1}\binom{2n}{n}z^n.
\end{equation*}
Note that
\begin{equation*}   
r_2(z)=-1+B(z)=zB^2(z).
\end{equation*}
There is a convenient method to pull out coefficients, using
(formal) residue calculus, compare e.~g. \cite{BrKnRi72}: On sets
$z=u/(1+u)^2$, then
\begin{equation*}   
g(z)=\left[
\frac{4}{3}\frac{1}{1+2u}-\frac{1}{3}\frac{(1+2u)(1-u)}{1-u^3}
\right](1+u)^6.
\end{equation*} 
Now
\begin{align*}   
[z^n]g(z)&=\frac{1}{2\pi i}\oint\frac{dz}{z^{n+1}}g(z)\\
&=\frac{1}{2\pi i}\oint\frac{du(1-u)(1+u)^{2n+2}}{(1+u)^3u^{n+1}}g\big(z(u)\big)\\
&=[u^n]{(1-u)(1+u)^{2n-1}}g\big(z(u)\big)\\
&=[u^n]{(1-u)(1+u)^{2n-1}}\left[
\frac{4}{3}\frac{1}{1+2u}-\frac{1}{3}\frac{(1+2u)(1-u)}{1-u^3}
\right](1+u)^6\\
&=[u^n]{(1+u)^{2n+5}}\left[
\frac{4}{3}\frac{1-u}{1+2u}-\frac{1}{3}\frac{(1+2u)(1-u)^2}{1-u^3}
\right]\,.
\end{align*}
Note that
\begin{equation*}   
[u^{n-k}](1-u)(1+u)^{2n+5}=2\frac{k+3}{n+k+6}\binom{2n+5}{n-k}
\end{equation*}
and $(1+2u)(1-u)^2=1-3u^2+2u^3$ and further 
\begin{align*}   
[u^{n-3k}]&(1-3u^2+2u^3)(1+u)^{2n+5}\\&=
\frac {2 (3{n}^{2}-54n{k}^{2}-153nk-87n+54{k}^{3}+54{k}^{2}-177k-168)}
{\left (n+8+3k\right )\left (n+7+3k\right )\left (n+6+3k\right )}
\binom{2n+5}{n-3k}.
\end{align*}
Hence
\begin{align}   \begin{split}
[z^n]g(z)&=\frac{8}{3}\sum_{0\le k\le n}(-2)^k
\frac{k+3}{n+k+6}\binom{2n+5}{n-k}\\&+
\frac{2}{3}\sum_{0\le 3k\le n}
{\frac {3{n}^{2}-54n{k}^{2}-153nk-87n+54{k}^{3}+54{k}^{2}-177k-168}
{\left (n+8+3k\right )\left (n+7+3k\right )\left (
n+6+3k\right )}}\binom{2n+5}{n-3k} \, .
   \end{split}\end{align}
This is admittedly not too nice, but it has only one (level of) summation, and
we cannot hope to do better than that.

Another approach would be based on the formula
\begin{equation*}   
g(z)=\frac{1}{z^2(1-z)}\sum_{k\ge1}\big(zB(z)\big)^{2k},
\end{equation*}
but that would lead to a double summation of the coefficients.

\section{Asymptotics}

The explicit form (\ref{g_loes}) 
suggests to expand $g(z)$ around its (dominant) singularity
$z=\frac14$, viz.
\begin{equation*}   
g(z)\sim \frac{64}{9}-\frac{512}{27}\sqrt{1-4z},
\end{equation*} 
with more terms available.

Now singularity analysis of generating functions \cite{FlOd90} tells us
that
\begin{equation*}   
g_{n,0}=[z^n]g(z)\sim \frac{256}{27\sqrt{\pi}}\,4^n\,n^{-3/2}.
\end{equation*}

   \section{A recursion}

   With Zeilberger's algorithm \cite{PeWiZe96} we can first {\it guess \/}
   a linear recursion with polynomial coefficients for the values
   $g_{n} := g_{n,0}$, which can be {\it proved\/} afterwards, just by looking at
   the corresponding linear differential equation with polynomial
   coefficients for the generating function $g(z)$.
                     
   In this manner we get for $g_{n}$ the recursion
   \begin{equation*}
      ( n+6) g_{n+3} + (\tfrac{9}{2} n-21) g_{n+2}
	+ (\tfrac{3}{2} n+6) g_{n+1}
	+( 2n+9) g_{n}  
	    = 0
   \end{equation*}
    with initial values $g_{0}=1$, $g_{1}=3$ and $g_{2}=9$.

   The corresponding differential equation for $g(z)$ can be written as
   \begin{equation*}
      \frac{1}{2} z (z-1)(z+2)(4z-1) g'(z) +
      \frac{1}{2} (18z^{3}+9z^{2}-24z+6) g(z) -3 = 0
   \end{equation*}
   with initial condition $g(0) = 1$. Now this differential equation
	can be solved (or, we might just check that its solution is
	(\ref{g_loes}))
   and therefore the validity of the above recursion is easily verified.

	A very useful tool in this context is the program {\sc Gfun} \cite{SaZi94}.
It would also guess the above recursion, based on the first few values. Or, it would
transform the explicit form of $g(z)$ into an algebraic equation for it, and this 
equation into an equivalent differential equation, from which the recursion with
polynomial coefficients would be available. 

   \section{The original recursion}

   The original recursion from \cite{XiTaUs97} that we want to treat is
   \begin{equation}   
      \widetilde{g}_{n,k}=\widetilde{g}_{n-1,k-1}+2\widetilde{g}_{n-1,k}+
      \widetilde{g}_{n-1,k+1}+1\quad\text{for }
      0\le k < n \; \text{and} \; n \ge 2
   \end{equation}
   with the assumption that all other values $\widetilde{g}_{n,k}$ are zero.

   When we introduce the bivariate generating function
   \begin{equation*}   
      \widetilde{G}(x,z)=\sum_{0\le k\le n }\widetilde{g}_{n,k}x^kz^n \, ,
   \end{equation*}
   this recursion leads by multiplication with $z^{n}x^{k}$ and
   summing up to the equation
   \begin{equation*}   
      G(x,z)=zxG(x,z)+2zG(x,z)+\frac{z}{x}\big(G(x,z)-g(z)\big)
      +\sum_{\stackrel{0\le k < n,}{n \ge 2}}x^kz^n,
   \end{equation*}
   with $\widetilde{g}(z)=\widetilde{G}(0,z)$. Of course we have
   \begin{equation*}   
      \sum_{\stackrel{0\le k < n,}{n \ge 2} }x^kz^n=
      \sum_{0 \le k<n} x^{k}z^{n} - z = \frac{1}{(1-z)(1-xz)}
      - \frac{1}{1-xz} - z \, .
   \end{equation*}
      This leads to the relation
   \begin{equation*}
      \widetilde{G}(z,u) = \frac{z \widetilde{g}(z) - \frac{x}{(1-z)(1-xz)} +
      \frac{x}{1-xz}+xz}{zx^{2}+(2z-1)x+z} \, .
   \end{equation*}
   Analogously to the previous derivation we get the solution 
   for $\widetilde{g}(z)$:
   \begin{equation*}
      \widetilde{g}(z) = \frac{r_{2}(z)}{(1-z)(1-z r_{2}(z))} -
      \frac{r_{2}(z)}{z(1-z r_{2}(z)} - r_{2}(z) \, .
   \end{equation*}
   To get an explicit expression for the coefficients of
   $\widetilde{g}(z)$ we also need
   \begin{equation*}
      [z^{n}] r_{2}(z) = \frac{1}{n+1} \binom{2n}{n} \quad \text{for } n \ge 1 
   \end{equation*}
   and
   \begin{equation*}
      [z^{n}] \frac{r_{2}(z)}{z (1-z r_{2}(z))} =
      [u^{n}] (1-u)(1+u)^{2n-1} \frac{(1+u)^{4}}{2u-1} \, .
   \end{equation*}
   This yields
   \begin{equation*}
      [z^{n}] \frac{r_{2}(z)}{z (1-z r_{2}(z))} =
      [u^{n}] \frac{(1-u)(1+u)^{2n+3}}{2u+1} = \sum_{0 \le k \le n}
      (-2)^{k} \frac{2k+4}{n+k+4} \binom{2n+3}{n-k} \, .
   \end{equation*}

   Combining the above formul{\ae} we thus get
	 an explicit expression for the coefficients of
   $\widetilde{g}(z)$ and therefore for the required parameter.
   For $n \ge 1$ we have
      \begin{align}   \begin{split}
      [z^n]\widetilde{g}(z)&=\frac{8}{3}\sum_{0\le k\le n}(-2)^k
      \frac{k+3}{n+k+6}\binom{2n+5}{n-k} - \sum_{0\le k \le n} (-2)^{k}
      \frac{2k+4}{n+k+4} \binom{2n+3}{n-k} - \frac{1}{n+1} \binom{2n}{n} \\
      &+ \frac{2}{3}\sum_{0\le 3k\le n}
      {\frac {-87n-177k+3{n}^{2}+54{k}^{3}+54{k}^{2}-54n{k}^
      {2}-168-153nk}{\left (n+8+3k\right )\left (n+7+3k\right )\left (
      n+6+3k\right )}}\binom{2n+5}{n-3k} \, .
   \end{split}\end{align}                       

   To evaluate this expression asymptotically, we expand
   $\widetilde{g}(z)$ around its algebraic singularity $z=\frac{1}{4},$
   and we obtain
   \begin{equation*}
      \widetilde{g}(z) \sim \frac{7}{9} - \frac{74}{27} \sqrt{1-4z\,} \, ,
   \end{equation*}
   which leads to
   \begin{equation*}
      [z^{n}] \widetilde{g}(z) \sim \frac{37}{27 \sqrt{\pi}} 4^{n} n^{-3/2} \, .
   \end{equation*}
   
   It is also of interest to present a linear recursion with polynomial 
   coefficients for the numbers $\widetilde{g}_{n} := \widetilde{g}_{n,0}$. We get 
   here
   \begin{equation*}
   \begin{split}
      0 & = {} \frac{1}{17}\left(n+6\right )\left (17n+25\right )
	  \widetilde{g}_{n+4}-{\frac {1}{238}}\left (1357{n}^{2}+7775n+7890\right )
	  \widetilde{g}_{n+3} \\
	  & \quad + {\frac {3}{119}}\left (274{n}^{2}+941n+605\right ) 
	  \widetilde{g}_{n+2}+{\frac {1}{238}}\left (47{n}^{2}+1897n+2790\right )
	  \widetilde{g}_{n+1} \\
	  & \quad {} -{\frac {1}{119}}\,\left (143n+315\right )\left (2n+1\right ) 
	  \widetilde{g}_{n} \, .
   \end{split}	  
   \end{equation*}
   
   This assertion can be proved by translating the recursion for 
   $\widetilde{g}_{n}$ to the corresponding differential equation for the
   generating function $\widetilde{g}(z)$. The validity of the resulting equation
   \begin{equation*}
   \begin{split}
      0 & = {}{z}^{2} (143z-119  ) (z-1 )
	   (4z-1 ) (z+2 ) \widetilde{g}''(z) \\
	  & \quad +2 z 
	(1059{z}^{4}-925      {z}^{3}-357{z}^{2}+495z-56 )
	 \widetilde{g}'(z) \\
	  & \quad {} +2 (315{z}^{4}-470{z}^{3}+543{z}^{2}-1611z+602 )
	  \widetilde{g}(z) -6{z}^{2} (105{z}^{2}-128z+84 )
   \end{split}	  
   \end{equation*}
   is then easy to check.


\section{Some numerical data}

The following Table \ref{tab1} contains 
the analysed parameters $g_{n}$ and $\widetilde{g}_{n}$ for a few values
of $n$. We compare the 
exact values with the asymptotic equivalents
$a_{n} := \frac{256}{27 \sqrt{\pi} \,} 4^{n} n^{-3/2}$ resp.\
$\widetilde{a}_{n} := \frac{37}{27 \sqrt{\pi} \,} 4^{n} n^{-3/2}$, and give 
also the ratios $\frac{g_{n}}{a_{n}}$ and 
$\frac{\widetilde{g}_{n}}{\widetilde{a}_{n}}$.

\begin{table}[p]

\tabcolsep4mm
\arraycolsep4mm

\begin{center}
 
\begin{tabular}{ | c | c | c | c | c | }
%
% 1. Zeile
%
   \cline{2-5}
   \multicolumn{1}{c|}{ \rule[-1.7ex]{0mm}{5ex} } 
   & 
   $g_{n}$    
   & 
   $\widetilde{g}_{n}$   
   &
   $\frac{g_{n}}{a_{n}}$
   &
   $\frac{\widetilde{g}_{n}}{\widetilde{a}_{n}}$
   \\
%
% 2. Zeile
%   
   \hline
   \rule[-1.2ex]{0mm}{4ex}
   $0$
   &
   $1$
   &
   $0$
   &
   &
   \\
%
% 3. Zeile
%   
   \hline
   \rule[-1.2ex]{0mm}{4ex}
   $1$
   &
   $3$
   &
   $0$
   &
   $0.140$
   &
   $0$
   \\   
%
% 4. Zeile
%
   \hline
   \rule[-1.2ex]{0mm}{4ex}
   $2$
   &
   $9$
   &
   $1$
   &
   $0.298$
   &
   $0.228$
   \\
%
% 5. Zeile
%   
   \hline
   \rule[-1.2ex]{0mm}{4ex}
   $3$
   &
   $27$
   &
   $4$
   &
   $0.407$
   &
   $0.419$
   \\
%
% 6. Zeile
%
   \hline
   \rule[-1.2ex]{0mm}{4ex}
   $4$
   &
   $84$
   &
   $13$
   &
   $0.489$
   &
   $0.524$
   \\
%
% 7. Zeile
%
   \hline
   \rule[-1.2ex]{0mm}{4ex}
   $5$
   &
   $270$
   &
   $42$
   &
   $0.550$
   &
   $0.594$
   \\
%
% 8. Zeile
%
   \hline
   \rule[-1.2ex]{0mm}{4ex}
   $6$
   &
   $892$
   &
   $138$
   &
   $0.599$
   &
   $0.642$
   \\
%
% 9. Zeile
%
   \hline
   \rule[-1.2ex]{0mm}{4ex}
   $7$
   &
   $3012$
   &
   $463$
   &
   $0.638$
   &
   $0.675$
   \\
%
% 10. Zeile
%
   \hline
   \rule[-1.2ex]{0mm}{4ex}
   $8$
   &
   $10350$
   &
   $1582$
   &
   $0.666$
   &
   $0.706$
   \\
%
% 11. Zeile
%
   \hline
   \rule[-1.2ex]{0mm}{4ex}
   $9$
   &
   $36074$
   &
   $5488$
   &
   $0.696$
   &
   $0.727$
   \\
%
% 12. Zeile
%
   \hline
   \rule[-1.2ex]{0mm}{4ex}
   $10$
   &
   $127218$
   &
   $19278$
   &
   $0.716$
   &
   $0.749$
   \\
%
% 13. Zeile
%
   \hline
   \rule[-1.2ex]{0mm}{4ex}
   $20$
   &
   $0.551 \cdot 10^{11}$
   &
   $0.818 \cdot 10^{10}$
   &
   $0.838$
   &
   $0.862$
   \\
%
% 14. Zeile
%
   \hline
   \rule[-1.2ex]{0mm}{4ex}
   $50$
   &
   $0.178 \cdot 10^{29}$
   &
   $0.261 \cdot 10^{28}$
   &
   $0.926$
   &
   $0.938$
   \\
%
% 15. Zeile
%
   \hline
   \rule[-1.2ex]{0mm}{4ex}
   $100$
   &
   $0.828 \cdot 10^{58}$
   &
   $0.120 \cdot 10^{58}$
   &
   $0.961$
   &
   $0.968$
   \\
%
% 16. Zeile
%
   \hline
   \rule[-1.2ex]{0mm}{4ex}
   $200$
   &
   $0.479 \cdot 10^{118}$
   &
   $0.695 \cdot 10^{117}$
   &
   $0.980$
   &
   $0.983$
   \\
%
% 17. Zeile
%
   \hline
   \rule[-1.2ex]{0mm}{4ex}
   $500$
   &
   $0.509 \cdot 10^{298}$
   &
   $0.736 \cdot 10^{297}$
   &
   $0.990$
   &
   $0.994$
   \\
   \hline
\end{tabular}   

\end{center}

\caption{\label{tab1}}

\end{table}

\bibliographystyle{plain}

%\bibliography{pro_bib}


\begin{thebibliography}{1}

\bibitem{BrKnRi72}
N.~G. De~Bruijn, D.~E. Knuth, and S.~O. Rice.
\newblock The average height of planted plane trees.
\newblock In R.~C. Read, editor, {\em Graph Theory and Computing}, pages
  15--22. Academic Press, 1972.

\bibitem{FlOd90}
P.~Flajolet and A.~Odlyzko.
\newblock Singularity analysis of generating functions.
\newblock {\em SIAM Journal on Discrete Mathematics}, 3:216--240, 1990.

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

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

\bibitem{SaZi94}
B.~Salvy and P.~Zimmermann.
\newblock {GFUN}: a {Maple} package for the manipulation of generating and
  holonomic functions in one variable.
\newblock {\em ACM Transactions on Mathematical Software}, 20(2):163--167,
  1994.

\bibitem{XiTaUs97}
L.~Xiang, C.~Tang, and K.~Ushijima.
\newblock Grammar--oriented enumeration of binary trees.
\newblock {\em The Computer Journal}, 40:278--291, 1997.

\end{thebibliography}




\end{document}

