簡單的介紹一下吧，斯特靈數其實有很多好玩的性質和擴展的。 定義 設$S(n, m)$表示把$n$個 不同的球 放到$m$個相同的盒子里，且不允許盒子為空的方案數 稱$S$為第二類斯特靈數 計算方法 遞推： 考慮第$n$個球放到了哪裡 第一種情況是自己占一個盒子，方案為$S(n 1, m 1)$ 第二 ...
簡單的介紹一下吧，斯特靈數其實有很多好玩的性質和擴展的。
定義
設$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$
