容斥原理及其证明
容斥原理是计数方法中一个重要的原理，在算法竞赛中也经常考到（大概是因为需要大量计算吧。。。。）
【容斥原理及其证明】容斥原理有个经典题目：一个班每个人都有自己喜欢的科目，有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
推荐阅读
- JS中的各种宽高度定义及其应用
- 做一件事情的基本原理是什么（）
- 【读书笔记】贝叶斯原理
- SG平滑轨迹算法的原理和实现
- Spark|Spark 数据倾斜及其解决方案
- “写作宝典”《金字塔原理》之读书笔记
- LSTM网络层详解及其应用实例
- Spring|Spring 框架之 AOP 原理剖析已经出炉！！！预定的童鞋可以识别下发二维码去看了
- Spring|Spring Boot 自动配置的原理、核心注解以及利用自动配置实现了自定义 Starter 组件
- Vue源码分析—响应式原理(二)