卡特兰数
引入
Catalan 数经常出现在各类计数问题中。比利时数学家 Eugène Charles Catalan 在 1958 年研究括号序列计数问题时发现了这一数列,它也因此得名。清朝数学家明安图早在 18 世纪 30 年代就已经发现这一数列。
Catalan 数满足如下递推关系:
数列的前几项为:(OEIS: A000108,下标从
应用
Catalan 数
-
路径计数问题:有一个大小为
的方格图,左下角为 ,右上角为 。从左下角开始,每次都只能向右或者向上走一单位,不走到对角线 上方(但可以触碰)的情况下,到达右上角的路径总数为 。证明
设方案数为
。考虑 的情况。设路径 第一次 走到对角线 的点是 。考察从 到 的除起点和终点外,中间的点 不经过对角线(不能碰到) 的路径。如图所示,这些路径的第一步一定向右,从
到 ;最后一步一定向上,从 到 。因此,这些路径就是从 到 的不越过直线 的路径,这样路径的数目就是 。同时,从 到 的合法路径数就是 。根据乘法原理,第一次在 处触碰对角线的路径数目为 。枚举 的所有可能性,所有合法路径的数目为做代换
就可以发现,这就是 Catalan 数的递推关系。由 可知 。 -
圆内不相交弦计数问题:圆上有
个点,将这些点成对连接起来且使得所得到的 条线段两两不交的方案数是 。证明
记
个点的方案数为 。将 个点按顺时针标号,分别为 。由于弦两两不交, 号点只能连接偶数号点;否则,两点之间的奇数个点无法在不穿过两点连线的情况下两两配对。如果连接了 和 ,那么左边有 个点,右边有 个点,由乘法原理,这样的方案数为 。因此,枚举 ,有 。令 ,就得到 Catalan 数的递推关系。由 可知 。 -
三角剖分计数问题:对角线不相交的情况下,将一个凸
边形区域分成三角形区域的方法数为 。证明
设
边形三角剖分的方案数为 。先选定一条边 作为基边,它一定属于一个三角形,记该三角形的第三个点为 。这样,原凸多边形变成了三个部分:- 三角形
。 边形,顶点 。 边形,顶点 。
后面两个部分都是子问题,所以,有递推关系
令
,就得到 Catalan 数递归关系。由 可知 。 - 三角形
-
二叉树计数问题:含有
个结点的形态不同的二叉树数目为 。等价地,含有 个非叶结点的形态不同的满二叉树数目为 。证明
记
个结点的二叉树数目为 。任取一个根结点,枚举左右子树大小。设左子树大小为 ,则右子树大小为 。左右子树均为子问题,所以,有递推关系这就是 Catalan 数递推关系。由
可知 。 -
括号序列计数问题:由
对括号构成的合法括号序列数为 。证明
联系路径计数问题。将左括号视为向上走,右括号视为向右走。合法括号序列即为,在任意位置,左括号的数量不少于右括号的数量。相当于路径计数问题中,在任意时刻,向上走的次数不少于向右走的次数。因此,合法括号序列与合法路径之间存在双射。合法括号序列的数目同样为
。 -
出栈序列计数问题:一个栈(无穷大)的进栈序列为
,合法出栈序列的数目为 。证明
联系括号序列计数问题。将入栈视为左括号,出栈视为右括号。任意时刻,入栈的次数不少于出栈的次数。因此,合法出栈序列与合法括号序列之间存在双射。合法出栈序列的数目同样为
。 -
数列计数问题:由
个 和 个 组成的数列 中,部分和满足 的数列数目为 。证明
联系括号序列计数问题。将
视为左括号, 视为右括号。任意时刻, 的数量不少于 的数量。因此,合法数列与合法括号序列之间存在双射。合法数列的数目同样为 。
尽管这一递推关系应用广泛,但是直接计算复杂度较高,需要寻找更为简单的公式。
常见形式
Catalan 数有如下常见的表达式:
Catalan 数的这些形式都可以高效计算:前两个形式将它转换为阶乘和组合数的计算问题,第三个形式则提供了顺次计算的递推公式。
对于这三种常见形式,本文提供两种证明方式。
代数推演
通过代数方法得出 Catalan 数的上述表达式共两步。首先,验证三个形式相互等价。
证明表达式 
等价
只需要证明表达式
以及,表达式
因此,三个表达式互相等价。
紧接着,验证这些形式确实是 Catalan 数递推公式的解。为此,考虑使用生成函数方法直接求出递推公式
利用生成函数方法求解递推公式 
考虑 Catalan 数的普通生成函数
其中,倒数第二个等号交换了求和次序,并令
由初值条件
接下来,需要将它展开为幂级数的形式。利用
其中,
代入
由此,就得到
组合意义
由于 Catalan 数具有明显的组合意义,所以只使用组合计数方法同样可以证明这些形式。本节为三个表达式分别提供一个组合意义的证明。
表达式 
的证明
考虑 数列计数问题。对于任意由
为此,可以构造一个从超额量为
由于原序列中
映射
由此,映射
这就证明了 Catalan 数的表达式
表达式 
的证明
考虑 路径计数问题。这是典型的格路计数问题,可以通过反射原理求解。具体到本问题,考虑用总路径数目减去不合法的路径数目。总路径数一共要走
由于从
这就是 Catalan 数的表达式
表达式 
的证明
考虑 三角剖分计数问题。设
如图所示,这两组操作得到的结果之间存在明显的双射。对于
稍作整理,并结合
例题
洛谷 P1044 栈
入栈顺序为
参考代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|
1 2 3 4 5 6 7 |
|
习题
- Luogu P2532 [AHOI2012] 树屋阶梯
- Luogu P1641 [SCOI2010] 生成字符串
- Luogu P3200 [HNOI2009] 有趣的数列
- AtCoder Beginner Contest 205 E - White and Black Balls
- AtCoder Regular Contest 145 C - Split and Maximize
- Luogu P5014 水の三角(修改版)
- Luogu P3978 [TJOI2015] 概率论
参考资料与注释
本页面最近更新:2025/9/12 00:20:24,更新历史
发现错误?想一起完善? 在 GitHub 上编辑此页!
本页面贡献者:Ir1d, StudyingFather, H-J-Granger, countercurrent-time, Enter-tainer, NachtgeistW, Xeonacid, MegaOwIer, AngelKitty, CCXXXI, cjsoft, diauweb, Early0v0, ezoixx130, GekkaSaori, Konano, ksyx, LovelyBuggies, Makkiy, mgt, minghu6, P-Y-Y, PotassiumWings, SamZhangQingChuan, sshwy, Suyun514, Tiphereth-A, weiyong1024, c-forrest, Chrogeek, Fidelxyz, GavinZhengOI, Gesrua, Great-designer, Henry-ZHR, HeRaNO, hsfzLZH1, iamtwz, kenlig, kfy666, kxccc, lychees, Marcythm, Menci, Peanut-Tang, purple-vine, refinedcoding, shawlleyw, ShizuhaAki, Skyminers, SukkaW, ucSec, xglight, zryi2003
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供,附加条款亦可能应用