$$n$$ 个结点构成的二叉搜索树的形态总数

$$n$$ 个结点构成的二叉树的形态总数为 $$f_n$$, 首先 $$f(0)=1$$

$$n>0$$ 时，不难得出如下结论

$f_n=\sum_{i=0}^{n-1}f_if_{n-i-1}$

\begin{aligned} F(x)&=\sum_{n=0}^{\infty}f_nx^n\\ &=1+\sum_{n=1}^{\infty}\sum_{i=0}^{n-1}f_if_{n-i-1}x^n\\ &=1+x\left(\sum_{i=0}^{\infty}f_ix^i\right)\left(\sum_{n=0}^{\infty}f_nx^n\right)\\ &=1+xF^2(x) \end{aligned}\tag{1}

\begin{aligned} F(x)={1\pm\sqrt{1-4x}\over 2x}={2\over 1\mp\sqrt{1-4x}} \end{aligned}\tag{2}

$F(x)={2\over 1+\sqrt{1-4x}}$

$F(x)={2\over 1+\sqrt{1-4x}}={1-\sqrt{1-4x}\over 2x}\tag{3}$

\begin{aligned} (1-4x)^{1\over 2}&=\sum_{n=0}^{\infty}{ {1\over 2}\choose n}(-4x)^n\\ &=1+\sum_{n=1}^{\infty}(-1)^{n-1}{(2n-3)!!\over 2^nn!}(-4x)^n\\ &=1-2\sum_{n=1}^{\infty}{(2n-2)!\over n!(n-1)!}x^n \end{aligned}\tag{4}

$$(4)$$ 式代入 $$(3)$$ 式，有

\begin{aligned} F(x)&={1-\sqrt{1-4x}\over 2x}\\ &=\sum_{n=1}^{\infty}{(2n-2)!\over n!(n-1)!}x^{n-1}\\ &=\sum_{n=0}^{\infty}{(2n)!\over n!(n+1)!}x^n \end{aligned}\tag{5}

$f_n={(2n)!\over n!(n+1)!}={ {2n\choose n}\over n+1}\tag{6}$