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