容斥原理

容斥原理又称排容原理，在组合数学里，其说明若${\displaystyle A_1}$₁，……，，当 = 2时容斥原理的公式为：

当 = 3时，公式为：

一般地：

也可以写成：

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

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

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

这是由于二项式系数${\displaystyle (\genfrac{}{}{0ex}{}{n}{k})}$₁，……，的并集的元素个数感兴趣，且对于{1, ..., }中的每一个，交集

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

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

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

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

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

元素集合中的元素子集的个数，是二项式系数${\displaystyle (\genfrac{}{}{0ex}{}{m}{k})}$的二项式展开式，因此可以看出，(*)对成立。

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

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

设：S₁= n (A₁)+n (A₂)+n (A₃) +…...+n (A_n)

S₂= n(A₁∩A₂)+ n(A₁∩A₃) …...+ n(A₁∩A_n)+ n(A₂∩A₃)+ …...+n(A_n-1∩An)

S₃= n(A₁∩A₂∩A₃)+ ……+ n(A_n-2∩A_n-1∩An)_……

S_n =n(A₁∩A₂∩A₃∩……∩A_n)

求证：A=n(A₁∪A₂∪A₃∪A₄……∪A_n)= S₁-S₂+ S₃+……+(-1)n-1S_n

证明：当n=2时，A=n(A₁∪A₂)=n(A₁)+n(A₂) -n(A₁∩ A₂)= S₁-S₂

假设：当n=k(k>=2)时，A=n (A₁∪A₂∪A₃∪A₄……∪A_k)= S₁-S₂+ S₃+……+(-1)k-1S_k 等式成立。

当n=k+1时，

A= n( (A₁∪A₂∪A₃∪A₄……∪A_k) ∪A_k+1)

= n (A₁∪A₂∪A₃∪A₄……∪A_k)+n(A_k+1)-n((A₁∪A₂∪A₃∪A₄……∪A_k) ∩A_k+1)

= n (A₁∪A₂∪A₃∪A₄……∪A_k) +n(A_k+1)-n((A₁∩A_k+1) ∪(A₂∩A_k+1) ∪(A₃∩A_k+1) ∪ …∪(A_k∩A_k+1))

∵ 当n=k时，等式成立

∴A= n (A₁∪A₂∪A₃∪A₄……∪A_k) +n(A_k+1)-(n (A₁∩A_k+1)+ n (A₂∩A_k+1)+ ……+n(A_k∩A_k+1)-n(A₁∩A₂∩A_k+1)-n(A₁A₃∩A_k+1) -……- n(A_k-1∩A_k∩A_k+1)+ ……+(-1)k.n(A₁∩A₂∩A₃∩∪……∩A_k+1)

   = S₁-S₂+ S₃+……+(-1)k-1S_k+n(A_k+1)-(n (A₁∩A_k+1)+ n (A₂∩A_k+1)+ ……+n(A_k∩A_k+1)-n(A₁∩A₂∩A_k+1)-n(A₁∩A₃∩A_k+1) -……- n(A_k-1∩A_k∩A_k+1)+ ……+(-1)k.n(A₁∩A₂∩A₃∩∪……∩A_k+1)

    = S₁-S₂+ S₃+……+(-1)kS_k+1

综上所述，当n>=2时,n (A₁∪A₂∪A₃∪A₄……∪A_n)

= n (A₁)+n (A₂)+n (A₃) ……+ n (A_n)-n(A₁∩A₂)- n(A₁∩A₃) ……- n(A₁∩A_n)- n(A₂∩A₃)- ……-n(A_n-1∩An)+n(A₁∩A₂∩A₃)+ n(A₁∩A₂∩A₃)+ ……+ n(A_n-2∩A_n-1∩An)- ……+……+(-1)n-1.n(A₁∩A₂∩A₃∩……∩A_n)

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

那么：

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

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

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

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

容斥原理与德·摩根定理结合起来，也可以用于计算集合的交集中元素的数目。设${\displaystyle {\stackrel{¯<!--\; ¯\; -->}{A}}_k}$关于全集的补集，使得对于每一个，都有${\displaystyle A_k\subseteq <!--\; \subseteq \; -->A}$]

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

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