第一类斯特林数
几何意义
把 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 无关的形式，比如：
- 利用组合意义求和，比如：
作者：@ethan-enhe
本文为作者原创，转载请注明出处：本文链接
阅读量: