当前课程知识点:组合数学 >  容斥原理和鸽巢原理 >  容斥原理的精妙 >  容斥原理的应用(1)

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

容斥原理的应用(1)在线视频

容斥原理的应用(1)

下一节:容斥原理的应用(2)

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

容斥原理的应用(1)课程教案、知识点、字幕

刚才我们介绍了容斥原理的

一些基本的概念

那么我们从简单的例子出发来看看

容斥原理怎么被应用来计数的

先看一个比较简单的计数问题

它说大从1到500

所有的这些整数中有

多少个数字能够被3或者5整除

这个问题一看被3整除的有一批

而被5整除的有一批

或代表的就是A并B

那直接就可以套用容斥原理呀

但关键问题在于我们怎么去

给各个集合进行计数

假如说A集合定为是

能被3整除的集合

而B是能被5整除的

在1到100之间

那这时候我们来计算一下

A的个数实际上就是500除以3

进行下取整

而B的个数相应的就是500除以5

进行下取整

而另外在容斥原理中

我们需要用到交集的个数

也就是A交B的个数

自然A交B表示既能被3整除

又能被5整除

那意味着就能够被15整除

所以这时候A交B的个数

就应该等于500除以3乘以5

我们分别计算它的个数以后

来套用到容斥原理

A并B的个数就等于

A的个数加上B的个数

减去A交B的个数

经过计算刚好是233

但是这道题目大家觉得相当简单

但是相应的大家一定要注意

这里3和5之间是没有公因子的

如果是6和15呢

所以大家在做题目的时候

一定要留意相应的陷井

我们再举一道题

这时候我们是用字符来表示的

比如说ABCDEF

这六个字母中

我要进行排列

但是我要求不允许出现ACE

而且不允许出现DF

也就是说在它的全排列中

ACE不能相邻出现

DF也不能相邻按顺序出现

这时候我们就会想

全排列的个数总个我很会算

就是6的阶乘

这里面它要去掉谁呢

我是不要去掉某些集合

那么我就可以设A集合表示是

在这个全排列中出现了ACE

B集合表示在这个全排列中出现了DF

我们要求什么

我们要求的是说不允许出现他们

那我知道用容斥原理

既然我可以计算出来AB

以及A交B的个数的话

我就可以计算出来想要求的

不允许出现的

那么不允许出现

也就是说A不允许出现

而且B不允许出现

我需要什么样的数字来计算

首先根据容斥原理

它就应该等于全集的

个数减去单个单个集合的个数

再加上两两相交的个数

单个集合

A表示什么

A表示说六个字母的

全排列中出现了ACE

ACE出现它就成为了一个集体

而剩下来元素可以随便放置

那这时候ACE已经合并成一个了

剩下的所有元素加在一起

只有4个了

因此A的集合个数就是4阶乘

相应B是D和F已经合并在一起

六个元素已经变成了5个元素

因此B的个数是5阶乘

对应于A加B是什么

A加B的个数是既出现ACE

又出现DF

那既然这五个元素已经

合并成了两个元素

因此总共就剩下了3个元素

那我们把这些集合的个数代进来

全集个数6阶乘减去

4阶乘减去5阶乘

再加上3阶乘

答案就是582

所以通过这两个例子

我们就可以看到

只要我们能够分析出来对应的子集

算得出来它们的交集

我们就可以很熟练的应用容斥原理

下面再看一道题

仍然是排列

ABCD四个字符

这时候它要组成一个

可以重复的n位字符串

我问你

这样的n位字符串如果

要求ABC都至少出现一次

请问有多少种不同的字符串数目呢

这时候我们就会想

至少出现一次

并不好求

而好求什么

不出现相应好求多了

比如说不出现

A不出现

那就意味着我只剩3个字母了

3个字母它要组成一个n位的

可重排列的话

很容易呀

无非就是3的n次方

每一位都有3个选择

一共有n位嘛

那所以我们就会看到

我们要设计一个什么样的集合呢

我们应该反其道而行之

我们要设计的是

A不出现的集合设为A

B不出现的集合设为B

C不出现的集合设为C

这时候我们去分别求A的个数

A的个数刚才已经分析到了

A表示的是它A字母不出现

那意味着只剩下3个字母

进行可重复的排列

就是3的n次方 同样B的个数

C的个数也和它是相等的

那么对应于A交B是什么意思

A交B表示的是字母A和

字母B都不出现

那意味着还剩下

4个字母中的两个了

因此就是2的阶乘

那么3个呢

A交B交C意味着什么

A不出现

B不出现

C也不出现

这时候只剩下了一个字母D

它要构成n位串

所以只能D重复n遍

只有这一个结果

这时候我们来看

我们要求的是什么

我们要求的集合就是

A补交B 交C补

也就是说在这里面

A的意思是说A不出现

那么它的A的补表示它必然出现

所以我们要求ABC都至少出现一次

的数目就应该等于A补交B补交C补

它的个数等于全集的个数

也就是4的n次方

减去单个单个集合3的n次方

一共有几个呢

一共有3个3的n次方

再加上两两相交的

两两相交是2的n次方

一共有3种这样的交集

所以就是3乘以2的n次方

然后再减掉A交B交C

A交B交C刚才计算出来就得1

所以它的答案就应该是

4的n次方减去3乘以3的n次方

再加上3乘以2的n次方减1

这就是这道题的答案

组合数学课程列表:

漫谈组合数学

-什么是组合数学

--什么是组合数学

--讨论题

-最精巧的排列——幻方

--幻方

-漫谈组合数学--最精巧的排列——幻方

-苦难的羊皮纸卷

--羊皮纸卷

-苦难的羊皮纸卷--作业

-你的手机密码安全吗

--你的手机密码安全吗

-漫谈组合数学--你的手机密码安全吗

-暴力枚举和抽象转换

--世界杯引出的问题

--世界杯引出的问题--练习

--一一对应

--七桥问题

--小结

--讨论题

-大家谈组合数学(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

-知识点串串烧

--知识点串串烧

期末测验

-期末测验--期末测验

容斥原理的应用(1)笔记与讨论

也许你还感兴趣的课程:

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