卡特兰数是一个出现在各种组合问题中的数列，比如“括号排列”“二叉树结构”“路径不走对角线”等。它像魔法一样，帮你快速算出这些问题的答案。

数列前几项： 当 n=0n=0 时，C0=1C0=1 当 n=1n=1 时，C1=1C1=1 当 n=2n=2 时，C2=2C2=2 当 n=3n=3 时，C3=5C3=5 当 n=4n=4 时，C4=14C4=14 ...（依次类推）

目录

一、如何计算卡特兰数

二、卡特兰数的经典问题（超详细例子）

三、什么时候用卡特兰数？

四、总结

---

一、如何计算卡特兰数

1. 递推公式

公式：

通俗解释：

• 要算第 n 项，需要知道前 n 项的值。

• 每一项都是前面所有项的“配对乘积之和”。

1. 组合数公式

公式：

​

通俗解释：

• 先算 （即从 2n 个物品中选 n 个的组合数），再除以 n + 1。

二、卡特兰数的经典问题（超详细例子）

问题 1：括号匹配

问题：3 对括号 () 有多少种合法排列方式？ 答案：5 种，即 C3=5C3​=5。

所有合法排列：

1. ()()()

2. ()(())

3. (())()

4. (()())

5. ((()))

为什么其他排列不合法？ 比如 )(() 或 ())()，因为左括号 ( 必须出现在对应的右括号 ) 之前。

没看卡特兰数之前想到全排列但是还是不太好做，终于找到正解了！！

---

问题 2：二叉搜索树（BST）的形态数

问题：3 个节点能组成多少种不同的二叉搜索树？ 答案：5 种，即 C3=5C3​=5。

所有可能的树结构（假设节点值为 1, 2, 3，按BST规则排列）：

1. 根节点为 1，右子树为 2 和 3

2. 根节点为 1，右子树为 3，其左子节点为 2

3. 根节点为 2，左右子树各为 1 和 3

4. 根节点为 3，左子树为 2，其左子节点为 1

5. 根节点为 3，左子树为 1 和 2

 1         1         2         3         3  
   \         \       / \       /         /  
    2         3     1   3     2         1  
     \       /               /           \  
      3     2               1             2  

---

问题 3：栈的合法出栈序列

问题：元素按顺序 1, 2, 3 入栈，有多少种不同的出栈顺序？ 答案：5 种，即 C3=5。

所有合法出栈序列：

1. 1, 2, 3（入栈后立刻出栈）

2. 1, 3, 2

3. 2, 1, 3

4. 2, 3, 1

5. 3, 2, 1

非法例子： 比如 3, 1, 2 不可能，因为 1 比 2 先入栈，必须先出 2 才能出 1。

---

卡特兰数在上述三个例子中运用比较多，在刷算法题时经常会遇到~~

---

问题 4：凸多边形的三角形划分

问题：将五边形（5 条边）用不相交的对角线分成三角形，有多少种方式？ 答案：C3​=5 种。

图解（以五边形 ABCDE 为例）：

1. 从 A 出发，连 AC 和 AD，划分成 3 个三角形。

2. 从 A 出发，连 AC 和 BD，划分方式不同。 ...（具体划分方式需画图，但总数是 5）

---

三、什么时候用卡特兰数？

核心思想：这些问题都可以拆解成“两个独立子问题”：

• 括号问题：左括号内的子问题 + 右括号外的子问题。

• 二叉树问题：左子树的形态数 × 右子树的形态数。

• 路径问题：第一次接触对角线的点，将路径分成两段。

递推公式的直观理解： 假设你要解决一个规模为 n的问题，你需要：

1. 固定一个“分割点” k（比如第一个左括号的匹配位置）。

2. 左边的规模是 k，右边的规模是 n−1−k。

3. 将所有可能的 k 的结果相加，得到 Cn。

---

四、总结

• 卡特兰数的特征：问题可以递归拆解成两个独立子问题。

• 如何计算：递推或组合数公式（推荐组合数公式，直接套用）。

• 常见问题：括号、二叉树、出栈序列、路径、多边形划分。