Catalan数

Catalan 数（卡特兰数） $C_{n}$ 计数许多“每一步都不能越过边界”的结构。一个明确的版本是：用 $n$ 个左括号和 $n$ 个右括号排成合法括号串，其中从左到右读的每个前缀，左括号数都不少于右括号数。 $n = 3$ 时共有五串： ((()))、(()())、(())()、()(())、()()()，故 $C_{3} = 5$ 。

先按最外层分解

一串非空合法括号必可唯一写成 (A)B，其中 A 与 B 都是合法括号串。若 A 用 $k$ 对括号，B 就用 $n - 1 - k$ 对，因此 $C_{0} = 1, C_{n} = \sum_{k = 0}^{n - 1} C_{k} C_{n - 1 - k} (n \geq 1) .$ 空串计为一种，才能让 $n = 1$ 的递推得到 $C_{1} = C_{0} C_{0} = 1$ 。再算得 $C_{2} = 2$ 、 $C_{3} = 1 \cdot 2 + 1 \cdot 1 + 2 \cdot 1 = 5$ 。

从全部排法减去越界排法

不管前缀条件， $2 n$ 个位置中选 $n$ 个放左括号，有 $(\binom{2 n}{n})$ 种。对第一次出现右括号数超过左括号数的非法串，把此处之前的左右括号互换，便与“ $n + 1$ 个左括号、 $n - 1$ 个右括号”的串一一对应；非法数为 $(\binom{2 n}{n + 1})$ 。所以 $C_{n} = (\binom{2 n}{n}) - (\binom{2 n}{n + 1}) = \frac{1}{n + 1} (\binom{2 n}{n}) .$ 递推适合逐项计算，封闭式适合比较规模。两式计数的是同一批结构，不是两个不同定义。

参考资料

MIT，Mathematics for Computer Science，Counting 章节。
MIT 6.042J Fall 2010，Mathematics for Computer Science 课程讲义。
继续阅读：组合数学、递推关系、二项式定理。