当前课程知识点:组合数学 >  容斥原理和鸽巢原理 >  回忆过去,容斥新解 >  容斥原理的应用(6)

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

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

容斥原理的应用(6)

下一节:鸽巢原理

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

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

我们刚才用容斥原理解决了

一些我们以前遇到的问题

下面我们仍然来解决一个

我们曾经介绍过的问题

也就是放球问题

大家都知道在放球问题中

我们引入了一个特殊的数

也就是第二类斯特林数

第二类斯特林数意味着什么呢

我将n个有区别的球

放入到m个无区别的盒子里

而且要求无一空盒的方案

如果大家认真完成了

前面的作业的话

就会知道

这就是我们对应的

放球模型中的一种

那么原来呢

我们是通过递推关系母函数方法

求解了第二类斯特林数的

一个展开式

它的式子看似非常复杂

那么我们是不是有可能用容斥原理

来给大家一个

简便直观的证明方法呢

我们回头想对应于

第二类斯特林数的放球模型

它的关键点在哪里

我们说有区别的球无区别的盒子

无区别的盒子

我完全可以把它打上标号

变成有区别的盒子

但是问题在于要求无一空盒

无一空盒这个概念好象

不太容易解决

我们是不是可以反过来想呢

那么它如果变成用容斥的思想

我们就先想

要求无一空盒

那就意味着这个盒子不能为空

那我是不是可以把这个变成

某一个盒子为空作为一个集合呢

那我要求无一空盒

意味着第一个盒子不为空

而且第二个盒子不为空

如果我假设用Ai表示

第n个盒子为空的话

那么斯特林数的无一空盒的

要求是不是就可以变成

A1的补集交A2的补集

一直累加下去

所以这时候我们有一个思想

对应于想要求无一空盒的话

我们反过来思考

另外无区别刚才说到了

我们完全可以用标号的方案来处理

有了这样的思想以后

我们把问题转化为我们先去考虑

n个有标志的球

放入n个有标志的盒子里

而且无一空盒的的方案数

对应于要去处理无一空盒

我们设计了Ai这样一个集合

表示第i个盒子为空

那这时候我们要求的就

相当于是A1的补集交A2的补集

一直交到Am的补集的个数

利用容斥原理我们需要求解什么呢

首先全集个数是多少

所有的没有任何约束的情况下

如果我们说n个有标志的

球放入m个有标志的盒子

意味着我每一个盒子

都会有不同的选择

因此全集个数就相当于

一个球有m种选择

一共n个球

全集解S的个数就等于m的n次方

而对应于它表示

第i个盒子如果为空的话

那意味着有一个盒子我不允许用

其他的盒子我都可以用

所以Ai的个数就应该

等于m减1的n次方

那么依次如果Ai交Aj呢

表示两个盒子为空

至少它们俩为空

剩下的盒子

仍然没有约束

因此两个交集就是

Ai交Aj的个数等于

m减2的n次方

依次类推

下面我们来看一下具体

该怎么求无空盒的方案数

利用容斥原理来求解呢

所以这里面我们已经设计出了

对应于某一个盒子为空它的集合

它的个数呢

比如说i这个盒子为空

那么Ai的个数就应该

等于剩下m减1个盒子

一共n个球

所以是m减1的n次方

它一共有多少个呢

我一共有m个盒子可以变空

那么每个盒子拿一个出来

总共它有多少种不同空盒子方案呢

也就是Cm 1个

对应于如果两个呢

我现在有两个盒子为空了

有多少种选择可能性呢

无非就是Cm 2

而每一个集合它的个数有多少个

就里面相当于是

m减2个盒子给n个球去用

依次类推

这时候我们就会发现

我们要求的实际上是

要求n等于A1的补集

交A2的补集

交An的补集

也就是第一个盒子不能为空

而且第二个盒子不能为空

一直到An个盒子都不能为空

这时候实际上对应于

我们全集的个数就是m的n次方

而对应于单个单个集合的累加和

实际上一共有每一个

Ai它的个数是m减1的n次方

一共有多少个这样的Ai呢

一共有Cm 1个

因此它们单个单个集合的个数和

就是Cm 1乘以Cm减1的n次方

再加上两两的

两两的每一个集合的

它们对应的方案数是m减2的n次方

一共有多少个呢

从m个不同的盒子里面取两个

再依次累加累减

直到最后一项因为是相当于

要有m个盒子

都全部选择为空了

那实际上它一共有Cm m

而选择数当然就是m减m是0个了

这个式子统一起来

实际上就相当于它们的

系数是负1的k次方Cm k

单项是m减k的n次方

k从0到m

那这个式子实际上是在求

m个有区别的盒子无空盒的方案数

而对应于第二类斯特林数要求的是

盒子无区别

那就相当于我们在

刚才这个方案数上

除以所有的盒子标号方案数

就是第二类斯特林数的展开形式

因此Snm等于m的阶乘分之

∑(k从0到m)负1的k次方

Cm k m减k的n次方

通过容斥原理的分析我们会发现

它的求解过程相对更加直观简洁

而且通过这个式子呢

比如说我们想知道

Sm m就是只有一个

意味着m个不一样的球

放到m个盒子里面

而且无一空盒

那必然一样一个了

所以对应于Sm m只有一个的话

代到上面的式子

就意味着m的阶乘就应该等于负1的

k次方Cm k乘以m减k的m次方

所以我们可以利用第二斯特林数的

这样一个递推关系求解出的

通项表达

可以算出来m阶乘

有这样一个恒等式

刚才呢我们用这样的一个容斥原理

帮大家再一次计算了

第二类斯特林数的展开式

还有一个我们很熟的东西

我们也可以用容斥原理

得到更简便的解答

比如说错排问题

错排问题我们回顾一下

它表示n个元素依次给

以标号1 2 3到n

但是它们的全排列中要求每个元素

都不能在自己原来的位置上

有多少种呢

我们在上一节课给它的

递推关系进行了分析

求解出了一个方程

对应的我们用容斥原理来

进一步的求解

假设对应于我们要求的是

每一个元素都不在自己的位置上

那反过来我们是不是可以

设每一个数字都在它自己的位置上

这样的集合称为Ai

它表示数字i就恰好在第i位上

那么因为这个数字不能动

因此Ai的个数非常方便计算

相当于i的位置定了

剩下n减1个随便排列n减1阶乘

如果两位都被定了

i和j被定了

所以Ai交Aj就等于n减2的阶乘

依次类推

那么对应于每个元素都不在

原来位置上的

不就相当于求1不在它的位置上

而且2不在它的位置上

而且一直到n不在它的位置上

因此A1补集交A2补集

一直交

累交到An的补集

利用容斥原理等于全集的个数

全集个数是不包含任何约束

就是n阶乘

减去单个单个的集合个数

单个单个Ai它的个数是n减i

有多少个Ai呢

相当于Cn1个ni

因此对于单个单个集合

它们个数的和就等于

Cn1乘以n减1阶乘

然后再加上两两的

两两的每一个它的个数是

n减2的阶乘

而一共有多少个两两集合呢

相当于从n个元素中

取两个组合数

依次累加或者累减

一直到Cn n1的阶乘

有了这个式子以后

我们可以进一步的整理

我们看

仔细看

Cn 1乘以n减1

或者说是Cn i乘以n减i阶乘

是不是可以进一步的简化呢

我们有这个式子

Cn i乘以n减i的阶乘

把Cn i打开变成n阶乘

除以n减i阶乘 i阶乘

再乘以n减i的阶乘

这里面我们会看到

n减i和n减i就可以消掉

最终只剩下了n阶乘和i阶乘

因此Cn i乘以n减i阶乘

就等于n的阶乘除以i的阶乘

有了这样一个式子以后

我们就可以把原来的错排问题

直接用n阶乘

乘以1减去1除以1阶乘

加上1除以2阶乘

一直累加或者累减

直到1除以n阶乘

这和我们通过递推关系母函数方法

求得的错排问题的

表达式是完全一样的

组合数学课程列表:

漫谈组合数学

-什么是组合数学

--什么是组合数学

--讨论题

-最精巧的排列——幻方

--幻方

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

-苦难的羊皮纸卷

--羊皮纸卷

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

-你的手机密码安全吗

--你的手机密码安全吗

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

-暴力枚举和抽象转换

--世界杯引出的问题

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

--一一对应

--七桥问题

--小结

--讨论题

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

-知识点串串烧

--知识点串串烧

期末测验

-期末测验--期末测验

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

也许你还感兴趣的课程:

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