第二类斯特林数

比起第一类斯特林数，第二类斯特林数更为常用。

\(\begin{Bmatrix}n\\m\end{Bmatrix}\) 表示将 \(n\) 个带标号球放入 \(m\) 个无标号盒子（非空）的方案数。

有递推式：（考虑第 \(n\) 个球放到哪里）

\[\begin{Bmatrix}n\\m\end{Bmatrix} = \begin{Bmatrix}n-1\\m-1\end{Bmatrix} + m\begin{Bmatrix}n-1\\m\end{Bmatrix} \]

通过这个递推式，我们可以用 \(O(n^2)\) 的时间计算出所有第二类斯特林数。

通过考虑无标号球无标号盒子与第二类斯特林数的关系可以得到下面的式子：

\[m^n = \sum_{k}{m\choose k} \begin{Bmatrix}n\\k\end{Bmatrix} k! \]

即：

\[m^n = \sum_{k}\begin{Bmatrix}n\\k\end{Bmatrix}m^{\underline{k} } \]

可以用于普通幂转下降幂。

发现有些像二项式反演，于是可以上反演：

\[m^n = \sum_{k}{m\choose k} \begin{Bmatrix}n\\k\end{Bmatrix} k!\\ \begin{Bmatrix}n\\m\end{Bmatrix}m! = \sum_{k}(-1)^{m-k} {m \choose k} k^n\\ \begin{Bmatrix}n\\m\end{Bmatrix} = \sum_{k}\frac{k^n}{k!} \frac{(-1)^{m-k}}{(m-k)!} \]

发现是个卷积形式，于是可以 \(O(n \log n)\) 求出一行的斯特林数。

如果想要求一列的话需要用到生成函数。

\[\begin{aligned} F_k(x)&=\sum_{i} \begin{Bmatrix}i\\k\end{Bmatrix}x^i\\ &= \sum_i \begin{Bmatrix}i-1\\k-1\end{Bmatrix}x^i + k\sum_i \begin{Bmatrix}i-1\\k\end{Bmatrix}x^i\\ &= x\sum_i \begin{Bmatrix}i\\k-1\end{Bmatrix}x^i + xk\sum_i \begin{Bmatrix}i\\k\end{Bmatrix}x^i\\ &= xF_{k-1}(x) + xkF_k(x) \end{aligned} \]

于是:

\[\begin{aligned} F_k(x) &= \frac{x}{1-kx}F_{k-1}(x)\\ &= \frac{x}{1-kx} \times \frac{x}{1-(k-1)x} \times ... \times \frac{x}{1-x}\\ &= \frac{x^k}{\prod_{i=1}^k (1-ix)} \end{aligned} \]

（由于边界为 \(F_0(x) = 1\)）

分子就是将多项式向右平移 \(k\)。分母可以用分治+NTT+求逆做到 \(O(n \log^2 n)\)。总复杂度为 \(O(n \log n)\)

第一类斯特林数

\(\begin{bmatrix}n\\m\end{bmatrix}\) 表示 \(n\) 个有标号元素形成 \(m\) 个圆排列（环）的方案数。

有递推式：（考虑最后一个球跟在谁后面）

\[\begin{bmatrix}n\\m\end{bmatrix} = \begin{bmatrix}n-1\\m-1\end{bmatrix} + (n-1)\begin{bmatrix}n-1\\m\end{bmatrix} \]

它和第一类斯特林数有个类似的式子：

\[x^{\overline{m}} = \sum_{k}\begin{bmatrix}m\\k\end{bmatrix} x^k \]

是不是有些像生成函数？于是可以用分治+NTT来 \(O(n \log^2 n)\) 求一行第二类斯特林数。