目录
斯特林数
第一类斯特林数
定义
第一类斯特林数 $\begin{bmatrix}n\\ k\end{bmatrix}$ 表示将 $n$ 个不同元素构成 $m$ 个圆排列的方案。
性质一
$$\begin{bmatrix}n\\ k\end{bmatrix}=\begin{bmatrix}n-1\\ k-1\end{bmatrix}+(n-1)\begin{bmatrix}n-1\\ k\end{bmatrix}$$
考虑新加入的数 $n$，要么单独成环，要么插入到其他环中，其中插入方式有 $n-1$ 种。
性质二
$$x^{\overline n}=\sum_{i=0}^n \begin{bmatrix}n\\ i\end{bmatrix}x^i$$
其中 $x^{\overline n}$ 表示上升幂。
考虑归纳证明，有
$$x^{\overline {n+1}}=x^{\overline n}(x+n)=(x+n)\sum_{i=0}^n \begin{bmatrix}n\\ i\end{bmatrix}x^i=\sum_{i=0}^{n+1} \left(\begin{bmatrix}n\\ i-1\end{bmatrix}+n\begin{bmatrix}n\\ i\end{bmatrix}\right)x^i=\sum_{i=0}^{n+1} \begin{bmatrix}n+1\\ i\end{bmatrix}x^i$$
性质三
$$x^{\underline n}=\sum_{i=0}^n \begin{bmatrix}n\\ i\end{bmatrix}(-1)^{n-i}x^i$$
其中 $x^{\underline n}$ 表示下降幂。
考虑归纳证明，有
$$x^{\underline {n+1}}=x^{\underline n}(x-n)=(x-n)\sum_{i=0}^n \begin{bmatrix}n\\ i\end{bmatrix}(-1)^{n-i}x^i=\sum_{i=0}^{n+1} \left(-\begin{bmatrix}n\\ i-1\end{bmatrix}-n\begin{bmatrix}n\\ i\end{bmatrix}\right)(-1)^{n-i}x^i=\sum_{i=0}^{n+1} \begin{bmatrix}n+1\\ i\end{bmatrix}(-1)^{n+1-i}x^i$$
运算
第一类斯特林数$\cdot$行
$$\begin{bmatrix}n\\ i\end{bmatrix}(0\le i\le n)$$
考虑倍增法，假设已知 $x^{\overline n}$，显然可以 $O(n)$ 计算出 $x^{\overline {n+1}}=(x+n)x^{\overline n}$。
接下来考虑求解 $x^{\overline {2n}}$，有 $x^{\overline {2n}}=x^{\overline n}(x+n)^{\overline n}$。设 $x^{\overline n}=\sum_{i=0}^n a_ix^i$，于是有
$$(x+n)^{\overline n}=\sum_{i=0}^n a_i(x+n)^i=\sum_{i=0}^n a_i\sum_{j=0}^i{i\choose j}n^{i-j}x^j=\sum_{j=0}^n x^j\sum_{i=j}^n a_i{i\choose j}n^{i-j}$$
展开组合数，有
$$\sum_{j=0}^n x^j\sum_{i=j}^n a_i{i\choose j}n^{i-j}x^j=\sum_{j=0}^n \frac {x^j}{j!}\sum_{i=j}^n a_ii!\frac {n^{i-j}}{(i-j)!}=\sum_{j=0}^n \frac {x^j}{j!}\sum_{i=0}^{n-j} a_{i+j}(i+j)!\frac {n^i}{i!}$$
设 $b_i=a_ii!,c_i=\cfrac {n^{n-i}}{(n-i)!}$，于是有
$$\sum_{j=0}^n \frac {x^j}{j!}\sum_{i=0}^{n-j} a_{i+j}(i+j)!\frac {n^i}{i!}=\sum_{j=0}^n \frac {x^j}{j!}\sum_{i=0}^{n-j} b_{i+j}c_{n-i}$$
于是可以 $O(n\log n)$ 计算出 $(x+n)^{\overline n}$，最后与 $x^{\overline n}$ 卷积即可 $O(n\log n)$ 计算出 $x^{\overline {2n}}$。
总时间复杂度 $T(n)=T(\frac n2)+O(n\log n)$，于是 $T(n)=O(n\log n)$。
第一类斯特林数$\cdot$列
$$\begin{bmatrix}i\\ k\end{bmatrix}(0\le i\le n)$$
考虑只有一个圆排列的方案的 $\text{EGF}$，有 $F(x)=\sum_{i=1}^{\infty} (i-1)!\cfrac {x^i}{i!}$。
于是 $k$ 个圆排列的 $\text{EGF}$ 为 $\cfrac {F^k(x)}{k!}$，利用 $\text{Exp}$ 和 $\text{Ln}$ 可以 $O(n\log n)$ 计算。
第二类斯特林数
定义
第二类斯特林数 $\begin{Bmatrix}n\\ k\end{Bmatrix}$ 表示将 $n$ 个不同元素划分到 $m$ 个非空集的方案数。
性质一
$$\begin{Bmatrix}n\\ k\end{Bmatrix}=\begin{Bmatrix}n-1\\ k-1\end{Bmatrix}+k\begin{Bmatrix}n-1\\ k\end{Bmatrix}$$
考虑新加入的数 $n$，要么单独划分成一个集合，要么加入到其他集合中，其中加入方式有 $k$ 种。
性质二
$$x^n=\sum_{i=0}^n \begin{Bmatrix}n\\ i\end{Bmatrix}(-1)^{n-i}x^{\overline i}$$
其中 $x^{\overline i}$ 表示上升幂。
考虑归纳证明，有
$$x^{n+1}=x\sum_{i=0}^n \begin{Bmatrix}n\\ i\end{Bmatrix}(-1)^{n-i}x^{\overline i}=\sum_{i=0}^n \begin{Bmatrix}n\\ i\end{Bmatrix}(-1)^{n-i}\left(x^{\overline {i+1}}-ix^{\overline i}\right)=\sum_{i=0}^{n+1} \begin{Bmatrix}n+1\\ i\end{Bmatrix}(-1)^{n+1-i}x^{\overline i}$$
性质三
$$x^n=\sum_{i=0}^n \begin{Bmatrix}n\\ i\end{Bmatrix}x^{\underline i}$$
其中 $x^{\underline i}$ 表示下降幂。
考虑归纳证明，有
$$x^{n+1}=x\sum_{i=0}^n \begin{Bmatrix}n\\ i\end{Bmatrix}x^{\underline i}=\sum_{i=0}^n \begin{Bmatrix}n\\ i\end{Bmatrix}\left(x^{\underline {i+1}}+ix^{\underline i}\right)=\sum_{i=0}^{n+1} \begin{Bmatrix}n+1\\ i\end{Bmatrix}x^{\underline i}$$
运算
第二类斯特林数$\cdot$行
$$\begin{Bmatrix}n\\ i\end{Bmatrix}(0\le i\le n)$$
考虑将 $n$ 个数装入 $k$ 个盒子，有 $k^n$ 种放法。其中 $i$ 个盒子中有球的方案数为 $i!{k\choose i}\begin{Bmatrix}n\\ i\end{Bmatrix}$
于是 $k^n=\sum_{i=0}^k i!{k\choose i}\begin{Bmatrix}n\\ i\end{Bmatrix}$。设 $f(i)=i^n,g(i)=i!\begin{Bmatrix}n\\ i\end{Bmatrix}$，于是有 $f(k)=\sum_{i=0}^k {k\choose i}g(i)$。根据二项式反演
$$k!\begin{Bmatrix}n\\ k\end{Bmatrix}=\sum_{i=0}^k (-1)^{k-i}{k\choose i}i^n=k!\sum_{i=0}^k \cfrac{(-1)^{k-i}}{(k-i)!}\cfrac{i^n}{i!}$$
于是 $O(n\log n)$ 卷积即可。
第二类斯特林数$\cdot$列
$$\begin{Bmatrix}i\\ k\end{Bmatrix}(0\le i\le n)$$
考虑只有一个非空集合的方案的 $\text{EGF}$，有 $F(x)=\sum_{i=1}^{\infty} \cfrac {x^i}{i!}$。
于是 $k$ 个非空集合的 $\text{EGF}$ 为 $\cfrac {F^k(x)}{k!}$，利用 $\text{Exp}$ 和 $\text{Ln}$ 可以 $O(n\log n)$ 计算。
练习题
习题一
题意
$$\sum_{i=0}^n\sum_{j=0}^i\begin{Bmatrix}i\\ j\end{Bmatrix}\times 2^j\times j!$$
题解
首先 $\begin{Bmatrix}i\\ j\end{Bmatrix}=0(j\gt i)$，于是
$$\sum_{i=0}^n\sum_{j=0}^i\begin{Bmatrix}i\\ j\end{Bmatrix}\times 2^j\times j!=\sum_{i=0}^n\sum_{j=0}^n\begin{Bmatrix}i\\ j\end{Bmatrix}\times 2^j\times j!=\sum_{j=0}^n2^j\times j!\sum_{i=0}^n\begin{Bmatrix}i\\ j\end{Bmatrix}$$
直接展开第二类斯特林数，有
$$\sum_{j=0}^n2^j\times j!\sum_{i=0}^n\begin{Bmatrix}i\\ j\end{Bmatrix}=\sum_{j=0}^n2^j\times j!\sum_{i=0}^n\sum_{k=0}^j \frac{(-1)^{j-k}}{(j-k)!}\frac{k^i}{k!}=\sum_{j=0}^n2^j\times j!\sum_{k=0}^j \frac{(-1)^{j-k}}{(j-k)!}\frac{k^{n+1}-1}{k!(k-1)}$$
需要注意 $k=0$ 时 $\cfrac{k^{n+1}-1}{k!(k-1)}=0$；$k=1$ 时 $\cfrac{k^{n+1}-1}{k!(k-1)}=n+1$。直接卷积即可，总时间复杂度 $O(n\log n)$。
