卡塔兰数是一个正整数序列,广泛出现于组合数学中,尤其常见于涉及嵌套、分支和非交叉结构的问题。下标从零开始时,第 个卡塔兰数为
这个序列的前几项是
这些数所计数的对象中,有许多看似互不相关,但它们的递归分解往往具有相同的形式。对象之间的对应关系解释了为什么同一个序列会反复出现。
定义与递推关系
在定义公式中, 是一个中心二项式系数,感叹号表示阶乘。在许多计数解释中,初始值 代表一个空结构。
一个基本的递推关系是
例如,
这一递推描述的对象由一个指定的根或最外层部分,以及两个有先后之分的子结构组成。如果两个子结构的规模分别为 和 ,那么它们共有 种选法。对所有可能的拆分求和,就得到总数。
显式公式还可以导出一个一阶递推:
与卷积递推不同,这个公式只需根据前一项就能直接算出下一项。
另一个有用的恒等式是
这个表达式不仅表明闭式公式的值是整数,也会在格路径的反射论证中自然出现。
主要计数解释
匹配括号
是由 个左括号和 个右括号组成的合法括号串的数量。所谓合法,是指任意前缀中的左括号数都不少于右括号数,且整个串中的左右括号总数相等。
当 时,五个合法括号串为
((()))
(()())
(())()
()(())
()()()
每个非空合法括号串都可以唯一分解为
其中 和 本身也是合法括号串。式中紧接 的右括号与最初的左括号配对。如果 含有 对括号,而整个串含有 对,那么 就含有 对。由此便得到卡塔兰递推。
戴克路径
半长为 的戴克路径是从 到 的格路径,其步长向量为
且始终不低于水平轴。这样的路径共有 条。
将每个左括号替换为 ,每个右括号替换为 ,就得到合法括号串与戴克路径之间的对应。括号匹配条件相应地变成路径高度始终非负的要求。
等价地, 也计数从 到 、每步向北或向东、且从不越到对角线 上方的路径。
有序严格二叉树
是具有 个内部顶点的有根、有序、严格二叉树的数量。这里:
- 每个内部顶点恰有两个子节点;
- 两个子节点区分为左子节点和右子节点;
- 具有 个内部顶点的树有 个叶节点。
对于一棵非平凡的树,移去根节点后,剩下左子树和右子树。如果原树有 个内部顶点,而左子树有 个,那么右子树就有 个,这又得到了卡塔兰递推。
“有序”和“严格”这两个限定很重要:改变树的类别,计数序列也会改变。卡塔兰数还计数具有 条边的有根平面树,其中每个顶点的子节点都具有线性顺序。
乘积的完全括号化
对于 个因子的乘积,在保持因子顺序且只使用二元运算的条件下,完全加括号的方式共有 种。
对于四个因子,五种方式为
这些是语法上的不同安排。如果运算满足结合律,所有安排的值都相同,但它们仍是不同的括号化方式。对于矩阵乘法,即使所得矩阵不变,不同括号化方式所需的算术运算次数也可能不同。
多边形的三角剖分
对于 ,具有 个顶点的凸多边形的三角剖分数为 。三角剖分是用互不相交的内部对角线,将多边形划分成三角形。
因此,五边形有 种三角剖分。这里将多边形的顶点视为固定且可区分的;通过旋转或反射相互对应的剖分不视为同一种。
固定一条边,考察以它为边的三角形,就可以把剩余区域分成两个较小的多边形区域。这给出了卡塔兰递推的另一种形式,其中空区域按约定 处理。
非交叉划分与模式避免置换
将 个点依次放在圆周上,它们的一个非交叉划分是指各块互不交叉的集合划分。更确切地说,不能存在按圆周顺序排列的四个点 ,使得 位于同一块,而 位于另一个块。这样的划分共有 个。
卡塔兰数还计数若干类受限置换。例如, 是 的避免模式 的置换数,即不存在下标 使得
公式的反射证明
包含 个上升步和 个下降步、不加其他限制的路径共有
条。要计数戴克路径,只需减去那些到达过高度 的路径。
对于每条这样的不合要求路径,将起点至首次到达高度 处的路径段反射,即互换其中的上升步和下降步。变换后的路径有 个上升步和 个下降步,终点高度为 。
这一变换是可逆的:每条长度为 、终点高度为 的路径都必定先到达高度 ,将起点至首次到达该高度处的路径段反射,就能还原出一条不合要求的路径。因此,这一变换是一个双射函数,不合要求的路径数为
所以,
这是路径计数中反射原理的一个实例。
生成函数
定义普通生成函数
卷积递推转化为
解这个二次方程可得
这里选择负号,是因为这一分支具有常数项为 的幂级数展开,而另一分支没有。在 处,表达式的值按其可去奇点处的极限理解。
作为形式幂级数,这个恒等式无需解析意义上的收敛条件,就能表达递推关系。作为复幂级数,它的收敛半径为 。
这种含平方根的形式是许多递归定义的树状结构类的典型特征。它也提供了从递推关系推导系数显式公式的一条途径。
增长与概率
在阶乘公式中使用斯特林近似,可得
更精确地,
其中 是大O记号。相邻两项之比满足
因此趋于 。
路径解释给出了一个简单的概率恒等式。如果从所有具有 个上升步和 个下降步的路径中等概率选取一条,那么
也就是说,路径始终不低于高度零的概率为 。等价地,对于一个以经过 步后回到零点为条件的对称随机游走,全过程保持非负的概率为 。
计算与应用
一阶递推可以用精确整数运算计算这个序列。在每一步中,分子
都能被 整除。先乘后除可以避免整数运算中的截断。直接用浮点数计算阶乘,即使最终结果仍在可表示范围内,中间计算也可能溢出。
计算到 为止的所有项,卷积递推需要 次算术运算,而一阶递推需要 次。这些是算术运算次数,而非位复杂度界:存储各项所需的位数会随 增大。
在计算机科学中,卡塔兰数描述了涉及表达式树、嵌套语法和括号化方式的搜索空间大小。它们解释了为什么穷举很快就会变得不可行。
计数和优化是不同的任务。对于 个矩阵的矩阵链乘法问题,虽然有 种可能的括号化方式,但动态规划无需列出所有方式,就能找到最优的括号化方案。
卡塔兰分解还可以用于均匀随机生成。要均匀随机生成一棵具有 个内部顶点的有序严格二叉树,先以概率
选择左子树的规模 ,再按照选定的规模,分别独立、均匀地生成左子树和右子树。如果等概率选择拆分规模,通常不能得到树上的均匀分布。
历史与推广
这一序列以比利时数学家欧仁·夏尔·卡塔兰命名,他在十九世纪研究过括号化问题。不过,它的历史更早:莱昂哈德·欧拉在十八世纪研究了多边形的三角剖分,约翰·安德烈亚斯·冯·塞格纳则得到了相应的递推关系。蒙古族数学家明安图的研究中也独立出现过这些数。
一种标准的推广是富斯–卡塔兰数:
它们计数具有 个内部顶点的有根有序严格 叉树,即每个内部顶点恰有 个有顺序的子节点。当 时,它们退化为普通卡塔兰数。其生成函数满足
纳拉亚纳数给出了卡塔兰计数的细分:
它们计数半长为 、恰有 个峰的戴克路径,其中峰指一个上升步后面紧接一个下降步。因此,