第二类斯特林数·行 笔记

Link。

理论知识

定义 $S(n,m)$ 表示将 $n$ 个有标号物品放进 $m$ 个无标号盒子里的方案数，每个盒子至少有一个。

即：当 $n=3,m=2$ 时，$\{\{1,3\},\{2\}\}$ 与 $\{\{2\},\{1,3\}\}$ 相同，但与 $\{\{1,2\},\{3\}\}$ 不同。

定理 1

$$S(n,m)=S(n-1,m-1)+m\times S(n-1,m)$$

即要么第 $n$ 个数自己开个盒子，要么放到之前一个有数的盒子。

定理 2

$$m^n=\sum _{i=0}^{m}S(n,i)\times i!\times (\genfrac{}{}{0ex}{}{n}{i})$$

左边是将 $n$ 个有标号物品放进 $m$ 个有标号盒子里的方案数，可以有空盒子。右边是选择 $i$ 个盒子不空，放进有标号盒子的方案数（因为 $\times i!$），两者等价。

实现

观察到定理 2 右边是个类似二项式反演的形式。

设 $f(i)=i^n$，$g(i)=S(n,i)\times i!$。

$$f(m)=\sum _{x=0}^{m}g(x)\times (\genfrac{}{}{0ex}{}{m}{x})\Rightarrow g(m)=\sum _{x=0}^m(-1{)}^{m-x}\times (\genfrac{}{}{0ex}{}{m}{x})\times f(x)$$$$g(m)=\sum _{x=0}^m\frac{(-1{)}^{m-x}\times m!}{(m-x)!}\times \frac{x^n}{x!}$$$$S(n,m)=\sum _{x=0}^m\frac{(-1{)}^{m-x}}{(m-x)!}\times \frac{x^n}{x!}$$

令 $A(x)=\sum _{i=0}^n\frac{(-1{)}^i}{i!}\times x^i$，$B(x)=\sum _{i=0}^n\frac{i^n}{i!}\times x^i$，$C(x)=A(x)\times B(x)$，$C(m)$ 的系数即为 $S(n,m)$，使用 NTT 即可。