第二类Stirling数

递推式

$$\begin{align} &S(n,1)=1(n>=1) \\ &S(n,n)=1 \\ &S(n,k)=k*S(n-1,k)+S(n-1,k-1) \end{align}$$

推导（来自百度百科)

• 第二类Stirling数的推导和第一类Stirling数类似，可以从定义出发考虑第$n+1$个元素的情况，假设要把$n+1$个元素分成$m$个集合则分析如下：
  1. 如果n个元素构成了$m-1$个集合，那么第$n+1$个元素单独构成一个集合。方案数$S(n,m-1)$
  2. 如果n个元素已经构成了$m$个集合，将第$n+1$个元素插入到任意一个集合。方案数 $m*S(n,m)$
• 综合两种情况得：$S(n+1,m)=m*S(n,m)+S(n,m-1)$

举例

以放球方案数为例

将n个球放入k个完全相同的盒子并保证每个盒子里至少有一个球，求方案数

1. 易知将n个球放入1个盒子只有一种方案
2. 易知将n个球放入n个盒子只有一种方案（因为不允许有空盒子）
3. 当$n>k$时
   1. 如果$n-1$个球已经放入了$k-1$个盒子中，那么第$n$个球就放在单独的一个盒子中，即$S(n-1,k-1)$
   2. 如果$n-1$个球已经放满了$k$个盒子，那么第$n$个球可以放入任何一个盒子中，即$k*S(n-1,k)$

应用

1. n个不同的球，放入m个无区别的盒子，不允许盒子为空。

   方案数：$S(n,m)$

2. n个不同的球，放入m个有区别的盒子，不允许盒子为空。

   方案数：$m!*S(n,m)$

   ​ 乘上盒子的全排列即可

3. n个不同的球，放入m个无区别的盒子，允许盒子为空。

   方案数：$\sum\limits^m_{k=1}S(n,k)$

   ​ 枚举非空盒个数并求和即可(相当于放入1~m个盒子中的方案数和)

4. n个不同的球，放入m个有区别的盒子，允许盒子为空。

   方案数：$\sum\limits^m_{k=1}S(n,k)*P(m,k)$

   乘上盒子的排列数（从m个里取k个）

另一种方案数求法：$m^n$

每一个球都有m种方法，一共有n个球，根据乘法原理，一共有$m^n$种放法

1. 盒子有区别就乘上排列数，盒子允许为空就枚举空盒数

代码实现

int Stirling(int n,int k){
	if(k == 1 || n == k) return 1;
	return k * Stirling(n-1,k) + Stirling(n-1,k-1); 
}