2014 字
10 分钟
卡特兰数

更详细的内容可以参考[Tutorial] Catalan Numbers and Catalan Convolution
卡特兰数 (Catalan)
以走网格为例,从格点 走到格点 ,只能向右或向上走,并且不能越过对角线的路径的条数,就是卡特兰数,记为 。
通项公式
(1) (2) (3)
证明(1)式
- 先求路径总数:在 次移动中选 次向右移动,即 。
- 再求非法路径:即越过对角线的路径。
- 反射原理:把 这条线画出来,碰到即说明是一条非法路径。 所有的非法路径与这条线有至少一个交点,把第一个交点设为 ,把 之后的路径全部按照 这条线对称过去。这样,最后的终点就会变成 。
- 结论:所有非法路径对称后都唯一对应着一条到 的路径,所以非法路径数就是 ,合法路径数就是 。
证明(2)式

卡特兰数的特征
一旦出现类似二叉树数量的递归定义,或是一种操作数不能超过另一种操作的操作数,大概率是卡特兰数
卡特兰数应用
求解下面的合法数量
1. 0和1组成的字串(任一前缀中 0 的个数 1)
- 推导:这可以直接映射为网格路径问题。
- 令 0 代表“向右走一步”,1 代表“向上走一步”。
- 共有 个 0 和 个 1,意味着从 走到 。
- “前缀中 0 的个数 1 的个数”意味着在路径的任何时刻,向右的步数都不小于向上的步数,即路径始终在 这条线的下方(或接触)。
- 结论:这就是卡特兰数的标准定义模型,方案数为 。
2. 组括号的合法运算式
- 推导:
- 将左括号
(看作数字 0,右括号)看作数字 1。 - 合法的括号表达式要求:在任意位置,左括号的数量必须大于等于右括号的数量(否则会出现未匹配的右括号)。
- 这与问题 1 的 0-1 字符串约束完全一致。
- 将左括号
- 结论:方案数为 。
3. 栈的出栈序列
- 推导:
- 在操作过程中,我们一共要执行 次“入栈”和 次“出栈”。
- 令入栈为 0,出栈为 1。
- 约束条件:在任何时刻,已经出栈的元素个数不能超过已经入栈的元素个数(栈空了就没法出栈)。
- 这再次回到了 0-1 字符串的路径模型。
- 结论:方案数为 。
4. 个结点构造二叉树
- 推导(递归法):
- 设 为 个结点的二叉树数量。
- 固定一个结点作为根结点,剩下的 个结点分配给左子树和右子树。
- 若左子树分配 个结点,则右子树有 个结点。
- 根据乘法原理,形态数为 。
- 遍历 的所有可能值 (),得到递推式:。
- 结论:这是卡特兰数的标准递归定义,方案数为 。
5. 圆上 个点连成 条不相交弦
- 推导:
- 任选一个点 ,它必须连接到另一个点 。
- 为了使剩下的点能成对且不与弦 相交,这条弦必须将圆周剩下的 个点分成两部分,且每部分点的个数必须是偶数。
- 设 连接到 ,则一边有 个点,另一边有 个点。
- 这就转化成了两个规模更小的同类子问题: 和 。
- 结论:其递推式与二叉树一致,方案数为 。
6. 多边形三角剖分
- 问题描述:通过不相交的对角线将 边凸多边形分割成 个三角形。
- 推导:
- 固定多边形的一条边作为底边。
- 选择除了底边端点外的任意一个顶点 与底边构成一个三角形。
- 这个三角形将原多边形分割成了两个较小的多边形(左边一个 边形,右边一个 边形)。
- 累加所有顶点的选择情况,其递推结构同样符合卡特兰数。
- 结论:对于 边形,剖分方案数为 。
P1044 [NOIP 2003 普及组] 栈 超级裸的板子 代码
#include <bits/stdc++.h>#include <cstdlib>#define ll long long#define N 10005#define pr pair<ll, ll>using namespace std;ll n, ans, m, cnt, vv, p;int main() { ios::sync_with_stdio(0); cin.tie(nullptr); cout.tie(nullptr); vector<unsigned long long> f(100, 0); f[0] = 1; for (unsigned long long i = 1; i <= 20; i++) { f[i] = (4 * i - 2) * f[i - 1] / (i + 1); } cin >> n; cout << f[n]; return 0;}进阶卡特兰数:广义与卷积
当问题不再是标准的“从0开始到0结束”,而是增加了“开局自带 个左括号”或“需要分成 个部分”的限制时,我们需要使用广义卡特兰数。
1. 问题模型:带 个前缀的合法序列
- 场景:你需要构造一个合法的括号序列。
- 限制:序列必须以 个左括号开头(或者题目给出的前缀导致当前左括号比右括号多 个)。
- 任务:在剩余的位置中,填入 个左括号和 个右括号,使得整个序列合法(最终左括号总数 = 右括号总数,且任意前缀左 右)。
- 记号:记为 。
2. 通项公式
化简后可得:
注意:当 时,公式变回普通卡特兰数 。
3. 证明:广义反射原理 (Reflection Principle)
依然使用网格路径模型,但死亡线发生了平移。
- 初始状态:因为开局自带 个左括号(相当于有 个“复活币”),只有当右括号数量比左括号数量多出 个时,路径才非法。
- 死亡线:从 变为 。
- 坐标变换:
- 起点:。
- 终点: ( 步向右, 步向上)。
- 总路径数:。
- 镜像反射:
- 非法路径一定触碰 。
- 将第一次触碰点之后的路径关于该直线对称。
- 原终点 对称后的新终点为 。
- 结论:
4. 结构意义:卡特兰卷积
为什么这种形式被称为卷积?
考虑 的情况,强制开头为 ((。这相当于把整个序列被这两个强制的左括号分割成了三个独立的部分(外层、中层、内层):
总方案数等于将 个空闲的括号对分配给 A、B、C 三个区域的方案之和:
这就是卡特兰数列的 次卷积。
递推公式
#include <bits / stdc++.h>#define N 1000005#define inf 0x3f3f3f3f3f3f3f3f#define ll long long#define pr pair<int, int>#define i128 __int128using namespace std;ll n, m, q;const ll mod = 1e9 + 7;int main() { ios::sync_with_stdio(0); cin.tie(nullptr); cout.tie(nullptr); vector<ll> f(N, 0); auto qp = [&](ll x, ll n) { ll res = 1; while (n) { if (n & 1) res = (res * x) % mod; x = (x * x) % mod; n >>= 1; } return res; }; cin >> n; string s; cin >> s; n -= s.length(); int k = 0; for (auto x : s) { if (x == '(') k++; else k--; if (k < 0) { cout << 0; return 0; } } n -= k; if (n < 0) { cout << 0; return 0; } auto init = [&]() { f[0] = 1; for (int i = 1; i < N; i++) { f[i] = (((f[i - 1] * (2 * i + k)) % mod * (2 * i + k - 1)) % mod * qp(i, mod - 2)) % mod * qp(i + k + 1, mod - 2) % mod; } }; init(); if (n % 2) cout << 0; else cout << f[n / 2]; return 0;}分享文章
生成精美分享图或复制链接,与更多人分享本文。
继续阅读
换条路线
从其他文章中稳定抽取
最后更新于 ,距今已过 74 天
部分内容可能已过时