第一类斯特林数
几何意义
把 n 各不同的数放进为 k 个环的方案数，用 $\begin{bmatrix}n\cr k\end{bmatrix}$ 表示。
代数意义
$$ \begin{aligned} x^{\overline{n}}&=\sum_{i=1}^n \begin{bmatrix}n\cr i\end{bmatrix}x^i\cr x^{\underline{n}}&=\sum_{i=1}^n (-1)^{n-i}\begin{bmatrix}n\cr i\end{bmatrix}x^i \end{aligned} $$计算方式
$O(nk)$ 递推：
$$ \begin{bmatrix}n\cr k\end{bmatrix}=(n-1)\begin{bmatrix}n-1\cr k\end{bmatrix}+\begin{bmatrix}n-1\cr k-1\end{bmatrix} $$第二类斯特林数
组合意义
把 n 各不同的数放进为 k 个非空集合的方案数，用 $\begin{Bmatrix}n\cr k\end{Bmatrix}$ 表示。
代数意义
$$ \begin{aligned}i^k&=&&\sum_{j=1}^k i^{\underline{j}}\begin{Bmatrix}k\cr j\end{Bmatrix}\cr &=&&\sum_{j=1}^k \binom i j j! \begin{Bmatrix}k\cr j\end{Bmatrix}\cr \end{aligned} $$计算方式
$O(nk)$ 递推：
$$ \begin{Bmatrix}n\cr k\end{Bmatrix}=k\begin{Bmatrix}n-1\cr k\end{Bmatrix}+\begin{Bmatrix}n-1\cr k-1\end{Bmatrix} $$$O(k \log n)$ 容斥：
$$ \begin{Bmatrix}n\cr k\end{Bmatrix}=\frac 1 {k!}\sum_{i=0}^k (-1)^i \binom k i (k-i)^n $$斯特林反演
哪些题可能是斯特林反演
- 求和 $\sum_{i=1}^n (\cdots) i^k$
- n 超级大，但 $k^2$ 能过
步骤
- 反演
- 换序求和
-
化简后面一部分：
- 重组组合数，尽量多凑成与 i 无关的形式，比如：
$\sum_{i=1}^n \binom i j \binom n i=\binom n j \sum_{i=1}^n \binom {n-j} {i-j}$
- 利用组合意义求和，比如：
$\sum_{i=1}^n \binom i j=\binom {n+1}{j+1}$