组合数学之Stirling数

组合数学之Stirling数"/>

组合数学之Stirling数

Stirling估计式

n ! ∼ 2 π n ( n e ) n n! \sim \sqrt{2 \pi n}(\frac{n}{e})^n n!∼2πn ​(en​)n
作用是为了方便计算n阶乘的复杂度

Stirling Numbers

第一类Stirling数

数学模型：n个人跳集体舞，分成m个圆环的方法数目
比如ABCD四个人跳舞，组成2个圆排列的方法有多少种？
可以是{AB},{CD}，也可以是{A}, {BCD}，这样算下来一共11种
列举一下：
1.{AB},{CD}
2.{AC},{BD}
3.{AD},{BC}
4.{A},{BCD}
5.{A},{BDC}
6.{B},{ACD}
7.{B},{ADC}
8.{C},{ABD}
9.{C},{ADB}
10.{D},{ABC}
11.{D},{ACB}
在Stirling数中记为s(4,2)=11
现在分析s(n,m)的情况，n个人，分成m个圈，如果分成0个圈呢，不存在的，怎么能分成0个圈呢？所以 s ( n , 0 ) = 0 s(n,0)=0 s(n,0)=0
如果是1个人分成1个圈呢，自然是一种情况了，所以 s ( 1 , 1 ) = 1 s(1,1)=1 s(1,1)=1
有了初始值就可以开始求 s ( n , m ) s(n,m) s(n,m) 的表达式了，和以往相同的是，还是分类讨论的思想，不同的是，这次求的是 s ( n + 1 , m ) s(n+1,m) s(n+1,m)的表达式
假设现在n个人已经找好位置了，现在又来了第n+1个人，这个人有两种情况(前提：最终是要构成m个圈)

• 前n个人已经构成了m-1个圈了(表达式为 s ( n , m − 1 ) s(n,m-1) s(n,m−1))，那最后一个人很简单，自己构成一个圈
• 前n个人已经构成m个圈了(表达式为 s ( n , m ) s(n,m) s(n,m))，第n+1个人来了，他不能自己构成圈了，只能插在别人旁边，于是，他就有n个位置可以插
  所以递归关系为： s ( n + 1 , m ) = s ( n , m − 1 ) + n s ( n , m ) s(n+1,m)=s(n,m-1)+ns(n,m) s(n+1,m)=s(n,m−1)+ns(n,m)

第二类Stirling数

数学模型：把n个求分成k组，组内无顺序区别，一共有多少种方案？
例子：红黄蓝绿四个球，分成两组，有几种方案？注意：组内无顺序。
答案是七种方案:
{A}{BCD}
{B}{ACD}
{C}{ABD}
{D}{ABC}
{AB}{CD}
{AC}{BD}
{AD}{BC}
记为 S ( 4 , 2 ) = 7 S(4,2)=7 S(4,2)=7
对应放球模型为：n个有区别的球放到m个相同的盒子中，要求无一空盒。
列举一些初始值: S ( n , 0 ) = 0 S(n,0)=0 S(n,0)=0 S ( n , 1 ) = 1 S(n,1)=1 S(n,1)=1 S ( n , n ) = n S(n,n)=n S(n,n)=n
现在我们先尝试求一下 S ( n , 2 ) = ? S(n,2)=? S(n,2)=?
我有n个球，先取其中一个球，放到一个盒子里，现在两个盒子就有区别了，一个有球，一个没球，然后剩下n-1个球，每个球有两种选择，于是就成了 2 n − 1 2^{n-1} 2n−1种方案，但是这样有可能所有球都放到一个盒子里，所以再减去这种情况，最终的方案数就是 2 n − 1 − 1 2^{n-1}-1 2n−1−1
下面再求一下 S ( n , m ) S(n,m) S(n,m)，还是分类讨论的思想
首先取一个球b1，这个球有两种情况

• b1独占一盒，那么剩下n-1个球，m-1个盒子，方案数为 S ( n − 1 , m − 1 ) S(n-1,m-1) S(n−1,m−1)
• b1不独占一盒，相当于先把剩下的n-1个球放到m个盒子里，方案数为 S ( n − 1 , m ) S(n-1,m) S(n−1,m)，最后把b1放到其中一个盒子里，m个盒子自然有m种情况，方案数为 m S ( n − 1 , m ) mS(n-1,m) mS(n−1,m)
  所以第二类Stirling数的表达式为： S ( n , m ) = S ( n − 1 , m − 1 ) + m S ( n − 1 , m ) S(n,m)=S(n-1,m-1)+mS(n-1,m) S(n,m)=S(n−1,m−1)+mS(n−1,m)

第二类Stirling数的通项表达式

需要母函数的基础，我是没看懂，直接放结果了
S ( n , m ) = 1 m ! ∑ h = 0 m C ( m , h ) ( − 1 ) h ( m − h ) n S(n,m)=\frac{1}{m!}\sum_{h=0}^mC(m,h)(-1)^h(m-h)^n S(n,m)=m!1​h=0∑m​C(m,h)(−1)h(m−h)n
推导过程：