容斥原理
容斥原理(inclusion-exclusion principle)又称排容原理,在组合数学里,其说明若, ..., 为有限集,则
描述
两个集合的容斥原理
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个集合的容斥原理
要计算几个集合并集的大小,我们要先将所有单个集合的大小计算出来,然后减去所有两个集合相交的部分,再加回所有三个集合相交的部分,再减去所有四个集合相交的部分,依此类推,一直计算到所有集合相交的部分。
最终得到公式:
又可写成
或
概率论中的容斥原理
在概率论中,对于概率空间 中的事件A1,……,An,当n = 2时容斥原理的公式为:
当n = 3时,公式为:
一般地:
也可以写成:
对于一般的测度空间(S,Σ,μ)和有限测度的可测子集A1,……,An,上面的恒等式也成立,如果把概率测度 换为测度μ。
特殊情况
如果在容斥原理的概率形式中,交集AI的概率只与I中元素的个数有关,也就是说,对于{1, ..., n}中的每一个k,都存在一个ak,使得:
- ,对于每一个
则以上的公式可以简化为:
这是由于二项式系数 的组合解释。
类似地,如果对有限集合A1,……,An的并集的元素个数感兴趣,且对于{1, ..., n}中的每一个k,交集
的元素个数都相同,例如ak = |AI|,与{1, ..., n}的k元素子集I无关,则:
在一般的测度空间(S,Σ,μ)和有限测度的可测子集A1,……,An的情况中,也可以进行类似的简化。
容斥原理的证明
欲证明容斥原理,我们首先要验证以下的关于指示函数的等式:
至少有两种方法来证明这个等式:
第一种方法 我们只需证明对于A1,……,An的并集中的每一个x,等式都成立。假设x正好属于m个集合(1 ≤ m ≤ n),不妨设它们为A1,……,Am。则x处的等式化为:
m元素集合中的k元素子集的个数,是二项式系数 的组合解释。由于 ,我们有:
把所有的项移到等式的左端,我们便得到(1 – 1)m的二项式展开式,因此可以看出,(*)对x成立。
第二种方法 设A表示集合A1,……,An的并集。于是:
这是因为对于不在A内的x,两边都等于零,而如果x属于其中一个集合,例如Am,则对应的第m个因子为零。把右端的乘积展开来,便可得到等式(*)。
归纳法证明
设:S1= n (A1)+n (A2)+n (A3) +…...+n (An)
S2= n(A1∩A2)+ n(A1∩A3) …...+ n(A1∩An)+ n(A2∩A3)+ …...+n(An-1∩An)
S3= n(A1∩A2∩A3)+ ……+ n(An-2∩An-1∩An)……
Sn =n(A1∩A2∩A3∩……∩An)
求证:A=n(A1∪A2∪A3∪A4……∪An)= S1-S2+ S3+……+(-1)n-1Sn
证明:当n=2时,A=n(A1∪A2)=n(A1)+n(A2) -n(A1∩ A2)= S1-S2
假设:当n=k(k>=2)时,A=n (A1∪A2∪A3∪A4……∪Ak)= S1-S2+ S3+……+(-1)k-1Sk 等式成立。
当n=k+1时,
A= n( (A1∪A2∪A3∪A4……∪Ak) ∪Ak+1)
= n (A1∪A2∪A3∪A4……∪Ak)+n(Ak+1)-n((A1∪A2∪A3∪A4……∪Ak) ∩Ak+1)
= n (A1∪A2∪A3∪A4……∪Ak) +n(Ak+1)-n((A1∩Ak+1) ∪(A2∩Ak+1) ∪(A3∩Ak+1) ∪ …∪(Ak∩Ak+1))
∵ 当n=k时,等式成立
∴A= n (A1∪A2∪A3∪A4……∪Ak) +n(Ak+1)-(n (A1∩Ak+1)+ n (A2∩Ak+1)+ ……+n(Ak∩Ak+1)-n(A1∩A2∩Ak+1)-n(A1A3∩Ak+1) -……- n(Ak-1∩Ak∩Ak+1)+ ……+(-1)k.n(A1∩A2∩A3∩∪……∩Ak+1)
= S1-S2+ S3+……+(-1)k-1Sk+n(Ak+1)-(n (A1∩Ak+1)+ n (A2∩Ak+1)+ ……+n(Ak∩Ak+1)-n(A1∩A2∩Ak+1)-n(A1∩A3∩Ak+1) -……- n(Ak-1∩Ak∩Ak+1)+ ……+(-1)k.n(A1∩A2∩A3∩∪……∩Ak+1)
= S1-S2+ S3+……+(-1)kSk+1
综上所述,当n>=2时,n (A1∪A2∪A3∪A4……∪An)
= n (A1)+n (A2)+n (A3) ……+ n (An)-n(A1∩A2)- n(A1∩A3) ……- n(A1∩An)- n(A2∩A3)- ……-n(An-1∩An)+n(A1∩A2∩A3)+ n(A1∩A2∩A3)+ ……+ n(An-2∩An-1∩An)- ……+……+(-1)n-1.n(A1∩A2∩A3∩……∩An)[1]
其它形式
有时容斥原理用以下的形式来表述:如果
那么:
在这种形式中可以看出,它是A的所有子集的偏序集合的指标代数的莫比乌斯反演公式。
应用
在许多情况下,容斥原理都可以给出精确的公式(特别是用埃拉托斯特尼筛法计算素数的个数时),但是用处不大,这是因为它里面含有的项太多。即使每一个单独的项都可以准确地估计,误差累积起来仍然意味着容斥原理不能直接应用。在数论中,这个困难由维戈·布朗解决。开始时进展很慢,但他的想法逐渐被其他数学家所应用,于是便产生了许多各种各样的筛法。这些方法是尝试找出被“筛选”的集合的上界,而不是一个确切的公式。
错排
容斥原理的一个著名的应用,是计算一个有限集合的所有乱序排列的数目。一个集合A的错排,是从A到A的没有不动点的双射。通过容斥原理,我们可以证明,如果A含有n个元素,则乱序排列的数目为[n! / e],其中[x]表示最接近x的整数。
这也称为n的子阶乘,记为!n。可以推出,如果所有的双射都有相同的概率,则当n增大时,一个随机双射是错排的概率迅速趋近于1/e。
交集的计算
容斥原理与德·摩根定理结合起来,也可以用于计算集合的交集中元素的数目。设 表示Ak关于全集A的补集,使得对于每一个k,都有 。于是,我们有:
这样便把计算交集的问题化为计算并集的问题。
参见
拓展阅读
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 (页面存档备份,存于互联网档案馆)
参考文献
- ^ 容斥原理的猜测与证明_ty1108_新浪博客. blog.sina.com.cn. [2018-02-06]. (原始内容存档于2019-08-22).
- 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 (页面存档备份,存于互联网档案馆)
本条目含有来自PlanetMath《principle of inclusion-exclusion》的内容,版权遵守知识共享协议:署名-相同方式共享协议。