第一类斯特林数（斯特林轮换数）

定义：

记为 $\begin{bmatrix}n\\ m\end{bmatrix}$ 或 $S_1(n,m)$ ，计算将 $n$ 个元素排成 $m$ 个轮换的方案数。

性质：

递推公式： $$ S_1(n,m)=S_1(n-1,m-1)+(n-1)S_1(n-1,m) $$ 也可以说成是恰好包含 $m$ 个轮换的 $n$ 个元素的排列个数，故： $$ \sum_{i=0}^n\begin{bmatrix}n\\i\end{bmatrix}=n! $$ 第一类斯特林数的生成函数为： $$ \sum_{i=0}^n\begin{bmatrix}n\\i\end{bmatrix}x^i=\prod_{i=0}^{n-1}(x+i) $$ 考虑乘上一个 $(x+n)$ 时整个函数每一项的变化就可以得到这个式子。

一个特殊值： $$ \begin{bmatrix}n\\2\end{bmatrix}=(n-1)!H_{n-1} $$ $H$ 是调和数： $$ H_n=\sum_{i=1}^n\frac 1 i $$ 证明大概就是枚举第一个元素所在轮换的大小： $$ \begin{align} \begin{bmatrix}n\\2\end{bmatrix}&=\sum_{x=1}^{n-1}\binom{n-1}{x-1}(x-1)!(n-x-1)!\\ &=\sum_{x=1}^{n-1}\frac{(n-1)!}{(x-1)!(n-x)!}(x-1)!(n-x-1)!\\ &=(n-1)!H_{n-1} \end{align} $$

预处理方法：

由上面那个式子有一个直接的 $O(n\log^2n)$ 的分治 $+FFT$ 的做法，就是分治到区间 $[l,r]$ 时计算 $\begin{align}\prod_{i=l}^r(x+i)\end{align}$ 的值，然后每次把两边用 $FFT$ 卷积起来。

还有一种 $O(n\log n)$ 的倍增方法。

还是利用生成函数，加入我们现在已经知道了 $S_n$ 的生成函数，我们想求 $S_{2n}$ 的生成函数。考虑求出： $$ \prod_{i=n}^{2n-1}(x+i) $$ 然后再乘起来就行了。 $$ \begin{align} &\prod_{i=n}^{2n-1}(x+i)\\ =&\prod_{i=0}^{n-1}(x+i+n)\\ \end{align} $$

因此我们可以把 $x=x+n$ 代入 $S_n(x)$ ，也就是： $$ \begin{align} &\sum_{i=0}^nf_i(x+n)^i\\ =&\sum_{i=0}^nf_i\sum_{j=0}^i\binom ijx^jn^{i-j}\\ =&\sum_{j=0}^n\sum_{i=j}^nf_i\frac{i!}{j!(i-j)!}x^jn^in^{-j}\\ =&\sum_{j=0}^n\frac1{n^jj!}\bigg(\sum_{i=j}^n\frac{f_ii!n^i}{(i-j)!}\bigg)x^j\\ =&\sum_{j=0}^n\frac1{n^jj!}\bigg(\sum_{i=j}^n\frac{f_ii!n^i}{(i-j)!}\bigg)x^j\\ \end{align} $$ 设 $r[i]=f_{n-i}(n-i)!n^{n-i}$ ，那么： $$ \sum_{i=j}^n\frac{r[n-i]}{(i-j)!}=\sum_{i=0}^{n-j}\frac{r[n-j-i]}{i!} $$ 是一个卷积，可以 $FFT$ 求，时间复杂度 $O(n\log n)$ 。

第二类斯特林数（斯特林子集数）

定义：

记为 $\begin{Bmatrix}n\\ m\end{Bmatrix}$ 或 $S_2(n,m)$ ，计算将 $n$ 个元素排成 $m$ 个集合的方案数。

性质：

递推公式： $$ \begin{Bmatrix}n\\ m\end{Bmatrix}=\begin{Bmatrix}{n-1}\\ {m-1}\end{Bmatrix}+m\times \begin{Bmatrix}{n-1}\\ m\end{Bmatrix} $$ 第二类斯特林数的前缀和就是贝尔数（集合划分数）： $$ \sum_{i=0}^n\begin{Bmatrix}n\\ i\end{Bmatrix}=Bell(n) $$ 展开式： $$ \begin{Bmatrix}n\\ m\end{Bmatrix}=\frac 1{m!}\sum_{i=0}^mC^m_i(-1)^i(m-i)^n $$ 思路就是枚举有几个集合一定是空的，然后把它们容斥掉。 $$ x^k=\sum_{i=0}^k\begin{Bmatrix}k\\ i\end{Bmatrix}P^x_i=\sum_{i=0}^k\begin{Bmatrix}k\\ i\end{Bmatrix}C^x_ii! $$

预处理方法：

$$ \begin{align} \begin{Bmatrix}n\\ m\end{Bmatrix}&=\frac 1{m!}\sum_{i=0}^mC^m_i(-1)^i(m-i)^n\\ &=\sum_{i=0}^m\frac{(-1)^i}{i!}\frac{(m-i)^n}{(m-i)!} \end{align} $$

显然是一个卷积，预处理阶乘的逆元然后 $NTT$ 就可以 $O(n\log n)$ 预处理了。

经典应用：

求： $$ \sum_{i=0}^nC_i^ni^k $$ $n=10^9,k=10^6$

把原式展开可得： $$ \sum_{d=0}^n\sum_{i=0}^k\begin{Bmatrix}k\\ i\end{Bmatrix}C^d_ii!C^n_d $$ 交换求和号，会发现最后是一个： $$ \sum_{d=0}^nC^d_iC^n_d $$ 的形式，然后会发现： $$ \sum_{d=0}^nC^d_iC^n_d=C^n_i\sum_{d=0}^nC^{n-i}_{d-i}=C^n_i\sum_{d=0}^{n-i}C^{n-i}_d=C^n_i2^{n-i} $$ 然后只要预处理第二类斯特林数就可以 $O(k\log k)$ 求解了。

上升幂与下降幂：

$$ x^{\overline i}=x(x+1)\cdots (x+i-1)\\ x^{\underline i}=x(x-1)\cdots(x-i+1) $$

性质： $$ x^{\underline i}=(-1)^i(-x)^{\overline i}\\ x^{\overline i}=(-1)^i(-x)^{\underline i} $$

斯特林数与上升下降幂的关系：

斯特林数的本质是上升下降幂的表示系数和展开系数：

下降幂转通常幂： $$ x^n=\sum_{k=0}^n\begin{Bmatrix}n\\ m\end{Bmatrix}x^{\underline k} $$ 上升幂转通常幂： $$ x^n=\sum_{k=0}^n(-1)^{n-k}\begin{Bmatrix}n\\ m\end{Bmatrix}x^{\overline k} $$ 通常幂转上升幂： $$ x^{\overline n}=\sum_{k=0}^n\begin{bmatrix}n\\ k\end{bmatrix}x^k $$ 通常幂转下降幂： $$ x^{\underline n}=\sum_{k=0}^n(-1)^{n-k}\begin{bmatrix}n\\ k\end{bmatrix}x^k $$

斯特林数法求自然数幂和：

第一类斯特林数法：

$$ x^{\underline n}=\sum_{k=0}^n(-1)^{n-k}\begin{bmatrix}n\\ k\end{bmatrix}x^k\Longrightarrow x^k=\frac{x!}{(x-n)!}-\sum_{k=0}^{n-1}(-1)^{n-k}\begin{bmatrix}n\\ k\end{bmatrix}x^k $$

$$ \begin{align} F_n(k)&=\sum_{x=1}^nx^k\\ &=\sum_{x=1}^n\biggl(\frac{x!}{(x-n)!}-\sum_{k=0}^{n-1}(-1)^{n-k}\begin{bmatrix}n\\ k\end{bmatrix}x^k\biggr)\\ \end{align} $$

两类斯特林数之间的关系、反转公式和斯特林反演：

斯特林反演公式： $$ f[i]=\sum_{j=0}^i\begin{Bmatrix}i\\j\end{Bmatrix}g[j]\Longleftrightarrow g[i]=\sum_{j=0}^i(-1)^{i-j}\begin{bmatrix}i\\j\end{bmatrix}f[j] $$

贝尔数