卡特兰数证明：从球ot投票问题到括号匹配的组合恒等式

定理陈述

设有 n 个 +1 与 n 个 -1，构成长度 2n 的序列 a₁, a₂, …, a₂ₙ。若对任意前缀 k (1 ≤ k ≤ 2n)，其部分和满足 a₁ + a₂ + … + aₖ ≥ 0，则这样的序列总数为第 n 个卡特兰数：

Cₙ = (1/(n+1)) * C(2n, n) = (2n)! / (n! (n+1)!)

经典反射法证明

1. 总排列数：从 2n 个位置中选 n 个放 +1，共 C(2n, n) 种。
2. 定义“非法”序列：存在最小的 k 使得前缀和 < 0。此时必有 a₁+…+aₖ₋₁ = 0 且 aₖ = -1，故 k 为奇数。
3. 构造双射：对每个非法序列，将前 k 项符号取反（+1↔-1），得到新序列包含 n+1 个 +1 和 n-1 个 -1。此映射是单射。
4. 计数非法序列：n+1 个 +1 与 n-1 个 -1 的排列数为 C(2n, n-1)。
5. 合法序列数：C(2n, n) - C(2n, n-1) = Cₙ。

几何解释：网格路径不越界

将 +1 视为向右步 (1,0)，-1 视为向上步 (0,1)。合法序列对应从 (0,0) 到 (n,n) 且不穿越对角线 y=x 的网格路径。反射法即将首次触碰 y=x+1 的路径关于该线反射，建立与到 (n-1,n+1) 路径的双射。

经典应用场景

• 合法括号序列：n 对括号的合法匹配数。
• 栈排列：1..n 入栈，出栈序列的合法排列数。
• 二叉树计数：n 个节点的不同二叉树形态数。
• 剧院排队找零：2n 人排队买票（n 人持 5 角，n 人持 1 元），售票处初始无零钱，不发生找零困难的排队方式数即 Cₙ。

递推与生成函数

卡特兰数满足递推：C₀=1, Cₙ₊₁ = Σᵢ₌₀ⁿ Cᵢ Cₙ₋ᵢ。生成函数 C(x) = Σ Cₙ xⁿ 满足 C(x) = 1 + x C(x)²，解得 C(x) = (1 - √(1-4x)) / (2x)，展开即得显式公式。

结语

卡特兰数以其简洁的公式和极其广泛的组合意义，成为离散数学中的明星数列。反射法证明不仅优雅，更揭示了“越界路径与对称路径”的深层对偶关系，是组合计数中值得反复品味的经典技巧。