【7】Catalan 数学习笔记

Eason_cyx · 2026-07-14 21:55:16 · 算法·理论

引入

下面摘抄自 OI Wiki：

Catalan 数经常出现在各类计数问题中。比利时数学家 Eugène Charles Catalan 在 1958 年研究括号序列计数问题时发现了这一数列，它也因此得名。清朝数学家明安图早在 18 世纪 30 年代就已经发现这一数列。

公式

记 C_n 为第 n 个卡特兰数，则有如下公式：

C_n=\sum_{i=0}^{n-1}C_iC_{n-1-i}

C_n=\frac{1}{n+1}\binom{2n}{n}

C_n=\binom{2n}{n}-\binom{2n}{n+1}

C_n=\frac{4n-2}{n+1}C_{n-1}

证明这些式子等价可以看 OI Wiki。

注意 C_0=1。用如上公式，可以得到 Catalan 数的前几项为

1,1,2,5,14,42,132,429\dots

（若在做题时跑小数据暴力发现答案与这个数列有重合，可以考虑 Catalan 数。）

应用

那么 Catalan 数有什么实际意义呢？下面来举几个例子：

路径计数问题：给定一个网格图，你要从左下角 (0,0) 走到右上角 (n,n)，且你的路径不能穿过对角线 y=x。求你的可行路径数。下面我们证明答案就是 C_n。
- 这个问题实际上和如下问题等价：
:::info[等价描述]{open} 求有多少个长度为 2n，包含恰好 n 个 0 和 n 个 1 的 01 串，满足对于该串的任意前缀，都有 1 的数量不少于 0 的数量。 :::

我们只需要考虑该等价问题即可。直接计算不太好算，我们考虑正难则反，总方案数显然是 \binom{2n}{n}，我们算出不合法的串串数，用总方案减掉即可。

记 p_i 为前 i 位中 1 的数量减去 0 的数量。如果该串不合法，那么一定存在一个地方使得 p_i=-1，此时 0 的数量比 1 多 1 个。那么我们找到第一个出现 p_i=-1 的位置，假设为 2q+1，那么也就是 p_{2q+1}=-1。那么也就是说，前 2q+1 位中包含 q 个 1 和 q+1 个 0。那么可以得出，后面剩下的位中包含 n-q 个 1 和 n-q-1 个 0。

现在我们将前 2q+1 位翻转，也就是 0 \to 1, 1 \to 0。翻转之后我们得到了一个新串，其中包含的 1 的个数恰好为 n-q+q+1=n+1 个！又由于我们选取的是最前面的一个位置，所以这些新串和原来不合法的串就一一对应，因此不合法串的个数就是 \binom{2n}{n+1}。

综上，合法字符串的方案数即为 \binom{2n}n-\binom{2n}{n+1}，这正是 Catalan 数。
括号序列计数问题：计算长度为 2n 的合法括号串数量。
- 记答案为 A_n，尝试递推。
不难发现第一个字符一定是左括号，我们考虑枚举与其匹配的右括号在哪里。假设其位置为 2k\ (1 \le k \le n)，那么 2 \sim 2k-1 位其实也构成了一个长度为 2k-2 的合法括号串，而这个长度的括号串方案数为 A_{k-1}；同理，2k+1 \sim 2n 也构成了一个长度为 2n-2k 的括号串，方案数为 A_{n-k}。根据乘法原理，答案就是
A_n=\sum_{k=1}^nA_{k-1}A_{n-k}=\sum_{k=0}^{n-1}A_kA_{n-1-k}
这正是 Catalan 数的递推公式。因此答案为 C_n。
二叉树计数问题：求包含 n 个点的不同二叉树数量。
- 考虑随便选一个根节点，假设左子树的大小为 k，那么右子树的大小就是 n-1-k。因此，如果设答案为 A_n，那么就有
A_n=\sum_{k=0}^{n-1}A_kA_{n-1-k}
这就是 Catalan 数的公式。

例题

P1641 [SCOI2010] 生成字符串

题目自己看，题意很简洁，这里不重复了。

这题其实和我们前面讲的路径计数问题很像，我们考虑在哪里修改一下……

在选出前 2q+1 个字符之后，剩下的个数变为了 n-q 个 1，m-q-1 个 0。那我们依旧把前面翻转，这样就有了 n-q+q+1=n+1 个 1。因此答案变为

\binom{n+m}{n}-\binom{n+m}{n+1}

时间复杂度 O((n+m)\log\text{mod})。带 \log 是因为我懒了，预处理直接写了快速幂。代码不贴了。

P3200 [HNOI2009] 有趣的数列

题意很简洁，不说了。

直接思考没啥头绪，我们考虑从 1 \sim 2n 依次往数列里面加数；显然如果放奇数 / 偶数位都需要顺着放，因此我们只需要记录这个数放在了奇数还是偶数位就可以还原出来最终数列。

用 0 表示放在了奇数位，1 表示放在了偶数位，那么我们将这个数列转换为了一个长度为 2n 的 01 串 s。

这个串有什么条件？这是本题最关键的一点：该串所有前缀 1 的个数都不超过 0 的个数。

如何证明？考虑反证，如果存在一个前缀 s_1 \sim s_p 使得其中的前缀 1 的个数超过了 0 的个数，假设 1 有 x 个，0 有 y 个，其中 x>y，那么这就意味着 a_{2x} 已经被填上了，但是 a_{2x-1} 还没有被填，这就会导致 a_{2x-1}>a_{2x}。所以上述结论成立。

既然如此，那么答案也就是 C_n 了。这题后续需要分解质因数来求最终答案（因为 p 可能不是质数），题解讲的很详细，且与本篇文章主题无关，不赘述。

P2532 [AHOI2012] 树屋阶梯

首先可以发现，既然这个阶梯的高为 n，并且只能用 n 的矩形，所以每个矩形必须占据一个最外侧的格子（即阶梯那一条）。

那么我们考虑枚举覆盖 (1,1) 的矩形对应的是哪一个阶梯。假设对应的是从上到下第 i 个阶梯，那么此时整个高为 n 的大阶梯被这个矩形切为了两个小阶梯，分别是

上方高为 i-1 的阶梯；
右边高为 n-i 的阶梯。

记高为 n 的阶梯的答案为 A_n，则根据上面分析，可以得到递推式为

A_n=\sum_{k=1}^{n}A_{k-1}A_{n-k}=\sum_{k=0}^{n-1}A_kA_{n-1-k}

这正是 Catalan 数的递推式。因此答案为 C_n。

本题需要使用高精度。~~所以我没写。~~

P3978 [TJOI2015] 概率论

期望题一般就是要么概率 DP 要么转成总数除以总方案数？这题看着后者就比较可做（？

我们记 f_n 表示 n 个点的二叉树个数，g_n 表示 n 个点的所有二叉树的叶子数之和。我们现在希望找到 f 和 g 的关系，因为显然答案即为 \frac{g_n}{f_n}，而 f_n 我们会算，就是 C_n。

对于一个 n 个点的二叉树，如果其有 k 个叶子，我们从其中任选一个去掉，就变成了一个包含 n-1 个点的二叉树。那么也就是说，这棵树有 k 种不同的方法变成一个 n-1 个点的二叉树。你会发现我们要求的就是 \sum k，而且这个操作是可逆的，并且是一一对应的，所以在这里可以完成原问题的转化——我们只需要求出对于所有包含 n-1 个点的二叉树，其加一个叶子的方案数之和即可。

我们随便拿一棵包含 n 个点的二叉树。设其有 a 个点有两个儿子，b 个点有一个儿子，c 个点是叶子。那么首先可以得到第一个等式：a+b+c=n。这是显然的，因为这是二叉树，每个点最多两个儿子。

然后还有另外一个等式：2a+b=n-1。这是为什么呢？因为 2a 相当于对应到这 a 个结点每个点的两个儿子，b 相当于那 b 个结点的所有儿子。所以 2a+b 可以不重不漏地对应到树中的所有儿子，而整颗树中只有根不作为儿子，因此加起来就是 n-1。

那么在这样的树上插入叶子有多少种方案呢？（注意，这里把一个叶子插入到一个点的左儿子和右儿子是不同的。）不难发现，就是 b+2c。那根据上面两个式子，其实可以算出 b+2c 的值：联立两个式子，可以得到 c-a=1；那么就有

b+2c=b+2(a+1)=b+2a-2=n+1

我们得到了一个常数！因此，一个包含 n-1 个点的二叉树插入一个叶子的方法有 n 种。

那么带回到原问题中，就可以得到：g_n=nf_{n-1}。

因此最终的答案就是 \dfrac{nf_{n-1}}{f_n}=\dfrac{nf_{n-1}}{\frac{4n-2}{n+1}f_{n-1}}=\dfrac{n(n+1)}{4n-2}。输出即可。

总结 & 后记

Catalan 数在组合数学题中比较常见，建议可以背一下前几项。这也启示我们，做这种数学题没思路的时候，可以试试先暴力跑一下小数据，看答案有没有什么规律。

码字不易，能否给个赞 /wq ><

若对文章有任何问题和建议可以与作者私信交流。