§ Part. 1 Stirling Number / FK.

Def. 定义 $\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}$$

即考虑已经放好的 $n-1$ 个数，第一种情况是自成环即 $\begin{bmatrix}n-1 \\ m-1\end{bmatrix}$，第二种情况是放在某一个环内，可以放在任意一个已经放好的数前，即 $(n-1)\begin{bmatrix}n-1 \\ m\end{bmatrix}$。

边界为：

$$\begin{bmatrix}n \\ 0\end{bmatrix}=[n=0]$$

一个性质：

$$n!=\sum_{i=0}^{n}\begin{bmatrix}n \\ i\end{bmatrix}$$

多项式形式：$\begin{bmatrix}n \\ m\end{bmatrix}$ 为 $f_{n}(x)=\prod_{i=0}^{n-1}(x+i)$ 的 $k$ 次项系数。

§ Part. 2 Stirling Number / SK.

Def. 定义 $\begin{Bmatrix}n \\ m\end{Bmatrix}$ 表示将 $n$ 个不同的球放进 $m$ 个相同的盒子的方案数。

递推式为

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

意义即前 $n-1$ 个球放进了 $m-1$ 的盒子里，$n$ 就只有一种方法，如果前 $n-1$ 个球放进了 $m$ 个盒子，那么这个球就有 $m$ 种放法。

容斥一下可以得到通项公式（背吧）

$$\begin{Bmatrix}n \\ m\end{Bmatrix}=\frac{1}{m!}\sum_{i=0}^{m}\left((-1)^{i}{m\choose i}(m-i)^{n}\right)$$

拆完组合数可以卷积 $\texttt{NTT}$ 做，不过咱多项式学得废，就不整了。