第二类斯特林数·行

什么是斯特林数?

第二类斯特林数

我们定义第二类斯特林数 $\begin{Bmatrix} n \m \end{Bmatrix}$ 表示把 $n$ 个不同元素划分成 $m$ 个相同的集合中的方案数。
又名整数的无序分拆数，也可以表示为 $S(n,m)=\begin{Bmatrix} n \m \end{Bmatrix}$。
第二类斯特林数有2个重要性质:

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

   证明：设原集合为 $\begin{Bmatrix}a_1,a_2\cdots a_n\end{Bmatrix}$ 我们将原始状态分为两种情况。
   分别:$\begin{Bmatrix}a_n\end{Bmatrix}$ 做为独立的集合，此时答案为 $\begin{Bmatrix} n-1 \m-1 \end{Bmatrix}$；
   另一种情况则是 $\begin{Bmatrix}a_n\end{Bmatrix}$ 被插入了一个非空集合，因为有 $m$ 种选择，答案显然为 $m\times \begin{Bmatrix} n-1 \m \end{Bmatrix}$。

2. $m^n=\displaystyle \sum _{i=1}^{m} \begin{Bmatrix}n\i\end{Bmatrix} \times i! \times \begin{pmatrix}m\i\end{pmatrix}$。
   这个可以这么理解：左面为将 $n$ 个数随意放在 $m$ 个集合中的方案数，可以存在空集；
   而右面为枚举非空集合个数 $i$ 后求解该情况的答案，左面显然等于右面。

化简：由二项式反演

$$f(n) = \sum_{i = 0}^{n} \begin{pmatrix}n\\i\end{pmatrix}g(i) \Leftrightarrow g(n) = \sum_{i = 0}^{n} (-1)^{n-i} \begin{pmatrix}n\\i\end{pmatrix}f(i)$$ $$\begin{Bmatrix}n\\m\end{Bmatrix}=\sum\limits _{i=1}^{m}\frac{(-1)^{m-i}}{(m-i)!}\times \frac{m!}{i!}$$

这是一个卷积形式，使用 ntt 即可