排容原理

排容原理（inclusion-exclusion principle）又称-{zh-hans:容斥原理;zh-hant:容斥原理;zh-cn:排容原理;zh-sg:排容原理}-、取捨原理，在組合數學裏，其說明若 為有限集，則


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

 描述 

 两个集合的容斥原理  

 三个集合的容斥原理 

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

最终得到公式：

又可写成

或

 概率论中的容斥原理 

在概率论中，对于概率空间中的事件 ，当  时容斥原理的公式为：

当  时，公式为：

一般地：

也可以写成：

对于一般的测度空间  和有限测度的可测子集 ，上面的恒等式也成立，如果把概率测度  换为测度 。

 特殊情况 

如果在容斥原理的概率形式中，交集  的概率只与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 

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