hexo的latex语法比较难搞，可以参见https://segmentfault.com/a/1190000011267196
1. 来源：LeetCode 96 - Unique Binary Search Trees
Given n, how many structurally unique BST’s (binary search trees) that store values 1…n?
For example,
Given n = 3, there are a total of 5 unique BST’s.
2
3
4
5
6
> \ / / / \ \
> 3 2 1 1 3 2
> / / \ \
> 2 1 2 3
>
2. 分析
假设有 $n$ 个 node，排序后的序列为 ($x_1, x_2, \dots, x_n$)。假设其可构造成 $f(n)$ 个不同的 BST。
- 若 $n=0$，唯一解为空树，即 $f(0)=1$。
- 若 $n>0$，一共有 n 种情况：
- 选 $x_1$ 做 root，使其左子树为空，右子树为剩下 $n-1$ 个 node 的构造 BST，问题转换为 $n-1$ 个 node 的构造 BST 有多少个解，即 $f(1)=f(0) f(n-1)$；
- 选 $x_2$ 做 root，使其左子树为 $x_1$，右子树为剩下 $n-2$ 个 node 的构造 BST，问题转换为 $n-1$ 个 node 的构造 BST 有多少个解，即 $f(2)=f(1)f(n-2)$；
- 选 $x_k(1\leq k \leq n)$ 做 root，其左子树共有 $f(k-1)$ 种可能，右子树有 $f(n-k)$ 种可能，即 $f(k)=f(k-1)f(n-k)，(k > 0)$。
由此得到
$$
f(n) =
\begin{cases}
1, & n=0 \
f(0)f(n-1) + \dots + f(n-1)f(0) = \sum_{k=1}^n f(k-1)f(n-k), & n>0
\end{cases}
\tag{1}
$$
3. 递推公式
令生成函数
$$
\begin{equation}
\begin{split}
g(x)&= \sum_{k=1}^{\infty}f(k-1)x^k\
&=f(0)x + f(1)x^2 + f(2)x^3 + \dots + f(n-1)x^n + \dots
\end{split}
\tag{2}
\end{equation}
$$
则
$$
\begin{split}
[g(x)]^2 &= f^2(0)x^2 \
&+ [f(0)f(1) + f(1)f(0)]x^3 \
&+ [f(0)f(2) + f^2(1) + f(2)f(0)]x^4 \
&+ \dots \
&+ [f(0)f(n-1) + f(1)f(n-2) + … + f(n-1)f(0)]x^n \
&+ \dots
\end{split}
$$
代入 $f(0) = 1$，$f(1) = 1$ 和 $f(n)$ 的递推公式，得到
$$
\begin{equation}
\begin{split}
[g(x)]^2 &= x^2 + f_2x^3 + f_3x^4 + … + f_{n-1}x^n \
&= g(x) - x
\end{split}
\tag{3}
\end{equation}
$$
解这个方程，其两个根为
$$
g_1(x)=\frac{1 + \sqrt{1-4x}}{2}, g_2(x)=\frac{1 - \sqrt{1-4x}}{2}
$$
由于 $g(0)=0$，验证得仅 $g_2(x)$ 成立，所以
$$
g(x)=g_2(x)=\frac{1}{2} - \frac{1}{2}(1-4x)^{\frac{1}{2}}
\tag{4}
$$
4. 牛顿二项式展开
根据牛顿二项式定理
$$
(x+y)^n = \sum_{k=0}^{n}\binom{n}{k}x^{n-k}y^{k}，其中\binom{n}{k}=\frac{n!}{k!(n-k)!}
\tag{5}
$$
当 $n$ 不是正整数时，$k$ 无法正好求和到 $n$，因此将一直求和至正无穷，这样形式上就得到了广义二项式定理:
$$
(x+y)^{\alpha} = \sum_{k=0}^{\infty}\binom{\alpha}{k}x^{\alpha-k}y^k
\tag{6}
$$
其中
$$
\binom{\alpha}{k}=\frac{\alpha(\alpha-1)\dots(\alpha-k+1)}{k!} \tag{7}
$$
是形式上的组合数。实际上广义二项式定理并非总是成立，因为等式右边不一定收敛。
其常见形式为
$$
\begin{equation}
\begin{split}
(1+z)^{\alpha} &= \sum_{k=0}^{\infty}\binom{\alpha}{k}z^{k} \
& = 1+ \sum_{k=1}^{\infty}\binom{\alpha}{k}z^{k}, (|z|<1)
\end{split}
\tag{8}
\end{equation}
$$
现考察 $\alpha=\frac{1}{2}$ 的情况，有
$$
\begin{equation}
\begin{split}
\binom{\alpha}{k}&=\frac{\frac{1}{2}(\frac{1}{2}-1)(\frac{1}{2}-2)\dots(\frac{1}{2}-k+1)}{k!} \
& = \frac{(-1)^{k-1}}{2^k}\frac{1 \times 3 \times 5 \times \dots \times (2k-3)}{k!} \
& = \frac{(-1)^{k-1}}{2^k}\frac{1 \times 2 \times 3 \times \dots \times(2k-3) \times (2k-2)}{2 \times 4 \times \dots \times (2k-2) \times k! } \
& = \frac{(-1)^{k-1}}{2^k}\frac{(2k-2)!}{2^{k-1}(k-1)!k!} \
& = \frac{(-1)^{k-1}}{k \times 2^{2k-1}} \frac{(2k-2)!}{[(k-1)!]^2} \
& = \frac{(-1)^{k-1}}{k \times 2^{2k-1}} \binom{2k-2}{k-1}, (k > 0)
\end{split}
\tag{9}
\end{equation}
$$
因此，
$$
(1+z)^{\alpha} = 1+\sum_{k=1}^{\infty}\frac{(-1)^{k-1}}{k \times 2^{2k-1}} \binom{2k-2}{k-1}z^{k}, (|z|<1)
\tag{10}
$$
5. 回到 $g(x)$
令上式中的 $z=-4x$，即得到
$$
\begin{equation}
\begin{split}
g(x)&=\frac{1}{2} - \frac{1}{2}(1-4x)^{1/2} \
&=\frac{1}{2}-\frac{1}{2}[1+\sum_{k=1}^{\infty}\frac{(-1)^{k-1}}{k \times 2^{2k-1}} \binom{2k-2}{k-1}(-4x)^{k}] \
&=\sum_{k=1}^{\infty}\frac{1}{k}\binom{2k-2}{k-1}x^k, (|x|<\frac{1}{4})
\end{split}
\tag{11}
\end{equation}
$$
又因为按照定义 $g(x)= \sum_{k=1}^{\infty}f(k-1)x^k$，所以
$$
\begin{equation}
\begin{split}
f(n-1)&=\frac{1}{n}\binom{2n-2}{n-1}, n>1
\end{split}
\end{equation}
$$
或写为
$$
\begin{equation}
\begin{split}
f(n)&=\frac{1}{n+1}\binom{2n}{n}, n>0
\end{split}
\tag{12}
\end{equation}
$$
此即卡特兰数（Catalan Number）的通项公式。递归计算时可采用
$$
f(n+1) = \frac{2(2n+1)}{n+2}f(n)
\tag{13}
$$
6. 卡特兰数的应用
- 括号化问题。矩阵链乘： $P=A1×A2×A3×\dots×An$，依据乘法结合律，不改变其顺序，只用括号表示成对的乘积，试问有几种括号化的方案？
- 将多边行划分为三角形问题。将一个凸多边形区域分成三角形区域（划分线不交叉）的方法数？类似：在圆上选择 2n 个点，将这些点成对连接起来使得所得到的 n 条线段不相交的方法数？
- 出栈次序问题。
- 一个栈（无穷大）的进栈序列为 1,2,3,…,n，有多少个不同的出栈序列？
- 有 2n 个人排成一行进入剧场。入场费 5 元。其中只有 n 个人有一张 5 元钞票，另外 n 人只有 10 元钞票，剧院无其它钞票，问有多少中方法使得只要有 10 元的人买票，售票处就有 5 元的钞票找零？(将持 5 元者到达视作将 5 元入栈，持 10 元者到达视作使栈中某 5 元出栈)
- 一位大城市的律师在他住所以北 n 个街区和以东 n 个街区处工作。每天她走 2n 个街区去上班。如果他从不穿越（但可以碰到）从家到办公室的对角线，那么有多少条可能的道路？