卡特兰数（Catalan Number）
你有没有遇到过这种面试题："给定 n 个括号，请问能组成多少种合法的括号序列？"
或者："有 n+1 个叶子节点的二叉树，有多少种不同的形状？"
再或者："一个栈依次入栈 1,2,3,...,n，有多少种不同的出栈序列？"
这几个看似毫不相干的问题，答案竟然是同一个数列——这就是今天要聊的卡特兰数 ✨。它隐藏在许多看似不同的计数问题背后，是一个非常优雅的数学概念。
什么是卡特兰数？
卡特兰数是组合数学中一个经典的整数序列，前几项是：
C₀ = 1
C₁ = 1
C₂ = 2
C₃ = 5
C₄ = 14
C₅ = 42
C₆ = 132
C₇ = 429
C₈ = 1430
C₉ = 4862
C₁₀ = 16796
...可以发现增长非常快，C₃₀ 已经超过 10 亿了。这个数列在 OEIS 上的编号是 A000108。
经典问题引入
问题 1：括号匹配
给定 n 对括号，问能组成多少种合法的括号序列？
python
n = 1 → "()" # 1 种
n = 2 → "(())", "()()" # 2 种
n = 3 → "((()))", "(()())", "(())()", # 5 种
"()(())", "()()()"答案正好是卡特兰数 Cₙ。
问题 2：二叉树计数
给定 n+1 个叶子节点，问能组成多少种不同形状的二叉树？
n = 0（空树） → 1 种
n = 1（1个节点） → 1 种
n = 2 → 2 种（两种结构）
n = 3 → 5 种
...这也是卡特兰数！
问题 3：出栈序列
1 到 n 按顺序入栈，问有多少种不同的出栈序列？
n = 1 → [1] # 1 种
n = 2 → [1,2], [2,1] # 2 种
n = 3 → [1,2,3], [1,3,2], [2,1,3], # 5 种
[2,3,1], [3,2,1]又是卡特兰数！
问题 4：购票问题
2n 个人排队买票，其中 n 个人拿 50 元，n 个人拿 100 元。售票员开始时没零钱，问有多少种排队方式让售票员总能找零？
这同样是一个卡特兰数问题。你可以把"拿 50 元"看成"左括号"，"拿 100 元"看成"右括号"，过程中"拿 100 元的人"不能比"拿 50 元的人"多——这和括号匹配完全一致。
原理拆解
递推公式
卡特兰数有多种等价定义，最常用的是递推公式：
C₀ = 1
Cₙ = Σ(Cᵢ × Cₙ₋₁₋ᵢ)，其中 i 从 0 到 n-1或者更简洁的闭式公式：
Cₙ = (2n)! / (n+1)! / n! = (2n choose n) / (n+1)为什么这些不同问题答案相同？
这就是卡特兰数的神奇之处——它们都可以互相归约！
以括号匹配为例：
- 合法序列的第一个左括号后面，一定跟着一个合法的短括号序列
- 这个短序列左边是"前缀"，右边是"后缀"
- 前缀和后缀本身又分别是合法的括号序列
"((()))" 可以分解为：
- 前缀 "(()" 包含 1 对括号 → C₁ 种
- 后缀 "())" 包含 2 对括号 → C₂ 种
- 贡献：C₁ × C₂ = 1 × 2 = 2
加上第一个左括号本身贡献的 Cₙ₋₁ = C₂ = 2
总贡献：2 + 2 = 4 ... 这不对，让我重新理清好吧，递推的严格证明比较复杂，但核心思想是：任何合法结构的"第一个关键分割"把问题分成两个子问题。
图解：括号匹配的递归结构
对于 n=3 的所有合法括号序列：
((())) → 第一个右括号在位置 2 → 前缀=(), 后缀=(())
()()() → 第一个右括号在位置 2 → 前缀=(), 后缀=()()
(()()) → 第一个右括号在位置 4 → 前缀=(()), 后缀=()
(())() → 第一个右括号在位置 4 → 前缀=(()), 后缀=()
()(())
等等，上面的分解不完全对，让我用更直观的方式展示：其实卡特兰数的递推可以从"第一个右括号"的位置来理解：
- 如果第一个右括号在位置
2i+2（即前i+1个左括号后），那么：- 前缀有
i对括号：Cᵢ种 - 后缀有
n-i-1对括号：Cₙ₋ᵢ₋₁种
- 前缀有
- 对所有可能的
i求和，就得到Cₙ = Σ(Cᵢ × Cₙ₋ᵢ₋₁)
代码实现
TypeScript：卡特兰数计算
typescript
/**
* 卡特兰数 —— 多种计算方法
*/
/**
* 方法一：递归（指数级复杂度，不推荐但直观）
* 时间：O(2^n)，空间：O(n) 递归栈
*/
function catalanRecursion(n: number): bigint {
if (n <= 1) return 1n;
let result = 0n;
for (let i = 0; i < n; i++) {
result += catalanRecursion(i) * catalanRecursion(n - 1 - i);
}
return result;
}
/**
* 方法二：动态规划（推荐）
* 时间：O(n²)，空间：O(n)
* 递推关系：C[n] = sum(C[i] * C[n-1-i])
*/
function catalanDP(n: number): bigint {
if (n <= 1) return 1n;
const dp: bigint[] = new Array(n + 1).fill(0n);
dp[0] = 1n;
dp[1] = 1n;
for (let i = 2; i <= n; i++) {
for (let j = 0; j < i; j++) {
dp[i] += dp[j] * dp[i - 1 - j];
}
}
return dp[n];
}
/**
* 方法三：组合数公式（最优）
* C(n) = (2n)! / (n+1)! / n! = C(2n, n) / (n+1)
* 时间：O(n)，空间：O(1)
*/
function catalanFormula(n: number): bigint {
// 使用 BigInt 处理大数
const factorial = (n: number): bigint => {
let result = 1n;
for (let i = 2; i <= n; i++) {
result *= BigInt(i);
}
return result;
};
// C(2n, n) = (2n)! / n! / n!
const combination = (2n: number, n: number): bigint => {
let result = 1n;
for (let i = 0; i < n; i++) {
result *= BigInt(2n - i);
result /= BigInt(i + 1);
}
return result;
};
return combination(2 * n, n) / BigInt(n + 1);
}
/**
* 验证
*/
console.log("=== 卡特兰数验证 ===");
for (let n = 0; n <= 10; n++) {
console.log(`C${n} = ${catalanDP(n)}`);
}
// 输出：
// C0 = 1
// C1 = 1
// C2 = 2
// C3 = 5
// C4 = 14
// C5 = 42
// C6 = 132
// C7 = 429
// C8 = 1430
// C9 = 4862
// C10 = 16796TypeScript：括号生成（LeetCode 22）
这是卡特兰数的经典应用——生成所有合法括号序列：
typescript
/**
* 生成所有 n 对括号的所有合法组合
* LeetCode 22: Generate Parentheses
*
* 思路：回溯 + 剪枝
* - 记录当前左右括号的使用数量
* - 左括号：数量 < n 时可以添加
* - 右括号：数量 > 左括号数量时才能添加（保证不会出现")("）
*/
function generateParenthesis(n: number): string[] {
const result: string[] = [];
function backtrack(current: string, left: number, right: number) {
// 终止条件：左右括号都用完了
if (current.length === 2 * n) {
result.push(current);
return;
}
// 尝试添加左括号（只要左括号还没用完）
if (left < n) {
backtrack(current + "(", left + 1, right);
}
// 尝试添加右括号（只有右括号数量 < 左括号时才能加）
if (right < left) {
backtrack(current + ")", left, right + 1);
}
}
backtrack("", 0, 0);
return result;
}
/**
* 图解回溯过程（n=2）
*
* ""
* / \
* "(" (剪枝：不能直接加")")
* / \
* "((" (剪枝：")"后无法继续)
* / \
* "(()" "()("
* | |
* (回溯) (回溯)
* | |
* "(())" "()()"
*
* 结果：["(())", "()()"]
*/
console.log("\n=== 括号生成测试 ===");
console.log(generateParenthesis(2)); // ["(())", "()()"]
console.log(generateParenthesis(3)); // ["((()))","(()())","(())()","()(())","()()()"]
console.log(`n=3 的合法括号序列数: ${generateParenthesis(3).length} = C₃ = 5 ✓`);Python：出栈序列计数
python
"""
卡特兰数应用：计算栈的不同出栈序列数
"""
def count_stack_sequences(n: int) -> int:
"""
n 个元素按顺序入栈，计算所有可能的出栈序列数
这就是卡特兰数 C_n
"""
# 使用动态规划
# dp[i] 表示 i 个元素的出栈序列数
dp = [0] * (n + 1)
dp[0] = 1 # 空栈：1 种
dp[1] = 1 # 1 个元素：1 种
for i in range(2, n + 1):
# 第 i 个元素出栈时，前面的 i-1 个元素可能出栈了 j 个
# j 个出栈 + (i-1-j) 个还在栈中（作为后缀）
# 组合数：j! * (i-1-j)! 但我们用卡特兰数的等价形式
for j in range(i):
dp[i] += dp[j] * dp[i - 1 - j]
return dp[n]
def is_valid_stack_sequence(seq: list[int], n: int) -> bool:
"""
判断一个序列是否是一个合法的出栈序列
"""
stack = []
expected = 1 # 下一个期望入栈的元素
for x in seq:
# 如果栈顶正好是我们想要的
if stack and stack[-1] == expected:
expected += 1
stack.pop()
continue
# 否则，尝试从输入序列中补充元素
while expected < x and expected <= n:
stack.append(expected)
expected += 1
if expected == x:
expected += 1
else:
return False
return True
# 测试
print("\n=== 栈序列计数测试 ===")
for n in range(1, 6):
count = count_stack_sequences(n)
print(f"{n} 个元素的出栈序列数: {count} (C{n} = {count})")
# 验证 n=3 的所有合法出栈序列
print("\n=== 验证 n=3 的合法出栈序列 ===")
valid_seq_3 = []
for perm in [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]:
if is_valid_stack_sequence(perm, 3):
valid_seq_3.append(perm)
print(f"合法的出栈序列: {valid_seq_3}")
print(f"数量: {len(valid_seq_3)} = C₃ = 5 ✓")Python：验证二叉树数量
python
"""
卡特兰数应用：不同二叉树形状的计数
"""
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def count_unique_trees(n: int) -> int:
"""
计算 n 个节点能组成多少种不同的二叉搜索树
（节点值为 1 到 n BST 性质确定形状）
这同样是卡特兰数！
"""
if n <= 1:
return 1
dp = [0] * (n + 1)
dp[0] = 1
dp[1] = 1
for nodes in range(2, n + 1):
total = 0
for root in range(1, nodes + 1):
# 左子树有 root-1 个节点
left_trees = dp[root - 1]
# 右子树有 nodes-root 个节点
right_trees = dp[nodes - root]
total += left_trees * right_trees
dp[nodes] = total
return dp[n]
def generate_trees(n: int) -> list:
"""
生成所有 n 个节点的二叉搜索树
LeetCode 95
"""
def generate(start: int, end: int) -> list:
if start > end:
return [None]
all_trees = []
for root in range(start, end + 1):
left_trees = generate(start, root - 1)
right_trees = generate(root + 1, end)
for left in left_trees:
for right in right_trees:
tree = TreeNode(root, left, right)
all_trees.append(tree)
return all_trees
return generate(1, n)
# 测试
print("\n=== 二叉搜索树计数测试 ===")
for n in range(1, 6):
count = count_unique_trees(n)
print(f"{n} 个节点的 BST 形状数: {count} (C{n} = {count})")
print(f"\nn=3 时共有 {len(generate_trees(3))} 种不同的 BST")
print("这正好等于卡特兰数 C₃ = 5 ✓")复杂度分析
| 方法 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|
| 递归 | O(2ⁿ) | O(n) 递归栈 | 理解原理，不推荐 |
| DP | O(n²) | O(n) | 小规模数据 |
| 组合公式 | O(n) | O(1) | 大规模数据，推荐 |
精确复杂度
- DP 递推：双重循环，外层 n，内层平均 n/2，故 O(n²)
- 组合公式：计算
C(2n, n)需要 O(n) 次乘法 - 数值范围：C₃₅ ≈ 3.11 × 10¹⁹，超出 64 位整数，需要 BigInt
面试题实战
题目 1：括号序列合法性（简单）
python
def is_valid_parentheses(s: str) -> bool:
"""
判断括号序列是否合法
剑指 Offer：判断字符串是否有效括号
"""
stack = []
mapping = {')': '(', ']': '[', '}': '{'}
for char in s:
if char in mapping:
top = stack.pop() if stack else '#'
if mapping[char] != top:
return False
else:
stack.append(char)
return len(stack) == 0
# 测试
print("\n=== 括号合法性 ===")
tests = ["()", "()[]{}", "(]", "([)]", "{[]}", ""]
for t in tests:
print(f"'{t}': {is_valid_parentheses(t)}")题目 2：票据找零（中等）
python
def ticket_issue(n: int) -> int:
"""
2n 个人排队，n 人拿 50 元，n 人拿 100 元
售票员初始无零钱，问有多少种排队方式？
这等价于括号匹配问题的变形
"""
# 直接用卡特兰数公式
result = 1
for i in range(1, n + 1):
result = result * (n + i) // i
return result // (n + 1)
print("\n=== 票据找零 ===")
for n in range(1, 6):
print(f"n={n} 时有 {ticket_issue(n)} 种排队方式")题目 3：上山/下山路径（困难）
python
def count_paths(m: int, n: int) -> int:
"""
从 (0,0) 到 (m,n) 的路径数（只能往右或往上走）
不穿过对角线的情况有多少种？
当 m=n 时，这就是卡特兰数！
"""
# 标准组合数：总共走 2n 步，选 n 步往右
# 不穿过对角线 = 卡特兰数
def catalan(n):
result = 1
for i in range(1, n + 1):
result = result * (n + i) // i
return result // (n + 1)
return catalan(min(m, n))
print("\n=== 上山路径（不穿过对角线）===")
for n in range(1, 6):
print(f"从 (0,0) 到 ({n},{n}) 不穿过对角线的路径数: {count_paths(n, n)}")实际应用场景
1. 括号相关系统
- 代码编辑器：实时检测括号是否匹配
- 表达式解析器：编译器、计算器中的语法解析
- SQL 解析：嵌套查询的合法性检查
2. 组合数学
- 二叉树结构：数据库索引、表达式树的形状计数
- 凸多边形三角剖分：一个凸多边形有多少种三角剖分方式
- 网格路径：不穿过对角线的网格路径数
3. 编译器/解释器
- 函数调用栈：嵌套调用的合法性
- XML/HTML 标签匹配：嵌套结构的闭合检测
小结
卡特兰数是一个看似简单但内涵丰富的数学工具 ✨：
Cₙ = (2n)! / (n+1)! / n! = C(2n, n) / (n+1)它揭示了这些看似不同的问题的本质联系：
| 问题 | 卡特兰数视角 |
|---|---|
| 合法括号序列 | 左括号 = 入栈，右括号 = 出栈 |
| BST 形状 | 左子树节点数 × 右子树节点数 |
| 出栈序列 | 入栈元素数 × 剩余元素数 |
| 票据找零 | 50元持有者 = 左括号，100元 = 右括号 |
记住：只要问题满足"在任意时刻 A 的数量不能少于 B 的数量"这样的约束，十有八九就是卡特兰数 🎯。
代码实现推荐使用组合公式，时间复杂度 O(n)，远比递归或 DP 优雅。面试时如果一时想不起公式，用 DP 也能拿到 offer，但能写出闭式解一定会让面试官眼前一亮 💡！