2026年3月专项训练巩固总结

组合数学特殊数列

卡特兰数

卡特兰数最重要的两个东西：

• 折线法推导
• 常见模型

$C_0 = 1, C_i = \sum_{i=0}^{n - 1}C_i \times C_{n - 1 - i}$

前几项是：$1,1,2,5,14,42...$

其有众多经典的现实模型，我们分两类介绍，下面是第一类：

• 长度为 $2n$ 的合法括号序列的个数。
• 从 $(0, 0)$ 走到 $(n, n)$ 的不穿过 $y = x$ 的路径条数。
• $n$ 个数，按照顺序入栈，只要不是空栈就随时可以出栈，得到的出栈序列种类数。

这一类强调的是，我们要做 $2n$ 次决策，决策有两种，决策序列的每个前缀中，第一种决策的个数不应该少于第二种决策的个数。

再看一下第二类：

• 圆周上给你 $2n$ 个点，两两配对连成弦，问有多少种使得弦两两不相交的方案。
• 凸 $n + 2$ 边形，剖分成 $n$ 个三角形的方案数。
• 含有 $n$ 个结点的不同的二叉树形态数。

这一类突出的是，我们有一个规模为 $n$ 的问题，通过枚举中间点，能将问题拆成规模为 $i$ 的问题和规模为 $n - 1 - i$ 的问题的乘积的和。

只要一个事情能转化得和这两类中的某类一样，就说明该上卡特兰数了。

卡特兰数的定义式不好算，我们要找一些更好的办法。

我们以 $(0, 0)$ 到 $(n, n)$ 的不穿过 $y = x$ 的路径条数来推导一下，已知所有路径有 $C(2n, n)$ 种，减去穿过的就是不穿过的。我们考虑某个穿过的路径，其肯定和 $y = x + 1$ 有交点，设第一次交点是 $p$。我们把 $(0, 0)$ 到 $p$ 的这段路径，以 $y = x + 1$ 为对称轴，对称过去，就能发现变成了一条由 $(-1, 1)$ 到 $(n, n)$ 的路径。容易说明每条从 $(-1, 1)$ 到 $(n, n)$ 的路径，唯一对应一条从 $(0, 0)$ 走到 $(n, n)$ 且穿过了 $y = x$ 的路径，所以非法路径条数其实就是 $C(2n, n + 1)$，所以合法路径条数就是 $C(2n, n) - C(2n, n + 1)$。

这个式子显然只需要预处理阶乘及其逆元就能算了，比定义式好算多了。

这个推导方法叫做折线法，使用这个办法也能推导出从 $(0, 0)$ 走到 $(n, m)$，不穿过 $y = x$ 的路径条数，这个东西叫做广义卡特兰数。

会这个方法，基本上就不愁不会算卡特兰数了，其他的公式可以暂时不管。

第二类斯特林数

第一类斯特林数

贝尔数

分拆数

思维题

曼哈顿距离

连续段DP