卡特兰数：从括号匹配到二叉树计数的组合数学之美

1. 引言卡特兰数Catalan Number是组合数学中一类极为重要的数列它以比利时数学家欧仁·查理·卡特兰Eugène Charles Catalan的名字命名。卡特兰数看似简单却频繁出现在看似毫不相干的计数问题中从括号的合法配对、出栈序列的数目到二叉树的形态计数、凸多边形的三角剖分乃至网格路径的走法都能看到它的身影。本文将从卡特兰数的定义出发介绍其递推公式、通项公式并通过若干经典应用场景帮助读者建立直观理解最后给出常见的代码实现。2. 卡特兰数的定义卡特兰数列的第 n 项通常记作 Cn注意与组合数符号区分其前几项为1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, ...其中 C0 1C1 1C2 2C3 5以此类推。3. 递推公式卡特兰数满足如下递推关系C0 1 Cn C0·C(n-1) C1·C(n-2) ... C(n-1)·C0 (n ≥ 1)这个递推式的组合意义非常直观把 n 个元素的问题拆成「左边 k 个」和「右边 n-1-k 个」两个独立子问题枚举所有可能的拆分方式并求和。4. 通项公式卡特兰数还有更简洁的通项公式Cn (1/(n1)) · C(2n, n)其中 C(2n, n) 表示从 2n 个元素中选取 n 个的组合数。等价地也可以写成Cn C(2n, n) - C(2n, n1)通项公式在计算较大 n 时非常有用可以直接利用组合数计算而不必逐项递推。5. 经典应用场景卡特兰数之所以著名是因为它统一了众多表面不同、本质相同的计数问题。以下是几个最经典的应用。5.1 括号匹配n 对括号能组成多少种合法括号序列答案是 Cn。例如 n 3 时共有 5 种合法序列((())) (()()) (())() ()(()) ()()()5.2 出栈序列n 个元素按 1, 2, ..., n 的顺序入栈合法的出栈序列有多少种答案同样是 Cn。这个问题与括号匹配本质相同把入栈记为左括号出栈记为右括号任意前缀中入栈次数不少于出栈次数。5.3 二叉树的形态计数n 个节点能组成多少种不同形态的二叉树答案是 Cn。若把根节点固定左子树有 k 个节点、右子树有 n-1-k 个节点枚举 k 即可得到递推式。5.4 凸多边形三角剖分一个 n2 条边的凸多边形用不相交的对角线将其剖分成三角形共有 Cn 种剖分方式。5.5 网格路径在 n×n 的网格中从左上角走到右下角每次只能向右或向上走且不越过对角线的路径数为 Cn。6. 代码实现下面给出 Java 和 Python 两种常见实现分别使用递推和通项公式两种方式。6.1 Java 递推实现public class Catalan { public static long catalan(int n) { long[] dp new long[n 1]; dp[0] 1; for (int i 1; i n; i) { for (int j 0; j i; j) { dp[i] dp[j] * dp[i - 1 - j]; } } return dp[n]; } public static void main(String[] args) { for (int i 0; i 10; i) { System.out.println(C( i ) catalan(i)); } } }6.2 Python 通项公式实现import math def catalan(n): return math.comb(2 * n, n) // (n 1) for i in range(11): print(fC({i}) {catalan(i)})7. 总结卡特兰数是一个看似简单却内涵丰富的数列它把括号匹配、出栈序列、二叉树计数、三角剖分和网格路径等众多问题统一在同一个递推关系之下。理解卡特兰数不仅有助于解决具体的计数问题更能培养「透过现象看本质」的组合数学思维。建议读者在掌握递推公式和通项公式后亲自推导一遍上述几个经典场景的对应关系体会其中的对称之美。