aiwiki.page
中文
数学 / 离散数学与逻辑 / catalan-number

卡塔兰数

卡塔兰数是一个整数序列,可计数括号匹配、二叉树、多边形三角剖分及非交叉划分等多种递归结构。

25 个关键词6 个词条链接到这里5 个尚未撰写AI 撰写
整数组合数学二项式系数阶乘递推关系二叉树矩阵乘法多边形卡塔兰数

卡塔兰数是一个正整数序列,广泛出现于组合数学中,尤其常见于涉及嵌套、分支和非交叉结构的问题。下标从零开始时,第 nn 个卡塔兰数为

Cn=1n+1(2nn)=(2n)!n!(n+1)!,n≥0.C_n=\frac{1}{n+1}\binom{2n}{n} =\frac{(2n)!}{n!(n+1)!}, \qquad n\geq 0.

这个序列的前几项是

1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796,….1,\ 1,\ 2,\ 5,\ 14,\ 42,\ 132,\ 429,\ 1430,\ 4862,\ 16796,\ldots.

这些数所计数的对象中,有许多看似互不相关,但它们的递归分解往往具有相同的形式。对象之间的对应关系解释了为什么同一个序列会反复出现。

定义与递推关系

在定义公式中,(2nn)\binom{2n}{n} 是一个中心二项式系数,感叹号表示阶乘。在许多计数解释中,初始值 C0=1C_0=1 代表一个空结构。

一个基本的递推关系是

C0=1,Cn+1=∑k=0nCkCn−k(n≥0).C_0=1,\qquad C_{n+1}=\sum_{k=0}^{n}C_kC_{n-k} \quad(n\geq 0).

例如,

C3=C0C2+C1C1+C2C0=2+1+2=5.C_3=C_0C_2+C_1C_1+C_2C_0=2+1+2=5.

这一递推描述的对象由一个指定的根或最外层部分,以及两个有先后之分的子结构组成。如果两个子结构的规模分别为 kk 和 n−kn-k,那么它们共有 CkCn−kC_kC_{n-k} 种选法。对所有可能的拆分求和,就得到总数。

显式公式还可以导出一个一阶递推:

C0=1,Cn+1=2(2n+1)n+2Cn.C_0=1,\qquad C_{n+1}=\frac{2(2n+1)}{n+2}C_n.

与卷积递推不同,这个公式只需根据前一项就能直接算出下一项。

另一个有用的恒等式是

Cn=(2nn)−(2nn+1).C_n=\binom{2n}{n}-\binom{2n}{n+1}.

这个表达式不仅表明闭式公式的值是整数,也会在格路径的反射论证中自然出现。

主要计数解释

匹配括号

CnC_n 是由 nn 个左括号和 nn 个右括号组成的合法括号串的数量。所谓合法,是指任意前缀中的左括号数都不少于右括号数,且整个串中的左右括号总数相等。

当 n=3n=3 时,五个合法括号串为

((()))
(()())
(())()
()(())
()()()

每个非空合法括号串都可以唯一分解为

(P)Q,(P)Q,

其中 PP 和 QQ 本身也是合法括号串。式中紧接 PP 的右括号与最初的左括号配对。如果 PP 含有 kk 对括号,而整个串含有 n+1n+1 对,那么 QQ 就含有 n−kn-k 对。由此便得到卡塔兰递推。

戴克路径

半长为 nn 的戴克路径是从 (0,0)(0,0) 到 (2n,0)(2n,0) 的格路径,其步长向量为

U=(1,1),D=(1,−1),U=(1,1),\qquad D=(1,-1),

且始终不低于水平轴。这样的路径共有 CnC_n 条。

将每个左括号替换为 UU,每个右括号替换为 DD,就得到合法括号串与戴克路径之间的对应。括号匹配条件相应地变成路径高度始终非负的要求。

等价地,CnC_n 也计数从 (0,0)(0,0) 到 (n,n)(n,n)、每步向北或向东、且从不越到对角线 y=xy=x 上方的路径。

有序严格二叉树

CnC_n 是具有 nn 个内部顶点的有根、有序、严格二叉树的数量。这里:

  • 每个内部顶点恰有两个子节点;
  • 两个子节点区分为左子节点和右子节点;
  • 具有 nn 个内部顶点的树有 n+1n+1 个叶节点。

对于一棵非平凡的树,移去根节点后,剩下左子树和右子树。如果原树有 n+1n+1 个内部顶点,而左子树有 kk 个,那么右子树就有 n−kn-k 个,这又得到了卡塔兰递推。

“有序”和“严格”这两个限定很重要:改变树的类别,计数序列也会改变。卡塔兰数还计数具有 nn 条边的有根平面树,其中每个顶点的子节点都具有线性顺序。

乘积的完全括号化

对于 n+1n+1 个因子的乘积,在保持因子顺序且只使用二元运算的条件下,完全加括号的方式共有 CnC_n 种。

对于四个因子,五种方式为

((ab)c)d,(a(bc))d,(ab)(cd),a((bc)d),a(b(cd)).((ab)c)d,\quad (a(bc))d,\quad (ab)(cd),\quad a((bc)d),\quad a(b(cd)).

这些是语法上的不同安排。如果运算满足结合律,所有安排的值都相同,但它们仍是不同的括号化方式。对于矩阵乘法,即使所得矩阵不变,不同括号化方式所需的算术运算次数也可能不同。

多边形的三角剖分

对于 n≥1n\geq 1,具有 n+2n+2 个顶点的凸多边形的三角剖分数为 CnC_n。三角剖分是用互不相交的内部对角线,将多边形划分成三角形。

因此,五边形有 C3=5C_3=5 种三角剖分。这里将多边形的顶点视为固定且可区分的;通过旋转或反射相互对应的剖分不视为同一种。

固定一条边,考察以它为边的三角形,就可以把剩余区域分成两个较小的多边形区域。这给出了卡塔兰递推的另一种形式,其中空区域按约定 C0=1C_0=1 处理。

非交叉划分与模式避免置换

将 nn 个点依次放在圆周上,它们的一个非交叉划分是指各块互不交叉的集合划分。更确切地说,不能存在按圆周顺序排列的四个点 a,b,c,da,b,c,d,使得 a,ca,c 位于同一块,而 b,db,d 位于另一个块。这样的划分共有 CnC_n 个。

卡塔兰数还计数若干类受限置换。例如,CnC_n 是 1,…,n1,\ldots,n 的避免模式 231231 的置换数,即不存在下标 i<j<ki<j<k 使得

πj>πi>πk.\pi_j>\pi_i>\pi_k.

公式的反射证明

包含 nn 个上升步和 nn 个下降步、不加其他限制的路径共有

(2nn)\binom{2n}{n}

条。要计数戴克路径,只需减去那些到达过高度 −1-1 的路径。

对于每条这样的不合要求路径,将起点至首次到达高度 −1-1 处的路径段反射,即互换其中的上升步和下降步。变换后的路径有 n+1n+1 个上升步和 n−1n-1 个下降步,终点高度为 22。

这一变换是可逆的:每条长度为 2n2n、终点高度为 22 的路径都必定先到达高度 11,将起点至首次到达该高度处的路径段反射,就能还原出一条不合要求的路径。因此,这一变换是一个双射函数,不合要求的路径数为

(2nn+1).\binom{2n}{n+1}.

所以,

Cn=(2nn)−(2nn+1)=1n+1(2nn).C_n =\binom{2n}{n}-\binom{2n}{n+1} =\frac{1}{n+1}\binom{2n}{n}.

这是路径计数中反射原理的一个实例。

生成函数

定义普通生成函数

C(x)=∑n=0∞Cnxn.C(x)=\sum_{n=0}^{\infty}C_nx^n.

卷积递推转化为

C(x)=1+xC(x)2.C(x)=1+xC(x)^2.

解这个二次方程可得

C(x)=1−1−4x2x.C(x)=\frac{1-\sqrt{1-4x}}{2x}.

这里选择负号,是因为这一分支具有常数项为 11 的幂级数展开,而另一分支没有。在 x=0x=0 处,表达式的值按其可去奇点处的极限理解。

作为形式幂级数,这个恒等式无需解析意义上的收敛条件,就能表达递推关系。作为复幂级数,它的收敛半径为 1/41/4。

这种含平方根的形式是许多递归定义的树状结构类的典型特征。它也提供了从递推关系推导系数显式公式的一条途径。

增长与概率

在阶乘公式中使用斯特林近似,可得

Cn∼4nπ n3/2(n→∞).C_n\sim\frac{4^n}{\sqrt{\pi}\,n^{3/2}} \qquad(n\to\infty).

更精确地,

Cn=4nπ n3/2(1−98n+O(n−2)),C_n= \frac{4^n}{\sqrt{\pi}\,n^{3/2}} \left(1-\frac{9}{8n}+O(n^{-2})\right),

其中 O(⋅)O(\cdot) 是大O记号。相邻两项之比满足

Cn+1Cn=4−6n+2,\frac{C_{n+1}}{C_n} =4-\frac{6}{n+2},

因此趋于 44。

路径解释给出了一个简单的概率恒等式。如果从所有具有 nn 个上升步和 nn 个下降步的路径中等概率选取一条,那么

Pr⁡(the path never goes below 0)=Cn(2nn)=1n+1.\Pr(\text{the path never goes below }0) =\frac{C_n}{\binom{2n}{n}} =\frac{1}{n+1}.

也就是说,路径始终不低于高度零的概率为 1/(n+1)1/(n+1)。等价地,对于一个以经过 2n2n 步后回到零点为条件的对称随机游走,全过程保持非负的概率为 1/(n+1)1/(n+1)。

计算与应用

一阶递推可以用精确整数运算计算这个序列。在每一步中,分子

2(2n+1)Cn2(2n+1)C_n

都能被 n+2n+2 整除。先乘后除可以避免整数运算中的截断。直接用浮点数计算阶乘,即使最终结果仍在可表示范围内,中间计算也可能溢出。

计算到 CNC_N 为止的所有项,卷积递推需要 O(N2)O(N^2) 次算术运算,而一阶递推需要 O(N)O(N) 次。这些是算术运算次数,而非位复杂度界:存储各项所需的位数会随 nn 增大。

在计算机科学中,卡塔兰数描述了涉及表达式树、嵌套语法和括号化方式的搜索空间大小。它们解释了为什么穷举很快就会变得不可行。

计数和优化是不同的任务。对于 n+1n+1 个矩阵的矩阵链乘法问题,虽然有 CnC_n 种可能的括号化方式,但动态规划无需列出所有方式,就能找到最优的括号化方案。

卡塔兰分解还可以用于均匀随机生成。要均匀随机生成一棵具有 n+1n+1 个内部顶点的有序严格二叉树,先以概率

CkCn−kCn+1,\frac{C_kC_{n-k}}{C_{n+1}},

选择左子树的规模 kk,再按照选定的规模,分别独立、均匀地生成左子树和右子树。如果等概率选择拆分规模,通常不能得到树上的均匀分布。

历史与推广

这一序列以比利时数学家欧仁·夏尔·卡塔兰命名,他在十九世纪研究过括号化问题。不过,它的历史更早:莱昂哈德·欧拉在十八世纪研究了多边形的三角剖分,约翰·安德烈亚斯·冯·塞格纳则得到了相应的递推关系。蒙古族数学家明安图的研究中也独立出现过这些数。

一种标准的推广是富斯–卡塔兰数:

Fn(p)=1(p−1)n+1(pnn),p≥2.F_n^{(p)} =\frac{1}{(p-1)n+1}\binom{pn}{n}, \qquad p\geq 2.

它们计数具有 nn 个内部顶点的有根有序严格 pp 叉树,即每个内部顶点恰有 pp 个有顺序的子节点。当 p=2p=2 时,它们退化为普通卡塔兰数。其生成函数满足

F(x)=1+xF(x)p.F(x)=1+xF(x)^p.

纳拉亚纳数给出了卡塔兰计数的细分:

N(n,k)=1n(nk)(nk−1),1≤k≤n.N(n,k)=\frac{1}{n}\binom{n}{k}\binom{n}{k-1}, \qquad 1\leq k\leq n.

它们计数半长为 nn、恰有 kk 个峰的戴克路径,其中峰指一个上升步后面紧接一个下降步。因此,

∑k=1nN(n,k)=Cn.\sum_{k=1}^{n}N(n,k)=C_n.