当前课程知识点:组合数学 >  容斥原理和鸽巢原理 >  且容且斥 >  容斥原理

返回《组合数学》慕课在线视频课程列表

容斥原理在线视频

容斥原理

下一节:容斥原理的证明

返回《组合数学》慕课在线视频列表

容斥原理课程教案、知识点、字幕

同学们这周我们将会介绍

两个基本的计数法则

一个被称为是容斥原理

另外一个被称为是鸽巢原理

那么我们先介绍容斥原理

要说起容斥原理

首先我们要从最最

基本的加法法则开始

大家还记得吧

我们如果想要进行计数的时候

我们最基本的法则就是加法法则

而加法法则很简单

从集合的角度来看 无非就是

两个集合如果他们没有交集的话

那么它们的合起来的

个数就是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算法

--程序支持与Stirling公式

-第二周作业

--H

--U

--G

--思考题

--公式测试

--作业讨论区说明

-第二周演示程序

--程序讨论区说明

--排列数和组合数的计算

--全排列生成

--组合生成器

--共享程序

-参考资料:Stirling估计式

--Stirling估计式

初识母函数

-母函数是函数的母亲吗

--母函数的定义(1)

--母函数的定义(1)--练习

--母函数的定义(2)

--母函数的定义(2)--练习

-母函数的简单应用

--母函数的简单应用(1)

--母函数的简单应用(2)

--初识母函数--母函数的简单应用

-整数拆分

--整数拆分(1)

--整数拆分(2)

-Ferrers图像

--Ferrers图像

--Ferrers图像--作业

-母函数与递推关系

--母函数能做什么

--Hanoi问题(1)

--Hanoi问题(2)

--偶数个5怎样算

--偶数个5怎样算(2)

--母函数小结

-大家谈组合数学(2)

--科研,找工作与组合数学

-第三周作业

--H

--U

--G

--思考题

--作业讨论区说明

-第三周演示程序

--程序讨论区说明

--整数拆分

--汉诺塔

--共享程序说明

线性常系数递推关系

-Fibonacci数列

--Fibonacci兔子

--Fibonacci恒等式

--线性常系数递推关系--Fibonacci数列

-Fibonacci数列的应用

--桌布魔术

--桌布魔术--练习

--Fibonacci的直接表达式

--Fibonacci优选法

--艾略特波浪曲线

-线性常系数齐次递推关系

--定义

--特征多项式

--母函数与特征多项式

--根据特征多项式求解递推关系通解(1)

--根据特征多项式求解递推关系通解(2)

--线性常系数递推关系--线性常系数齐次递推关系

-说“数”解题

--说“数”解题(1)

--说“数”解题(2)

-第四周作业

--H

--U

--G

--GT思考题

--作业讨论区说明

-第四周演示程序

--程序讨论区说明

--Fibonacci优选法

--Fibonacci数值计算

--程序共享说明

-爆笑花絮

--爆笑花絮

-参考资料:K线分析中的Fibonacci 相关理论

--Fibonacci retracement资料

神奇的序列

-Catalan数

--计算机界的精灵

--Catalan数的直接表达式

--Catalan数的各种实例

--神奇的序列--Catalan数

-指数型母函数

--指数型母函数

--指数型母函数的应用

--神奇的序列--指数型母函数

-错排

--错排1

--错排2

--神奇的序列--错排

-Stirling数

--第一类Stirling数

--神奇的序列--Stirling数

--第二类Stirling数

-母函数小结

--母函数小结

-大家谈组合数学(3)

--采访郭家宝(BYVoid)

-第五周作业

--H

--U

--G

--思考题

--作业讨论区说明

-第五周演示程序

--讨论区说明

--Catalan数

--第二类Stirling数

--程序共享

容斥原理和鸽巢原理

-且容且斥

--容斥原理

--容斥原理的证明

--容斥原理和鸽巢原理--且容且斥

-容斥原理的精妙

--容斥原理的应用(1)

--容斥原理的应用(2)

--容斥原理的应用(3)

-回忆过去,容斥新解

--容斥原理的应用(4)

--容斥原理的应用(5)

--容斥原理的应用(6)

--容斥原理和鸽巢原理--回忆过去,容斥新解

-鸽子抢巢

--鸽巢原理

--鸽巢原理--练习

--鸽巢原理的应用(1)

--鸽巢原理的应用(1)--练习

-看得见摸得着的鸽巢

--鸽巢原理的应用(2)

--韩信点兵

--中国剩余定理

--容斥原理和鸽巢原理--看得见摸得着的鸽巢

-6人行和Ramsey数

--6人行

--Ramsey数

--小结

-第六周作业

--H

--U

--G

--GT

--作业讨论区说明

-第六周演示程序

--讨论区说明

--Find a multiple

--程序共享说明

-可以转的世界

--可以转的世界

--可以转的世界--练习

--伽罗华与群

--群的定义

--群的定义--练习

--群的一些概念

-置换群

--置换群

--群--置换群

--共轭类

--对换

--对换--练习

--置换群的应用

-Burnside引理

--着色问题的等价类

--Burnside引理--作业

--Burnside引理

--Burnside引理的应用

-闲话群

--无处不在的群(1)

--无处不在的群(2)

-第七周作业

--H

--U

--G

--作业讨论区说明

Polya定理

-Burnside引理的困境

--Burnside引理的困境(1)

--Burnside引理的困境(2)

-从Burnside到Polya

--Polya定理

--Polya定理的应用(1)

--Polya定理的应用(2)

-立方体旋转

--立方体旋转(1)

--立方体旋转(2)

--立方体旋转--作业

--立方体旋转(3)

--立方体旋转--作业

--立方体旋转(4)

-母函数型Polya定理

--母函数型Polya定理(1)

--母函数型Polya定理(2)

--母函数型Polya定理(3)

--母函数型Polya定理(4)

--Polya定理--母函数型Polya定理

-图的计数

--图的计数

-总结

--本章小结

-第八周作业

--H

--U

--G

--GT

--作业讨论区说明

-大家谈组合数学(4)

--采访黄连生老师

组合之美

-组合之美

--组合之美之计数

--组合之美之排列组合

--组合之美之多样组合和全排列

-组合之美之线性常系数递推关系

--组合之美之线性常系数递推关系

-组合之美之多样的序列

--组合之美之多样的序列

-组合之美之鸽巢原理

--组合之美之鸽巢原理

-组合之美之转动群与染色

--组合之美之转动群与染色

-采访邹欣

--采访邹欣1

--采访邹欣2

-知识点串串烧

--知识点串串烧

期末测验

-期末测验--期末测验

容斥原理笔记与讨论

也许你还感兴趣的课程:

© 柠檬大学-慕课导航 课程版权归原始院校所有,
本网站仅通过互联网进行慕课课程索引,不提供在线课程学习和视频,请同学们点击报名到课程提供网站进行学习。