第二类斯特灵数学习笔记

简单的介绍一下吧，斯特灵数其实有很多好玩的性质和扩展的。

定义

设(S(n, m))表示把(n)个不同的球放到(m)个相同的盒子里，且不允许盒子为空的方案数

称(S)为第二类斯特灵数

计算方法

递推：

考虑第(n)个球放到了哪里

第一种情况是自己占一个盒子，方案为(S(n - 1, m - 1))

第二种情况是和之前的元素共占(m)个盒子，方案为(S(n - 1, m) * m)，最后的系数是考虑放在不同位置。

这里我们认为{1}{2 4}{3}与{1}{2}{3 4}是不同的方案

而{1}{2 4}{3}与{1}{3}{2 4}是相同的方案

综上

(S(n, m) = S(n - 1, m - 1) + S(n - 1, m) * m)

边界条件(S(0, 0) = 1)

容斥

(S(n, m) = frac{1}{m!} sum_{k = 0}^m (-1)^k C(m, k) (m - k)^n)

也比较好理解，我们去枚举一个空盒子的个数

答案 = 无视空盒子放的方案 - 至少有一个盒子为空的方案 + 至少有两个盒子为空的方案 + (dots)

显然，这个式子可以用FFT优化，因此我们可以在(O(nlogn))的复杂度内得到一行的斯特灵数

性质

1. [n^k=sum_ { i=0}^k S(k,i)×i!×C_{n}^i ]

2. (S(n, 2) = 2^{n - 1} - 1)