Enumeration of the Binary Trees (Catalan numbers).

For each number of nodes, n, there is a certain number of possible binary tree configurations. These numbers form a sequence of integers with respect to n. A useful way to describe an integer sequence is to construct a generating function:
whose coefficients bi are the sequence. B(x) is power series over a purely formal variable x. We are not interested in studying convergence of B(x), etc. The whole point of building it is to figure out the formula for bi. (Also, a closed form expression for B(x), if exists, gives another useful opportunity to study the sequence.)

So the idea is to assume a generic generating function (1) with coefficients representing the number of binary trees. Now we have to find some regularity in the behavior of coefficients.

We can start with analyzing trees with small n. Apparently, b1 is 1, and b2 is 2. The b0 coefficient is somewhat artificial, its the no-nodes tree which is, I guess, the only one. Further analysis gives the following idea: if a binary tree has n nodes, then there must be one node as the root and two subtrees. The total number of nodes in the subtrees must be n-1, and either of them may be empty. Assuming k nodes in the left subtree, the right subtree then has n-k-1 nodes, k going from 0 to n-1. The root node is always there, and therefore the tree configurations differ only by the configuration of subtrees. The total number of possible trees on n nodes can then be expressed as:
This formula expresses the specifics of our problem. The number of terms in (2) varies depending on n. The expression is invalid for n=0; for n=1 we have just one term b0b0; for n=2 there are two terms b0b1 + b1b0. Thus, we can rewrite (2) more accurately as
Substituting (3) into (1), we get

Regretfully, we just claimed that the expression in the brackets is invalid for k = 0. I donít know how to deal with this inconsistency.

The next step is to convert the sum-of-product expression in (4) to an appropriate product-of-sum expression. This operation actually represents the rule of multiplication of polynomials [Henrici, 1982, p 382]:
which should be used in the reverse direction for our purposes.
Multiplication of polynomials (5) may be actually shown to be identical to the operation of convolution if we let n = 2m and pad coefficients pi and qi in (5) with m zeroes so that upper summation limit for ri may be extended to n-1. I had difficulty to use the Convolution Theorem as instructed in the homework problem description, as its description in [Henrici, 1982, p.385] contains the Hadagard product of two Fourier transforms and the conjugate Fourier transform used to speed up the conventional convolution.

In our case p(x) and q(x) are the same B(x). We can now apply the rule (5) in the backward direction to (4) or, better yet, obtain an expression for B(x)2 and compare it to (4):
Comparing (6) to (4), we see that, for the sake of finding the similarity, summation index should be changed from k to k-1:
After multiplying both parts by x:

we need one term with k=0 for the right part to become (4). Adding 1 to both sides,

Two solutions for B(x) in (9) are

The second root turns to infinity when x is 0 so that B(0) does not exist. Therefore we use the first root for further manipulations.

The Binomial Theorem can now be applied to the square root in (10) to reduce it to the form with xk and the coefficients that we are looking for. The Binomial theorem can be written as


Substituting (12) into our valid solution (10), we have

Letís use the term with k=0 to cancel 1 inside the brackets:
Here we used the fact thatis 1. I failed to figure out why this is true.

Changing index k to index n running from 0 to ¥ where k runs from 1 to ¥ , we have

and, therefore,

The final simplifications of the binomial coefficient are identical to the Example 1b.


Henrici, P. Essentials of Numerical Analysis with Pocket Calculator Demonstrations. John Wiley & Sons, NY., 1982.