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} \]
本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用