当前课程知识点:组合数学 > 组合之美 > 组合之美之鸽巢原理 > 组合之美之鸽巢原理
我们在组合数学中有一段
非常有意思的内容
也就是鸽巢原理
大家会说鸽巢原理好像
总是会涉及到鸽巢
涉及一个鸽子
那么这样一些形式和定理
能帮助我们来写更好的代码吗
实际上我们来看一下
在编程之美的第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算法
-第二周作业
--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
-知识点串串烧
--知识点串串烧
-期末测验--期末测验