动机
有些比较刻画的是依赖关系,而不是大小。某项任务可能必须先于另一项任务,某个子集可能包含于另一个子集,某个正整数可能整除另一个正整数。两个对象不必可比较。若把这些关系换成任意的数值顺序,就可能掩盖证明所需要的结构。
偏序恰好保留所需的比较。它支持两个起初看似无关的问题。这些对象能否排成一个满足所有依赖关系的序列?如果每个对象上报的总量都包含其下方所有对象的贡献,能否还原各个对象自身的贡献?第一个问题引出线性扩张,第二个问题引出莫比乌斯(Möbius)反演。有限的序使这两个问题都能构造性地解决。
定义
定义 6.1.1
(偏序与区间)
集合 上的偏序是满足自反性、反对称性与传递性的关系 。即 ;若 且 ,则 ;并且 蕴含 。序对 称为偏序集。当 且 时记作 。若两个元素中一个不大于另一个,则称它们可比较。对于 ,区间 定义为 。
本章中所有偏序集都是有限的。极小元没有严格更小的元素;最小元则小于或等于每一个元素。极小元可以有很多个,而最小元若存在则唯一。线性扩张是对所有元素的一个排列,其中每一个严格比较都使较小的元素排在前面。它为不可比较的元素选定先后次序,但不改变原关系所断言的比较。
定义 6.1.2
(关联函数与卷积)
关联函数给每一对可比较的 指定一个实数 。定义
单位关联函数在 时满足 ,否则取 。zeta 函数为 ,对每一对可比较元素都成立。这些都是以两个有序端点为变量的函数,不应与单变量数列或解析意义下的 zeta 函数混淆。
定理/命题
定理 6.1.3
(有限偏序集都有线性扩张)
每个有限偏序集都有线性扩张。反复移除剩余元素中的一个极小元,并将其列在下一位。在多个极小元之间任意选择,得到的都是有效的扩张。空偏序集对应空排列。
定理 6.1.4
(有限偏序集上的莫比乌斯反演)
存在唯一的关联函数 满足 。它由下式确定:
对任意函数 ,等式
对每个 成立,当且仅当
对每个 成立。
该定理允许出现负值。它的目的是撤销一次汇总,而不是断言还原出的贡献在计数对象。若要得到非负的解释,还需要关于具体函数的额外信息。
证明思路或证明
证明
(逐个移除极小元)
非空有限偏序集必有极小元。从任一元素出发,只要可能就不断移向一个严格更小的元素。由传递性与反对称性,没有元素会重复出现,所以有限性迫使这一下降过程终止。移除这样的元素,对其余的偏序集应用归纳法。若某元素严格小于另一元素,则当较大者被选为极小元时,较小者不可能仍然在场。因此所得的排列满足所有比较。
证明
(求 zeta 函数的逆)
卷积满足结合律。展开 或 ,都得到对 的同一个有限和 。直接代入可知 是其单位元。所列递推式在各区间上依次确定 :当 时,区间 严格小于 。由此立即得到 。
右逆元同样存在:定义 及
这使得 。再由结合律得
于是同一个函数既是左逆元也是右逆元,任何其他逆元也由同一等式推得与之相等。这一步很关键,因为卷积不一定可交换:不应不加说明地把单侧的消去用到另一侧。
把下集求和的表达式代入 ,得到所提出的反演式,再重新整理:
内层的和是 。反过来,把反演式代入 ,内层的和变为 ,剩下 。每个区间上的和都是有限和,所以不需要任何收敛条件。
证明透视
两种端点求和各司其职
递推式固定第一个端点,对可能的第二个端点求和,证明的是其中一个逆元等式。下集反演需要的则是固定第二个端点的那个等式。分别构造两个单侧逆元并利用结合律,就弥合了这一差距。 中端点的顺序是定理的一部分,而不是排版上的随意选择。
例题详解
例题 6.1.5
(链把累计总量化为差分)
设 。递推式给出 ,相邻元素之间为 ,跨越更长区间时为零。例如 ,。因此由累计值 可还原 。负的贡献与总量从五降到四是相符的。
例题 6.1.6
(子集产生正负交替的符号)
将一个有限集的子集按包含关系排序。对于 ,
事实上,若差集非空且大小为 ,则对中间子集的求和为 ,而差集为空时和为一。若在三元集的子集上取 ,反演给出 。直接看,总量就是每个子集各贡献一的总和。
例题 6.1.7
(整除关系还原算术莫比乌斯函数的值)
将十二的正因数按整除关系排序。从一到某个因数的区间恰好包含它的所有正因数。递推式给出 ,,, 以及 。对于最后一个值,把前面的值相加得 ,再取相反数。这与算术莫比乌斯函数一致:十二含有重复的素因子。这里的取值取决于区间的整除结构,而不是它在数值上的长度。
为什么图示需要其背后的序
Hasse 图只记录覆盖关系:当 且二者之间没有任何元素时,称 覆盖 。自反的环以及由传递性推出的比较都被省略。因此,一幅带向上边的图所编码的可比较元素对,可能比可见的边多得多。关联函数的卷积对所有中间元素(包括端点)求和,而不是只对图中的相邻点求和。
对于四元链,其两端点之间的区间含有四个元素,尽管两端点之间没有覆盖边相连。反过来,不可比较的顶点之间不存在所述类型的有序区间。若把每一对元素都当作对卷积有贡献,就会改变代数结构。通常有益的做法是先重建由传递性推出的比较,再把图示仅当作参考。
在这套语言里,极小与最小也有明显区别。两个互不可比较的底部顶点可以都是极小元,但二者都不是最小元。有限非空偏序集必有极小元,但不一定有最小元。线性扩张的算法用到的是前一个事实,它恰好足以支持下一步的选择。若要求每一阶段都有最小元,就会错误地排除许多有效的偏序集。
移除极小元素的算法给出一个递推式:对所有可能的第一个元素求和。
自然的下一个问题
一个偏序集有多少个线性扩张?
移除极小元素的算法给出一个递推式:对所有可能的第一个元素求和。
每个线性扩张都以某个极小元素 开头,后面接着 的一个线性扩张;反过来,每一对这样的选择都给出一个线性扩张,而不同的第一个元素给出不同的排列。因此 ,且 。链只有一个线性扩张, 元反链有 个,练习中的菱形偏序集有两个。这个递推式可能要经过指数多个子偏序集,而且没有一个简单的封闭公式适用于所有偏序集。
反演背后的三角方程组
选定一个线性扩张,并按该次序写出各下集的总量。每个总量含有自身贡献(系数为一)以及只出现在列表更前位置的那些贡献。这个方程组是对角线全为一的三角方程组。解出第一个方程,代入第二个,依此类推。这样不必先计算关联函数的逆,就得到了被还原函数的存在性与唯一性。
莫比乌斯公式把这些逐次相减打包成仅由序决定的系数。若在同一个偏序集上给出若干不同的总量函数,可以重复使用同一组系数。更换线性扩张只会改变矩阵的呈现方式,而不改变序关系及其区间递推式,因此不会改变还原的结果。
概念视角结构
累计求和依赖于一个关系
在链上,下集就是初始段,反演就是普通的差分。在子集上,下集指所有被包含的子集,反演使用正负交替的符号。在因数上,下集指所有整数因数,反演使用算术莫比乌斯函数的值。是关系决定了哪些贡献被汇总;逆属于该关系本身,而不是某种通用的减法规则。
由上集总量得到容斥原理
还有一个同样有用的上集形式。若 ,则 。把第一个表达式代入第二个:对 的内层求和是 ,所以只有 的项保留下来。反方向则用另一个逆元等式得到。由于汇总的方向改变了,端点的角色也随之对调。
对于带有若干命名性质的有限全集,令 表示恰好具有指标集 所对应性质的对象个数。令 表示具有 中每一个性质的对象个数(可能同时具有其他性质)。则 。在空集处对布尔(Boole)偏序集作反演,就得到不具有任何这些性质的对象的交替交集公式。特别地,空指标的总量是整个全集,而不是零。这解释了容斥原理中最初的全集项。
常见错误
(交集计数不是恰好计数)
“恰好”一词至关重要。交集计数要求具有所有命名的性质,但并不禁止其他性质。恰好具有某些性质的计数则禁止指标集之外的每一种性质。把这两类总量混用,会改变所反演的关系,通常会得出错误的数字。
计算遵循证明
要列出关联函数的逆,按区间由小到大的次序处理。先存入对角线上的一。之后每个递推式所用的项,都已在严格更小的区间上得到。也可以改用扩张的次序来做三角反演。若输入的序的 zeta 值为整数,两种方法都应保持精确的整数运算;由递推式可知,每个还原出的系数都是整数。
这是一个有限的过程,并不意味着所有偏序集都有廉价的表示。列出每一对可比较元素本身就可能需要二次方量级的条目。由紧凑规则给出的序(例如子集包含)可能有特殊公式,从而避免完整的表。布尔公式之所以有用,正是因为它用一个基数之差表达了整族区间的逆。
常见错误
反例模式
按区间长度正负交替并非普遍规则
在链 上,端点之间的值为零,尽管两端点之间有两个覆盖步。若赋予符号 ,则得到一,这违反递推式 。基数公式的正负交替之所以在子集区间上成立,是因为所有中间子集的选择会产生二项式抵消。它不能移植到任意的 Hasse 图上。
常见错误
(线性扩张不增加任何比较)
线性扩张也不会使原本不可比较的对象在原偏序中变得可比较。它给出的是与该关系相容的辅助全序。在构造区间、依赖关系的邻域或累计和时,应保留原来的关系。
总结
有限偏序允许给出尊重依赖关系的排列。它们的 zeta 函数沿着序汇总各项贡献,而唯一确定的关联函数的逆则撤销这一汇总。普通差分、子集的容斥原理以及算术因数反演,是同一个有限求和证明的三种不同实例。
练习
快速检查
(在菱形偏序集中计算自底元出发的莫比乌斯值,其中底元为 ,互不可比较的中间元素为 与 ,顶元为 。)
然后由总量 还原这四个贡献。
解答 · 答案
各值为 ,,以及 。从两个中间元素到顶元的两个区间,其值为 。因此在 处的贡献分别为 ;最后一个是 。把下方的贡献相加就能重现每一个总量。
快速检查
(某个对象全集具有两个性质。全集大小为 ,两个性质各自的计数分别为 与 ,交集计数为 。请还原全部四个恰好具有某些性质的计数。)
在两个性质的子集偏序集上使用上集总量。
解答 · 答案
两个性质同时出现在三个对象上。只有第一个性质的有 个;只有第二个性质的有 个;两个性质都没有的有 个。这四个数之和为二十,并且对它们作相应的上集求和可还原九、八与三。反演把交集当作一个包含计数使用,而不是当作另一个需要被减去两次的互不相交的类别。
快速检查
(证明:每个具有唯一极小元的有限非空偏序集都有最小元。)
唯一的极小元是比单纯选取某一个极小元更强的条件。
解答 · 答案
设 为唯一的极小元,并任取 。有限非空的下集 有一个极小元 。若整个偏序集中有任何元素严格小于 ,由传递性它会落在这个下集中,与 在其中的极小性相矛盾。因此 在全局上是极小的,必定等于 。故 。由于 是任意的, 是最小元。