容斥原理是组合数学中的一个基本恒等式,用于根据有限集合各交集的大小确定其并集的大小。直接将各个集合的大小相加,会使共有元素被重复计数;减去两两交集的大小可以消除部分重复,但还需要利用更高阶的交集进一步修正。由此得到的交错和使并集中的每个元素都恰好被计数一次。同一恒等式也适用于概率、有限测度和加权计数。
基本公式
对于两个有限集合 A 和 B,有
∣A∪B∣=∣A∣+∣B∣−∣A∩B∣,
其中 ∣A∣ 表示 A 的基数。同时属于两个集合的元素在 ∣A∣+∣B∣ 中被计数两次,因此减去 ∣A∩B∣ 后,该元素就只被计数一次。
对于三个有限集合,有
∣A∪B∪C∣=∣A∣+∣B∣+∣C∣−∣A∩B∣−∣A∩C∣−∣B∩C∣+∣A∩B∩C∣.
同时属于三个集合的元素最初被计数三次,随后又被减去三次。最后一项将其计数恢复为一次。
例如,假设三个社团分别有 30、25 和 20 名成员。它们两两交集的成员数分别为 10、8 和 5,另有 3 人同时属于三个社团。则至少属于一个社团的人数为
30+25+20−10−8−5+3=55.
这里,每个两两交集都包含同时属于第三个社团的人,并不是指恰好只属于那两个社团的人。
一般表述
设 A1,…,An 为有限集合,其中 n≥1,并记 [n]={1,…,n}。则
i=1⋃nAi=∅=I⊆[n]∑(−1)∣I∣+1i∈I⋂Ai.
等价地,按照参与求交的集合个数将各项分组,可得
i=1⋃nAi=k=1∑n(−1)k+11≤i1<⋯<ik≤n∑∣Ai1∩⋯∩Aik∣.
也就是说,先加上各单个集合的元素数,再减去两两交集的元素数,加上三重交集的元素数,之后依此交替加减。
一个密切相关的公式可以计算不具有任何所列性质的对象数目。如果所有 Ai 都是有限全集 U 的子集,则
U∖i=1⋃nAi=I⊆[n]∑(−1)∣I∣i∈I⋂Ai,
其中约定
i∈∅⋂Ai=U.
因此,空指标集对应的项为 ∣U∣。使用这一形式时,通常将 Ai 视为不满足第 i 项要求的对象所组成的集合。
公式为何成立
计算单个元素的贡献
假设某个元素恰好属于其中 r≥1 个集合。那么,它恰好属于这些集合的 (kr) 个 k 重交集,其中 (kr) 是二项式系数。该元素对交错和的总贡献为
k=1∑r(−1)k+1(kr)=1.
这可由二项式定理推出:
0=(1−1)r=k=0∑r(−1)k(kr).
并集中的每个元素都贡献一,而并集之外的每个元素都贡献零。
示性函数恒等式
利用示性函数 1A,可以给出一个等价的逐点恒等式;该函数在 A 上取值为一,在其他位置取值为零:
1⋃i=1nAi=1−i=1∏n(1−1Ai).
展开这个有限乘积,得到
1⋃i=1nAi=∅=I⊆[n]∑(−1)∣I∣+11⋂i∈IAi.
在有限全集上求和,即可证明计数公式。取期望或积分,则可证明概率和测度形式。这也说明了为什么容斥原理并不局限于对象计数。
概率与测度
对于概率空间中的事件 A1,…,An,有
Pr(i=1⋃nAi)=∅=I⊆[n]∑(−1)∣I∣+1Pr(i∈I⋂Ai).
左侧是至少一个事件发生的概率。该恒等式不要求事件具有统计独立性。独立性只是为计算交集的概率提供了另一种方法。
如果这些事件相互独立,则利用对立事件的形式可简化为
Pr(i=1⋃nAi)=1−i=1∏n(1−Pr(Ai)).
当事件有三个或更多时,仅有两两独立一般不足以保证这个乘积公式成立。
在测度论中,同样的交错求和公式适用于具有有限测度的可测集。有限测度这一条件避免了无穷量相减所产生的未定义表达式。更一般地,将示性函数恒等式乘以一个可积权函数后积分,可以得到加权容斥公式。
部分和与邦费罗尼不等式
计算所有交集可能并不现实。不过,截断交错和仍能给出严格的界,称为邦费罗尼不等式。
对于事件 A1,…,An,定义
Sk=1≤i1<⋯<ik≤n∑Pr(Ai1∩⋯∩Aik),
以及
Tm=k=1∑m(−1)k+1Sk.
当 1≤m≤n 时,
⎩⎨⎧Pr(i⋃Ai)≤Tm,Pr(i⋃Ai)≥Tm,m odd,m even.
最初两个界为
S1−S2≤Pr(i⋃Ai)≤S1.
上界 Pr(⋃iAi)≤∑iPr(Ai) 通常称为并集界。它是多重假设检验中邦费罗尼校正的基础。
这些界的方向可以逐个样本点考察。对于恰好属于 r 个事件的样本点,其在截断和中的贡献为
k=1∑m(−1)k+1(kr)=1−(−1)m(mr−1),
其中,当二项式系数的下标大于其非负上标时,该系数取零。对于奇数 m,误差非负;对于偶数 m,误差非正。有限集合的基数和有限测度也有类似的界。
计算恰好具有指定个数性质的对象数
容斥原理还可以求出恰好属于 r 个集合的对象数。
对于有限全集 U 的子集 A1,…,An,令
Sk=I⊆[n]∣I∣=k∑i∈I⋂Ai,S0=∣U∣.
若 Nr 表示恰好属于其中 r 个集合的对象数,则
Nr=k=r∑n(−1)k−r(rk)Sk,0≤r≤n.
一个恰好属于 j 个集合的对象对 Sk 的贡献为 (kj)。除非 j=r,否则这些交替正负的系数会将该对象的贡献抵消;当 j=r 时,其贡献为一。
应用
无不动点的置换
错排是没有不动点的置换。对于 n 个对象的置换,令 Ai 为保持对象 i 不动的置换所组成的集合。固定任意指定的 k 个对象后,还剩下 (n−k)! 个置换,这里使用了阶乘记号。
由容斥原理,错排数 Dn 为:
Dn=k=0∑n(−1)k(kn)(n−k)!=n!k=0∑nk!(−1)k.
因此,
n!Dn⟶e−1,
其中 e 是自然常数e。所以,均匀随机选取的一个置换没有不动点的概率趋近于 1/e。
满射函数
考虑从一个含 m 个元素的集合到一个含 n 个元素的集合的函数,其中 m,n≥1。满射函数的值域包含目标集合中的每个元素。
令 Ai 为不取目标值 i 的函数所组成的集合。不取指定的 k 个目标值时,还剩下 (n−k)m 个函数。因此,满射的个数为
k=0∑n(−1)k(kn)(n−k)m.
这等于将定义域分成 n 个非空块的集合划分数乘以 n!。
整除与筛法
在数论中,令 Ai 为从 1 到 N 中能被指定素数 pi 整除的整数所组成的集合。对于互不相同的素数,有
i∈I⋂Ai=⌊∏i∈IpiN⌋.
补集公式给出了不被这些素数中任何一个整除的整数个数。这是筛法的一个初等模型:通过对相互重叠的整除条件交替加减修正,排除不需要的对象。
图着色
对于有限简单图 G=(V,E),考虑用 q 种颜色为其顶点着色的所有方案。对每条边,定义其两个端点颜色相同为一个不良事件。
如果要求边集 F⊆E 中各边的端点颜色相同,那么 (V,F) 中每个连通分量的所有顶点都必须同色。这样的着色方案有 qc(F) 个,其中 c(F) 是包含孤立顶点在内的连通分量数。
因此,容斥原理给出
PG(q)=F⊆E∑(−1)∣F∣qc(F).
对于正整数 q,该式给出正常着色的方案数。它还表明,这一计数是一个多项式,称为色多项式,是图论中的一个重要不变量。
代数解释
将有限集的所有子集按包含关系排序,容斥原理就是其上的莫比乌斯反演的一个特例。
如果函数 f 和 g 满足
g(S)=T⊆S∑f(T),
则
f(S)=T⊆S∑(−1)∣S∣−∣T∣g(T).
系数 (−1)∣S∣−∣T∣ 就是子集包含序上的莫比乌斯函数。这一观点将容斥原理纳入了更广泛的理论,即在偏序集上对累积和进行反演的理论。
计算与无限集合族方面的局限
对于 n 个集合,完整公式包含 2n−1 个非空指标集所对应的交集项。因此,即使每个交集的大小都很容易获得,直接求值的计算成本仍随集合个数呈指数增长。利用对称性、空交集或共有结构,可以大幅减少计算量。
该恒等式还要求掌握高阶重叠的信息。当涉及三个或更多集合时,仅凭各集合的大小和两两交集的大小,一般无法确定并集的大小。在数值计算中,将数值很大且彼此接近的项相减,可能造成精度损失。
在未检验收敛性的情况下,不应将有限形式的恒等式直接推广为无穷交错和。对于可数多个事件,一个可靠的表述是
Pr(i=1⋃∞Ai)=n→∞limPr(i=1⋃nAi).
每个有限并集的概率都可以用容斥原理计算。若要将所得极限重新组织成按交集阶数分组的级数,则需要额外的论证,例如验证适当的绝对收敛条件。