当前课程知识点:组合数学 > 神奇的序列 > Stirling数 > 第一类Stirling数
这节课会介绍一个叫做
斯特林数的东西
当然对斯特林大家应该这个名字
并不陌生
因为我们在介绍全排列的时候
曾经给大家介绍过一个
斯特林估计式
斯特林估计式是告诉大家n的阶乘
当n趋于无穷大的时候
越大它越逼近于根号下2πn乘以n
除以e的n次方
当然确实这个斯特林就是我们今天
要讲的斯特林
James Stirling
James Striling他呢其实不仅仅有估计式
甚至他在排列也非常有名气
有一个排列专门以他命名
称为Stirling Permutation
它实际上是讲一个多重集
我其中每个元素都重复两次
但是我要求它摆出来的所有的排列
两个重复数字之间它们的数字差距
一定要大于该数
所以这个排列是非常有意思的
当然今天我们不会去细致地分析
Stirling Permutation
而我们的重点是被称为叫做
斯特林数
而且大家看到一下
它的英文
我们写的是Stirling Numbers
为什么有s呢
实际上它不是单个一个数
至少它被分成的两类
一个是称为第一类斯特林数
一个称为第二类斯特林数
所谓第一类斯特林数
其实它的模型也很简单
我们有n个人去跳集体舞
有多少种方法把它分成m个圈呢
我们知道在跳集体舞华尔兹的时候
我们经常有可能是一个人一个
有可能是两个人一圈
或者是三个人一圈
来我们看一个例子
比如ABCD四个人他要跳舞
能有多少种画圈的方法呢
可以说AB一组
CD一组
甚至我也可以说A单个一个人
而BCD是一圈
因此根据不同的分类
我们可以把它一一列举出来
而这样的一个问题
同样等价于我们可以在四个点上
比如说圆周上的四个点如何去画圈
这两个问题是等价的
这个的个数就被称为是
第一类斯特林数
一般我们用小s(n,k)来表示
而我们这个问题
四个元素中我们要把它画成
两个圈的方法
实际上通过枚举我们列举出来s(4,2)
就等于11
那么我们来分析一下
第一类斯特林数s(n,m)
可以说s(n,m)就是说一共有n个人
进行跳舞的话
我有多少种方法把它分成m个圈
而我们知道如果没有人跳舞
那么自己就是没有了
那么如果说是
我要有n个人分成0个圈呢
那怎么也没有办法
但是如果一个人呢
他要分成一个圈
就只有一种方法
所以s(n,0)等于0
而s(1,1)等于1
下面我们来分析一下
这样一个跳舞画圈的问题
有什么样的递推关系
实际上我们会分析
对应于一共有n加1个人
那么假设n个人的位置已经摆好了
然后又来了这最后一个人
那么这个人他就有两种不同的方法
一种他自己就单独一个
那么剩下的其他n个人呢
组成了m-1个圈
还有一种方法
那n个人已经凑够了m个圈
那这最后一个人来了
他必须在刚才所有的人中间
选一个位置
那他会有多少个位置呢
因为前面已经有n个人了
那我就选择是不是在这个人的左边
因此他有n种不同的位置选择
而剩下那n个人呢
他们被画成了m个圈
因此根据这两个分类
我们就可以写出第一类斯特林数
他的对应的递推关系
也就是s(n+1,m)等于s(n,m-1)
加上n乘以s(n,m)
对于第一类斯特林数我们有了
这样一个递推关系
可能细心的同学会发现
在一些参考书中
它们在介绍斯特林数的时候
好象递推关系不太一样嘛
它们有可能有这样一个式子
我们分析一下
这两个式子几乎一模一样
只差在哪儿呢
一个是加
一个是减
实际上这是第一类斯特林数的
两种表达方式
第一个它实际上被称为是unsigned
什么意思
也就是说它是无符号的
大家分析一下
第一个式子它永远出来的都是正数
而第二个式子却不一定
因为它是两个数字之差
那么它有可能有正有负
所以在下一个式子
它实际上对应的是一个有符号的
第一类斯特林数
在几何意义上它们也完全不一样
实际上我们有这样一种定义
用括号x小n来表示
它表示的是从x乘以x减1
一直乘乘乘
累减下去
而还有另外一个式子
我们要是x一直乘以x加1
一直累加下去
这两个式子分别对应的是不同的
类型的第一类斯特林数
而对于累加上去的呢
我们称为是rising factorial
而对于累减我们就叫它是falling factorial
实际上这样两种累乘方法
对应的就是不同的第一类斯特林数
对应于刚才依次累降相乘的
它对应的符号就是正好对应的是
有符号的第一类斯特林数
而对应于刚才累加依次相乘的
它对应的是无符号的
第一类斯特林数
那么我们来分析一下
为什么对应于有符号的
第一类斯特林数
它的递推关系中间是一个减号呢
那我们来分析一下
第一类斯特林数它的递推关系
尤其是对于有符号的
第一类斯特林数
它为什么中间会是一个减号呢
根据它的定义我们知道它是对应于
x这样依次累降的一个累乘的
对应的系数
那么这个式子如果它对应的系数
正好是s(n,0) s(n,1)x加上s(n,2)x平方
一个到s(n,n)xn次方的话
那我们来看一下它的递推关系
对应于更大一点
比这个xn稍微再大一些的
我们可比把它做成x对应的n加1
它的累乘实际上对应于就是说
对应于从这里依次减减减
直到这个数字
还要把n替换成n加1
那么它的系数相当于在后面
又多了一项x减n加1
然后再加1
这时候我们对应的这一项
实际上就是x减n
也就是比这一项再多一项
前面的这些系数就是我们刚才
对应的xn的系数
而后面又多了一项x减n
而这一个式子它恰好是n加1的falling factorial
那这时候它的系数根据
第一类斯特林数的定义
就应该是s(n+1,0)
加上s(n+1,1)x
依此类推
因此这两项的乘积对应的系数
就应该对应于这里面s(n+1,k)
那么这样的递推关系我们来看一下
xk次方在这上述两项的系数
应该是什么
在左边
我们看一下
它会怎么得到呢
它要么对应的是这里面取到的x的
k减1次方
那它的系数就是s(n,k-1)
最后乘以一个x
它凑出来一个x的k次方
另外有可能是在这个式子里面
我们取的是xk次方
x的k次方再乘以对应的这里
有个负n项
所以这边xk次方的系数
刚好是s(n,k)
再乘以个负n变成了减去ns(n,k)
而这个式子正好对应的就是在
第二个式子中xk次方的系数
它就等于s(n+1,k)
所以通过上面的分析我们会发现
对于有符号的第一类斯特林数
它的递推关系中间是减的关系
刚才我们介绍了第一类的斯特林数
对于第一类的斯特林数
它的递推关系的通项表达我们在此
就不进行介绍了
我们着重会介绍第二类斯特林数
而第二类斯特林数其实它的模型
跟第一类非常相似
但是区别在于第一类斯特林数中
我们最终还是让跳舞的人
要围成圈的
而在第二类斯特林数
我只把它堆成一堆就好了
因此在第二类斯特林数
它的模型是说
诶 我拿放球模型来看
有n个球要分成k组
那么有多少种不同的方案
在组中是没有顺序可言的
比如说我们举个例子
一共有红 黄 蓝 白四个球
我要分别分成一组
有多少种方案呢
那不就把它们放在一起嘛
我要把它分成四组呢
也只有一种方案
也就是一个组里面一个
但是如果要分成了两组呢
有多少种不同的方案
请大家一定要留意组内
是没有顺序关系的
那么请大家完成一下
下面的一道quiz吧
-什么是组合数学
--什么是组合数学
--讨论题
-最精巧的排列——幻方
--幻方
-漫谈组合数学--最精巧的排列——幻方
-苦难的羊皮纸卷
--羊皮纸卷
-苦难的羊皮纸卷--作业
-你的手机密码安全吗
-漫谈组合数学--你的手机密码安全吗
-暴力枚举和抽象转换
--世界杯引出的问题
--世界杯引出的问题--练习
--一一对应
--七桥问题
--小结
--讨论题
-大家谈组合数学(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
-知识点串串烧
--知识点串串烧
-期末测验--期末测验