容斥原理

容斥原理（inclusion-exclusion principle）又称排容原理，在组合数学里，其说明若${\displaystyle A_{1}}$, ..., ${\displaystyle A_{n}}$ 为有限集，则 ${\displaystyle {\begin{aligned}\left|\bigcup _{i=1}^{n}A_{i}\right|={}&\sum _{i=1}^{n}|A_{i}|-\sum _{1\leq i<j\leq n}|A_{i}\cap A_{j}|+\sum _{1\leq i<j<k\leq n}|A_{i}\cap A_{j}\cap A_{k}|-\cdots +(-1)^{n-1}\left|A_{1}\cap \cdots \cap A_{n}\right|.\end{aligned}}}$

三个集的情况

其中${\displaystyle |A|}$表示${\displaystyle A}$的基数。例如在两个集的情况时，我们可以通过将${\displaystyle |A|}$和${\displaystyle |B|}$相加，再减去其交集的基数，而得到其并集的基数。

描述

两个集合的容斥原理  

${\displaystyle \left|A\cup B\right|=\left|A\right|+\left|B\right|-\left|A\cap B\right|}$

三个集合的容斥原理

${\displaystyle \left|A\cup B\cup C\right|=\left|A\right|+\left|B\right|+\left|C\right|-\left|A\cap B\right|-\left|A\cap C\right|-\left|B\cap C\right|+\left|A\cap B\cap C\right|}$

${\displaystyle n}$个集合的容斥原理

      要计算几个集合并集的大小，我们要先将所有单个集合的大小计算出来，然后减去所有两个集合相交的部分，再加回所有三个集合相交的部分，再减去所有四个集合相交的部分，依此类推，一直计算到所有集合相交的部分。

最终得到公式：

${\displaystyle {\begin{aligned}\left|\bigcup _{i=1}^{n}A_{i}\right|={}&\sum _{i=1}^{n}|A_{i}|-\sum _{1\leq i<j\leq n}|A_{i}\cap A_{j}|+\sum _{1\leq i<j<k\leq n}|A_{i}\cap A_{j}\cap A_{k}|-\cdots +(-1)^{n-1}\left|A_{1}\cap \cdots \cap A_{n}\right|.\end{aligned}}}$

又可写成

${\displaystyle \left|\bigcup _{i=1}^{n}A_{i}\right|=\sum _{k=1}^{n}(-1)^{k+1}\left(\sum _{1\leq i_{1}<\cdots <i_{k}\leq n}|A_{i_{1}}\cap \cdots \cap A_{i_{k}}|\right)}$

或

${\displaystyle \left|\bigcup _{i=1}^{n}A_{i}\right|=\sum _{\emptyset \neq J\subseteq \{1,2,\ldots ,n\}}(-1)^{|J|-1}{\Biggl |}\bigcap _{j\in J}A_{j}{\Biggr |}.}$

概率论中的容斥原理

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

${\displaystyle \mathbb {P} (A_{1}\cup A_{2})=\mathbb {P} (A_{1})+\mathbb {P} (A_{2})-\mathbb {P} (A_{1}\cap A_{2}),}$

当n = 3时，公式为：

${\displaystyle \mathbb {P} (A_{1}\cup A_{2}\cup A_{3})=\mathbb {P} (A_{1})+\mathbb {P} (A_{2})+\mathbb {P} (A_{3})-\mathbb {P} (A_{1}\cap A_{2})-\mathbb {P} (A_{1}\cap A_{3})-\mathbb {P} (A_{2}\cap A_{3})+\mathbb {P} (A_{1}\cap A_{2}\cap A_{3})}$

一般地：

${\displaystyle \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})+\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 )},}$

也可以写成：

${\displaystyle \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，上面的恒等式也成立，如果把概率测度${\displaystyle \mathbb {P} }$换为测度μ。

特殊情况

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

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

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

${\displaystyle \mathbb {P} {\biggl (}\bigcup _{i=1}^{n}A_{i}{\biggr )}=\sum _{k=1}^{n}(-1)^{k-1}{\binom {n}{k}}a_{k}}$

这是由于二项式系数${\displaystyle \scriptstyle {\binom {n}{k}}}$的组合解释。

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

${\displaystyle A_{I}:=\bigcap _{i\in I}A_{i}}$

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

${\displaystyle {\biggl |}\bigcup _{i=1}^{n}A_{i}{\biggr |}=\sum _{k=1}^{n}(-1)^{k-1}{\binom {n}{k}}a_{k}\,.}$

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

容斥原理的证明

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

${\displaystyle 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处的等式化为：

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

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

${\displaystyle {\binom {m}{0}}=\sum _{k=1}^{m}(-1)^{k-1}{\binom {m}{k}}.}$

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

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

${\displaystyle 0=(1_{A}-1_{A_{1}})(1_{A}-1_{A_{2}})\cdots (1_{A}-1_{A_{n}})\,,}$

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

归纳法证明

设 ${\displaystyle S_{1}=n(A_{1})+n(A_{2})+n(A_{3})+\cdots +n(A_{n})}$

${\displaystyle S_{2}=n(A_{1}\cap A_{2})+n(A_{1}\cap A_{3})+\cdots +n(A_{1}\cap A_{n})\;+\;n(A_{2}\cap A_{3})+\cdots +n(A_{n-1}\cap A_{n})}$

${\displaystyle S_{3}=n(A_{1}\cap A_{2}\cap A_{3})+\cdots +n(A_{n-2}\cap A_{n-1}\cap A_{n})}$

⋮

${\displaystyle S_{n}=n(A_{1}\cap A_{2}\cap A_{3}\cap \cdots \cap A_{n})}$

求证 ${\displaystyle n(A_{1}\cup A_{2}\cup A_{3}\cup \cdots \cup A_{n})=S_{1}-S_{2}+S_{3}-\cdots +(-1)^{n-1}S_{n}.}$

证明： 当${\displaystyle n=2}$时， ${\displaystyle n(A_{1}\cup A_{2})=n(A_{1})+n(A_{2})-n(A_{1}\cap A_{2})=S_{1}-S_{2}.}$

假设当${\displaystyle n=k\ (k\geq 2)}$时，有 ${\displaystyle n(A_{1}\cup A_{2}\cup \cdots \cup A_{k})=S_{1}-S_{2}+S_{3}-\cdots +(-1)^{k-1}S_{k}.}$

当${\displaystyle n=k+1}$时， ${\displaystyle {\begin{aligned}n(A_{1}\cup A_{2}\cup \cdots \cup A_{k}\cup A_{k+1})&=n{\Bigl (}(A_{1}\cup A_{2}\cup \cdots \cup A_{k})\cup A_{k+1}{\Bigr )}\\[1ex]&=n(A_{1}\cup A_{2}\cup \cdots \cup A_{k})+n(A_{k+1})\\[1ex]&\quad -n{\Bigl (}(A_{1}\cup A_{2}\cup \cdots \cup A_{k})\cap A_{k+1}{\Bigr )}\\[1ex]&=n(A_{1}\cup A_{2}\cup \cdots \cup A_{k})+n(A_{k+1})\\[1ex]&\quad -n{\Bigl (}(A_{1}\cap A_{k+1})\cup (A_{2}\cap A_{k+1})\cup \cdots \cup (A_{k}\cap A_{k+1}){\Bigr )}.\end{aligned}}}$

∵ 当 \(n=k\) 时，上式成立， ∴ ${\displaystyle n(A_{1}\cup A_{2}\cup \cdots \cup A_{k+1})=S_{1}-S_{2}+S_{3}-\cdots +(-1)^{k}S_{k+1}.}$

综上所述，当${\displaystyle n\geq 2}$时， ${\displaystyle {\begin{aligned}n(A_{1}\cup A_{2}\cup \cdots \cup A_{n})=&\;n(A_{1})+n(A_{2})+\cdots +n(A_{n})\\[1ex]&\;-{\Bigl [}n(A_{1}\cap A_{2})+n(A_{1}\cap A_{3})+\cdots +n(A_{n-1}\cap A_{n}){\Bigr ]}\\[1ex]&\;+{\Bigl [}n(A_{1}\cap A_{2}\cap A_{3})+\cdots {\Bigr ]}\\[1ex]&\;-\cdots +(-1)^{n-1}n(A_{1}\cap A_{2}\cap \cdots \cap A_{n}).\end{aligned}}}$

其它形式

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

${\displaystyle g(A)=\sum _{S\,:\,S\subseteq A}f(S)}$

那么：

${\displaystyle 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。

交集的计算

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

${\displaystyle \bigcap _{i=1}^{n}A_{i}={\overline {\bigcup _{i=1}^{n}{\overline {A}}_{i}}}}$

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

参见

• 其他组合原理，如：
  • 乘法原理
  • 抽屉原理
• 布尔不等式
• 项链问题
• 许特-内斯比特公式
• 最大-最小恒等式

拓展阅读

• http://cs.tju.edu.cn/faculty/zhangkl/teaching/comb/lec09.pdf （页面存档备份，存于互联网档案馆）

• http://blog.sina.com.cn/s/blog_6be9596c0100miag.html （页面存档备份，存于互联网档案馆）

• http://e-maxx.ru/algo/inclusion_exclusion_principle （页面存档备份，存于互联网档案馆） （页面存档备份，存于互联网档案馆）（俄文） 中文翻译：http://www.cppblog.com/vici/archive/2011/09/05/155103.html （页面存档备份，存于互联网档案馆）

参考文献

• 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.
• http://blog.csdn.net/xianglunxi/article/details/9310105 （页面存档备份，存于互联网档案馆）

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