排容原理

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

\begin{align}
\left|\bigcup_{i=1}^n A_i\right| = {} & \sum_{i=1}^n |A_i| - \sum_{1 \le i

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

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

最终得到公式：

\begin{align}
\left|\bigcup_{i=1}^n A_i\right| = {} & \sum_{i=1}^n |A_i| - \sum_{1 \le i

又可写成

\left|\bigcup_{i=1}^n A_i\right| = \sum_{k = 1}^n (-1)^{k+1} \left( \sum_{1 \leq i_1

或

\left|\bigcup_{i=1}^n A_i\right| = \sum_{\emptyset\neq J\subseteq\{1,2,\ldots,n\}}(-1)^g(S)

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

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

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

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

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

:
\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

评论 (0)