自 2010 年 · 每月支持超过 200 万次工具运行
自 2010 年
添加到 Chrome

我的工具箱

自动模式

还没有收藏的工具。

升级为高级版
相关工具
斯特林数计算器多边形对角线计算器相对风险计算器保留率计算器
主页 > 数学 > 数列工具
 

卡特兰数生成器

计算第 n 个卡特兰数，查看公式推导、括号匹配和多边形三角剖分图示、数列表及相关组合意义。

免费使用无需注册2026年2月更新
卡特兰数生成器立即免费试用 ▼

尝试快速示例：

C₅ = 42 C₁₀ = 16796 C₃ = 5 C₂₀ (大数值)
提示： 卡特兰数 Cn 用于计算平衡括号序列、二叉树、多边形三角剖分、Dyck 路径以及 200 多种其他组合结构。

Embed 卡特兰数生成器 Widget

卡特兰数生成器

欢迎使用卡特兰数生成器。这是一个用于计算和探索卡特兰数（数学中最引人入胜的序列之一）的综合工具。无论您是在学习组合数学、准备算法竞赛，还是研究代数结构，本计算器都能提供 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。

闭式公式

第 n 个卡特兰数
$$C_n = \frac{1}{n+1}\binom{2n}{n} = \frac{(2n)!}{(n+1)!\,n!}$$

递推关系

卡特兰递推公式
$$C_0 = 1, \quad C_{n+1} = \sum_{i=0}^{n} C_i \, C_{n-i} = \frac{2(2n+1)}{n+2}\,C_n$$

生成函数

卡特兰数的普通生成函数为：

生成函数
$$c(x) = \frac{1 - \sqrt{1 - 4x}}{2x} = \sum_{n=0}^{\infty} C_n x^n$$

组合数学解释

卡特兰数回答了极其大量的计数问题。数学家理查德·斯坦利（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} 的非交叉划分数量。这些划分具有如下性质：当在圆周上绘制时，没有任何两个块会相互“交叉”。

如何使用此计算器

  1. 输入 n： 在输入框中键入 0 到 500 之间的非负整数。可以使用快速示例按钮获取常用值。
  2. 点击生成： 点击“生成卡特兰数”按钮来计算 Cn。
  3. 查看结果： 查看 Cn 的精确值、位数、逐步公式推导以及递推关系验证。
  4. 探索可视化： 对于较小的 n (≤ 4)，浏览所有平衡括号序列。对于 n ≤ 5，查看交互式 Dyck 路径图。
  5. 浏览序列： 滚动查看卡特兰数对照表，您计算的数值会被高亮显示。

渐近增长

卡特兰数呈指数级增长。渐近公式为：

渐近近似
$$C_n \sim \frac{4^n}{n^{3/2}\sqrt{\pi}}$$

这意味着 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日

开发者 API 可用: 用一次 JSON HTTP 请求，把这个工具接入你的应用、自动化流程或智能体。 查看 API 文档

您还可以尝试我们的 AI数学解题器 GPT，通过自然语言问答解决您的数学问题。

数列工具:

热门与最新工具:

快乐数计算器复数计算器五数概括计算器查看全部 →
主页 > 数学 > 数列工具 > 卡特兰数生成器