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

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

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

容斥原理的应用(5)

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

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

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

下面我们用容斥原理来

求解一下隔路问题

大家对隔路问题一定很熟悉了

我们是屡次三番的提到它

但是在这儿呢

我们有一个特殊的问题

也就是在隔路中我们是

可以有障碍的

那么如果有障碍的话

一共有多少条隔路呢

比如说在这个图中

我们从00点要走到15点

但是它一共有4条障碍

也就是ABCDEF以及HG

那么这时候我就问你了

我要求我的隔路不能

经过这些障碍线段

一共有多少条呢

对于这个分析我们就可以想

我们是不是可以来分析

经过这些障碍的有多少

那么如果能够把它抛掉的话

就可以用运用容斥的思想了

也就是首先我们先不考虑

所有的障碍

它能有多少个呢

我们知道对应于

隔路它实际上就是组合模型

在这里

横的方向要走十步

竖的方向要走五步

因此就相当于C15 5

那么我们就分析

对应于设计一个集合

集合是经过AB

也就是经过障碍从00到15

一共有多少条

这时候相当于把这样一个

隔路变化了两段

从00点到A

然后再从B走到了15点

这时候我们可以利用分步的思想

求出经过AB的路径数是多少

同样经过CD的呢

必然经过CD的也是从

00点先走到C点

然后再从D点一直走到15点

那么依次类推

我们这时候就会发现

一些集合我们是可以求得出来的

也就是我们可以

设计要求是不经过障碍

但是我们去利用经过障碍的数值

通过容斥原理得到答案

这里面我们设计的集合是

经过AB的路径数为集合A

经过CD的为B

依次类推

一共设计了四种不同的集合

下面我们用容斥原理来求解

有障碍的路径数

通过上面的分析

我们可以知道如果我们

先考虑没有任何障碍的时候

这时候我们的所有的路径数

就相当于是C15 5

而对应于我们设计的集合AB来说

意思是说必然经过

AB这个障碍的路径有多少条

它的个数就是相当于A1等于

C2加2 2乘以C7加7 3

对应于CD呢

我们用A2来表示

它就相当于从00点走到C

然后再从D走到15

它的答案是

C4加2 2 C5加3 3

对应于EF经过的路径数

我们用A3来表示

对于GH

我们的路径数用A4来表示

这样的话我们想要求的实际上

我们想要求的就是相当于不经过A1

而且不经过A2

而且不经过A3的

因此对应的我们想求的方案数

就应该是A1的补集

交A2的补集

交A3的补集

一直交A4的补集

有了这样的想法之后

我们就可以分别计算

两两相交的集合

以及三三相交的集合该如何计算

下面先看两两相交的

对于两两相交的

我们拿AB和CD来看

如果要经过AB

也经过CD的话

正好它们在一条水平线上

因此有相当于从00点走到A

然后再从D点走到15点

这时候这两段呢

A1交A2就相当于是

C4 2乘以C8 3

接着往下

经过AB和EF

这时候因为ABE在一条线上

它们的路径数就相当于从00到A

以及从F到15

它们相当于路径数

C4 2乘以C6 2

对于AB和HG呢

AB和HG相当于从00到A

然后再从H点走到15点

是C4 2 C5 2

对应于另外两个CD和EF

CDEF相当于从00到C

然后再从F走到15

对于CD和HG来说

CDHG相当于从00到C

再从H到15

依次类推

接下来呢

还有一个EFHG

这两条线刚好是平行的关系

因为在隔路中不允许回退的

因此它们两个不可能同时经过

因此路径数为0

接下来我们再求三个三个的

ABCDEF

相当于从00到A

再从F到15

接下来ABCDEGH

相当于从00到A

再从H到15

然后接下来对应于

A2交A3交A4等于0

A1交A2交A4交A3

四个所有的集合

也当然不能全部通过

所以是0

有了这样所有的

单个单个集合两两相交的

以及三个三个的和四个四个的

我们直接就可以求得

A1补交A2补交A3补交A4补

它的个数恰好等于2049

组合数学课程列表:

漫谈组合数学

-什么是组合数学

--什么是组合数学

--讨论题

-最精巧的排列——幻方

--幻方

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

-苦难的羊皮纸卷

--羊皮纸卷

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

-你的手机密码安全吗

--你的手机密码安全吗

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

-暴力枚举和抽象转换

--世界杯引出的问题

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

--一一对应

--七桥问题

--小结

--讨论题

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

-知识点串串烧

--知识点串串烧

期末测验

-期末测验--期末测验

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

也许你还感兴趣的课程:

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