当前课程知识点:组合数学 > 神奇的序列 > Stirling数 > 第二类Stirling数
大家刚才做了那道quiz
是不是有点感觉
对于这样一个放球模型
似乎我们原来的方法是不适用的
那么对于第二类斯特林数
它用放球模型该怎么描述呢
也就是说我们应该有n个
有区别的球
放入m个无区别的盒子里
而且还有一点要求
我要求盒子不能有空的
这就是第二类斯特林数对应的模型
而刚才我们要说把红黄蓝白四个球
分别放入两个一模一样的盒子
实际上我们是可以通过枚举发现
它有七种不同的答案
那回头返回到
第二类斯特林数的概念
也就是把四个元素
分成两组它的方案数
也就是S(4,2)
应该等于7
我们来分析几个比较简单的例子
比如对应我要把n个球放入
0个盒子里
有多少种方案呢
实际上我们就可以分析它等于0
而对于我要把n个球都放进
一个盒子
无非就一种方案
如果我要把n个球要放到n个盒子
而且因为在第二类斯特林数中
没有空盒
因此我们把n个球分别放入
n个盒子
就只有一种方案
那么下面我们来分析一下
对应于S(n,2)应该等于多少呢
S(n,2)它表示的是
我有n个有区别的球
放入两个相同的盒子
而且无一空盒
请问有多少种方案
我们来分析一下
其实在第二类斯特林数中
困难是什么
困难在于盒子都长的一样
那是不是我可以先第一步
就把盒子搞得不一样呢
比如说我就把第一个元素拿出来
这时候我们不是说要把
n个元素要放到两个盒子里嘛
那么第一个b1
我肯定要落在其中的一个盒子里
这时候就变成了一个b1的盒子
一个是没有b1的盒子
这两个盒子已经有了区别
那剩下的其他元素
n减1的元素
往里面放就面临着两个选择
一个是不是要和b1同盒
一个是和b1不同盒
那所有的方案应该是多少呢
每个球都有两种不同的方案
一共有n减1个球
因此所有的方案是2的n减1次方
但是还有一个巧妙的地方
因为在第二类斯特林数中
不允许有空盒
所以我们把那一个空盒的方案
去掉就可以了
那这时候再总结一下
S(n,2)等于多少呢
它直接就等于2的n减1次方减1
刚才我们分析的都是
第二类斯特林数中最简单的形式
那这时候我们就会想
有没有可能有递推关系呢
既然它是个放球模型
我们完全可以去分析一下
它的递推关系
比如说对应于我们就把一个球
b1拿出来
我们来看
如果b1根据不同的分类
是不是就会有不同的方案
那b1有可能它自己就占一个盒子呀
如果它自己站了一个盒子
那剩下的还剩下了m减1个盒子
还剩多少球呢
n减1个球
所以对应b1已经占了一个盒子之后
剩下的就应该方案是S(n-1,m-1)
而对于如果b1不独占盒子
那么它可以先后把n减1个球
放到m的盒子里
而b1再往这m盒子里去选
因此如果b1不独占盒子的话
那么它的方案数就应该是
m乘以S(n-1,m)
这两类无重复 无遗漏
把所有的第二类斯特林数的
放球模型涵盖在内了
因此我们有这样一个递推关系
S(n,m)就等于m乘以S(n-1,m)加上S(n-1,m-1)
那么刚才我们已经去试验了
对于四个球如果放入两个盒子的话
它的答案是7
也就是S(4,2)等于7
那这时候我们稍微复杂一点
我不仅仅有红黄蓝白四个球
我又来了一个绿色的球
这时候五个球要
放入两个无区别的盒子
而且无空盒
那我们就可以利用递推关系来看了
也就是说S(5,2)等能等于多少呢
S(5,2)根据递推关系我们有
S(5,2)等于2倍的S(4,2)
再加上S(4,1)
这可以根据绿球的不同方案
是否绿球独占一盒
还是和别人共享盒子分类得到
既然S(4,2)我们已经算得出来
S(4,1)又只等于1的话
我们可以直接算出S(5,2)就等于
2乘以7加1
等于15
所以可以看到
递推关系实际上根据绿球的
不同方案就可以给我们带来了
简便的计算方法
那么有没有真正的直接的表达式呢
我们来进一步的分析一下
其实我们看一下
在第二类斯特林数的模型中
它要求n个有区别的球放入到m个
相同的盒子中
要求无一空盒
这时候这个相同对我们来说
并不是一个非常好的事情
因此我就想是不是有可能我们用
其他的方式
来把相同的盒子转化成不同盒子呢
我们就先把问题转化成由n个
有标志的球放入到m个
有区别的盒子
而且无空盒
那它的方案数不就相当于要把盒子
标号数计算在内
因此是m阶乘乘以S(n,m)
它就相当于是把m有标志的元素取
n个作为允许重复的排列
既然是排列的话
我们想到的就应该是用
指数型母函数
而对于每一个盒子来说的话
我们这就相当于每一个盒子它现在呢
对应着要么没有元素
要么相当于a有2个 3个 4个
这时候它要求是无空盒是不允许的
因此在指数型的母函数中
我们的x0次方是不会允许有的
最后它的母函数写出来就是x加上x
平方除以2阶乘
加上x3次方除以3阶乘
它呢元素一共有m个
所以是这样多的母函数
一共乘以m次幂
里面这个式子实际上就相当于
e的x次方减1
因此它的指数型母函数就变成了
要e的x次方减1的m次方
我们把这个式子再通过两项式定理
进行展开以后
就变成了取h作为一个变量的话
h从1到m
它是C(m,h)乘以负1的h次方
e的(m-h)x
那这里面我们发现组合数和负1
的这个h次方都没有问题
而剩下的e的(m-h)x
等于多少呢
e的(m-h)x实际上利用ex的
展开式
又可以把它化成是1加上m减h
除以1阶乘x
加上m减x的平方
除以2阶乘x平方
因此对应于通项xk次方除以
k阶乘的话
它前面的系数就应该等于m
减h的k次方
最后我们把它写成n从0到无穷大
m减h的n次方
除以n阶乘
再乘以xn次方
这个式子最后还要和前面的
C(m,h)负1x次方相互累乘
累乘之后的结果其实我们完全可以
把对应的h提出来之后
变成了n从0到无穷大
n的阶乘x的n次方
h的变化从1到m
变成了cmh负1的h次方
乘以m减h的n次方
因此我们就可以说对应于
这样的一个母函数
它的系数是谁
它的系数就是∑h从1到m
C(m,h)负1h次方乘以(m-h)n次方
这个的系数刚好又是我们求的方案数
m阶乘乘以S(n,m)
因此我们就可以算出来对应的
第二类斯特林数它的表达式
就是S(n,m)等于1除以m阶乘
乘以∑h从1到m
cmh负1的h次方m减h的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
-知识点串串烧
--知识点串串烧
-期末测验--期末测验