当前课程知识点:组合数学 > 容斥原理和鸽巢原理 > 且容且斥 > 容斥原理
同学们这周我们将会介绍
两个基本的计数法则
一个被称为是容斥原理
另外一个被称为是鸽巢原理
那么我们先介绍容斥原理
要说起容斥原理
首先我们要从最最
基本的加法法则开始
大家还记得吧
我们如果想要进行计数的时候
我们最基本的法则就是加法法则
而加法法则很简单
从集合的角度来看 无非就是
两个集合如果他们没有交集的话
那么它们的合起来的
个数就是A加上B
但是现实中没有那么想当然的事情
很多情况下A和B是有交集的
那么这种情况下我们该如何计数呢
这里就要用到容斥的思想
何为容何为斥呢
实际上它就包含着说
如果我想计数困难的时候
我是不是可以先把所有的
全部包括在内呢
那么包括进来的时候
肯定会有重复
比如说A交B它们中间的过程
我们说A算一遍
B又算了一遍
那么它们的中间的交集我就多算了
这时候我们该怎么办
容进来的有冗余
那我们就应该把冗余部分
再排斥出去
所以这就是运用了一种容斥的思想
那么又英文来说也是这两个字
容斥原理用英文就是
inclusion exclusion
principle
那么我们说到计数最重要的是什么
我要达到目的就是无重复 无屋漏
因此在利用容斥思想的时候
一定要想清楚我怎么
把它包含进来的
我又怎么把它排斥出去
最后要求每个元素我只数了一次
这就是容斥的思想
那么要想利用好容斥原理
我们先看一个例子
比如说1到20这一共有20个数字
那么这20个数字中
是2或者是3的倍数
这两个数字一共有多少个呢
大家一看
那我先去找2的倍数
再找3的倍数就可以了
确实如此
2的倍数我们数下来一共有10个
3的倍数我们数一下
一共有6个
如果我们用加法法则的话
直接就是10加上6
但是这里面我们发现有交集
我们会发现在2的倍数和3的倍数
它们中间有3个数字是重复的
因此如果一开始我们用容的思想
算出来一共是10加上6的话
现在我们应该把
它们相交的部分排斥出去
因此答案就是16减3等于13
就这样一道简单的例题就告诉我们
要进行容斥的时候
首先先把单个集合计算出来
然后再去减掉它的交集
那意味着容斥原理和集合有着
密切的关系
下面我们来复习一些有关
集合论里面的概念
比如说什么是补集
补集也就意味着说对于一个
集合A它在一个全集U中
那么在U中的元素如果它不在A中
就构成了A的补集
而同时对于两个元素集合进行
相交或者相并的补集
我们有狄摩根定律
也就是说A并上B的补集
等于A的补集交B的补集
而A交B的补集等于
A的补集并B的补集
这些呢我想大家直接去看
它的文氏图就很容易地得到答案
当然如果我们把它推广一下
刚才无非就是两个集合嘛
现在如果有n个集合呢
我们同样可以得到类似的概念
比如说A1并A2
一直并到An
它们的补集就等于A1的
补集交A2的补集
一直交到An的补集
同样我们把这个补和并换一下
变成A1交A2
一直交到An的补集
自然就等于它们补集的并了
我们可以通过数学归纳法
来进行证明
因为我们对于n个集合
完全可以把它化成
前面n减1项和后面一个最后一项
所以我们假设已经知道对于n来说
狄摩根定律的推广形式是正确的
我们直接在后面
如果再去多加一个An加1的集合呢
这时候我们就相应地可以把它看作
是两个集合进行狄摩根定律
我们知道两个集合的无非就是
把它们进行变换就可以得到了
因此我们可以把刚才的两个集合的
狄摩根定律扩展成为
n个集合的狄摩根定律
有了这样的思想呢
其实我们来深入地
分析一下容斥原理
对于两个集合我们看
A和B它们中间有一个交集
那A并B的它的个数实际上就应该
等于A的个数加上B的个数
再减去A交B的个数
这个从图像上很容易就可以得出来
那么我就问大家
如果三个集合呢
比如说这样三个集合
它们之间两两都有交集
三个集合还有共同的部分
那么请问它的个数该如何计算呢
也就是说A并B并C的
个数等于多少呢
我们同样还是用容斥的
思想来证明一下
对于数个数的时候
我们先用容的思想
把所有的元素根据它的
集合挨个挨个数一遍
那么对应的刚才
那样一个图形我们发现
如果我们来算A的个数加B的个数
加C的个数的话
在这样一张文氏图上
我们标记它的数到的次数
可以发现A加B的部分
我数了两次
同样A交B A交C
我都数了两次
而且更为严重的是
中间A交B交C的那部分
因为这个元素在所有的
集合中都存在
每个集合我都数了一遍
因此这时候我对它数了三遍
用容的思想我们发现有冗余了
那这个时候我们是不是
应该用排斥的思想
把相交的部分减掉
减谁呢
自然首先我们想到减A交B
减A交C
减B交C
这时候确实是减
会发现A交B的部分
我们每个元素给它减了一次
同样A交C B交C都减了一次
这时候它的个数变成的这个样子
大家会发现有什么问题
对
A交B的那个部分它因为被减了一次
所以仅仅属于A交B的
部分它现在变成了数了一次了
但是三个元素的集合
A交B交C的集合
因为每个交集我都把它扣掉了一次
因此它被扣了三次
这时候中间的一部分
被我排斥出去排斥的多了
那该怎么办
应该把它再容回来呀
所以这时候我们再把
它们的A交B交C的三个集合的
交集容回来 加进来
就得到了所有的元素
统统只被数了一遍
那么这样分析来看
A交B交C就应该等于
首先有容的思想
A的集合加B集合加C集合的
个数之和
减去两两相交集合的个数
然后再加上3个元素交集的部分
这就是对于三个元素
进行容斥的结果
同样四个集合我照样可以用
容斥的思想得到答案
那么大家发现有什么规律了没有呢
对应于我要求若干个集合
它们并的个数的话
通常会单独单独一个集合的个数和
减去两两相交的
再加上三三相交的
再减去四个四个相交的
那么总结来看
我们不仅做两个集合
三个集合 四个集合
我们可以对应于n个集合
A1并A2一直并到An
它的所有的个数和就是等于
所有单个单个集合个数
减去两两相交集合个数
再加上三三的
再减四四的
依次累加过去
当然我们知道有了补集的
概念和狄摩根的推广定律
我们可以用A的补
它就等于全集的个数减去A的个数
因此我如果在上面一个式子上
整个把它变成补集的话
它就等于A1的补交A2补
一直交到An的补集
它的个数就应该等于全集
个数减去上面的式子结果
现在我们得到了两个通项的表示
而这两个式子就被称为是容斥原理
在英语中它被称为是
inclusion exclusion
principle
缩写我们称它为IEP
-什么是组合数学
--什么是组合数学
--讨论题
-最精巧的排列——幻方
--幻方
-漫谈组合数学--最精巧的排列——幻方
-苦难的羊皮纸卷
--羊皮纸卷
-苦难的羊皮纸卷--作业
-你的手机密码安全吗
-漫谈组合数学--你的手机密码安全吗
-暴力枚举和抽象转换
--世界杯引出的问题
--世界杯引出的问题--练习
--一一对应
--七桥问题
--小结
--讨论题
-大家谈组合数学(1)
--采访武永卫老师
-第一周作业
--作业说明
--H
--U
--G
--作业讨论区说明
-第一周演示程序
--程序讨论区说明
--幻方生成器
--换方计数
--屏幕解锁方案数
--欧拉路计数
--共享程序
-加减乘除来计数
--计数的基本法则
-排列还是组合
--排列还是组合
--小乒乓球的组合之旅--排列还是组合
-各种各样的排列
--圆排列和项链排列
--圆排列和项链排列--习题
--多重排列
--多重排列--练习
-多样的组合
--可重组合
--不相邻组合
--小乒乓球的组合之旅--多样的组合
-钟声里的全排列
--钟声里的全排列
--钟声里的全排列
--字典序法
--SJT算法
-第二周作业
--H
--U
--G
--思考题
--公式测试
--作业讨论区说明
-第二周演示程序
--程序讨论区说明
--全排列生成
--组合生成器
--共享程序
-参考资料:Stirling估计式
-母函数是函数的母亲吗
--母函数的定义(1)--练习
--母函数的定义(2)--练习
-母函数的简单应用
--初识母函数--母函数的简单应用
-整数拆分
--整数拆分(1)
--整数拆分(2)
-Ferrers图像
--Ferrers图像--作业
-母函数与递推关系
--母函数能做什么
--偶数个5怎样算
--母函数小结
-大家谈组合数学(2)
-第三周作业
--H
--U
--G
--思考题
--作业讨论区说明
-第三周演示程序
--程序讨论区说明
--整数拆分
--汉诺塔
--共享程序说明
-Fibonacci数列
--线性常系数递推关系--Fibonacci数列
-Fibonacci数列的应用
--桌布魔术
--桌布魔术--练习
--艾略特波浪曲线
-线性常系数齐次递推关系
--定义
--特征多项式
--线性常系数递推关系--线性常系数齐次递推关系
-说“数”解题
-第四周作业
--H
--U
--G
--GT思考题
--作业讨论区说明
-第四周演示程序
--程序讨论区说明
--程序共享说明
-爆笑花絮
--爆笑花絮
-参考资料:K线分析中的Fibonacci 相关理论
-Catalan数
--计算机界的精灵
--神奇的序列--Catalan数
-指数型母函数
--指数型母函数
--神奇的序列--指数型母函数
-错排
--错排1
--错排2
--神奇的序列--错排
-Stirling数
--神奇的序列--Stirling数
-母函数小结
--母函数小结
-大家谈组合数学(3)
-第五周作业
--H
--U
--G
--思考题
--作业讨论区说明
-第五周演示程序
--讨论区说明
--Catalan数
--程序共享
-且容且斥
--容斥原理
--容斥原理的证明
--容斥原理和鸽巢原理--且容且斥
-容斥原理的精妙
-回忆过去,容斥新解
--容斥原理和鸽巢原理--回忆过去,容斥新解
-鸽子抢巢
--鸽巢原理
--鸽巢原理--练习
--鸽巢原理的应用(1)--练习
-看得见摸得着的鸽巢
--韩信点兵
--中国剩余定理
--容斥原理和鸽巢原理--看得见摸得着的鸽巢
-6人行和Ramsey数
--6人行
--Ramsey数
--小结
-第六周作业
--H
--U
--G
--GT
--作业讨论区说明
-第六周演示程序
--讨论区说明
--程序共享说明
-可以转的世界
--可以转的世界
--可以转的世界--练习
--伽罗华与群
--群的定义
--群的定义--练习
--群的一些概念
-置换群
--置换群
--群--置换群
--共轭类
--对换
--对换--练习
--置换群的应用
-Burnside引理
--着色问题的等价类
--Burnside引理--作业
-闲话群
-第七周作业
--H
--U
--G
--作业讨论区说明
-Burnside引理的困境
-从Burnside到Polya
--Polya定理
-立方体旋转
--立方体旋转(1)
--立方体旋转(2)
--立方体旋转--作业
--立方体旋转(3)
--立方体旋转--作业
--立方体旋转(4)
-母函数型Polya定理
--Polya定理--母函数型Polya定理
-图的计数
--图的计数
-总结
--本章小结
-第八周作业
--H
--U
--G
--GT
--作业讨论区说明
-大家谈组合数学(4)
--采访黄连生老师
-组合之美
--组合之美之计数
-组合之美之线性常系数递推关系
-组合之美之多样的序列
-组合之美之鸽巢原理
-组合之美之转动群与染色
-采访邹欣
--采访邹欣1
--采访邹欣2
-知识点串串烧
--知识点串串烧
-期末测验--期末测验