当前课程知识点:组合数学 >  组合之美 >  组合之美之鸽巢原理 >  组合之美之鸽巢原理

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

组合之美之鸽巢原理在线视频

组合之美之鸽巢原理

下一节:组合之美之转动群与染色

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

组合之美之鸽巢原理课程教案、知识点、字幕

我们在组合数学中有一段

非常有意思的内容

也就是鸽巢原理

大家会说鸽巢原理好像

总是会涉及到鸽巢

涉及一个鸽子

那么这样一些形式和定理

能帮助我们来写更好的代码吗

实际上我们来看一下

在编程之美的第2.16中

曾经有这样一个题目

它要求给定的一个序列的

最长的增子序列

什么概念呢

比如说我现在就这样一串数

那么我要从里面想要找最长的

从小到大的一个子串

该如何计算呢

我们仔细看一下

这样一串数字中

实际上我们会发现它的最长的

一个增序子序列实际上就只能

包含四个元素

那么我就是通过每一个

每一个子串进行枚举

自然可以找到这样一个

最长的增子序列

但是这道题目实际上有一个要求

它说要求大家用尽可能少的

复杂度去计算

当然在算法上我们是可以通过

一些技巧来避免冗余的计算的

那么在数学理论分析上

是不是也可以帮助我们来

减少一些不必要的搜索呢

刚才我们说到了

有这样一道题目让你编程

去实现对于给定一个序列找它的

最长增子序列

那这时候我们由鸽巢原理可以

得到这样一个定理

也就是说对应于我们也是

一块儿序列

A1 A2一直到Amn+1

这些中间的数字呢是随意的

而且各个数字是不相等的

那么m,n是正整数

则S有一个长度为m+1的

严格增子序列

或者为n+1的减子序列

同时增子序列和减子序列

它们两个是可以互换的

因此也会有S有一个长度为m+1的

减子序列或者

长度为n+1的增子序列

那么如果这样一个定理成立的话

实际上我们就可以找到

对于增子序列它的长度一个下界

因此就不需要盲目的

去寻找比较短的增子序列了

那么有这样一个概念之后

我们来用鸽巢原理来看

如何给它一个证明呢

我们会发现

首先我们对应于每一个序列

它的开头可以是ai

ai向后去找它对应最长的增子序列

以及最长的减子序列

那么自然它们有一定的长度

假设它的增子序列的长度是li

而对应的减子序列的

长度是li'的话

那么根据我们的提议

说至少要有m+1的li

或者n+1的li'

那我是不是可以反过来想

假设确实这个条件不成立呢

我们用反证法

对于任何一个i

假设li

也就是增子序列它的长度

没有大于m的

属于1到m之间

而对于li'它也没有比n长的

因此li'在1到n之间

那这个时候我们是不是可以发现

它们所有的长度

累乘起来不会超多mn种

那么对应于每一个i从1到mn+1

它一共有多少个对应的一个序列呢

实际上它可以从

l1 l2一直到mn+1

对应应该有mn+1个

而这个时候我们知道那么

既然一共是mn种

一共有mn+1个落进来

那意味着对应的

它们应该有两个序列对儿

是相等的

假设我们正好是j小于k的时候

lj lj'和

lk lk'完全相等的

这时候如果完全相等的话

那意味着什么

意味着哎

我现在有两个串儿

它后面的对应的增子序列

和对应的减子序列长度是一样的

这时候我们由于知道对应的从

j开始往前数有多少个

就会发下它有多少个对应的增子序列

那么我们就会发现对应的

j和k它们是不是相等呢

因为我们说到对于序列中

各个数值是不相等的

那意味着有可能aj就小于ak的

如果aj小于ak的话

那意味着在k的前面有一个数字

比当前的ak还要小

那就意味着如果我从j开始的话

在后面再加上ak对应的增子序列

那就意味着从j开始的这个增子序列

比从k开始的增子序列还要多

那意味着实际上

如果aj小于ak的话

aj和ak后面的

增子序列就构成了一个

更长一点儿的增子序列

也就是lj应该大于lk

那么aj小于ak是不行的

我们看看aj大于ak可不可以

如果aj是大于ak的

那么ak它的后面又可以和

ak后面的减子序列构成一个

更长一点儿的减子序列

也就是对应的ljˊ

肯定应该大于lkˊ了

应为aj不能等于ak

我们会发现在这样的一个假设下

它对应的lj不能等于lk

或者ljˊ不能等于lkˊ

那就意味着我们原来的假设

假设LI在1到m之间

LIˊ在1到n之间

是不成立的

有了这个矛盾我们就发现

那既然这个假设我们不成立

它的矛盾就意味着至少存在

某一个LI应该大于m

或者至少存在某一个LIˊ是大于n

因此实际上对于任意给定的

各个数字不相等的字符串儿中

它的增子序列或者减子序列是

存在一定的界限的

当然这只是从一个问题的

角度去进行分析

如何把它变成程序的实现

还是有待同学们进一步分析的

除了鸽巢原理之外

另外一个非常神奇的定理呢

实际上是容斥原理

容斥原理其实说起来思想很简单

也就是说我们想要无重复

无遗漏的进行计数的时候

往往呢直接求解是非常困难的

那么我们会怎么想呢

首先我们有很多很多不同的

对应的条件

我们把每一个条件分门别类的

进行处理

这时候我们可能会求说要

满足这个条件的所有的元素

这时候我们会想

可以说先说所有的条件我先不管

列出它的全局个数

然后呢再减去对应于满足

一个条件的

比如说A1 A2 A3

它们每一个对应的方案数有多少个

那么这时候刨掉之后会发现

可能它们交集被重复去掉了

因此呢我们要把重复去掉的

再累加回来

也就是累加上A1交A2

A2交A3

两两相交的集合

依次累减 累加

这样就够成了容斥原理

实际上容斥原理的这两个形式呢

无非就是一个用补集

一个不用补集

有了这两个形式其实可以

帮助我们进行无重复无遗漏的计数

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

这样一道题

还是从1到10000之间

这时候我们要数什么样的数呢

我们要数既不是完全平方数

也不是完全立方数的数字的个数

那么首先我们要了解一下

什么是完全平方数呢

比如说2的平方

3的平方

5的平方 完全立方数

自然就是3的三次方

5的三次方

那么它要求得是既不是

平方数也不是立方数

那么我们首先发现我们想去

用容斥原理的话这就有两个性质

一个是完全平方数

一个是完全立方数

那么我们分别去求对应满足

这个条件的

那么如果在1到10000之间

有什么样的数字是能够

完全平方数呢

那无非就是1的平方

2的平方

最大能到多少呢

也就是100的平方

所以对应于1到10000之间

能够是完全平方数的个数

正好就是100

对应于完全立方数呢

我们算了一下

要在1到10000之间正好21的

立方正好小于10000

而22的立方大于10000

因此完全立方数一共有21个

那么下一个问题就是说

如果我要想要求既是完全平方数

又是完全立方数

那就意味着它应该是一个

数字的六次方

这时候我们要求从1到10000

之间是一个数字的六次方的

这样的形式有多少个数字

实际上我们算出来正好是4的

六次方是小于10000的

而5的六次方正好大于10000

因此既是平方数又是立方数

它的个数就应该是只有4个

这时候我们再代到容斥原理

会发现全局的个数

不就是10000吗

然后我们再减去单个单个集合

也就是100和21

然后再加上两两相交的集合个数

也就是4

最后我们就可以得到

这道题目的答案

组合数学课程列表:

漫谈组合数学

-什么是组合数学

--什么是组合数学

--讨论题

-最精巧的排列——幻方

--幻方

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

-苦难的羊皮纸卷

--羊皮纸卷

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

-你的手机密码安全吗

--你的手机密码安全吗

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

-暴力枚举和抽象转换

--世界杯引出的问题

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

--一一对应

--七桥问题

--小结

--讨论题

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

-知识点串串烧

--知识点串串烧

期末测验

-期末测验--期末测验

组合之美之鸽巢原理笔记与讨论

也许你还感兴趣的课程:

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