第二类Stirling数

第二类Stirling数实际上是集合的一个拆分，表示将n个不同的元素拆分成m个集合的方案数，本文将其记为$S(n,m)={n\brace m}$

求解S(n,m)的问题可以等价为解决以下问题：
将n个不同的球放入m个无差别的盒子中，要求盒子非空，有几种方案？

容易得到以下式子：

1、${n \brace 0}=0$
2、${n \brace 1}=1$
3、${n \brace n} = 1$
4、${n \brace 2}= 2^{n-1} - 1$
5、${n \brace n-1}= C _n^2$

这五个式子不足以求解，还需要下面的递推公式：${n\brace r} = r {n-1 \brace r} + {n-1\brace r-1}$

如何理解这个公式呢？

1、我们先将n个球随机标记为1、2、3…n。

2、先将前n-1个球放入r个盒子。放置完成后有两种情况：
①每个盒子都有球${n-1\brace r}$
②只有一个盒子没有球。${n-1\brace r-1}$

3、再放第n个球
①每个盒子已经有球了，由于每个球都是不同的，这r个盒子每个都是独一无二的，所以需要乘以r$r {n-1 \brace r}$
②有一个空盒，那么第n个球只能放在这个空盒里 ，不需要再作运算${n-1\brace r-1}$
因此得出最后结果${n\brace r} = r {n-1 \brace r} + {n-1\brace r-1}$
我觉得需要注意的点是：第n个球是随机得来的，没有任何特殊性，所以取球的过程是不需要运算的。

C语言实现：

long long Stirling2(int n,int m)
{
    if(n < m)
        return 0;
    if(!m)
        return 0;
    if(m == 1)
        return 1;
    if(m == n)
        return 1;
    if(m == 2)
        return (1 << (n - 1)) - 1;
    if(n == m + 1)
        return n * m / 2;
    return m * (Stirling2(n - 1,m)) + Stirling2(n - 1,m - 1);
}