动机
把五条互不相同的记录分成三个非空组,可以有不同含义。如果三组分别叫训练集、验证集和测试集,那么交换组名会改变分配。如果它们只是三个聚类,那么只需保留各组包含哪些记录,交换列出的顺序并不产生新分组。还有第三种问题:把五枚相同的筹码放进三个有名称的盒子。这三种问题都提到“五个对象、三个组”,却在数不同的东西。
程序通常为每条记录保存一个聚类标签。把所有标签一致地重新命名,会改变存储表示,却不会改变实际分组。我们先直接数分组,再确定每种分组有多少种带标签的表示。由此得到的递推也展示了动态规划的一个基本原则:数学上如何分解对象,决定程序该按什么顺序更新状态。
定义与边界情形
定义 1.4.1
(集合划分与块)
对整数 ,记 ,并约定 。 的一个集合划分是一族非空、两两不交且并集为 的子集。这些子集称为块。块没有名称,也没有规定的排列顺序。例如, 与 是同一个划分。
定义 1.4.2
(第二类斯特林数)
用 表示把 恰好划分成 块的方法数,称为第二类斯特林(Stirling)数。即使两块大小相同,其中的元素也仍然互不相同。规定
空的子集族是空集的唯一划分;非空集合不能划分成零块。为方便书写,对负的 也令 ,这并不是在定义具有负数个元素的集合。
定义 1.4.3
(满射)
满射 必须使用全部 个输出标签。记这种函数的数量为 。当 时,若 ,有一个满射;若 ,则没有。当 时,非空纤维 就是标着 的组。忘掉这些标签,便得到一个集合划分。
移去最后一个元素,得到递推
定理 1.4.4
(斯特林递推)
对 和 ,
结合边界值,这个递推唯一确定所有 。
证明
(按最后元素所在的块分类)
考察指定元素 所在的块。如果该块就是单元素集 ,删除它后剩下的是 的一个 块划分。反过来,添加这个单元素块能唯一恢复原划分,因此此类贡献 。
否则,只从该块中移去 ,保留其中其他元素。剩下一个具有 个非空块的划分,同时还记住了 来自哪一块。反过来,先选 的一个 块划分,再选其中一块,把 放入即可。每个划分恰有 个可选块。块虽然无标签,但它们是不同的元素子集,因此仍是不同的选择。此类贡献 。
两类互不重叠,因为 所在块不可能既是单元素块又不是单元素块。它们又包含所有划分,所以相加得到递推。右边各项的第一个下标都减小,而初始行已经确定,因此对 归纳就证明了唯一性。
证明透视
递推证明需要可逆的分类
“把下一个元素放到某处”还不是完整的计数证明。我们分清两种插入,并说明如何从结果恢复较小划分以及插入时的选择。能够恢复原来的选择,保证同一类内部没有重复计数;是否形成单元素块的区别,则保证两类之间没有重叠。
前几行如下;没有显示出来的越界项均为零。
| 0 | 1 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 0 | 0 | 0 | 0 |
| 2 | 0 | 1 | 1 | 0 | 0 | 0 |
| 3 | 0 | 1 | 3 | 1 | 0 | 0 |
| 4 | 0 | 1 | 7 | 6 | 1 | 0 |
| 5 | 0 | 1 | 15 | 25 | 10 | 1 |
例如,。这个等式不仅给出总数,还说明其中七个划分以 为一块,另十八个把 放在较大的块里。
用标签连接划分与函数
定理 1.4.5
(满射就是给划分的块加标签)
对非负整数 ,
更一般地,对 ,
这里的 表示从空集到自身的函数数量,不是实数幂的极限。
证明
(带标签的块与像的大小)
给定一个有 块的划分,选取从块集到 的一个双射,共有 种。把每个元素映到所在块的标签,便得到满射。该满射的纤维能恢复原划分及块的标签,因此这构成带标签划分与满射之间的双射,证明第一个等式。 时,两边构造都为空,但仍然唯一。
对第二个等式,按照像的大小 对全部函数 分类。先用 种方式选择像集,再用 种方式选取到这些标签的满射。像集不同,或划分不同,都会得到不同函数。每个函数又有唯一的像集,所以分类完整。按照前面的约定,等式也包含空定义域和空陪域。
因此, 数的是向 个有名称的盒子分配元素的所有方式,允许盒子不用。斯特林数则数无标签且必须非空的块。二者之间的转换需要追踪实际用了哪些标签,不能直接把总数除以 。
概念视角代数
斯特林数作为基的变换
恒等式 对每个整数 都成立,而 在 时自动为零。两个次数至多为 的多项式若在无穷多个点上相等,它们就相等,所以
当 时即为 。数 就是 在下降阶乘基下的坐标。
用容斥原理数满射
定理 1.4.6
(排除缺少输出标签的函数)
对所有非负 ,
这里同样采用空函数约定 。把这个整数除以 ,便得到 。
证明
(每个函数贡献一次或零次)
对一个子集 ,避开 中所有标签的函数共有 个。对所有 把该数量乘以符号 后相加。为了证明这个带符号的和究竟数什么,固定一个函数,令 为它漏掉的标签集。该函数对总和的贡献是
若 非空,固定其中一个元素,把不含它的子集与添加它后得到的子集配对,两者符号相反,故全部抵消。于是恰好每个满射贡献一。再按 的大小合并项,就得到定理中的公式。定义域为空时,同样的贡献论证仍适用于唯一的空函数;它漏掉全部陪域标签。
例题 1.4.7
(五条不同记录分成三组)
递推给出 个无标签分组。给三组指定名称后有 种分配。容斥原理也给出
相反,五枚相同筹码放入三个有名称的非空盒子,只有 个正整数占用向量。这个数只记录三组的大小,没有记录五条不同记录分别属于哪一组。
反例模式
把所有分配除以阶乘可能出错
对四个元素和两个标签,,但 。两个常值函数都只用一个标签,表示的是单块划分。先去掉它们,才得到 。在满射上除以 是正确的,因为每个两块划分恰有两种标签分配;但除法不会把有空盒子的分配变成两块划分。
更一般地,对 ,一个固定的 块划分若用 中的标签表示,共有 种表示。它依赖于 ,所以对全部函数忘掉标签时,不同块数对应的纤维大小并不相同。
指定块大小时,需要两种对称因子
有时要求各组的大小,但组仍然无标签。用 表示大小为 的块必须有多少个,其中非负整数 满足
定理 1.4.8
(具有指定大小分布的划分)
对于这样的大小分布,划分数量为
当 时,空的大小分布计数为一,并规定空乘积等于一。
证明
(分槽与对称因子)
把 个不同元素排成一行,再按固定顺序切成若干位置:先放 个长度一的位置,再放 个长度二的位置,依此类推。原始排列共有 个。忘掉每个位置内部的顺序,以及大小相同的位置之间的顺序,便得到符合要求的划分。
固定一个最终划分。它的 个大小为 的块可以用 种方式安排到对应位置中;每块内部的元素还能用总共 种方式排列。这些选择对不同大小独立,并且恰好恢复所有产生该划分的原始排列。因此每个纤维都有相同的分母大小,公式得证。大小不同的块已经对应不同类型的位置,再额外除以 就会重复消去本来合法的区别。
例题 1.4.9
(分成两块为何有七种)
对四个不同元素,两块的大小只能是 或 。第一类贡献 ,也就是选择哪个元素独自成块。第二类贡献 ,其中两对元素没有先后顺序。因此 。
同理,六个不同元素分成三个无标签的二元素块,共有 种。如果再给三对指定三个名称,则乘以 ,得到 种。
例题 1.4.10
(按像的大小分类全部分配)
将四条不同记录分配给三个可用标签,允许部分标签不用。像的大小为一、二、三时,分别贡献
总和为 。像大小为二的那项不仅选择分组及其标签,还要选择究竟用了哪两个标签。漏掉 ,就只数了使用某一对指定标签的分配。
精确的动态规划
计算单个 时,如果 ,直接返回零。 或 的边界也可以直接处理。对 且 ,递推只依赖上一行,因此只存 个整数单元即可。
def stirling(n, k):
if n < 0 or k < 0:
raise ValueError("n and k must be nonnegative integers")
if k > n:
return 0
if n == 0:
return 1 # Here k is necessarily zero.
if k == 0:
return 0
d = [0] * (k + 1)
d[0] = 1
for i in range(1, n + 1):
for j in range(min(i, k), 0, -1):
d[j] = j * d[j] + d[j - 1]
d[0] = 0
return d[k]
函数假设参数是整数。开始计算第 行时,单元中存着 对应的 。按 递减更新,便保证读取 和 时两者都是旧值。更新写入的正是 的斯特林递推。 的单元保持零,最后把 置零,符合非空行的边界。对 归纳便证明算法正确;第一行的单元素块正是由初始的 产生的。
算法执行 次整数加法及乘以不超过 的整数的运算,存储 个整数单元。这是算术运算次数。若要估计比特代价,注意对 有 :按每块最小元素的递增次序给块标号,就把每个划分单射地编码为函数 。因此,存储的计数及更新中的非负项最多需要
个比特。使用基本加法以及乘以 的方法,可得足够的上界: 次比特运算,整数数组占 比特。循环下标和输入本身另有存储代价。这个较宽松的上界没有假设任意大的整数都能单位时间运算。
运行时间依赖 的数值,而不仅是它的二进制长度。事实上,对 ,精确答案 本身就有 个二进制位。因此,一般不能要求精确输出算法只用关于 的多项式时间。
常见误解与适用范围
常见错误
(把块当作有标签,或允许空块)
元素有标号,块没有标签。大小相同的块仍然是不同子集,但交换它们的列出顺序不产生新划分。定义排除了空块;若允许任意添加空块,又不增加额外约定,块数本身就不再有明确意义。
上的等价关系由其等价类唯一确定,反过来,每个划分都可通过“属于同一块”定义等价关系。因此,等价关系的总数为 ,称为贝尔(Bell)数。四个元素时为 。这是全部等价关系的计数,并不意味着均匀随机分配标签就能均匀抽取等价关系。
常见错误
(把精确计数当作数值或抽样结果)
带符号公式、固定大小分布公式和动态规划,通过不同分解来数同一类对象。证明建立的是精确整数等式,没有证明用浮点数计算很大的交错和具有数值稳定性,也没有给出均匀随机抽取划分的方法。
练习
快速检查
(对 ,证明 。解释为何 必须单独处理。)
解答 · 答案
当 时,到两个标签的函数共有 个。恰有两个常值函数,其余全部是满射。每个两块划分有 种标签分配,所以 。 时正确地得到零。但 时只有一个空函数,并不是两个不同的常值函数;又没有两块划分,所以应单独规定 。
快速检查
(对 ,通过描述可能的块大小,证明 。)
解答 · 答案
先给 块各放一个元素,已经用了 个元素。唯一剩余的元素只能把其中一块扩大到大小二。因此,划分必有一对元素,其余全是单元素块。选择那一对有 种,而且从结果能唯一找回这对元素。 时得到唯一的单块划分,也符合公式。
快速检查
(六个不同元素中,恰有两个大小为二的块和两个大小为一的块的划分有多少个?若再给四个块分配四个指定的不同标签,有多少种分配?)
解答 · 答案
大小分布为 ,因此计数为 。虽然大小有重复,但每个划分包含四个不同的元素子集;把四个指定标签双射地分配给它们有 种。于是带标签的分配数为 。第二问没有限制某个标签必须用于某种大小的块。
快速检查
(把内部循环改成让 从一递增到 。追踪 这一行,找出第一个错误值,并解释递推所需的哪个输入已经被覆盖。)
解答 · 答案
第三行开始前,数组是 。递增更新先写入 ,再写入 ,最后得到 。最后一项本应是 。递推所需的 已被新的 覆盖。递减更新则会在修改 前读到旧值一,使各项始终来自同一个上一行。
快速检查
(直接求出 、 和 ,再分别核对带符号公式。解释为何该公式中的 必须表示一。)
解答 · 答案
从空集到自身有唯一函数,其空像等于空陪域,因此 。空函数不能覆盖三个标签,所以 。从三个元素到空集的函数不存在,所以 。
带符号的和分别是 、 和 。中间的和中,即使没有可用标签,该项仍须数到一个空函数:由于没有输入,所有关于输入的条件均自动成立。若令 ,就破坏了这个计数,得到错误答案。