\documentstyle [12pt,amstex]{article} \def\email#1{\relax}\let\address\email %\www{http://www.tu-graz.ac.at/rote} %\documentstyle {amsart} \input german.sty %%%%%%\selectlanguage{USenglish} \textwidth 15,5 true cm \textheight24 true cm \hoffset -10mm \voffset -25mm \newtheorem{lemma} {Lemma} \newtheorem{theorem} {Theorem} \newtheorem{corollary} {Corollary} \def\proof{\noindent {\em Proof}} \def\affe{@@} \begin{document} \title % [Counting binary trees by degree sequence] %\shorttitle % % {Binary trees having a given number of nodes with 0, 1, and 2~children. %%%%%\\ \em DRAFT --- PLEASE DISTRIBUTE } % \author {G\"unter Rote% % \thanks{Institut f\"ur Mathematik, Technische Universit\"at Graz, Steyrergasse 30, A-8010~Graz, Austria. \hskip0pt plus 20cm\penalty0 \hskip0pt plus -20cm Electronic mail: {\tt rote\protect\affe opt.math.tu-graz.ac.at}. \hskip0pt plus 20cm\penalty0 \hskip0pt plus -20cm World-Wide~Web:~{\tt http://www.tu-graz.ac.at/rote}. }} \address{Institut f\"ur Mathematik (501~B)\\Technische Universit\"at Graz\\ Steyrergasse 30\\A-8010~Graz\\Austria} \email{\tt rote@@opt.math.tu-graz.ac.at} %\www {\tt http://www.tu-graz.ac.at/rote} \date{13. August 1997} \maketitle %\def\Ipe#1{\def\IPEfile{#1}\input{\IPEfile}} %\def\Ipe#1{{\def \makebox (0,0)[lb]##1{\vbox {\hbox {##1}\kern 0pt}}% % \def\IPEfile{#1}\input{\IPEfile}}} \def\qedbox{\vrule width 0.61em depth 0.12em height 0.49em} \def\qed {\ifinner \noalign {\global\dimen1=\prevdepth \ifdim\prevdepth=-1000pt \global\dimen1=0pt \fi \vskip-\dimen1 \nointerlineskip} \omit\span\omit \hfil \vbox to -\dimen1{\vss \hbox to 0pt {\hss \hbox to \hsize{\hfill\qedbox}\hss}}\hfil\crcr % funktionirt auch in \eqalign (nach dem letzten \cr) \else \ifmmode \eqno\qedbox \else \qquad\hbox{}\nobreak\hfill \nopagebreak \qedbox\par \smallskip \fi\fi} \begin{abstract} We give three combinatorial proofs for the number of binary trees having a given number of nodes with 0, 1, and 2~children. We extend these results to ordered trees with given distribution of nodes according to their numbers of children. \end{abstract} \section{Introduction} A {\em binary tree} is either empty, or it consists of a {\em root node\/} and two binary trees, called the left subtree and the right subtree. A nonempty binary tree can also be regarded as a rooted directed tree graph (arborescence) where the outgoing arcs of each node are labeled by distinct labels from the set $\{ {\mathrm L, \mathrm R}\}$. (We take the arcs as directed away from the root.) \begin{theorem} \label{lem-bintrees} The number of binary trees having $i$~nodes with $2$~children, $j$~nodes with $1$~child, and $k=i+1$ nodes without children, is $$ 2^j \binom {2i+j}{j} b_i = \binom {n} {i \ j \ k} \frac{2^j}{n},$$ where $b_i = \binom {2i}{i-1}/i$ is the $i$-th Catalan number and $n=i+j+k$ is the total number of nodes. \end{theorem} Note that $k$ must always equal $i+1$ in a binary tree. Prodinger~\cite{P} recently computed the probability that a random binary tree with $n$ nodes has $i$~nodes with 2~children (and hence $i+1$ nodes without children and $n-2i-1$~nodes with 1~child). Since the total number of binary trees with $n$ nodes is known---it is~$b_n$---, his formulas can be derived easily from the above theorem and vice versa. Prodinger proved his results by simplifying sums of expressions involving binomial coefficients that were derived by Mahmoud~\cite{M}. This paper contains three independent combinatorial proofs of Theorem~\ref{lem-bintrees}. The first proof is very simple; it it based on the fact that nodes with one child don't really add very much to the combinatorial structure of binary trees and can be easily eliminated, thus reducing the problem to the case where $j=0$, for which the answer is known to be the Catalan numbers. The second proof relates the trees to be counted to labeled trees with given vertex degrees; the third proof relates them to integer sequences with certain properties. These sequences can be counted very easily by observing that, in each equivalence class under cyclic rotations, there is precisely one sequence that has the required properties (Rotation Principle). The second and third proofs can be generalized to ordered trees with arbitrary node degrees. \section {The first proof % of Lemma~\protect\ref{lem-bintrees}} --- binary trees} Consider one of the binary trees $B$ which are counted in the theorem. A vertex with 1~child in a binary tree can be eliminated by ``short-cutting'' it, connecting its child directly with its parent. To avoid problems when trying to eliminate the root node in this way, let us attach to $B$ an artificial new root, whose only child is the original root node, thus getting a {\em planted\/} binary tree. Now, by % successively eliminating all $j$ nodes with one child (except the artifical root), we get a unique planted tree $B'$ with the artificial root plus $2i+1$ nodes, each having either 0 or 2 children. (Viewed as graphs, $B$ and $B'$ are homeomorphic.) Each edge of $B'$ corresponds to a chain of one or more edges in $B$. The number of possible trees $B'$ is~$b_i$. To reconstruct $B$ from its transformed tree $B'$, we have to distribute $j$ new nodes over the $2i+1$ edges of~$B'$. There are $\binom {j+2i}{j}$ ways to do this. The factor $2^j$ accounts for the fact that each new node can have either a left child or a right child. \section {The second proof --- $d$-ary trees} The second proof establishes a correspondences with {\em labeled trees\/} with $n$ vertices of given degrees $d_1,\ldots,d_n$, whose number is the multinomial coefficient \begin{equation} \label{eq-lab-trees} \binom {n-2} {d_1-1 \quad d_2-1 \ \cdots \ d_n-1}, \end{equation} see for example Moon~\cite{Moon}. This proof works more generally for $d$-ary trees, and the resulting theorem generalizes Theorem~\ref{lem-bintrees}. A nonempty {\em $d$-ary tree\/} is a rooted directed tree where the (at most~$d$) outgoing arcs of each node are labeled by distinct labels from the set $\{1,\ldots,d\}$. \begin{theorem} \label{th-d-ary} The number of $d$-ary trees with $n$ nodes, having $n_i$ nodes with $i$ children, for $i=0,1,\ldots,d$, is $$ \frac 1n \cdot \binom {n} {n_0 \ n_1 \ \cdots \ n_d} \cdot \textstyle \binom d0 ^{n_0} \binom d1 ^{n_1} \binom d2 ^{n_2} \cdots \binom dd ^{n_d} , $$ if $\sum_{i=0}^d n_ii=n-1$. If this equation does not hold, there are no such trees. \end{theorem} \proof. We augment the $d$-ary tree to a planted tree as in the previous section by adding an artificial root, and then we {\em label} the augmented tree $B$ by giving the special label $0$ to the artificial root, and the labels $(i,1),\ldots,(i,n_i)$ to the nodes with $i$ children, in arbitrary order. This procedure gives rise to a {\em labeled $d$-ary tree}. The number of labeled $d$-ary trees obtained in this way is $n_0!n_1!\ldots n_d!$ times the number of trees that we want to determine. On the other hand, a labeled $d$-ary tree can be constructed from a rooted labeled tree $T$ (viewed as a graph), where $n_0+1$ vertices have degree~1 (including the artificial root), $n_1$ vertices have degree~2, and $n_2$ vertices have degree~3, etc. They have a total of $n+1$ nodes, and by (\ref{eq-lab-trees}), their number is $$\frac{(n-1)!} { 0!^{n_0+1} 1!^{n_1} 2!^{n_2}\ldots d!^{n_d} }.$$ For each such tree, we have to select labels for the arcs going from each node to its children. This can be done in $$ 1^{n_0} \cdot d ^{n_1} \cdot \bigl(d(d-1)\bigr) ^{n_2} \cdots (d!) ^{n_d} = \frac{d!^n} { d!^{n_0} (d-1)!^{n_1} (d-2)!^{n_2}\ldots 0!^{n_d} } $$ ways. %Each tree $B$ can be labeled in $i!j!k!$ different ways. (Remember that each %label corresponds to a specified degree, and the artificial root is %distinguished.) %However, when we swap the two subtrees of a node with one child or two %children, this is not reflected in the labeled tree, where all edges incident %with a vertex are considered as equal. %Therefore, each labeled tree is generated $2^{i+j}$ times. % Putting everything together, we get % %$$\frac{(n-1)!}{2^i} \cdot \frac 1 {i!j!k!} \cdot 2^{i+j}, %$$ which is the second expression of the theorem. %This approach will also extend to ternary and higher trees with given degree %sequences. % the theorem. \qed \begin{corollary} % {\textrm{\cite{d-ary-trees}}} The number of $d$-ary trees with $n$ nodes is $$\binom {dn}{n-1} \frac 1n.$$ \end{corollary} This result was obtained by many authors independently in different forms. For example, Harary, Palmer, and Read~\cite{HPR} considered partitions of a convex polygon into $(d+1)$-gons without introducing additional vertices. Beineke and Pippert~\cite{BP1,BP2} considered partitions of a $d$-ball into $d$-simplices. All these proofs use generating functions. \section {The third proof --- ordered trees} An {\em ordered tree\/} is a rooted tree where the arcs from each node to its children are numbered consecutively starting with~1. So the first child is distinguished from the second child and so on. \begin{theorem} \label{th-ordered} The number of ordered trees with $n$ nodes, having $n_i$ nodes with $i$ children, for $i=0,1,\ldots$, is $$ \frac 1n \binom {n} {n_0 \ n_1 \ n_2 \ \cdots },$$ if $\sum_{i\ge0} n_i(i-1)=-1$. If this equation does not hold, there are no such trees. \end{theorem} % This theorem is equivalent to Theorem~\ref{th-d-ary}, since in a $d$-ary tree the arcs from a node to its $i$ children can be labeled by any subset of $i$ numbers from the set $\{1,\ldots,d\}$, not just by the labels $\{1,\ldots,i\}$. Therefore, to get the number of $d$-ary trees, the number of ordered trees must simply be multiplied by if $\prod_{i=0}^d \binom di ^{n_i}$ to account for the additional choices of labels. Tutte~\cite{Tutte} obtained this result by using generating functions, % Harary in MR32#4044: "elegant and elementary combinatorial methods % using differential calculus" see also Goulden and Jackson~\cite[2.7.7, pp.~112--113] {GJ}. However, we give another completely independent and elementary proof. \proof { \em of Theorem~\ref{th-ordered}.} We construct a bijection between ordered trees and certain sequences of integers. A~{\em preorder traversal\/} of an ordered tree starts at the root, and then successively traverses the first subtree, the second subtree, etc., in preorder. If we note the number of children of each node in preorder, we get a sequence $(c_1,\ldots,c_d)$ containing $n_i$ elements equal to $i$, for $i=0,1,\ldots$. From this sequence, the ordered tree can be uniquely reconstructed: We start at the root and generate its $c_1$ children. Then we go to the first child and add $c_2$ children to it, and so on. When we come to a node with $c_k=0$ children, we backtrack to the next node for which the number of children has not been determined, and generate $c_{k+1}$ children for it. However, not every sequence corresponds to a tree. Consider a sequence starting with $2,0,1,0,0,4,0,\ldots$. After the fourth node has been finished with $c_4=0$ children, there is no fifth node whose number of children is to be determined as $c_5=0$. One can characterize this situation by observing the number $t$ of {\em ``unfinished'' nodes\/} as the construction proceeds. Initially we have $t_0=1$ unfinished node, the root. In the $k$-th step we finish one node by determining its number of children, but we generate $c_k$ new unfinished nodes. Thus, $t_{k}=t_{k-1}-1+c_k$. The construction can go on as long as there is at least one unfinished node, i.e., $t_k\ge 1$, except at the last step, where we have $t_n=0$, by the condition on the numbers $n_i$. This is summarized in the following lemma, where we have for later convenience substituted the sequence $c_k$ by $a_k:=c_k-1$ and replaced $t_k$ by $s_k:=t_k-1$. \begin{lemma} \label{lem-equiv} The number of trees in Theorem~\ref{th-ordered} equals the number of sequences $a_1,\ldots,a_n$ containing $n_i$ elements equal to $i-1$, for $i=0,1,\ldots$, such that the partial sums $s_k=a_1+\cdots+a_k$ are nonnegative, for $k=1,\ldots,n-1$. \qed \end{lemma} The total number of sequences of $n$ elements with $n_i$ elements equal to $i-1$, for $i=0,1,\ldots$, without regarding the nonnegativity condition, is $\binom {n} {n_0 \ n_1 \ n_2 \ \cdots }$. This is by a factor $n$ more than the number that we want. Thus, it appears that one out of $n$ sequences should satisfy the nonnegativity condition of the partial sums. This is proved by the next lemma, which I call the Rotation Principle, in analogy to Andr\'e's Reflection Principle~\cite{Andre}, see~\cite[exercise 5.3.7, pp.~533--534] {GJ}, % Knuth, Fundamental Algorithms, 2nd ed., ex. 2.2.1.4, p.~531 which is another principle that is useful for counting sequences subject to certain geometric restictions on the paths they generate. In contrast to this principle, which is applicable to $\pm1$-sequences (possibly with the inclusion of zeros), the following lemma does not have this restriction. \begin {lemma} [Rotation Principle] \label {rotprin} Consider a sequence $a_1,\ldots,a_n$ of integers with $a_1+\cdots+a_n=-1$. \begin{enumerate} \item \label{1} All $n$ cyclic rotations $a_{j+1},a_{j+2},\ldots,a_n,a_1,\ldots,a_{j}$ are distinct. \item \label{2} Among the $n$ cyclic rotations there is precisely one whose first $n-1$ partial sums are nonnegative. \end{enumerate} \end{lemma} % \begin{figure}[ht] \centering \unitlength=1,4pt \begin{picture}(250,70)(-5,-45) \newdimen\stepsize \stepsize=10sp % ganzzalig \newcount\stepnum \stepnum=\stepsize \newcount\xx \newcount\yy \count\xx=0 \count\yy=0 \def\step #1{ \put(\xx,\yy){\line(1,#1){\stepnum}} \advance\xx by \stepsize \dimen0=#1\stepsize \advance\yy\dimen0 \put(\xx,\yy){\circle*{2,8}} } \thicklines \linethickness {0,3pt} \multiput (-5,20)(0,-10){7}{\line(1,0){250}} \multiput (0,25)(10,0){25}{\line(0,-1){70}} \thicklines \put(\xx,\yy){\circle*{4}} {\linethickness {1pt} \put(\xx,27){\line(0,-1){74}}} %(2,0,1,0,0,4,0,0,3,1,0,0) \step 1 \step {-1} \step 0 \step {-1} \step {-1} \step 3 \step {-1} \step {-1} \step2 \step0 \step {-1} \step {-1} \put(\xx,\yy){\circle*{4}} {\linethickness {1pt} \put(\xx,27){\line(0,-1){74}}} \step 1 \step {-1} \step 0 \step {-1} \step {-1} \step 3 \step {-1} \step {-1} \step2 \step0 \step {-1} \step {-1} \put(\xx,\yy){\circle*{4}} {\linethickness {1pt} \put(\xx,27){\line(0,-1){74}}} % \multiput(50,-20)(2.4,-0.2){83}{\circle*{0.9}} \multiput(50,-20)(-2.4,0.2){25}{\circle*{0.9}} \thinlines \put(46,-23){\line(1,0){112}} \put(158,-23){\line(1,-1){14}} \end{picture} \caption {The path corresponding to two cycles of a sequence.} \label{figrot} \end{figure} % \proof. Let us draw a polygonal path on a plane grid with a sequence of steps in the directions $(1,a_i)$, starting at the point $(0,0)$. Figure~\ref{figrot} shows two consecutive cycles corresponding to the sequence $(1,-1,0,-1,-1,3,-1,-1,2,0,-1,-1)$. %(2,0,1,0,0,4,0,0,3,1,0,0) The sequence goes through the points $(k,s_k)$ and terminates at the point $(n,-1)$. Each successive cycle is shifted by the vector $(n,-1)$. Now, the condition $s_k\ge0$ for $1\le k