卡特兰数
引入
不妨从找规律开始。
下标从\(0\)开始，卡特兰数的前几项为：
1,1,2,5,14,42,132,429,1430,4862,16796,58786,208012,742900,2674440,9694845,35357670,129644790…
那么通过认真的瞪眼观察，会发现它们满足递推关系。
关于
卡特兰数是一个很常见的数列。它并没有一个足够具体的意义，但诸多问题中都出现了与之相符的数学规律。
比起组合数的用形式规范问题，它更像是用诸多例子来勾勒出的形式。
下面根据几个实际的问题模型来讨论卡特兰数。
通项公式
\[C(n) = \tbinom{2n}{n}-\tbinom{2n}{n+1}
\]
问题
- 给定\(n\times n\)的网格图。问，从左下角走到右上角，且不越过\(x=y\)对角线的方案数。
等价问题
-
\(n\)个左括号和\(n\)个右括号的括号匹配的方案数。
括号匹配：任意前缀中，左括号数量不小于右括号数量。 -
\(1\)到\(n\)依次入栈，可能的不同出栈序列数量。
-
\(n\)个无编号节点构成的区别左右儿子的有根二叉树数量。
-
\(2n+1\)个无编号节点构成的左右儿子有区别的有根真二叉树数量。
证明：因为懒得写了（其实是不会），所以推荐参考%%%sto这篇otz%%%
变形
\[C(n) = \frac{1}{n+1} \tbinom{2n}{n} \\
C(n) = \frac{1}{n+1} \sum_{i=0}^{n}\tbinom{n}{i}^2
\]
递推公式
对于\(n \ge 2\)，有：
\[C(n)=\sum_{i=1}^{n} C(i-1)C(n-i)
\]
问题
尤其是一些凸多边形问题
-
已知一个凸\(n\)边形，将其三角剖分，问可能的方案数。
-
已知一个凸\(n\)边形，在其顶点上插入钉子，在钉子间缠绕若干橡皮筋，问使橡皮筋不相交的方案数。
等价问题
-
\(n\)个无编号节点构成的区别左右儿子的有根二叉树数量。
-
用若干个矩形构成\(n\)级楼梯，且每个矩形的右下角都作为一级楼梯的组成，问可能的方案数。
证明
类似动态规划中的转移方程，略。
另一个递推公式
\[C(n) = \frac{4n-2}{n+1}\times C(n-1)
\]