动机
把互不相同的对象放入若干组,并不能仅由各组的大小确定。我们还必须指明哪些标签出现在同一组,以及各组本身是否带有名称。置换的轮换又引入另一种选择:每个组内部的循环顺序。即使参数中出现的是同样的整数,这些区别也会导出不同的计数序列。
斯特林(Stirling)数用来整理其中两种模型。贝尔(Bell)数对所有集合划分求总和,而指数生成函数则表达带标签的块如何组装。同样的数组还出现在多项式恒等式中:在那里,普通幂与下降阶乘以两种不同的方式计数函数。我们将从被计数的对象出发推导这些联系,而不是把这些公式当作互不相关的数表。
定义
定义 2.7.1
(划分与两种斯特林数组)
的一个集合划分,是由互不相交的非空块构成的无序集合,且这些块的并集为 。设 为划分成 个块的划分个数。设 为 上恰有 个互不相交轮换的置换个数,其中每个轮换带有循环顺序,而轮换的整体是无序的。定义 。
约定 ,它们对应空划分或空置换。对正整数 ,约定 。当 或 时,两种斯特林数均取为零。这些约定使递推式的边界情形有意义,而无需虚构一个空块。
定义 2.7.2
(下降阶乘与形式指数级数)
令 ,并对 令 。对 令 。对带标签的计数 ,其指数生成函数为 ,在此处按实数上的形式级数来理解。把 写作形式级数。
形式恒等式指系数相等,而不是关于数值收敛的断言。乘积在每个次数上使用有限卷积。把一个级数代入常数项为零的另一个级数,同样可以逐个系数地良好定义;这将用来论证贝尔数的生成函数。
定理/命题
定理 2.7.3
(两个插入递推式)
对 与 ,
从 到带标签的 元目标集的满射共有 个。因此,对 ,由容斥原理得
必要时采用空定义域的计数约定 。
定理 2.7.4
(贝尔递推式与指数生成函数)
对 ,
对每个 ,再对所有块数求和,有
这些都是形式级数恒等式,包括常数项在内。
定理 2.7.5
(两个互逆的多项式基)
对每个非负整数 ,作为 的多项式恒等式,
因此,第二类数组与带符号的第一类数组是互逆的基变换。特别地,对 ,
证明思路或证明
证明
(插入最后一个标签,以及为纤维命名)
在一个划分中,标签 要么自成一个单点块,要么属于其余 个块之一。去掉单点块后得到划分成 个块的划分;否则去掉该标签后剩下 个块,并需记录哪一个块将重新接收它。这些情形互不相交且可唯一还原,由此证得 的递推式。
对于置换的轮换,标签 要么自成一个轮换,要么被插入某个已有轮换中、紧接在其余 个标签之一的后面。去掉它即还原该插入,并保持轮换个数不变。这两种情形证明了 的递推式。插入位置对应的是带标签的元素,而不是轮换的个数:每个轮换提供的位置数等于它的长度。
一个满射把其定义域划分成非空的纤维,并把互不相同的目标标签分配给这些块。每个划分恰有 种这样的分配,即使有些块大小相等也一样,因为各块的内容互不相同。容斥原理通过排除未被取到的目标标签来计数满射;按可用目标的个数 分组,便得到所示的交错和公式。
证明透视
删除操作必须恰好记住重构所需的选择
两条递推式都来自同一步:删去最大的标签。它们之所以是等式,是因为删除恰好配上还原所需的信息。在集合划分中,非单点标签要靠指明 个尚存块之一来接回;各块由其内容区分,所以这 种选择给出 个不同的划分。在轮换中,标签要靠指明它的前驱来接回,前驱是 减 1 个标签之一,每种选择都给出轮换个数相同的不同置换。因子 与 减 1 的差别全部来自这里。单点情形是零值约定介入的地方:它使块数或轮换数减一,而在 等于 0 或 时,相应的项按约定为零或为一,而不需另作论证。满射公式用的是同一事实,即各块可以区分,这次是为了使每个划分恰有 的阶乘种标号方式。
证明
(指定标签所在的块,以及有序块)
对于贝尔递推式,考察含有一个新指定标签的那个块。从其余 个标签中选出它的 个同伴,再把剩下的 个标签任意划分。指定标签所在的块与剩余的划分可以唯一地重构原对象。对同伴个数求和即证得递推式。
要证明固定 时的生成函数,先给这 个非空块排序。若它们的大小为 ,则把标签分配到这些有序块中共有 种方式。 中 的系数,恰是对总和为 的所有正整数大小,把倒数阶乘权重相加。因此乘以 即得到有序块划分的个数;再除以 便忘掉块的顺序。在每个固定次数上,除空情形外,只有 的项起作用。对 求和这些形式恒等式,得到 ,其内层级数的常数项为零。
证明
(按像计数函数,再求逆)
对于第一个多项式恒等式,取正整数 ,计数从 到 元目标集的函数。其定义域的纤维构成划分成某个 个非空块的划分。给这些块分配互不相同的目标值,共有 种方式。求和即对每个正整数 得到该恒等式,进而得到多项式恒等式,因为非零多项式只有有限多个根。
对于第二个恒等式,把 乘以 ,得到系数递推式
带符号的轮换计数满足完全相同的递推式和相同的初值,所以由归纳法知两组系数相等。最后,把第二个多项式展开式代入第一个,比较 的系数,即得逆数组公式。下降阶乘构成一组基,是因为它们是次数相继的首一多项式:比较最高次数得到线性无关,逐次相减得到生成整个空间。
例题详解
例题 2.7.6
(六个带标签对象放入三个无名块)
首先 ,。因此 。又 ,所以 。给三个盒子命名,则乘以 ,得到 种满射分配。另一方面,容斥原理给出 ,这验证了标签与非空性的处理是一致的。
例题 2.7.7
(贝尔总数与块大小模式)
由贝尔递推式得 ,,,以及 。在四个标签上,块大小的模式有 、、、 与 。它们各自对应的集合划分个数依次为一、四、三、六与一,总共十五。仅仅数这五种大小模式,数的是整数划分,而不是带标签元素的集合划分。
例题 2.7.8
(同样的块还带有额外的轮换顺序)
对四个标签上恰有两个轮换的置换,类型 的贡献是:单点有四种选法,其余标签上的循环顺序有两种,共八个。类型 的贡献是三种配对,共三个。所以 ,而 。大小为 的块有 种循环顺序:固定一个标签作为起点,再排列其余标签。正是这些内部顺序解释了两类斯特林数之间的差别。
概念视角代数
把整行轮换数写成一个乘积
轮换递推式说明每一行都是一次因子的乘积:
因为把第 行的多项式乘以 ,正好重现 。 时乘积为 ,与 一致。把 换成 再乘以 ,就得到带符号 的下降阶乘展开。
为什么无名块仍有均匀的标号计数
集合划分是无序的,但它的各个块是互不相同的集合。两个大小相等的块并不相同:互不相交的非空块含有不同的元素。因此,即使若干块大小一致,给盒子标号时也恰有完整的阶乘个分配。这个标号映射的纤维大小是均匀的,这正是除以阶乘有效的精确原因。
整数块大小模式则有意忘掉了更多信息。一个模式说明每种大小有多少个块,却不说明它们含有哪些元素。不同的模式有不同数目的实现方式,四个标签的例子即说明了这一点。若不另作论证,把带标签的总数除以某个统一的模式因子,是无法恢复这些不同重数的。
轮换模型增加的是信息,而不是忘掉信息。对固定的集合划分,在每个块内独立地选取一个循环顺序。各块循环顺序数目的乘积,就是轮换支撑恰为这些块的置换个数。对所有划分求这些乘积之和,便得到无符号第一类数。这解释了它们之间的关系,却并未把它们所计数的对象等同起来。
正确理解指数生成函数
指数生成函数中的阶乘分母记录的是标签的分配。两个这样的级数相乘,是把定义在所选互不相交标签子集上的对象组合起来,从而在所得计数中产生二项式系数。普通生成函数对其背后的计数解释使用另一套系数规则。在没有检验系数之前,不应把形如有理函数或指数函数的同一套代数运算在两种模型之间随意搬用。
项 描述一个非空的带标签块:每个正大小的标签集上都恰有一种块结构。去掉常数项,是因为划分中没有空块。外层的指数函数则允许这类块构成的无序集合。这种描述是证明中显式的有序块与阶乘论证的简写,而不是对它的替代。
在零次,恰有一个由块组成的空集合。因此,贝尔生成函数与零块固定的级数,其常数系数都是一。若遗漏这一情形,递推式在第一个输入处以及形式指数恒等式都会失效。确定这些系数并不需要任何分析上的收敛问题。
概念视角组合
一种变换改变标签,另一种变换改变多项式坐标
满射与划分的差别在于是否给非空纤维命名。置换与划分的差别在于块内是否有循环顺序。幂与下降阶乘则是通过计数像集大小而联系起来的多项式基。同样的数组联系着这些描述,但公式相等并不意味着它们的对象可以互换。
精确数表及其计算代价
从前一行计算斯特林数的一行,依次遍历所有合法的块数。两种递推式为得到到指定下标为止的各行,都需要二次多项式量级的算术运算;若不再需要更早的项,则只需保留两行。贝尔数可以通过对每一行第二类数求和得到,也可以由它们自己的递推式得到。
这里数的是对不断增长的整数所做的算术运算次数。对正整数 ,每个划分都可以编码为把每个标签映到其所在块中最小标签的函数。该编码是单射,因为它的非空纤维可以恢复各个块。因此 ,这给出划分个数的二进制长度的 界。类似地,轮换计数至多为 。所以,初等的精确整数算术给出多项式比特复杂度的实现,尽管它与数表的运算次数所对应的单位代价界并不相同。
要计算精确计数,无需对形式的贝尔表达式作数值求值。递推式只使用精确的加法与整数乘法,并自动保持整数性。若用浮点数近似指数函数,则需要另行给出误差论证,才能通过取整来确认一个系数。
常见错误
反例模式
隔板法计数的是另一种对象
的正整数解为 ,共三个。但 。整数解描述的是两个有名位置上的大小;它们并不说明哪四个标签出现在一起,而集合划分的块是无名的。修正后的模型必须同时记录标签的归属,以及块的名称是否重要。
其余两个错误涉及符号与约定,而非模型本身。
常见错误
(丢掉第一类数的符号)
按幂展开所用的是 ,而不是 。已经有 ,而无符号的一行 会给出 。符号随 交替变化。
常见错误
(允许空块)
若允许空块, 就成为 分成两个块的划分, 会变成 而不是 ,而两个空块甚至无法区分。不要仅仅为了让递推式看起来整齐就允许出现空块;请使用明确陈述的零值约定。
总结
集合划分与置换的轮换导出不同的插入递推式。贝尔数对划分的各行求和,而带标签块的组装解释了它们的指数生成函数。两类斯特林数(第一类带符号)还给出普通幂与下降阶乘之间互逆的变换。
练习
快速检查
(利用计数意义计算 与 。)
指出第二个计数中唯一可能的非单点轮换类型。
解答 · 答案
:从两个有名盒子的分配中排除两种常值分配,再忘掉名称。五个标签上恰有四个轮换的置换,含有一个对换和三个不动点,所以 。没有更长的轮换符合这个轮换个数。
快速检查
(证明 ,并判断何时不等式严格成立。)
把新标签加为单点块,并找出该像之外的一个划分。
解答 · 答案
把新标签加为独立的块,将 的划分单射到 的划分中。对 ,标签 与新标签同在一块、其余标签均为单点块的划分,不在该像之中。因此对 有 。在 时两者都是一,所以在非负下标中,等号恰好只在此处成立。
快速检查
(把 展开为下降阶乘的组合,并把 展开为普通幂。)
使用第四行,并在 处检验这两个多项式表达式。
解答 · 答案
第二类数的一行给出 。把 相乘得到 ,与带符号的轮换计数一致。在 处,第一个表达式给出 ,而第二个给出 ,这正是第四个下降阶乘的正确值。