相遇
在刷leetcode题不同的二叉搜索树的时候，遇到了卡特兰数。
搜索一番，貌似与离散数学相关，这个时候我对我大学时期的离散老师深感歉意。
秉着好学的态度，借这个机会对卡特兰数深入的了解一番。
相识
卡特兰数是什么？卡特兰数是组合数学中一个常在各种计数问题中出现的数列。
了解卡特兰数的几种形式。
形式一：$f(n) = f(0) * f(n-1) + f(1) * f(n-2) + … + f(n-1) * f(0)$
形式二：$f(n) = C_{2n}^{n} - C_{2n}^{n-1}$
形式三：$f(n) = \frac{1}{n+1}C_{n}^{2n}$
形式四：$f(n) = \frac{f(n-1) * (4n-2))}{n+1}$
推导过程
对于形式一，推导过程是解决leetcode搜索二叉树的生成数量利用动态规划推导出来的。
其推导过程为：
第一步，定义动态规划数组
- G(n)：长度为 n 的序列能构成的不同二叉搜索树的个数。
- F(i, n)：以 i 为根、序列长度为 n 的不同二叉搜索树个数(1 ≤ i ≤ n)。
第二步，动态规划基本流程
初始化：$G(0)=1,G(1)=1$
转移方程：$F(i, n)=G(i−1) * G(n−i)$
答案：$G(n) = F(1, n) + F(2, n) + … + F(n, n)$
也就是：$G(n) = G(0) * G(n−1) + G(1) * G(n−2) + … + G(n−1) * G(0) $
对于形式二，推导过程是解决 n 个 +1，和 n 个 -1 的组成的排列 $a_{2n}$，对于任意一个 k，使得 $a_{1} + a_{2} + … + a_{k} >= 0$；
其推导过程为：
假设 $B_{2n}$ 中有 n+1 个 +1，n-1 个 -1；
因为 $B_{1} + B_{2} + … + B_{2n} = 2$
则必存在一个 m ，使得 $B_{1} + B_{2} + … + B_{m} = 1$
那么 $-(B_{1} + B_{2} + … + B_{m}) + (B_{m+1} + B_{m+2} + … + B_{2n}) = 0$
令
$a_{1} = -B_{1}, a_{2} = -B_{2}, … a_{m} = -B_{m}$
$a_{m+1} = B_{m+1}, a_{m+2} = B_{m+2}, …, a_{2n} = B_{2n}$
那么有
\[\left\{\begin{matrix} a_{1} + a_{2} + ... + a_{m} < 0;\\ a_{1} + a_{2} + ... + a_{2n} = 0; \end{matrix}\right.\]这个答案恰好是不符合要求的解。
所以对于 n 个 +1 和 n 个 -1 组成的排列有 $C_{2n}^{n}$ 个；
而 n+1 个 +1，n-1 个 -1 组成的排列有 $C_{2n}^{n-1}$ 个；
所以符合答案的有 $C_{2n}^{n} - C_{2n}^{n-1}$ 个。
对于形式三和形式四，化简形式二可以得到
形式三：
\[f(n) = C_{2n}^{n} - C_{2n}^{n-1} = \frac{(2n)!}{n!*n!} - \frac{(2n)!}{(n-1)!*(n+1)!} = \frac{1}{n+1}*C_{2n}^{n}\]形式四：
根据
\[\left\{\begin{matrix} f(n) = \frac{1}{n+1}C_{2n}^{n} \\ f(n-1) = \frac{1}{n}C_{2(n-1)}^{n-1} \end{matrix}\right.\]可得
\[\frac{f(n)}{f(n-1)} = \frac{n*C_{2n}^{n}}{(n+1)*C_{2(n-1)}^{n-1}} = \frac{(2n)!}{n*(n+1)*(2(n-1))!}= \frac{2*(2n-1)}{n+1}\]最后可得
$f(n) = \frac{2*(2n-1)}{n+1} * f(n-1)$
相知
常见的例题有：
01排序序列
括号匹配
凸多边形的三角划分
搜索二叉树
进出栈问题
