📖 组合数学高阶：卡特兰数与格点路径
卡特兰数 (Catalan Number) 是组合数学中应用极广的一个数列。在二叉树计数、括号匹配、多边形三角剖分以及不越界的格点路径规划中都有其身影。
📐 基础公式与递推公式
卡特兰数通项公式为：
$C_n = \frac{1}{n+1}\binom{2n}{n} = \binom{2n}{n} - \binom{2n}{n-1}$
其乘积求和的递推式（用于二叉树拆分、括号配对）：
$C_0 = 1, \quad C_n = \sum_{i=0}^{n-1} C_i C_{n-1-i} \quad (n \ge 1)$
📐 折线反射映射证明定理（几何精髓）
从格点 $(0,0)$ 到 $(n,n)$ 只能向右和向上移动：
- 总路径数：任意由 $n$ 次向右和 $n$ 次向上移动组成的路径共有 $\binom{2n}{n}$ 种。
- 非法路径与折线反射：任何越过对角线 $y=x$（即触及直线 $y = x + 1$）的非法路径。如果以第一次触及 $y = x + 1$ 的触点为对称轴，将该点之后的路径关于 $y = x + 1$ 轴对称翻折，则终点 $(n,n)$ 被反射映射到固定坐标点 $(n-1, n+1)$。
- 因为从 $(0,0)$ 到 $(n-1, n+1)$ 的路径数正好是 $\binom{2n}{n-1}$，且它们与非法路径一一对应，故合法路径数即为两者相减：$C_n = \binom{2n}{n} - \binom{2n}{n-1}$。
点击“合法路径”或“非法路径”查看从 $(0,0)$ 到 $(N,N)$ 的格点移动轨迹。
网格大小 N
4
总组合数 C(2N, N)
C(8, 4) = 70
非法路径数 C(2N, N-1)
C(8, 3) = 56
卡特兰数 Cn (结果)
14
// 递推计算卡特兰数 C_n
long long getCatalan(int n) {
vector<long long> C(n + 1, 0);
C[0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 0; j < i; j++) {
C[i] += C[j] * C[i - 1 - j]; // 分治递推关系
}
}
return C[n];
}