「琐记」卡特兰数
卡特兰数的证明能够扩展到处理一类括号序列的问题上。不仅仅只是为了应付 sb 初赛。
卡特兰数
基本定义
使用 \(C(n)\) 表示卡特兰数的第 \(n\) 项。
通项： \[ C(n) = \dbinom{2n}{n} - \dbinom{2n}{n-1} =\frac{1}{n+1}\dbinom{2n}{n}=\frac{1}{n+1}\sum_{i=0}^{n}\dbinom{n}{i}^2 \] 递推式： \[ C(n)=\sum_{i=0}^{n-1}C(i)C(n-1 - i) \]
通项的推导
考虑通项公式的推导：
第 \(n\) 项卡特兰数的定义之一就是 \(n\) 对括号的合法配对方案。
将括号序列中的 ( 看成 +1 将 ( 看成 -1 ，合法的括号序列方案不仅仅是代数和等于 \(0\) 这么简单。
如果某一个位置的前缀和变成负数，那么这个括号是不可能合法了。
所以，按照上面括号向数字的映射定义，这个序列的任意一个位置的前缀和都应该不小于 \(0\)。
可以将问题转化为从平面上 \((0, 0)\) 走到 \((2n, 0)\)，每一个位置都需要决策是沿着右上对角线走还是沿着右下对角线走。 走的过程中不能越过 \(y=0\) 这条线。
考虑没有最后一条限制，方案数就是 \(\dbinom{2n}{n}\)。
考虑哪些方案不合法，必然是到达过 \(y=-1\) 这条线的方案都不合法，考虑算出这部分不合法的方案。
可以强制一定要穿过 \(y=-1\) 这条线，只需要把终点设置为原终点 \((2n, 0)\) 关于 \(y=-1\) 的对称点 \((2n, -2)\)，然后格路计数，考虑这样统计的所有方案一定穿过了若干次 \(y=-1\) ，考虑最后一次穿过的点，到终点这一段路径全部翻着之后就是走到原终点的方案。不难发现，之前所计入的不合法方案和走到 \((2n, -2)\) 的方案一一对应。
这样就能得到不合法的方案数为 \(\dbinom{2n}{n-1}\)
《组合数学》 中给出的证明只是把 最后一次穿越 改成了 第一次穿越，没有引入格点计数的转换，本质相同。
应用
卡特兰数的几个应用如下：
\(n\)对括号的合法配对方案数.
\(n\) 个节点的有根二叉树的形态数.这个对应了递推式.
\(n\) 个数入栈后出栈的排列总数
对凸 \(n+2\) 边形进行不同的三角形分割的方案数(分割线断点仅为顶点，且分割线仅在顶点上相交)
\(n\) 层的阶梯切割为 \(n\) 个矩形的切法数 P2532 [AHOI2012]树屋阶梯
\(n+1\) 个叶子（\(n\) 个非叶子）的满二叉树形态数，这个对应了递推式.
这里的满二叉树指满足 结点要么是叶子结点，度为0，要么是度为2的结点，不存在度为1的结点 的二叉树。
美国以及国际上所定义的满二叉树，即 full binary tree ,和国内的定义不同，美国 NIST 给出的定义为：A binary tree in which each node has exactly zero or two children. In other words, every node is either a leaf or has two children. For efficiency, any Huffman coding is a full binary tree.
前几项为：1,1,2,5,14,42,132