排容原理

容斥原理又称排容原理，在组合数学里，其说明若, ...,  为有限集，则
 
其中表示的基数。例如在两个集的情况时，我们可以通过将和相加，再减去其交集的基数，而得到其并集的基数。

两个集合的容斥原理 

n(A∪B)=n(A)+n(B) -n(A∩B)

三个集合的容斥原理

|A∪B∪C|=|A|+|B|+|C|-|A∩B|-|A∩C|-|B∩C|+|A∩B∩C|

n个集合的容斥原理

      要计算几个集合并集的大小，我们要先将所有单个集合的大小计算出来，然后减去所有两个集合相交的部分，再加回所有三个集合相交的部分，再减去所有四个集合相交的部分，依此类推，一直计算到所有集合相交的部分。
最终得到公式：
又可写成
或

归纳法证明

设：S₁= n (A₁)+n (A₂)+n (A₃) +…...+n (Aₙ)
S₂= n(A₁∩A₂)+ n(A₁∩A₃) …...+ n(A₁∩Aₙ)+ n(A₂∩A₃)+ …...+n(Aₙ₋₁∩An)
S₃= n(A₁∩A₂∩A₃)+ ……+ n(Aₙ₋₂∩Aₙ₋₁∩An)……
Sₙ =n(A₁∩A₂∩A₃∩……∩Aₙ)
求证：A=n(A₁∪A₂∪A₃∪A₄……∪Aₙ)= S₁-S₂+ S₃+……+(-1)ⁿ⁻¹Sₙ
证明：当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ₖ)= S₁-S₂+ S₃+……+(-1)ᵏ⁻¹Sₖ 等式成立。
当n=k+1时，
A= n( (A₁∪A₂∪A₃∪A₄……∪Aₖ) ∪Aₖ₊₁)
= n (A₁∪A₂∪A₃∪A₄……∪Aₖ)+n(Aₖ₊₁)-n((A₁∪A₂∪A₃∪A₄……∪Aₖ) ∩Aₖ₊₁)
= n (A₁∪A₂∪A₃∪A₄……∪Aₖ) +n(Aₖ₊₁)-n((A₁∩Aₖ₊₁) ∪(A₂∩Aₖ₊₁) ∪(A₃∩Aₖ₊₁) ∪ …∪(Aₖ∩Aₖ₊₁))
∵ 当n=k时，等式成立
∴A= n (A₁∪A₂∪A₃∪A₄……∪Aₖ) +n(Aₖ₊₁)-(n (A₁∩Aₖ₊₁)+ n (A₂∩Aₖ₊₁)+ ……+n(Aₖ∩Aₖ₊₁)-n(A₁∩A₂∩Aₖ₊₁)-n(A₁A₃∩Aₖ₊₁) -……- n(Aₖ₋₁∩Aₖ∩Aₖ₊₁)+ ……+(-1)ᵏ.n(A₁∩A₂∩A₃∩∪……∩Aₖ₊₁)
   = S₁-S₂+ S₃+……+(-1)ᵏ⁻¹Sₖ+n(Aₖ₊₁)-(n (A₁∩Aₖ₊₁)+ n (A₂∩Aₖ₊₁)+ ……+n(Aₖ∩Aₖ₊₁)-n(A₁∩A₂∩Aₖ₊₁)-n(A₁∩A₃∩Aₖ₊₁) -……- n(Aₖ₋₁∩Aₖ∩Aₖ₊₁)+ ……+(-1)ᵏ.n(A₁∩A₂∩A₃∩∪……∩Aₖ₊₁)
    = S₁-S₂+ S₃+……+(-1)ᵏSₖ₊₁
综上所述，当n>=2时,n (A₁∪A₂∪A₃∪A₄……∪Aₙ)
= n (A₁)+n (A₂)+n (A₃) ……+ n (Aₙ)-n(A₁∩A₂)- n(A₁∩A₃) ……- n(A₁∩Aₙ)- n(A₂∩A₃)- ……-n(Aₙ₋₁∩An)+n(A₁∩A₂∩A₃)+ n(A₁∩A₂∩A₃)+ ……+ n(Aₙ₋₂∩Aₙ₋₁∩An)- ……+……+(-1)ⁿ⁻¹.n(A₁∩A₂∩A₃∩……∩Aₙ)

应用

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

错排

容斥原理的一个著名的应用，是计算一个有限集合的所有乱序排列的数目。一个集合A的错排，是从A到A的没有不动点的双射。通过容斥原理，我们可以证明，如果A含有n个元素，则乱序排列的数目为[n! / e]，其中[x]表示最接近x的整数。
这也称为n的子阶乘，记为!n。可以推出，如果所有的双射都有相同的概率，则当n增大时，一个随机双射是错排的概率迅速趋近于1/e。

拓展阅读

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