斯特林数 学习笔记
一份简要的斯特林数学习笔记. 从原博客迁移而来.
第二类斯特林数（斯特林子集数）
\(\begin{Bmatrix}n \\ k\end{Bmatrix}\)，表示将 \(n\) 个两两不同的元素，划分为 \(k\) 个互不区分的非空集合的方案数。
有递推式 \(\begin{Bmatrix}n \\ k\end{Bmatrix}=k\cdot \begin{Bmatrix}n-1 \\ k\end{Bmatrix}+\begin{Bmatrix}n-1 \\ k-1\end{Bmatrix},\begin{Bmatrix}n \\ 0\end{Bmatrix}=[n=0]\)。
同时还有通项公式
\[ \begin{Bmatrix}n \\ k\end{Bmatrix}=\sum_{i=0}^k\dfrac{(-1)^{k-i}i^n}{(k-i)!i!} \]
证明：
考虑这样一个问题：将 \(n\) 个物品涂成 \(k\) 种颜色，我们用两种方法计算它的方案数：
\[ k^n=\sum_{i=0}^k\binom{k}{i}\begin{Bmatrix}n \\ i\end{Bmatrix}i! \]
左边是显然的。右边是枚举用几种颜色涂。（注意到第二类斯特林数不允许空集）
做一个二项式反演，得到
\[ \begin{Bmatrix}n \\ k\end{Bmatrix}k!=\sum_{i=0}^k(-1)^{k-i}\binom{k}{i}i^n \]
稍加整理就能得到结论。
第一类斯特林数（斯特林轮换数）
\(\begin{bmatrix}n \\ k\end{bmatrix}\)，将 \(n\) 个两两不同的元素，划分为 \(k\) 个互不区分的非空轮换的方案数。
有递推式 \(\begin{bmatrix}n \\ k\end{bmatrix}=(n-1)\begin{bmatrix}n-1 \\ k\end{bmatrix}+\begin{bmatrix}n-1 \\ k-1\end{bmatrix},\begin{bmatrix}n \\ 0\end{bmatrix}=[n=0]\)
它没有实用的通项公式。
斯特林数的计算
显然，两种斯特林数都可以 \(O(nk)\) 求。
第二类斯特林数 · 行
根据通项公式
\[ \begin{Bmatrix}n \\ k\end{Bmatrix}=\sum_{i=0}^n\dfrac{(-1)^{k-i}i^n}{(k-i)!i!} \]
于是设 \(f_n=\sum_{k\ge 0}\begin{Bmatrix}n \\ k\end{Bmatrix}x^k,g_n=\sum_{k\ge 0}\dfrac{i^n}{i!}x^k\)，则 \(f_n=e^{-x}*g_n\)。
第二类斯特林数 · 列
先考虑把相同的集合变成不同的非空盒子，则最后答案需要除以 \(k!\)。
设一个非空盒子的 EGF（以物品数量为组合对象）为 \(G(x)\)，\(k\) 个非空盒子的 EGF 为 \(F(x)\)。故有
\[ G(x)=\sum_{i\ge 1} \dfrac{x^i}{i}=e^x-1,F(x)=G^k(x) \]
于是有
\[ \sum_{i\ge 0}\begin{Bmatrix}i \\ k\end{Bmatrix}\dfrac{x^i}{i!}=\dfrac{(e^x-1)^k}{k!} \]
直接多项式快速幂计算。
第一类斯特林数 · 行
设 \(f_n(x)=\sum_{i\ge 0}\begin{bmatrix}n \\ k\end{bmatrix}x^i\)，由递推式得到
\[ f_{n+1}(x)=(x+n)f_n(x) \]
得到
\[ f_n(x)=\prod_{i=0}^{n-1}(x+i)=x^{\overline n} \]
我们的任务转化为计算上升幂。可以通过分治 FFT 以 \(O(n\log^2n)\) 完成。
但是，也可以如下计算：
考虑倍增，\(f_{2n}(x)=x^{\overline{2n}}=x^{\overline {n}}(x+n)^{\overline{n}}=f_n(x)f_n(x+n)\)
下面为了方便表述，设 \(f_n(x)=\sum_{i\ge 0}a_ix^i\)
\[ \begin{aligned} f_n(x+n)=&\sum_{i=0}^na_i(x+n)^i \\=&\sum_{i=0}^na_i\sum_{j=0}^i\binom{i}{j}x^jn^{i-j} \\=&\sum_{j= 0}^n\dfrac{x^j}{j!}\sum_{i = j}^n\dfrac{n^{i-j}}{(i-j)!}a_ii! \end{aligned} \]
设 \(A_i=a_ii!,B_i=\dfrac{n^i}{i!}\)
故
\[ \begin{aligned} f_n(x+n)=&\sum_{j=0}^n\dfrac{x^j}{j!}\sum_{i=j}^nA(i)B(i-j) \\=&\sum_{j=0}^n\dfrac{x^j}{j!} \sum_{i=0}^{n-j}A(i+j)B(i) \end{aligned} \]
后面那部分显然可以卷积，于是再做个和、除以 \(j!\) 就可以得到 \(f_n(x+n)\)。
总复杂度 \(O(n\log n)\)。
第一类斯特林数 · 列
先写出单个轮换的EGF：
\[ f(x)=\sum_{i\ge 1}(i-1)!\dfrac{x^i}{i!}=\sum_{i\ge 1}\dfrac{x^i}{i}=\ln\dfrac{1}{1-x} \]
于是，\(k\) 个轮换的 EGF 即为
\[ \dfrac{f^k(x)}{k!} \]
做多项式快速幂即可。
阶乘幂与方幂的转化
根据上面第一类斯特林数的性质，有
\[ x^{\overline{n}}=\sum_{i=0}^n\begin{bmatrix} n \\ i\end{bmatrix}x^i \]
利用有符号第一类斯特林数，用类似的推导方法可以得到
\[ x^{\underline{n}}=\sum_{i=0}^n(-1)^{n-i}\begin{bmatrix}n \\ i\end{bmatrix}x^i \]
我们再看看怎么转化回去：
\[ x^n=\sum_{i=0}^n\begin{Bmatrix}n \\ i\end{Bmatrix}\binom{x}{i} i! \]
而 \(\binom{x}{i}i!=x^{\underline i}\)。
于是
\[ x^n=\sum_{i=0}^n\begin{Bmatrix}n \\ i\end{Bmatrix}x^{\underline i} \]
同样有方幂转上升幂
\[ x^n=\sum_{i=0}^n(-1)^{n-i}\begin{Bmatrix}n \\ i\end{Bmatrix}x^{\overline{i}} \]
这两个有符号斯特林数推出的式子，可以直接用上升幂和下降幂的相似性得到（它们展开后仅差一些负号）。
当然，这四个式子都可以数学归纳证明。
如何记忆呢？
将阶乘幂转化为方幂，使用第一类斯特林数（它的 OGF 决定了这一点）；
将方幂转化为阶乘幂，使用第二类斯特林数（它的 组合意义 决定了这一点）。
那么，什么时候添加 \((-1)^{n-i}\)？显然有 \(x^{\overline{n}}\ge x^n \ge x^{\underline{n}}\)，当将大的幂转化为小的幂的时候，需要添加负号。
斯特林反演
若
\[ g(n)=\sum_{i=0}^n\begin{Bmatrix}n \\ i\end{Bmatrix}f(i) \]
则
\[ f(n)=\sum_{i=0}^n(-1)^{n-i}\begin{Bmatrix}n \\ i\end{Bmatrix}g(i) \]
当然，把第一类和第二类反过来也对；根据反演的一般套路，改为枚举 \(j\ge i\) 也对。