记$x^{\overline{n}}=x(x+1)(x+2)\cdots(x+n-1)$xn=x(x+1)(x+2)⋯(x+n−1)，$x^{\underline{n}}=x(x-1)(x-2)\cdots(x-n+1)$xn​=x(x−1)(x−2)⋯(x−n+1)。

第一类斯特林数

定义为$x^{\overline{n}}$xn的$m$m次项系数，即$x^{\overline{n}}=\sum_{i=0}^n\begin{bmatrix}n\\i\end{bmatrix}x^i$xn=∑i=0n​[ni​]xi。组合意义为将$n$n个数分为$m$m个环的方案数。

可在$O(n\log n)$O(nlogn)内求$\begin{bmatrix}n\\i\end{bmatrix}$[ni​]。

第二类斯特林数

组合意义为将$n$n个数分为$m$m个无区别组的方案数。定义为$x^n=\sum_{i=0}^n\begin{Bmatrix}n\\i\end{Bmatrix}x^{\underline{i}}$xn=∑i=0n​{ni​}xi​。

可以用容斥原理求斯特林数，枚举几个组为空即可。公式为$\begin{Bmatrix}n\\m\end{Bmatrix}=\frac{1}{m!}\sum_{i=0}^m(-1)^i\binom{m}{i}(m-i)^n${nm​}=m!1​i=0∑m​(−1)i(im​)(m−i)n

幂的转换

由各种方法可得：
$x^n=\sum_{i=0}^n\begin{Bmatrix}n\\i\end{Bmatrix}x^{\overline{i}}(-1)^{n-i}$xn=i=0∑n​{ni​}xi(−1)n−i
$x^{\underline{n}}=\sum_{i=0}^n\begin{bmatrix}n\\i\end{bmatrix}x^i(-1)^{n-i}$xn​=i=0∑n​[ni​]xi(−1)n−i
以上两个定义式和两个幂的转换公式可简记为正降卷升，一归二歧（“正”指挨个乘）。

把两个式子拼起来可得斯特林反演。把一个式子带到另一个里去可得翻转公式。

练习题

幂和

$\begin{aligned} \sum_{i=1}^n i^k &=\sum_{i=1}^n\sum_{j=0}^k \begin{Bmatrix}k\\j\end{Bmatrix}i^{\underline j}\\ &=\sum_{j=0}^k\begin{Bmatrix}k\\j\end{Bmatrix}\sum_{i=1}^ni^{\underline j}\\ &=\sum_{j=0}^k\begin{Bmatrix}k\\j\end{Bmatrix}j!\sum_{i=1}^n{i\choose j}\\ &=\sum_{j=0}^k\begin{Bmatrix}k\\j\end{Bmatrix}j!{n+1\choose j+1}\\ \end{aligned}$i=1∑n​ik​=i=1∑n​j=0∑k​{kj​}ij​=j=0∑k​{kj​}i=1∑n​ij​=j=0∑k​{kj​}j!i=1∑n​(ji​)=j=0∑k​{kj​}j!(j+1n+1​)​

*2018.12