斯特林数

非常幽默的是到现在我都不会斯特林数，昨天联考有个下降幂转化，突然想起来有玩意儿，补一下。

由于我这辈子不会学多项式，所以本篇文章不涉及任何多项式内容。只能说省选 NOI 考了我自己倒霉。

第一类斯特林数	第二类斯特林数
置换环划分方案数	集合划分方案数
$\begin{bmatrix}n\\m\end{bmatrix}=\begin{bmatrix}n-1\\m-1\end{bmatrix}+(n-1)\begin{bmatrix}n-1\\m\end{bmatrix}$	$\begin{Bmatrix}n\\m\end{Bmatrix}=\begin{Bmatrix}n-1\\m-1\end{Bmatrix}+m\begin{Bmatrix}n-1\\m\end{Bmatrix}$
$/$	$\begin{Bmatrix}n\\m\end{Bmatrix}=\sum\limits_{i=0}^m\dfrac{(-1)^{m-i}i^n}{(m-i)!i!}$

斯特林反演

感觉反演证明都没啥必要要写，直接列式子：

$$f(n)=\sum\limits_{i=0}^n\begin{bmatrix}n\\i\end{bmatrix}g(i)\Leftrightarrow g(n)=\sum\limits_{i=0}^n(-1)^{n-i}\begin{Bmatrix}n\\i\end{Bmatrix}f(i)$$

上升幂，下降幂，普通幂转化

上升幂转普通幂：$x^{\overline n}=\sum\limits_{i=0}^n\begin{bmatrix}n\\i\end{bmatrix}x^i$。

$x=1$ 显然相等。后面式子的组合意义是给每个环染 $1\sim x$ 的颜色，令 $f(x)=x^{\overline n}$，则有递推式 $f(x)=(n+x-1)f(x-1)$，归纳易证。

普通幂转上升幂：$x^n=\sum\limits_{i=0}^n(-1)^{n-i}\begin{Bmatrix}n\\i\end{Bmatrix}x^{\overline{i}}$，上面式子斯特林反演。

普通幂转下降幂：$x^n=\sum\limits_{i=0}^n\begin{Bmatrix}n\\i\end{Bmatrix}x^{\underline{i} }$，枚举上界 $x,n$ 均可。

下降幂转普通幂：$x^{\underline n}=\sum\limits_{i=0}^n(-1)^{n-i}\begin{bmatrix}n\\i\end{bmatrix}x^{i}$，上面式子斯特林反演。

题

[省选联考 2020 A 卷] 组合数问题

拆式子里的幂没啥用，把 $f$ 拆成下降幂多项式，化一下式子发现可以二项式定理合并，那就 $\mathcal O(m^2)$ 了。