简单的介绍一下吧，斯特灵数其实有很多好玩的性质和扩展的。
定义
设$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)$的复杂度内得到一行的斯特灵数
性质
-
$$n^k=sum_ { i=0}^k s(k,i)×i!×c_{n}^i$$
-
$s(n, 2) = 2^{n – 1} – 1$
本文来自网络收集，不代表计算机技术网立场，如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址：https://www.ctvol.com/c-cdevelopment/611606.html