当前课程知识点:组合数学 >  神奇的序列 >  Stirling数 >  第二类Stirling数

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

第二类Stirling数在线视频

第二类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算法

--程序支持与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

-知识点串串烧

--知识点串串烧

期末测验

-期末测验--期末测验

第二类Stirling数笔记与讨论

也许你还感兴趣的课程:

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