容斥原理及其证明

容斥原理是计数方法中一个重要的原理,在算法竞赛中也经常考到(大概是因为需要大量计算吧。。。。)
【容斥原理及其证明】容斥原理有个经典题目:一个班每个人都有自己喜欢的科目,有20人喜欢数学,10人喜欢语文,11人喜欢英语,其中3人同时喜欢数学语文,3人同时喜欢语文英语,4人同时喜欢数学英语,2人都喜欢,问全班有多少人?
这个肯定不可以20+10+11的简单计算,因为有人喜欢多个科目,会重复计算,在之前基础上-3-3-4,这时候会发现全部都喜欢的被多减了,再+2。得到班级人数=20+10+11-3-3-4+2
设喜欢数学的为A,喜欢语文的为B,英语为C,那么可以得到容斥原理及其证明
文章图片



会发现奇数个集合前面是+,偶数个是-。
推广到一般情况也符合这个规律,可以把公式表示为:容斥原理及其证明
文章图片
(为表示方便,B为全部Ai的并集,公式图片来自网络)


证明如下:
设i为m个集合中的元素
在考虑集合个数为1的时候,i被加了C(1,m)次
在考虑集合个数为2的时候,i被减了C(2,m)次

在考虑集合个数为3的时候,i被加了C(3,m)次

...
i总共被加了C(1,m)-C(2,m)+C(3,m)-C(4,m)+...C(m,m)次
由二项式定理得:
C(1,m)-C(2,m)+C(3,m)-C(4,m)+...C(m,m)=C(0,m)-(1-1)^m=1
所以i被加了1次,所以算法正确
转载于:https://www.cnblogs.com/Chenyao2333/p/3691883.html

    推荐阅读