当前课程知识点:组合数学 > 容斥原理和鸽巢原理 > 回忆过去,容斥新解 > 容斥原理的应用(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算法
-第二周作业
--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
-知识点串串烧
--知识点串串烧
-期末测验--期末测验