卡特兰数生成器
生成第 n 个卡特兰数，包含逐步公式推导、括号化与多边形三角剖分的交互式可视化、完整的序列对照表，以及针对数学、计算机科学和算法竞赛的深度组合数学解释。
检测到广告拦截，导致我们无法展示广告
MiniWebtool 依靠广告收入免费提供服务。如果这个工具帮到了你，欢迎开通 Premium（无广告 + 更快），或将 MiniWebtool.com 加入白名单后刷新页面。
- 或升级 Premium（无广告）
- 允许 MiniWebtool.com 显示广告，然后刷新
卡特兰数生成器
欢迎使用卡特兰数生成器。这是一个用于计算和探索卡特兰数（数学中最引人入胜的序列之一）的综合工具。无论您是在学习组合数学、准备算法竞赛，还是研究代数结构，本计算器都能提供 Cn 的精确值，以及逐步推导过程、交互式 Dyck 路径可视化、平衡括号序列枚举和深入的组合数学解释。
什么是卡特兰数？
卡特兰数是一组自然数序列，出现在组合数学中种类繁多的计数问题中。序列如下：
C0=1, C1=1, C2=2, C3=5, C4=14, C5=42, C6=132, C7=429, ...
这些数字以比利时数学家欧仁·查理·卡特兰（Eugène Charles Catalan, 1814–1894）的名字命名，但实际上最早是由莱昂哈德·欧拉发现的，他在 1750 年代使用它们来计算凸多边形的三角剖分数量。该序列在 OEIS（整数序列在线百科全书）中被编为 A000108。
闭式公式
递推关系
生成函数
卡特兰数的普通生成函数为：
组合数学解释
卡特兰数回答了极其大量的计数问题。数学家理查德·斯坦利（Richard Stanley）归纳了 200 多种不同的组合解释。以下是最重要的几种：
1. 平衡括号序列
Cn 计算正确匹配 n 对括号的方法数。例如，C3 = 5，因为 3 对括号恰好有 5 种有效排列：((())), (()()), (())(), ()(()), 和 ()()()。
2. Dyck 路径
Cn 是 Dyck 路径的数量。Dyck 路径是从 (0,0) 到 (2n,0) 的单调网格路径，使用步进 U=(1,1) 和 D=(1,−1)，且永远不会跌至 x 轴下方。等效地，这些是 n×n 网格中从左下角到右上角且保持在主对角线上方（或下方）的路径。
3. 多边形三角剖分
Cn 计算通过绘制不相交的对角线将具有 n+2 条边的凸多边形划分为三角形的方法数。这是导致该序列被发现的最初的欧拉问题。
4. 满二叉树
Cn 计算具有 n+1 个叶节点（等效地，n 个内部节点）的满二叉树（每个节点有 0 或 2 个子节点）的数量。这与具有 n 个键的不同二叉搜索树的数量密切相关。
5. 山脉轮廓
Cn 是可以用 n 次上坡和 n 次下坡绘制的山脉轮廓数量。这些在视觉上与 Dyck 路径相同，但被解释为地平线剪影。
6. 非交叉划分
Cn 等于集合 {1, 2, ..., n} 的非交叉划分数量。这些划分具有如下性质：当在圆周上绘制时，没有任何两个块会相互“交叉”。
如何使用此计算器
- 输入 n： 在输入框中键入 0 到 500 之间的非负整数。可以使用快速示例按钮获取常用值。
- 点击生成： 点击“生成卡特兰数”按钮来计算 Cn。
- 查看结果： 查看 Cn 的精确值、位数、逐步公式推导以及递推关系验证。
- 探索可视化： 对于较小的 n (≤ 4)，浏览所有平衡括号序列。对于 n ≤ 5，查看交互式 Dyck 路径图。
- 浏览序列： 滚动查看卡特兰数对照表，您计算的数值会被高亮显示。
渐近增长
卡特兰数呈指数级增长。渐近公式为：
这意味着 Cn 大致按 4n 增长，但带有一个多项式修正因子。随着 n 变大，比率 Cn/Cn-1 趋于 4。
在计算机科学中的应用
| 应用场景 | Cn 的计算意义 |
|---|---|
| 二叉搜索树 | 具有 n 个键的不同 BST 数量 |
| 矩阵链乘法 | n+1 个矩阵相乘时的括号化方法数 |
| 堆栈排序排列 | 可以通过单个堆栈排序的 {1,...,n} 的排列数 |
| 表达式解析 | 具有 n 个运算符的表达式的不同解析树数量 |
| 递归算法 | 算法竞赛中动态规划问题的基础模型 |
其他领域的卡特兰数
- 代数几何： 出现在格拉斯曼流形和舒伯特演算的研究中。
- 概率论： 与选票问题（ballot problem）和随机游走理论相关。
- 数学物理： 与量子场论中的平面图（planar diagrams）有关。
- 语言学： 计算给定长度句子的语法解析树数量。
常见问题解答
什么是卡特兰数？
卡特兰数是一组自然数序列（1, 1, 2, 5, 14, 42, 132, ...），出现在组合数学的许多计数问题中。第 n 个卡特兰数由公式 Cn = (2n)! / ((n+1)! × n!) = C(2n,n) / (n+1) 给出。它们用于计算平衡括号序列、二叉树、多边形三角剖分和 Dyck 路径等结构的数量。
如何计算第 n 个卡特兰数？
第 n 个卡特兰数可以使用直接公式 Cn = C(2n,n)/(n+1) 计算，其中 C(2n,n) 是中心二项式系数。或者，也可以使用递推关系 Cn = 2(2n−1)/(n+1) × Cn−1，其中 C0 = 1。对于较大的 n，渐近近似公式 Cn ≈ 4n / (√(πn) × (n+1)) 可以提供很好的估计。
卡特兰数可以计算什么？
卡特兰数可以计算极其广泛的组合结构：正确匹配 n 对括号的方法数、具有 n 个内部节点的满二叉树数量、长度为 2n 的 Dyck 路径数量、将凸 n+2 边形剖分为三角形的方法数、集合的非交叉划分数量，以及其他 200 多种已知的解释。
卡特兰数的增长速度有多快？
卡特兰数呈指数级增长。其渐近公式为 Cn ~ 4n / (n3/2 × √π)，意味着它们大致按 4 的幂增长。例如，C10 = 16,796，C20 = 6,564,120,420，而 C100 拥有 58 位数字。随着 n 的增加，比率 Cn/Cn−1 趋近于 4。
卡特兰数在计算机科学中有什么用途？
在计算机科学中，卡特兰数出现在：计算具有 n 个节点的二叉搜索树的数量、解析具有 n 个运算符的表达式的方法数、堆栈排序排列、n+1 个矩阵相乘的乘法顺序（与矩阵链乘法相关），以及算法竞赛中的各种动态规划问题中。
延伸资源
引用此内容、页面或工具为：
"卡特兰数生成器" 于 https://MiniWebtool.com/zh-cn//，来自 MiniWebtool，https://MiniWebtool.com/
由 miniwebtool 团队开发。更新日期：2026年2月19日
您还可以尝试我们的 AI数学解题器 GPT，通过自然语言问答解决您的数学问题。