定义
-
公式 \(1\)：\(C_n=\begin{pmatrix}2n\\n\end{pmatrix}-\begin{pmatrix}2n\\n-1\end{pmatrix}\)
-
公式 \(2\)：\(C_n=\sum_{a+b=n-1}C_aC_b\)
-
公式 \(3\)：\(C_n=\frac{4n-2}{n+1}C_{n-1},C_0=1\)
其中公式 \(3\) 表明其增长速度是 \(O(4^n)\) 的。
定义式 \(C_n=\frac{1}{n+1}\begin{pmatrix}2n\\n\end{pmatrix}\) 可以由公式 \(1\) 直接拆组合数推导出来。
组合意义
主包不会代数，所以在此仅说明一下公式 \(1\) 的组合意义推导过程。我们考虑通过 \(\text{Catalan}\) 数解决这么一个问题：
Statement：从 \((0,0)\) 走到 \((n,n)\)，只能向上走或向右走，不能穿过直线 \(y=x\)（即 \(y-x\le 0\)），方案数是多少？
方案数是 \(C_n\)，接下来我们考虑证明这一结论。
（图片来源于OI-wiki：卡特兰数，侵删）
计数通常要求找到的特性与对象存在双射关系，我们也尝试这样寻找，以下我们尝试用第一次触碰点这一特殊性无重地映射若干种情况。
为什么有这样的对应？我们不妨令其方案数为 \(T_n\)，显然 \(T_0=1\)，而考虑每种方案第一次触碰 \(y=x\) 的位置 \((k,k)\)，发现第一步一定向右，最后一步一定向上。然后就可以划分为两个子问题，下面 \((1,0)\to(k,k-1)\) 的方案数是 \(T_{k-1}\)，上面 \((k,k)\to(n,n)\) 的方案数是 \(T_{n-k}\)，总递推式就是 \(T_n=\sum_{a+b=n-1}T_aT_b\)，符合公式 \(2\)。
由于主包没有高超代数技巧，为了证明公式 \(1\) 和 \(2\) 的等效性，我们再来验证一下公式 \(1\) 的对应性。首先不考虑穿过的限制，方案数是 \(2n\) 步中选 \(n\) 步向上即 \(\begin{pmatrix}2n\\n\end{pmatrix}\)，然后我们考虑去掉每个非法情况，这些非法情况一定在至少一个点触碰了 \(y=x+1\)，一样地找到第一个触碰点 \((k,k+1)\)，到 \((n,n)\) 的向量就是 \((n-k,n-k-1)\)。关于 \(y=x+1\) 翻折一下后半段，可以得到位移变成了 \((n-k-1,n-k)\)，所到的点为 \((n-1,n+1)\)。这个翻折保证了计数的双射性，且对于到 \((n-1,n+1)\) 没有任何限制，每种方案都可以对应一个初始触碰点。那么这些非法情况的计数就是 \(\begin{pmatrix}2n\\n-1\end{pmatrix}\) 或者 \(\begin{pmatrix}2n\\n+1\end{pmatrix}\) 的。
所以得到
至于公式 \(3\) 我们平时不用我也不会证。
递推
-
可以预处理 \(4n\) 范围内的乘法逆元后采用公式 \(3\)。
-
可以预处理 \(2n\) 范围内的组合数后采用公式 \(1\)。
以上处理方法都是 \(\Theta(n)\) 的。
应用
上述 \((0,0)\to(n,n)\) 路径计数问题是比较经典的问题。
- 括号计数问题
Statement：由 \(n\) 对括号构成的合法括号序列数 \(C_n\)。
将 \(x\) 坐标映射为前缀左括号数量，\(y\) 映射为右括号数量，前缀长度 \(x+y\)。
- 三角剖分计数问题
Statement：对角线不相交的情况下，将一个凸 \((n+2)\) 边形区域分成三角形区域的方法数为 \(C_n\)。
同样通过公式 \(2\) 推导，给顶点编号 \(1\dots n+2\)，枚举关于边 \((1,n+2)\) 的三角形第三个顶点 \(k\) 即可。
- 出栈序列计数问题
Statement：一个栈（无穷大）的进栈序列为 \(1,2,3,\dots,n\)，合法出栈序列的数目为 \(C_n\)。
和括号计数类似。
- 数列计数问题
Statement：由 \(n\) 个 \(+1\) 和 \(n\) 个 \(−1\) 组成的数列 \(a_1,a_2, \ldots ,a_{2n}\) 中，部分和满足 \(a_1+a_2+ \ldots +a_k \geq 0~(k=1,2,3, \ldots ,2n)\) 的数列数目为 \(C_n\)。
和括号计数类似。
- 圆内不相交弦计数问题：
Statement：圆上有 \(2n\) 个点，将这些点成对连接起来且使得所得到的 \(n\) 条线段两两不交的方案数是 \(C_n\)。
考虑点 \(1\) 只能和 \(2k(k\in [1,n]\cap \Z)\) 连边，否则无法分出合法子问题。同样枚举这个 \(k\) 然后可以由公式 \(2\) 推出。