12-4 Number of different binary trees

Let $b_n$ denote the number of different binary trees with $n$ nodes. In this problem, you will find a formula for $b_n$, as well as an asymptotic estimate.

a. Show that $b_0 = 1$ and that, for $n \ge 1$,

$$b_n = \sum_{k = 0}^{n - 1} b_k b_{n - 1 - k}.$$

b. Referring to Problem 4-4 for the definition of a generating function, let $B(x)$ be the generating function

$$B(x) = \sum_{n = 0}^\infty b_n x^n.$$

Show that $B(x) = xB(x)^2 + 1$, and hence one way to express $B(x)$ in closed form is

$$B(x) = \frac{1}{2x} (1 - \sqrt{1 - 4x}).$$

The Taylor expansion of $f(x)$ around the point $x = a$ is given by

$$f(x) = \sum_{k = 0}^\infty \frac{f^{(k)}(a)}{k!} (x - a)^k,$$

where $f^{(k)}(x)$ is the $k$th derivative of $f$ evaluated at $x$.

c. Show that

$$b_n = \frac{1}{n + 1} \binom{2n}{n}$$

(the $n$th Catalan number) by using the Taylor expansion of $\sqrt{1 - 4x}$ around $x = 0$. (If you wish, instead of using the Taylor expansion, you may use the generalization of the binomial expansion (C.4) to nonintegral exponents $n$, where for any real number $n$ and for any integer $k$, we interpret $\binom{n}{k}$ to be $n(n - 1) \cdots (n - k + 1) / k!$ if $k \ge 0$, and $0$ otherwise.)

d. Show that

$$b_n = \frac{4^n}{\sqrt{\pi}n^{3 / 2}} (1 + O(1 / n)).$$

a. A root with two subtree.

b.

$$ \begin{aligned} B(x)^2 & = (b_0 x^0 + b_1 x^1 + b_2 x^2 + \cdots)^2 \\ & = b_0^2 x^0 + (b_0 b_1 + b_1 b_0) x^1 + (b_0 b_2 + b_1 b_1 + b_2 b_0) x^2 + \cdots \\ & = \sum_{k = 0}^0 b_k b_{0 - k} x^0 + \sum_{k = 0}^1 b_k b_{1 - k} x^1 + \sum_{k = 0}^2 b_k b_{2 - k} x^2 + \cdots \end{aligned} $$

$$ \begin{aligned} xB(x)^2 + 1 & = 1 + \sum_{k = 0}^0 b_k b_{1 - 1 - k} x^1 + \sum_{k = 0}^2 b_k b_{2-1 - k} x^3 + \sum_{k = 0}^2 b_k b_{3-1 - k} x^2 + \cdots \\ & = 1 + b_1 x^1 + b_2 x^2 + b_3 x^3 + \cdots \\ & = b_0 x^0 + b_1 x^1 + b_2 x^2 + b_3 x^3 + \cdots \\ & = \sum_{n = 0}^\infty b_n x^n \\ & = B(x). \end{aligned} $$

$$ \begin{aligned} x B(x)^2 + 1 & = x \cdot \frac{1}{4x^2} (1 + 1 - 4x - 2\sqrt{1 - 4x}) + 1 \\ & = \frac{1}{4x} (2 - 2\sqrt{1 - 4x}) - 1 + 1 \\ & = \frac{1}{2x} (1 - \sqrt{1 - 4x}) \\ & = B(x). \end{aligned} $$

c. Let $f(x) = \sqrt{1 - 4x}$, the numerator of the derivative is

$$ \begin{aligned} 2 \cdot (1 \cdot 2) \cdot (3 \cdot 2) \cdot (5 \cdot 2) \cdots & = 2^k \cdot \prod_{i = 0}^{k - 2} (2k + 1) \\ & = 2^k \cdot \frac{(2(k - 1))!}{2^{k - 1}(k - 1)!} \\ & = \frac{2(2(k - 1))!}{(k - 1)!}. \end{aligned} $$

$$f(x) = 1 - 2x - 2x^2 - 4 x^3 - 10x^4 - 28x^5 - \cdots.$$

The coefficient is $\frac{2(2(k - 1))!}{k!(k - 1)!}$.

$$ \begin{aligned} B(x) & = \frac{1}{2x}(1 - f(x)) \\ & = 1 + x + 2x^2 + 5x^3 + 14x^4 + \cdots \\ & = \sum_{n = 0}^\infty \frac{(2n)!}{(n + 1)!n!} x \\ & = \sum_{n = 0}^\infty \frac{1}{n + 1} \frac{(2n)!}{n!n!} x \\ & = \sum_{n = 0}^\infty \frac{1}{n + 1} \binom{2n}{n} x. \end{aligned} $$

$$b_n = \frac{1}{n + 1} \binom{2n}{n}.$$

d.

$$ \begin{aligned} b_n & = \frac{1}{n + 1} \frac{(2n)!}{n!n!} \\ & \approx \frac{1}{n + 1} \frac{\sqrt{4 \pi n}(2n / e)^{2n}}{2 \pi n (n / e)^{2n}} \\ & = \frac{1}{n + 1} \frac{4^n}{\sqrt{\pi n} } \\ & = (\frac{1}{n} + (\frac{1}{n + 1} - \frac{1}{n})) \frac{4^n}{\sqrt{\pi n}} \\ & = (\frac{1}{n} - \frac{1}{n^2 + n}) \frac{4^n}{\sqrt{\pi n}} \\ & = \frac{1}{n} (1 - \frac{1}{n + 1}) \frac{4^n}{\sqrt{\pi n}} \\ & = \frac{4^n}{\sqrt{\pi}n^{3 / 2}} (1 + O(1 / n)). \end{aligned} $$