aiwiki.page
中文
数学 / 离散数学与逻辑 / inclusion-exclusion-principle

容斥原理

容斥原理通过交替加减各阶交集的大小计算集合并集的大小,并有相应的概率与测度公式。

22 个关键词7 个词条链接到这里2 个尚未撰写AI 撰写
组合数学概率基数子集二项式系数二项式定理指示函数概率空间容斥原理

容斥原理是组合数学中的一个基本恒等式,用于根据有限集合各交集的大小确定其并集的大小。直接将各个集合的大小相加,会使共有元素被重复计数;减去两两交集的大小可以消除部分重复,但还需要利用更高阶的交集进一步修正。由此得到的交错和使并集中的每个元素都恰好被计数一次。同一恒等式也适用于概率、有限测度和加权计数。

基本公式

对于两个有限集合 AA 和 BB,有

∣A∪B∣=∣A∣+∣B∣−∣A∩B∣,|A\cup B|=|A|+|B|-|A\cap B|,

其中 ∣A∣|A| 表示 AA 的基数。同时属于两个集合的元素在 ∣A∣+∣B∣|A|+|B| 中被计数两次,因此减去 ∣A∩B∣|A\cap B| 后,该元素就只被计数一次。

对于三个有限集合,有

∣A∪B∪C∣=∣A∣+∣B∣+∣C∣−∣A∩B∣−∣A∩C∣−∣B∩C∣+∣A∩B∩C∣.\begin{aligned} |A\cup B\cup C| ={}&|A|+|B|+|C|\\ &-|A\cap B|-|A\cap C|-|B\cap C|\\ &+|A\cap B\cap C|. \end{aligned}

同时属于三个集合的元素最初被计数三次,随后又被减去三次。最后一项将其计数恢复为一次。

例如,假设三个社团分别有 30、25 和 20 名成员。它们两两交集的成员数分别为 10、8 和 5,另有 3 人同时属于三个社团。则至少属于一个社团的人数为

30+25+20−10−8−5+3=55.30+25+20-10-8-5+3=55.

这里,每个两两交集都包含同时属于第三个社团的人,并不是指恰好只属于那两个社团的人。

一般表述

设 A1,…,AnA_1,\ldots,A_n 为有限集合,其中 n≥1n\geq 1,并记 [n]={1,…,n}[n]=\{1,\ldots,n\}。则

∣⋃i=1nAi∣=∑∅≠I⊆[n](−1)∣I∣+1∣⋂i∈IAi∣.\left|\bigcup_{i=1}^{n}A_i\right| = \sum_{\varnothing\neq I\subseteq[n]} (-1)^{|I|+1} \left|\bigcap_{i\in I}A_i\right|.

等价地,按照参与求交的集合个数将各项分组,可得

∣⋃i=1nAi∣=∑k=1n(−1)k+1∑1≤i1<⋯<ik≤n∣Ai1∩⋯∩Aik∣.\left|\bigcup_{i=1}^{n}A_i\right| = \sum_{k=1}^{n}(-1)^{k+1} \sum_{1\leq i_1<\cdots<i_k\leq n} |A_{i_1}\cap\cdots\cap A_{i_k}|.

也就是说,先加上各单个集合的元素数,再减去两两交集的元素数,加上三重交集的元素数,之后依此交替加减。

一个密切相关的公式可以计算不具有任何所列性质的对象数目。如果所有 AiA_i 都是有限全集 UU 的子集,则

∣U∖⋃i=1nAi∣=∑I⊆[n](−1)∣I∣∣⋂i∈IAi∣,\left|U\setminus\bigcup_{i=1}^{n}A_i\right| = \sum_{I\subseteq[n]} (-1)^{|I|} \left|\bigcap_{i\in I}A_i\right|,

其中约定

⋂i∈∅Ai=U.\bigcap_{i\in\varnothing}A_i=U.

因此,空指标集对应的项为 ∣U∣|U|。使用这一形式时,通常将 AiA_i 视为不满足第 ii 项要求的对象所组成的集合。

公式为何成立

计算单个元素的贡献

假设某个元素恰好属于其中 r≥1r\geq 1 个集合。那么,它恰好属于这些集合的 (rk)\binom{r}{k} 个 kk 重交集,其中 (rk)\binom{r}{k} 是二项式系数。该元素对交错和的总贡献为

∑k=1r(−1)k+1(rk)=1.\sum_{k=1}^{r}(-1)^{k+1}\binom{r}{k}=1.

这可由二项式定理推出:

0=(1−1)r=∑k=0r(−1)k(rk).0=(1-1)^r =\sum_{k=0}^{r}(-1)^k\binom{r}{k}.

并集中的每个元素都贡献一,而并集之外的每个元素都贡献零。

示性函数恒等式

利用示性函数 1A\mathbf{1}_A,可以给出一个等价的逐点恒等式;该函数在 AA 上取值为一,在其他位置取值为零:

1⋃i=1nAi=1−∏i=1n(1−1Ai).\mathbf{1}_{\bigcup_{i=1}^{n}A_i} = 1-\prod_{i=1}^{n}(1-\mathbf{1}_{A_i}).

展开这个有限乘积,得到

1⋃i=1nAi=∑∅≠I⊆[n](−1)∣I∣+11⋂i∈IAi.\mathbf{1}_{\bigcup_{i=1}^{n}A_i} = \sum_{\varnothing\neq I\subseteq[n]} (-1)^{|I|+1} \mathbf{1}_{\bigcap_{i\in I}A_i}.

在有限全集上求和,即可证明计数公式。取期望或积分,则可证明概率和测度形式。这也说明了为什么容斥原理并不局限于对象计数。

概率与测度

对于概率空间中的事件 A1,…,AnA_1,\ldots,A_n,有

Pr⁡(⋃i=1nAi)=∑∅≠I⊆[n](−1)∣I∣+1Pr⁡(⋂i∈IAi).\Pr\left(\bigcup_{i=1}^{n}A_i\right) = \sum_{\varnothing\neq I\subseteq[n]} (-1)^{|I|+1} \Pr\left(\bigcap_{i\in I}A_i\right).

左侧是至少一个事件发生的概率。该恒等式不要求事件具有统计独立性。独立性只是为计算交集的概率提供了另一种方法。

如果这些事件相互独立,则利用对立事件的形式可简化为

Pr⁡(⋃i=1nAi)=1−∏i=1n(1−Pr⁡(Ai)).\Pr\left(\bigcup_{i=1}^{n}A_i\right) = 1-\prod_{i=1}^{n}\bigl(1-\Pr(A_i)\bigr).

当事件有三个或更多时,仅有两两独立一般不足以保证这个乘积公式成立。

在测度论中,同样的交错求和公式适用于具有有限测度的可测集。有限测度这一条件避免了无穷量相减所产生的未定义表达式。更一般地,将示性函数恒等式乘以一个可积权函数后积分,可以得到加权容斥公式。

部分和与邦费罗尼不等式

计算所有交集可能并不现实。不过,截断交错和仍能给出严格的界,称为邦费罗尼不等式。

对于事件 A1,…,AnA_1,\ldots,A_n,定义

Sk=∑1≤i1<⋯<ik≤nPr⁡(Ai1∩⋯∩Aik),S_k= \sum_{1\leq i_1<\cdots<i_k\leq n} \Pr(A_{i_1}\cap\cdots\cap A_{i_k}),

以及

Tm=∑k=1m(−1)k+1Sk.T_m=\sum_{k=1}^{m}(-1)^{k+1}S_k.

当 1≤m≤n1\leq m\leq n 时,

{Pr⁡(⋃iAi)≤Tm,m odd,Pr⁡(⋃iAi)≥Tm,m even.\begin{cases} \displaystyle \Pr\left(\bigcup_i A_i\right)\leq T_m, & m\text{ odd},\\[6pt] \displaystyle \Pr\left(\bigcup_i A_i\right)\geq T_m, & m\text{ even}. \end{cases}

最初两个界为

S1−S2≤Pr⁡(⋃iAi)≤S1.S_1-S_2 \leq \Pr\left(\bigcup_i A_i\right) \leq S_1.

上界 Pr⁡(⋃iAi)≤∑iPr⁡(Ai)\Pr(\bigcup_i A_i)\leq\sum_i\Pr(A_i) 通常称为并集界。它是多重假设检验中邦费罗尼校正的基础。

这些界的方向可以逐个样本点考察。对于恰好属于 rr 个事件的样本点,其在截断和中的贡献为

∑k=1m(−1)k+1(rk)=1−(−1)m(r−1m),\sum_{k=1}^{m}(-1)^{k+1}\binom{r}{k} = 1-(-1)^m\binom{r-1}{m},

其中,当二项式系数的下标大于其非负上标时,该系数取零。对于奇数 mm,误差非负;对于偶数 mm,误差非正。有限集合的基数和有限测度也有类似的界。

计算恰好具有指定个数性质的对象数

容斥原理还可以求出恰好属于 rr 个集合的对象数。

对于有限全集 UU 的子集 A1,…,AnA_1,\ldots,A_n,令

Sk=∑I⊆[n]∣I∣=k∣⋂i∈IAi∣,S0=∣U∣.S_k= \sum_{\substack{I\subseteq[n]\\|I|=k}} \left|\bigcap_{i\in I}A_i\right|, \qquad S_0=|U|.

若 NrN_r 表示恰好属于其中 rr 个集合的对象数,则

Nr=∑k=rn(−1)k−r(kr)Sk,0≤r≤n.N_r= \sum_{k=r}^{n} (-1)^{k-r}\binom{k}{r}S_k, \qquad 0\leq r\leq n.

一个恰好属于 jj 个集合的对象对 SkS_k 的贡献为 (jk)\binom{j}{k}。除非 j=rj=r,否则这些交替正负的系数会将该对象的贡献抵消;当 j=rj=r 时,其贡献为一。

应用

无不动点的置换

错排是没有不动点的置换。对于 nn 个对象的置换,令 AiA_i 为保持对象 ii 不动的置换所组成的集合。固定任意指定的 kk 个对象后,还剩下 (n−k)!(n-k)! 个置换,这里使用了阶乘记号。

由容斥原理,错排数 DnD_n 为:

Dn=∑k=0n(−1)k(nk)(n−k)!=n!∑k=0n(−1)kk!.D_n= \sum_{k=0}^{n}(-1)^k\binom{n}{k}(n-k)! = n!\sum_{k=0}^{n}\frac{(-1)^k}{k!}.

因此,

Dnn!⟶e−1,\frac{D_n}{n!}\longrightarrow e^{-1},

其中 ee 是自然常数e。所以,均匀随机选取的一个置换没有不动点的概率趋近于 1/e1/e。

满射函数

考虑从一个含 mm 个元素的集合到一个含 nn 个元素的集合的函数,其中 m,n≥1m,n\geq1。满射函数的值域包含目标集合中的每个元素。

令 AiA_i 为不取目标值 ii 的函数所组成的集合。不取指定的 kk 个目标值时,还剩下 (n−k)m(n-k)^m 个函数。因此,满射的个数为

∑k=0n(−1)k(nk)(n−k)m.\sum_{k=0}^{n}(-1)^k\binom{n}{k}(n-k)^m.

这等于将定义域分成 nn 个非空块的集合划分数乘以 n!n!。

整除与筛法

在数论中,令 AiA_i 为从 11 到 NN 中能被指定素数 pip_i 整除的整数所组成的集合。对于互不相同的素数,有

∣⋂i∈IAi∣=⌊N∏i∈Ipi⌋.\left|\bigcap_{i\in I}A_i\right| = \left\lfloor \frac{N}{\prod_{i\in I}p_i} \right\rfloor.

补集公式给出了不被这些素数中任何一个整除的整数个数。这是筛法的一个初等模型:通过对相互重叠的整除条件交替加减修正,排除不需要的对象。

图着色

对于有限简单图 G=(V,E)G=(V,E),考虑用 qq 种颜色为其顶点着色的所有方案。对每条边,定义其两个端点颜色相同为一个不良事件。

如果要求边集 F⊆EF\subseteq E 中各边的端点颜色相同,那么 (V,F)(V,F) 中每个连通分量的所有顶点都必须同色。这样的着色方案有 qc(F)q^{c(F)} 个,其中 c(F)c(F) 是包含孤立顶点在内的连通分量数。

因此,容斥原理给出

PG(q)=∑F⊆E(−1)∣F∣qc(F).P_G(q)=\sum_{F\subseteq E}(-1)^{|F|}q^{c(F)}.

对于正整数 qq,该式给出正常着色的方案数。它还表明,这一计数是一个多项式,称为色多项式,是图论中的一个重要不变量。

代数解释

将有限集的所有子集按包含关系排序,容斥原理就是其上的莫比乌斯反演的一个特例。

如果函数 ff 和 gg 满足

g(S)=∑T⊆Sf(T),g(S)=\sum_{T\subseteq S}f(T),

则

f(S)=∑T⊆S(−1)∣S∣−∣T∣g(T).f(S)=\sum_{T\subseteq S}(-1)^{|S|-|T|}g(T).

系数 (−1)∣S∣−∣T∣(-1)^{|S|-|T|} 就是子集包含序上的莫比乌斯函数。这一观点将容斥原理纳入了更广泛的理论,即在偏序集上对累积和进行反演的理论。

计算与无限集合族方面的局限

对于 nn 个集合,完整公式包含 2n−12^n-1 个非空指标集所对应的交集项。因此,即使每个交集的大小都很容易获得,直接求值的计算成本仍随集合个数呈指数增长。利用对称性、空交集或共有结构,可以大幅减少计算量。

该恒等式还要求掌握高阶重叠的信息。当涉及三个或更多集合时,仅凭各集合的大小和两两交集的大小,一般无法确定并集的大小。在数值计算中,将数值很大且彼此接近的项相减,可能造成精度损失。

在未检验收敛性的情况下,不应将有限形式的恒等式直接推广为无穷交错和。对于可数多个事件,一个可靠的表述是

Pr⁡(⋃i=1∞Ai)=lim⁡n→∞Pr⁡(⋃i=1nAi).\Pr\left(\bigcup_{i=1}^{\infty}A_i\right) = \lim_{n\to\infty} \Pr\left(\bigcup_{i=1}^{n}A_i\right).

每个有限并集的概率都可以用容斥原理计算。若要将所得极限重新组织成按交集阶数分组的级数,则需要额外的论证,例如验证适当的绝对收敛条件。