【组合数学】卡特兰数

luyuanhong

【组合数学】卡特兰数

原创  尹志扬  三金家的 Y 同学  2025 年 04 月 15 日 08:03  北京

概念

卡特兰数（Catalan Number）是一个在组合数学中非常重要的数列，广泛应用于各种算法竞赛问题中，尤其是涉及递归、分治法、树结构、路径问题等领域。

卡特兰数的定义：



卡特兰数的应用：

卡特兰数在许多组合数学问题中都有应用，以下是一些典型的应用场景：

1. 有效的括号配对：卡特兰数可以用于计算有效括号配对的数目。例如，对于给定的n对括号，卡特兰数可以表示有多少种不同的方式来有效地配对这些括号。

2. 二叉树的数量：卡特兰数还可以表示一个具有n个节点的不同二叉树的数量。具体来说，C_n表示n个节点的二叉搜索树的个数。

3. 路径问题：在一个格子中从左下角到右上角，如何计算经过一系列合法的路径（仅能向上或向右走）的数量。卡特兰数可以解决这类路径问题。

4. 堆排序的树结构：卡特兰数还与堆排序和堆的构建有关系，特别是在处理堆的结构时，卡特兰数可以用于计算堆的不同排列。

卡特兰数的计算方法：

1. 递推法：根据递推公式逐步计算。

2. 动态规划：用动态规划存储每个卡特兰数的值，避免重复计算。

3. 显式公式：使用组合数公式直接计算。

卡特兰数的前几个值：



通项公式



相关例子

1. 有 2n 个人排成一行进入剧场：

问题描述：有 2n 个人排成一行进入剧场，其中只有 n 个人有 5 元钞票，另 n 人只有 10 元钞票，且售票处没有其他钞票。要求的是如何安排这 2n 个人的顺序，使得每个拥有 10 元钞票的人都能在售票员处找到 5 元的零钱。

解法：这个问题可以转化为一个“有效括号配对”问题。每个有 5 元钞票的人可以视为一个“开括号”（表示增加 5 元），而每个有 10 元钞票的人可以视为一个“闭括号”（表示减少 5 元）。我们要求的是一个有效的括号序列，其中每个闭括号都必须在一个开括号之前出现。

这个问题的解法就是求卡特兰数  Cn ，它表示 n 对括号的有效配对方式。

公式：

2. 大小为 n×n 的方格图，从左下角走到右上角不越过对角线：

问题描述：在一个 n×n 的方格中，从左下角 (0,0) 到右上角 (n,n) ，每步只能向右或向上走，且不能越过对角线  y=x 。

解法：这个问题可以通过卡特兰数来解决。具体来说，在每个路径中，我们可以将向右和向上的步骤视为 "右" 和 "上" 的动作，且要求路径从不越过对角线。这样的路径数目正好等于第  n 个卡特兰数。

答案： Cn  

3. 在圆上选择 2n 个点，连接成不相交的线段：

问题描述：在圆上选择  2n 个点，并将这些点成对连接，要求得到的  n 条线段不相交。

解法：这个问题对应的是卡特兰数的经典应用，涉及无交叉的配对。通过连线将圆上的  2n 个点成对连接，并且要求这些线段不相交，实际上是一个经典的卡特兰数问题。

答案：  Cn

4. 将凸多边形分成不相交的三角形：

问题描述：将一个 n 边的凸多边形分成不相交的三角形区域。

解法：这正是一个卡特兰数的经典应用问题，表示将一个凸多边形分解为不相交三角形的方式数。具体地，给定一个  n 边形，分割成三角形的方式数是  Cn-2 ，因为分割的三角形数目是 n-2 。

答案：  

5. 栈的不同出栈序列：

问题描述：对于一个无穷大的栈，入栈序列为 1, 2, 3, ..., n ，问有多少个不同的出栈序列。

解法：这个问题也可以通过卡特兰数来解决。它的数学意义是：对于一个给定的入栈序列，求出栈顺序不违反栈的顺序规则的不同方式数。此问题的解法就是第 n 个卡特兰数。

答案： Cn

6. n 个结点的不同二叉树：

问题描述：给定  个节点，问能构造多少个不同的二叉树。

解法：卡特兰数也可以表示构造不同二叉树的数量。给定  个节点，构造二叉树的不同方式数是第  个卡特兰数。

答案： Cn

7. 由 n 个 +1 和 n 个 -1 组成的数列，部分和不小于 0 ：

问题描述：



解法：这个问题可以通过卡特兰数来描述，因其本质上要求部分和始终不小于零。这是典型的“有效括号问题”，其中每个 +1 对应一个“开括号”，每个 -1 对应一个“闭括号”，而我们需要保证每个闭括号都在一个开括号之后。

答案：  Cn

8. 路径计数问题：



例题

P1044 [NOIP 2003 普及组] 栈



P1754 球迷购票问题



三金家的 Y 同学