（不同二叉树的数目）设bn表示含有n个节点的不同二叉..._

（不同二叉树的数目）设b_n表示含有n个节点的不同二叉树的数目。在本题中，试给出一个求b_n的公式和一个渐近估计。

a.证明：b₀=1且对 $n\geq1$ ，有

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

b.设B(x)是下面的生成函数：

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

其中，生成函数定义为：生成函数F定义为：

$F(z)=\sum_{i=0}^{\infty}{F_{i}z^{i}}=0+z+z^{2}+2z^{3}+3z^{4}+5z^{5}+8z^{6}+13z^{7}+21z^{8}+....$ ，其中F_i为第i个斐波拉契数。

证明：B(x)=xB²(x)+1，因此以闭形式表示B(x)的一种方式是：

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

f(x)在点x=a出的泰勒展开式（Taylor expansion）为

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

这里f^(k)(x)是在x处的k阶导数。

c.使用 $\sqrt{1-4x}$ 在x=0处的泰勒展开式，证明：

（即第n个Catalan数）。（如果读者愿意，可以不用泰勒展开式，而是将二项展开式推广到非整数的指数上去，也就是对于任何实数n和任何整数k，当 $k\geq 0$ 时，

可以表示为n(n-1)...(n-k+1)/k!，否则为0）

d.证明： $b_{n}=\frac{4^{n}}{\sqrt{\pi}n^{+}}(1+O(1/n))$ 。

（不同二叉树的数目）设bn表示含有n个节点的不同二叉...