第一类斯特林数
1
$n$ 个元素划分为 $k$ 个环的方案数
$$
\begin{aligned}
& \begin{bmatrix} n \\ m\end{bmatrix}=\begin{bmatrix}n - 1 \\ m - 1\end{bmatrix}+(n-1)\begin{bmatrix} n - 1 \\ m\end{bmatrix} \\
\Rightarrow
& F_n(x)=\sum_{i=0}^{\infty}
\begin{bmatrix}
n \\
i
\end{bmatrix}
x^i
\\
\Rightarrow
& F_n(x)=F_{n-1}(x)x+(n-1)F_{n-1}(x)=F_{n-1}(x)(x+n-1) \\
\Rightarrow
& F_n(x)=\prod_{i=0}^{n-1}(x+i)
\end{aligned}
$$
假设已经求得了 $F(x)$，现在要求 $F(x+n)$：
$$
\begin{aligned}
F(x+n)
=&\sum_{i} a_i(x+n)^i \\
=&\sum_{i}a_i \sum_{j=0}^{i} \frac{i!}{j!(i-j)!} x^jn^{i-j} \\
=&\sum_{j} \frac{x^j}{j!} \sum_{i \ge j} a_ii! \frac{n^{i-j}}{(i-j)!}
\end{aligned}
$$
对于后半部分，翻转后直接多项式乘法，时间复杂度 $T(n)=T(\frac{n}{2})+O(n \log n)=O(n \log n)$
2
$$
n^{\overline m}=\sum_{k=0}^{m}\begin{bmatrix} m \\ k \end{bmatrix} n^k
$$
第二类斯特林数
1
$n$ 个元素划分成 $k$ 类的方案数
$$
\begin{Bmatrix}n\\k \end{Bmatrix}=\begin{Bmatrix}n-1\\k-1\end{Bmatrix}+k \begin{Bmatrix}n-1\\k \end{Bmatrix}\\
$$
2
$n^m$ 的意义是有一个长度为 $m$ 的序列，每个位置可以填 $n$ 种数字，填完这个序列的方案数，考虑乘法原理，这个过程相当于先选出 $k$ 种数字，然后把 $m$ 个位置划分成 $k$ 类，每类对应的填上选出的数字，然后做全排列
$$
n^m=\sum_{k=0}^{m}{n \choose k}\begin{Bmatrix}m\\k \end{Bmatrix}k!=\sum_{k=0}^{m}\begin{Bmatrix}m\\k \end{Bmatrix}n^{\underline k}
$$
一个应用是把 $n^m$ 的计数转化为 ${n \choose k}$ 的计数，其中 $0 \le k \le m$
还有一个应用是，可以证明 $F(x)=\sum a_ix^i$ 是可以转化为 $F(x)=\sum b_ix^{\underline i}$ 的形式
3
如果把 $m$ 个元素划分成 $k$ 类，然后做全排列，相当于容斥掉先从 $k$ 类选出 $i$ 类，然后每个元素可以染成 $i$ 种颜色之一
$$
\begin{aligned}
& k! \begin{Bmatrix}m \\ k\end{Bmatrix}=\sum_{i=0}^{k} (-1)^{k-i}{k \choose i} i^m \\
\Rightarrow
& \begin{Bmatrix}m \\ k\end{Bmatrix}=\sum_{i=0}^{k}\frac{(-1)^{k-i}}{(k-i)!}\frac{i^m}{i!} \\
\end{aligned}
$$
反转公式
1
$$
\sum_{k=m}^{n}\begin{Bmatrix}n \\ k\end{Bmatrix}\begin{bmatrix}k \\ m\end{bmatrix}(-1)^{n-k}=[n=m]
$$
2
$$
\sum_{k=m}^{n}\begin{bmatrix}n \\ k\end{bmatrix}\begin{Bmatrix}k \\ m\end{Bmatrix}(-1)^{n-k}=[n=m]
$$
换而言之，两类斯特林数互为逆矩阵
斯特林反演
本质上就是把反转公式代入
$$
f(n)=\sum_{k=0}^{n}\begin{Bmatrix}n \\ k\end{Bmatrix}g(k) \Leftrightarrow g(n)=\sum_{k=0}^{n}(-1)^{n-k}\begin{bmatrix}n \\ k\end{bmatrix}f(k)
$$
这里有一个应用：【TCO2014 Wildcard】CountTables
