查看“︁排容原理”︁的源代码

-{T|zh-hans:容斥原理;zh-hant:排容原理}-
[[File:Inclusion-exclusion.svg|thumb|三個集的情況]]

'''-{A|zh-hans:容斥原理;zh-hant:排容原理}-'''（inclusion-exclusion principle）又称'''-{zh-hans:排容原理;zh-hant:容斥原理}-'''，在[[組合數學]]裏，其說明若<math>A_1</math>, ..., <math>A_n</math> 為[[有限集]]，則
<math>
\begin{align}
\left|\bigcup_{i=1}^n A_i\right| = {} & \sum_{i=1}^n |A_i| - \sum_{1 \le i < j \le n} |A_i\cap A_j| + \sum_{1 \le i < j < k \le n} |A_i \cap A_j\cap A_k| - \cdots + (-1)^{n-1} \left|A_1\cap\cdots\cap A_n\right|.
\end{align}
</math> 

其中<math>|A|</math>表示<math>A</math>的[[基数 (数学)|基數]]。例如在兩個集的情況時，我們可以通過將<math>|A|</math>和<math>|B|</math>相加，再減去其[[交集]]的基數，而得到其[[并集]]的基數。 

== 描述 ==

=== 两个集合的容斥原理  ===
<math> \left | A \cup B \right | = \left | A \right | + \left | B \right | - \left | A \cap B \right | </math>

=== 三个集合的容斥原理 ===
<math> \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 |  </math>

=== <math>n</math>个集合的容斥原理 ===
      要计算几个集合并集的大小，我们要先将所有'''单个集合'''的大小计算出来，然后减去所有'''两个集合相交'''的部分，再加回所有'''三个集合相交'''的部分，再减去所有'''四个集合相交'''的部分，依此类推，一直计算到'''所有集合相交'''的部分。

最终得到公式：

<math>
\begin{align}
\left|\bigcup_{i=1}^n A_i\right| = {} & \sum_{i=1}^n |A_i| - \sum_{1 \le i < j \le n} |A_i\cap A_j| + \sum_{1 \le i < j < k \le n} |A_i \cap A_j\cap A_k| - \cdots + (-1)^{n-1} \left|A_1\cap\cdots\cap A_n\right|.
\end{align}
</math>

又可写成

<math>\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)</math>

或

<math>\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|.</math>

== 概率论中的容斥原理 ==

在[[概率论]]中，对于[[概率空间]]<math>(\Omega,\mathcal{F},\mathbb{P})</math>中的事件''A''<sub>1</sub>，……，''A''<sub>''n''</sub>，当''n''&nbsp;=&nbsp;2时容斥原理的公式为：

:<math>\mathbb{P}(A_1\cup A_2)=\mathbb{P}(A_1)+\mathbb{P}(A_2)-\mathbb{P}(A_1\cap A_2),</math>

当''n''&nbsp;=&nbsp;3时，公式为：

:<math>\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)
</math>

一般地：

:<math>
\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),
</math>

也可以写成：

:<math>\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),</math>

对于一般的[[测度空间]](''S'',''Σ'',''μ'')和有限测度的[[可测]]子集''A''<sub>1</sub>，……，''A<sub>n''</sub>，上面的恒等式也成立，如果把概率测度<math>\mathbb{P}</math>换为测度''μ''。

== 特殊情况 ==

如果在容斥原理的概率形式中，交集''A<sub>I</sub>''的概率只与''I''中元素的个数有关，也就是说，对于{1,&nbsp;...,&nbsp;''n''}中的每一个''k''，都存在一个''a<sub>k</sub>''，使得：

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

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

:<math>\mathbb{P}\biggl(\bigcup_{i=1}^n A_i\biggr)  =\sum_{k=1}^n (-1)^{k-1}\binom nk a_k</math>

这是由于[[二项式系数]]<math>\scriptstyle\binom nk</math>的组合解释。

类似地，如果对有限集合''A''<sub>1</sub>，……，''A<sub>n</sub>''的并集的元素个数感兴趣，且对于{1, ..., ''n''}中的每一个''k''，交集
:<math>A_I:=\bigcap_{i\in I} A_i</math>

的元素个数都相同，例如''a<sub>k</sub>'' = |''A<sub>I</sub>''|，与{1,&nbsp;...,&nbsp;''n''}的''k''元素子集''I''无关，则：

:<math>\biggl|\bigcup_{i=1}^n A_i\biggr|  =\sum_{k=1}^n (-1)^{k-1}\binom nk a_k\,.</math>

在一般的测度空间(''S'',''Σ'',''μ'')和有限测度的可测子集''A''<sub>1</sub>，……，''A<sub>n''</sub>的情况中，也可以进行类似的简化。

== 容斥原理的证明 ==

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

:<math>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(*)</math>

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

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

:<math>1 =\sum_{k=1}^m (-1)^{k-1}\sum_{\scriptstyle I\subset\{1,\ldots,m\}\atop\scriptstyle|I|=k} 1.</math>

''m''元素集合中的''k''元素子集的个数，是[[二项式系数]]<math>\textstyle\binom mk</math>&nbsp;的组合解释。由于<math>\textstyle1=\binom m0</math>&nbsp;，我们有：

:<math>\binom m0 =\sum_{k=1}^m (-1)^{k-1}\binom mk.</math>

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

'''第二种方法''' 设''A''表示集合''A''<sub>1</sub>，……，''A<sub>n''</sub>的并集。于是：

:<math>0=(1_A-1_{A_1})(1_A-1_{A_2})\cdots(1_A-1_{A_n})\,,</math>

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

=== 归纳法证明 ===

设  
<math>
S_1 = n(A_1) + n(A_2) + n(A_3) + \cdots + n(A_n)
</math>

<math>
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)
</math>

<math>
S_3 = n(A_1 \cap A_2 \cap A_3) + \cdots + n(A_{n-2} \cap A_{n-1} \cap A_n)
</math>

⋮

<math>
S_n = n(A_1 \cap A_2 \cap A_3 \cap \cdots \cap A_n)
</math>

求证  
<math>
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.
</math>

证明：  
当<math>n=2</math>时，
<math>
n(A_1 \cup A_2) = n(A_1) + n(A_2) - n(A_1 \cap A_2)
= S_1 - S_2.
</math>

假设当<math>n=k\ (k\ge2)</math>时，有
<math>
n(A_1 \cup A_2 \cup \cdots \cup A_k)
=
S_1 - S_2 + S_3 - \cdots + (-1)^{k-1} S_k.
</math>

当<math>n=k+1</math>时，
<math>
\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}
</math>

∵ 当 \(n=k\) 时，上式成立，  
∴
<math>
n(A_1 \cup A_2 \cup \cdots \cup A_{k+1})
=
S_1 - S_2 + S_3 - \cdots + (-1)^k S_{k+1}.
</math>

综上所述，当<math>n\ge2</math>时，
<math>
\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}
</math>

== 其它形式 ==

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

:<math>g(A)=\sum_{S\,:\,S\subseteq A}f(S)</math>

那么：

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

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

== 应用 ==

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

=== 错排 ===

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

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

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

:<math> 
\bigcap_{i=1}^n A_i = \overline{\bigcup_{i=1}^n \overline{A}_i}
</math>

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

== 参见 ==
* 其他[[组合原理]]，如：
** [[乘法原理]]
** [[抽屜原理]]
* [[布尔不等式]]
* [[项链问题]]
* [[许特-内斯比特公式]]
* [[最大-最小恒等式]]

== 拓展阅读 ==
*http://cs.tju.edu.cn/faculty/zhangkl/teaching/comb/lec09.pdf {{Wayback|url=http://cs.tju.edu.cn/faculty/zhangkl/teaching/comb/lec09.pdf |date=20190815232416 }}

*http://blog.sina.com.cn/s/blog_6be9596c0100miag.html {{Wayback|url=http://blog.sina.com.cn/s/blog_6be9596c0100miag.html |date=20190822030310 }}

*http://e-maxx.ru/algo/inclusion_exclusion_principle {{Wayback|url=http://e-maxx.ru/algo/inclusion_exclusion_principle |date=20200716032755 }} {{Wayback|url=http://e-maxx.ru/algo/inclusion_exclusion_principle |date=20200716032755 }}<nowiki/>（俄文） 中文翻译：http://www.cppblog.com/vici/archive/2011/09/05/155103.html {{Wayback|url=http://www.cppblog.com/vici/archive/2011/09/05/155103.html |date=20200928174758 }}

== 参考文献 ==

{{reflist}}
* 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 {{Wayback|url=http://blog.csdn.net/xianglunxi/article/details/9310105 |date=20191130185901 }}
{{planetmath|urlid=principleofinclusionexclusion|title=principle of inclusion-exclusion}}

[[Category:组合计数]]
[[Category:概率论]]
[[Category:包含证明的条目]]
[[Category:数学原理]]