Catalan 数

Catalan 数是计数组合中的一个计数序列, 记为 $C_{n}$ , 其前几项为 $C_{0} = 1, C_{1} = 1, C_{2} = 2, C_{3} = 5, C_{4} = 14, \dots$

Catalan 数见于许多计数结果, 包括凸多边形的三角剖分数目、二叉树的数目、括号序列的数目等.

1定义

定义 1.1 (Catalan 数). 对自然数 $n$ , Catalan 数 $C_{n}$ 定义为自然数 $C_{n} = \frac{1}{n + 1} (n 2 n),$ 其中 $(n 2 n)$ 是二项式系数.

•	Catalan 数满足如下递推公式: $C_{0} = 1$ , 且当 $n \geq 1$ 时, $C_{n} = k = 0 \sum n - 1 C_{k} C_{n - 1 - k} .$

•

Catalan 数的生成函数为 $C (x) = \frac{1 - 1 - 4 x}{2 x} .$

证明.

证明. 由二项式级数

\frac{1}{1 - 4 x} = k = 0 \sum \infty (k 2 k) x^{k}, ∣ x ∣ < \frac{1}{4}

从

0

到

x

积分, 得

\frac{1 - 1 - 4 x}{2} = k = 0 \sum \infty \frac{1}{k + 1} (k 2 k) x^{k + 1}

除以

x

, 得

\frac{1 - 1 - 4 x}{2 x} = k = 0 \sum \infty \frac{1}{k + 1} (k 2 k) x^{k}

$□$

•	对整数 $n \geq 3$ , 凸 $n$ 边形的三角剖分的数目是 $C_{n - 2}$ . 这里, 三角剖分是指选取该 $n$ 边形的 $(n - 3)$ 条两两不相交的对角线的方法, 从而这些对角线将 $n$ 边形划分为 $(n - 2)$ 个三角形.
•	对 $n \geq 0$ , 具有 $n$ 个元素的二叉树的数目是 $C_{n}$ . 这里, 二叉树是指由形如 $(a_{1}, \dots, a_{n})$ 的序列构成的集合 $T$ , 其中 $n \geq 0$ , 且每个 $a_{i} \in {0, 1}$ , 使得若 $n \geq 1$ 且 $(a_{1}, \dots, a_{n}) \in T$ , 则 $(a_{1}, \dots, a_{n - 1}) \in T$ . 例如, 具有 $2$ 个元素的二叉树有 ${(), (0)}$ 和 ${(), (1)}$ .
•	对 $n \geq 0$ , 具有 $n$ 对括号的括号序列的数目是 $C_{n}$ . 这里, 括号序列是指形如 `(()())()` 的序列, 其中要求括号能正确地配对, 也就是对任何 $0 \leq i \leq n$ , 其前 $i$ 个符号中左括号的数量不少于右括号的数量. 例如, 具有 $2$ 对括号的括号序列有 `(())` 和 `()()`.
•	在 $N^{2}$ 中, 由 $(0, 0)$ 到 $(m, n)$ 的最短路径共有 $(m m + n)$ 条. 由 $(0, 0)$ 到 $(n, n)$ 且恒满足 $y ⩽ x$ 的最短路径的数目为 $C_{n}$ .

术语翻译

Catalan 数 • 英文 Catalan number • 德文 Catalan-Zahl (f) • 法文 nombre de Catalan (m) • 日文 Catalan 数 (Catalan すう) • 韩文 Catalan 수