问：求不同二叉树的数目。

设 $b_n$ 表示含有 $n$ 个结点的不同二叉树的数目。

有：

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

设 $B(x)$ 为生成函数：

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

可以证明 $B(x) = xB(x)^2 + 1$。证明 $B(x) = xB(x)^2 + 1$ 的过程如下：

$$ \begin{aligned}B(x)^2 &= \bigl(b_0 x^0 + b_1 x^1 + b_2 x^2 + \cdots \bigr)^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 \\[6pt]&= 1 + b_1 x^1 + b_2 x^2 + b_3 x^3 + \cdots \\[6pt]&= b_0 x^0 + b_1 x^1 + b_2 x^2 + b_3 x^3 + \cdots \\[6pt]&= \sum_{n=0}^{\infty} b_n x^n \\[6pt]&= B(x).\end{aligned} $$

因此，可得：

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

由 $f(x)$ 在 点 $x = a$ 处的泰勒展开式

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

可得：$\sqrt{1 - 4x}$ 在 $x = 0$ 处的泰勒展开式为

$$ \sqrt{1 - 4x} = \sum_{n=0}^{\infty} \binom{\tfrac{1}{2}}{n} (-4x)^n = 1 - 2x - 2x^2 - 4x^3 - 10x^4 - 28x^5 - \cdots $$

系数是，

$$ a_0 = 1 \\ \\ a_n = - \frac{2(2n-2)!}{(n-1)! \, n!}, \quad n \geq 1 $$

由此，

$$ B(x) = \frac{1}{2x} \left( 1 - f(x) \right)= 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} \cdot \frac{(2n)!}{n! \, n!} x = \sum_{n=0}^\infty \frac{1}{n+1} \binom{2n}{n} x $$