容斥原理

三個集的情況

容斥原理又称排容原理，在組合數學裏，其說明若$A_1$, ..., $A_n$ 為有限集，則

$\left|\bigcup_{i=1}^n A_i\right|=\sum_{i=1}^n\left|A_i\right| -\sum_{i,j\,:\,i\neq j}\left|A_i\cap A_j\right|$$+\sum_{i,j,k\,:\,i\neq j\neq k}\left|A_i\cap A_j\cap A_k\right|-\ \cdots\cdots\ \pm \left|A_1\cap\cdots\cap A_n\right|$

其中$|A|$表示$A$的基數。例如在兩個集的情況時，我們可以透過將$|A|$和$|B|$相加，再減去其交集的基數，而得到其并集的基數。

概率论中的容斥原理

在概率论中，对于概率空间$\scriptstyle(\Omega,\mathcal{F},\mathbb{P})$中的事件A₁，……，A_n，当n = 2时容斥原理的公式为：

$\mathbb{P}(A_1\cup A_2)=\mathbb{P}(A_1)+\mathbb{P}(A_2)-\mathbb{P}(A_1\cap A_2),$

当n = 3时，公式为：

$\begin{align}\mathbb{P}(A_1\cup A_2\cup A_3)&=\mathbb{P}(A_1)+\mathbb{P}(A_2)+\mathbb{P}(A_3)\\ &\qquad-\mathbb{P}(A_1\cap A_2)-\mathbb{P}(A_1\cap A_3)-\mathbb{P}(A_2\cap A_3)\\ &\qquad+\mathbb{P}(A_1\cap A_2\cap A_3) \end{align}$

一般地：

$\begin{align} \mathbb{P}\biggl(\bigcup_{i=1}^n A_i\biggr) & {} =\sum_{i=1}^n \mathbb{P}(A_i) -\sum_{i,j\,:\,i<j}\mathbb{P}(A_i\cap A_j) \\ &\qquad+\sum_{i,j,k\,:\,i<j<k}\mathbb{P}(A_i\cap A_j\cap A_k)-\ \cdots\ +(-1)^{n-1}\, \mathbb{P}\biggl(\bigcap_{i=1}^n A_i\biggr), \end{align}$

也可以写成：

$\mathbb{P}\biggl(\bigcup_{i=1}^n A_i\biggr) =\sum_{k=1}^n (-1)^{k-1}\sum_{\scriptstyle I\subset\{1,\ldots,n\}\atop\scriptstyle|I|=k} \mathbb{P}(A_I),$

对于一般的测度空间(S,Σ,μ)和有限测度的可测子集A₁，……，A_n，上面的恒等式也成立，如果把概率测度$\mathbb{P}$换为测度μ。

特殊情况

如果在容斥原理的概率形式中，交集A_I的概率只与I中元素的个数有关，也就是说，对于{1, ..., n}中的每一个k，都存在一个a_k，使得：

$a_k=\mathbb{P}(A_I)$，对于每一个$I\subset\{1,\ldots,n\} \,\, (|I|=k),$

则以上的公式可以简化为：

$\mathbb{P}\biggl(\bigcup_{i=1}^n A_i\biggr) =\sum_{k=1}^n (-1)^{k-1}\binom nk a_k$

这是由于二项式系数$\scriptstyle\binom nk$的组合解释。

类似地，如果对有限集合A₁，……，A_n的并集的元素个数感兴趣，且对于{1, ..., n}中的每一个k，交集

$A_I:=\bigcap_{i\in I} A_i$

的元素个数都相同，例如a_k = |A_I|，与{1, ..., n}的k元素子集I无关，则：

$\biggl|\bigcup_{i=1}^n A_i\biggr| =\sum_{k=1}^n (-1)^{k-1}\binom nk a_k\,.$

在一般的测度空间(S,Σ,μ)和有限测度的可测子集A₁，……，A_n的情况中，也可以进行类似的简化。

容斥原理的证明

欲证明容斥原理，我们首先要验证以下的关于指示函数的等式：

$1_{\cup_{i=1}^n A_i} =\sum_{k=1}^n (-1)^{k-1}\sum_{\scriptstyle I\subset\{1,\ldots,n\}\atop\scriptstyle|I|=k} 1_{A_I}\qquad(*)$

至少有两种方法来证明这个等式：

第一种方法 我们只需证明对于A₁，……，A_n的并集中的每一个x，等式都成立。假设x正好属于m个集合（1 ≤ m ≤ n），不妨设它们为A₁，……，A_m。则x处的等式化为：

$1 =\sum_{k=1}^m (-1)^{k-1}\sum_{\scriptstyle I\subset\{1,\ldots,m\}\atop\scriptstyle|I|=k} 1.$

m元素集合中的k元素子集的个数，是二项式系数$\textstyle\binom mk$ 的组合解释。由于$\textstyle1=\binom m0$ ，我们有：

$\binom m0 =\sum_{k=1}^m (-1)^{k-1}\binom mk.$

把所有的项移到等式的左端，我们便得到(1 – 1)^m的二项式展开式，因此可以看出，(*)对x成立。

第二种方法 设A表示集合A₁，……，A_n的并集。于是：

$0=(1_A-1_{A_1})(1_A-1_{A_2})\cdots(1_A-1_{A_n})\,,$

这是因为对于不在A内的x，两边都等于零，而如果x属于其中一个集合，例如A_m，则对应的第m个因子为零。把右端的乘积展开来，便可得到等式(*)。

其它形式

有时容斥原理用以下的形式来表述：如果

$g(A)=\sum_{S\,:\,S\subseteq A}f(S)$

那么：

$f(A)=\sum_{S\,:\,S\subseteq A}(-1)^{\left|A\right|-\left|S\right|}g(S)$

在这种形式中可以看出，它是A的所有子集的偏序集合的指标代数的莫比乌斯反演公式。

应用

在许多情况下，容斥原理都可以给出精确的公式（特别是用埃拉托斯特尼筛法计算素数的个数时），但是用处不大，这是因为它里面含有的项太多。即使每一个单独的项都可以准确地估计，误差累积起来仍然意味着容斥原理不能直接应用。在数论中，这个困难由维戈·布朗解决。开始时进展很慢，但他的想法逐渐被其他数学家所应用，于是便产生了许多各种各样的筛法。这些方法是尝试找出被“筛选“的集合的上界，而不是一个确切的公式。

乱序排列

容斥原理的一个著名的应用，是计算一个有限集合的所有乱序排列的数目。一个集合A的乱序排列，是从A到A的没有不动点的双射。通过容斥原理，我们可以证明，如果A含有n个元素，则乱序排列的数目为[n! / e]，其中[x]表示最接近x的整数。

这也称为n的子阶乘，记为!n。可以推出，如果所有的双射都有相同的概率，则当n增大时，一个随机双射是乱序排列的概率迅速趋近于1/e。

交集的计算

容斥原理与德·摩根定理结合起来，也可以用于计算集合的交集中元素的数目。设$\scriptstyle\overline{A}_k$表示A_k关于全集A的补集，使得对于每一个k，都有$\scriptstyle A_k\, \subseteq\, A$。于是，我们有：

$\bigcap_{i=1}^n A_i = \overline{\bigcup_{i=1}^n \overline{A}_i}$

这样便把计算交集的问题化为计算并集的问题。

参见

• 组合原理
• 布尔不等式
• 项链问题
• 许特-内斯比特公式
• 最大-最小恒等式

参考文献

• Klaus Dohmen: Improved Bonferroni Inequalities via Abstract Tubes - Inequalities and Identities of Inclusion-Exclusion Type, Springer-Verlag, 2003, ISBN 3-540-20025-8.
• Stasys Jukna: Extremal Combinatorics, Springer, 2001, ISBN 3-540-66313-4.

本條目含有来自PlanetMath《principle of inclusion-exclusion》的材料，版权遵守乃遵守知识共享协议：署名-相同方式共享协议。