11.6 卡塔兰数与斯特林数

数学学习 · 爱知数学讲义

18
本章目录 · 1 节

本章导读

【定义11.6.1】将凸(n+1)边形用内部互不相交的对角线分成三角形,方案数记为hₙ,称卡塔兰数。对实际多边形n≥2;补定义h₁=1作为递推中的空区域计数。不要把“两边形”当成通常的凸多边形。

凸五边形有五种三角剖分,即h₄=5,每种恰有两条对角线、三个三角形。

A1A2A3A4A5
图11.6.1(a) 五边形的第一种三角剖分
A1A2A3A4A5
图11.6.1(b) 五边形的第二种三角剖分
A1A2A3A4A5
图11.6.1(c) 五边形的第三种三角剖分
A1A2A3A4A5
图11.6.1(d) 五边形的第四种三角剖分
A1A2A3A4A5
图11.6.1(e) 五边形的第五种三角剖分

取固定底边A₁Aₙ₊₁,在任一剖分中,与其相邻的唯一三角形第三个顶点必为Aₖ₊₁,1≤k≤n−1。去掉该三角形后,剩下两个区域的顶点数为k+1和n−k+1,其剖分独立;边界退化为空区域时按1种计。于是

A1A2A3A4A5A6A7R1TR2a
图11.6.2 固定底边相邻三角形T将其余部分分为R₁与R₂,示例n=6、k=3

前几项为1,1,2,5,14,42。常用从0开始的卡塔兰数 与本书关系为hₙ=Cₙ₋₁。平衡括号及固定入栈顺序下n个元素的栈输出数为Cₙ=hₙ₊₁。格路径中允许在中途接触对角线的非降路径为Cₙ;若要求除端点外完全不接触,且固定在对角线一侧,则为Cₙ₋₁=hₙ,二者相差一位,若两侧均允许还要区分两种情况。

【例11.6.1】矩阵链乘法。设Aᵢ大小为pᵢ₋₁×pᵢ,输入为维度向量P=(p₀,…,pₙ)。两个矩阵相乘,每个结果项需要p₁次标量乘法,整个p₀×p₂结果需p₀p₁p₂次。矩阵乘法满足结合律,但不同括号次序可能需要不同运算量。

P=(10,100,5,50)时, 需10·100·5+10·5·50=7500次; 需100·5·50+10·100·50=75000次。输入、最终结果相同,后者代价为前者10倍。

设n个矩阵的完整括号方案数为Tₙ,按最后一次相乘的位置m划分,。由斯特林公式 ,有

穷举所有括号方案会遇到指数规模。可用动态规划:,,按链长递增填表,时间O(n³)、空间O(n²),同时记录最优断点即可还原括号方案。(例完)

【定义11.6.2】第一类无符号斯特林数记为 ,由降阶乘多项式定义:

它是展开系数的绝对值;若使用带符号版本,需要额外乘 ,不能混用。

【命题11.6.1】由n−1阶降阶乘再乘x−n+1并比较系数,得

初值 ;n>0时第0列为0,第1列为(n−1)!;r<0或r>n均为0。递推可构成类似杨辉三角的表。

【命题11.6.2】n≥1时

首式看最高次项;次式看所有常数1到n−1之和;第三式将上升阶乘 的展开在x=1求值。组合解释是n个不同元素的排列分解为恰好r个不相交循环:循环之间无顺序,循环内部只区别环形次序。加入新元素时,要么独立成为循环,要么插入原来n−1个元素之一之后,得到同一递推。所有循环数相加就是全部n!个排列。

【定义11.6.3】第二类斯特林数 是将n个不同元素分成恰好r个非空、无编号块的方法数,也等于将n个不同球放入r个相同盒且每盒非空的方法数。它不是允许空盒的固定r盒计数。

例如 :abc|d、abd|c、acd|b、bcd|a、ab|cd、ac|bd、ad|bc。竖线两侧交换不产生新方案。

【命题11.6.3】将指定元素单独成块,或插入其余元素已有r块中的某一块,得

边界为 ;n>0时第0列0,第1列1;r<0或r>n为0。

n=11n=211n=3131n=41761n=511525101S(n,r) = r S(n-1,r) + S(n-1,r-1)
图11.6.3 第二类斯特林数三角表,n=1至5,最末行为1、15、25、10、1

【命题11.6.4】第二类斯特林数满足以下恒等式,所用m、n、r均取使表达式有定义的非负整数,个别边界在式后说明。

(1) (n≥1)。固定一个元素所在块,其余n−1个各自选入此块或另一块,去掉另一块为空的一种。

(2) (n≥1):只有一块含两个元素,其余单元素。

(3) (n≥0)。

(4) (m≥1)。左边按每个有编号非空盒的球数计满射,右边先分无编号块,再编号。

(5) 。先把n个不同球放到恰好k个无编号非空块,再从m个盒中选k个并编号。原式若把n、m在组合数及斯特林数的上标位置对调,将得到nᵐ而不是mⁿ;这里用实际放球对象校正。n=0时k=0项为1,按空函数约定0⁰=1。

(6) (r≥1)。固定一个元素,另选i个不在它所在块的元素分成r−1块,其余与该元素同块,恰好覆盖全部方案。

【表11.6.1 放球问题八种类型】以下先设n≥1、m≥1;“允许空盒”的相同盒只区分非空块,空盒本身不标号。

不同球、有编号盒、可空:mⁿ。

不同球、有编号盒、不空:。

不同球、相同盒、可空:。

不同球、相同盒、不空:。

相同球、有编号盒、可空:。

相同球、有编号盒、不空:n≥m时 ,否则0。

相同球、相同盒、可空:,即至多m个部分。

相同球、相同盒、不空:,即恰好m个正部分;从每个盒先放一个球的平移解释了因子xᵐ。n=0且允许空盒时为1,不允许空盒而m>0时为0。

【例11.6.2】|A|=n、|B|=m。(1)从A到B的关系是A×B的任意子集,共2ⁿᵐ个。(2)A上二元关系共2ⁿ²个;等价关系对应集合划分,共 个,其中B₀=1,称贝尔数。(3)函数共mⁿ个;单射n≤m时为m!/(m−n)!,否则0;满射共 ;双射仅n=m时有n!个,否则0。空集到空集有唯一空函数,既单射又满射。(例完)

【命题11.6.5】满射容斥公式与第二类斯特林数的关系为

第一种证明是对未命中的值作容斥。第二种用指数生成函数: 的xⁿ/n!系数,按乘积展开是 ,按二项式展开是 ,比较系数即得。n<m时两边均为0;m=0、n=0时两边均为1(空对象约定),可统一涵盖边界。