下降幂和上升幂
\(x\) 的 \(k\) 次下降幂记作 \(x^{\underline{k}}\)，表示的是 \(\prod_{i=0}^{k-1}(x-i)\) 。
\(x\) 的 \(k\) 次上升幂记作 \(x^{\overline{k}}\)，表示的是 \(\prod_{i=0}^{k-1}(x+i)\)。
第一类斯特林数
\(\begin{bmatrix} n \\ i \end{bmatrix}\) 表示第一类斯特林数，它的意义是把 \(n\) 个有标号的点放入 \(i\) 个圆排列的方案数。圆排列不能为空。
第一类斯特林数有一个递推式，\(\begin{bmatrix} n \\ i \end{bmatrix}=\begin{bmatrix} n-1 \\ i \end{bmatrix}\times(n-1)+\begin{bmatrix} n-1 \\ i-1 \end{bmatrix}\)，即考虑最后一个点放在哪里，要么是新开一个圆排列，要么就跟在某个数的后面。
第二类斯特林数
\(\begin{Bmatrix}n \\ i\end{Bmatrix}\) 表示第二类斯特林数，它的意义是把 \(n\) 个有标号的点放入 \(i\) 个无标号的集合的方案数。集合不能为空。
第二类斯特林数有一个递推式，\(\begin{Bmatrix}n \\ i\end{Bmatrix}=\begin{Bmatrix}n-1 \\ i\end{Bmatrix}\times i+\begin{Bmatrix}n-1 \\ i-1\end{Bmatrix}\)，即考虑最后一个点放在哪里，要么是新开一个集合，要么就放在之前的某个集合里面。
斯特林数和自然幂、下降幂、上升幂的关系
对于自然幂和下降幂，有这么一个式子。\(n^m=\sum_{i=0}^m\begin{Bmatrix}m \\ i\end{Bmatrix}n^{\underline{i}}\)。
考虑从组合意义来理解它。\(n^m\) 相当于是把 \(m\) 个有标号的球放入 \(n\) 个有标号的盒子的方案数，考虑枚举有多少个盒子有球，假设为 \(i\)，那么选盒子的方案就是 \(\begin{pmatrix}n \\ i\end{pmatrix}\)，然后把 \(m\) 个球放到这 \(i\) 个盒子里面去，方案是 \(\begin{Bmatrix}m \\ i\end{Bmatrix}\)，而因为第二类斯特林数的集合是无标号的，这里是有标号的，所以最后需要乘上一个 \(i!\)，然后把组合数展开，就得到上面的那个式子。
对于自然幂和上升幂，有这么一个式子。\(n^{\overline{m}}=\sum_{i=0}^m\begin{bmatrix}m \\ i\end{bmatrix}n^i\) 。
考虑用数学归纳法来证明它，对于 \(m=0\) 式子显然成立，假设现在已经证明对于 \(m\leq k-1\) 式子成立，需要证明对于 \(m=k\) 式子成立。
\[ \begin{split} n^{\overline{k}}&=n^{\overline{k-1}}\times(n+k-1)\\ &=n^{\overline{k-1}}\times n+n^{\overline{k-1}}\times(k-1)\\ &=\sum_{i=0}^{k-1}\begin{bmatrix}k-1 \\ i\end{bmatrix}n^{i+1}+\sum_{i=0}^{k-1}(k-1)\begin{bmatrix}k-1 \\ i\end{bmatrix}n^i~~~~~~\\ &=\sum_{i=1}^{k-1}\begin{bmatrix}k-1 \\ i-1\end{bmatrix}n^{i}+\sum_{i=0}^{k-1}(k-1)\begin{bmatrix}k-1 \\ i\end{bmatrix}n^i~~~~~~~~~\\ &=\sum_{i=0}^k\begin{bmatrix}k \\ i\end{bmatrix}n^i \end{split} \]
故可以证明原式子成立。
斯特林反演
反转公式 I
\(x^{\overline{k}}=(-1)^k(-x)^{\underline{k}}\)，\(x^{\underline{k}}=(-1)^k(-x)^{\overline{k}}\)。
这两个式子把它们拆开就可以证明相等了。
反转公式 II
\(\sum_{i=m}^n(-1)^{n-i}\begin{bmatrix}n \\ i\end{bmatrix}\begin{Bmatrix}i \\ m\end{Bmatrix}=[m==n]\)
\(\sum_{i=m}^n(-1)^{n-i}\begin{Bmatrix}n \\ i\end{Bmatrix}\begin{bmatrix}i \\ m\end{bmatrix}=[m==n]\)
对于第二个证明如下： \[ \begin{split} n^m&=\sum_{i=0}^m\begin{Bmatrix}m \\ i\end{Bmatrix}n^{\underline{i}}\\ &=\sum_{i=0}^m\begin{Bmatrix}m \\ i\end{Bmatrix}(-1)^i(-n)^{\overline{i}}\\ &=\sum_{i=0}^m\begin{Bmatrix}m \\ i\end{Bmatrix}(-1)^i\sum_{j=0}^i\begin{bmatrix} i \\ j \end{bmatrix}(-n)^j\\ &=\sum_{j=0}^mn^j\sum_{i=j}^m\begin{Bmatrix}m \\ i\end{Bmatrix}\begin{bmatrix} i \\ j \end{bmatrix}(-1)^{i-j}\\ \end{split} \] 把 \(n\) 看成是一个未知数时，对于一个多项式 \(\sum a_in^i\)，\(n^m\) 可以且仅可以用 \(a_mn^m\) 来表示，所以最后的式子只有 \(j=m\) 的时候为 \(1\)，否则为 \(0\)。
对于第一个式子，有 \(n^{\overline{m}}=\sum_{i=0}^m\begin{bmatrix}m \\ i\end{bmatrix}(-1)^i(-n)^i\)，把后面的自然幂展开成下降幂，然后再推一推就可以类似于上面讨论证明。
斯特林反演公式
\(f(n)=\sum_{i=0}^n\begin{Bmatrix}n \\ i\end{Bmatrix}g(i)\Leftrightarrow g(n)=\sum_{i=0}^n(-1)^{n-i}\begin{bmatrix}n \\ i\end{bmatrix}f(i)\)。
和二项式反演类似，只需要证明一个方向，另一个方向显然成立。
正向证明如下： \[ \begin{split} g(n)&=\sum_{i=0}^n[i==n]g(i)\\ &=\sum_{i=0}^n\sum_{j=i}^n(-1)^{n-j}\begin{bmatrix}n \\ j\end{bmatrix}\begin{Bmatrix}j \\ i\end{Bmatrix}g(i)\\ &=\sum_{j=0}^n(-1)^{n-j}\begin{bmatrix}n \\ j\end{bmatrix}\sum_{i=0}^j\begin{Bmatrix}j \\ i\end{Bmatrix}g(i)\\ &=\sum_{j=0}^n(-1)^{n-j}\begin{bmatrix}n \\ j\end{bmatrix}f(j) \end{split} \]
第一类斯特林数求自然数幂和
设 \(\sum_{i=1}^n i^k\) 为 \(S_k(n)\)。 \[ \begin{split} &\because n^m=\sum_{i=0}^m\begin{Bmatrix}m \\ i\end{Bmatrix}n^{\underline{i}}\\ &\therefore n^{\underline{m}}=\sum_{i=0}^m(-1)^{m-i}\begin{bmatrix}m \\ i\end{bmatrix}n^i\\ &\therefore n^m=n^{\underline{m}}-\sum_{i=0}^{m-1}(-1)^{m-i}\begin{bmatrix}m \\ i\end{bmatrix}n^i\\ &\therefore \sum_{n=1}^X n^m=\sum_{n=1}^Xn^{\underline{m}}-\sum_{n=1}^X\sum_{i=0}^{m-1}(-1)^{m-i}\begin{bmatrix}m \\ i\end{bmatrix}n^i\\ &\begin{split} \therefore S_m(X)&=m!\sum_{n=1}^X\begin{pmatrix}n \\ m\end{pmatrix}-\sum_{i=0}^{m-1}(-1)^{m-i}\begin{bmatrix}m \\ i\end{bmatrix}\sum_{n=1}^Xn^i\\ &=m!\begin{pmatrix}X+1 \\ m+1\end{pmatrix}-\sum_{i=0}^{m-1}(-1)^{m-i}\begin{bmatrix}m \\ i\end{bmatrix}S_i(X)\\ &=\frac{(X+1)^{\underline{m+1}}}{m+1}-\sum_{i=0}^{m-1}(-1)^{m-i}\begin{bmatrix}m \\ i\end{bmatrix}S_i(X)~\\ \end{split} \end{split} \] 故 \(S_m(X)\) 可以在 \(m^2\) 的时间复杂度内求得，且不要求模数是质数。
快速求两类斯特林数
第一类斯特林数·行
我们知道 \(x^{\overline n}=\prod \begin{bmatrix}n \\ i\end{bmatrix}x^i\) ，那直接算出 \(x(x+1)(x+2)...(x+n-1)\) 就行了，分治 FFT 解决，时间复杂度 \(n\log^2 n\)。
但是这样似乎有亿点点慢，考虑优化。
设 \(F_n(x)\) 表示 \(x^{\overline n}\) 形成的多项式，那么 \(x^{\overline {2n} }\) 的多项式是等于 \(F_n(x)\times F_n(x+n)\) 的，用二项式定理把后者展开，会发现是一个减法卷积的形式，所以可以在 \(n\log n\) 的时间内求得 \(F_{2n}\)，倍增的处理就可以做到 \(n\log n\)。
第一类斯特林数·列
考虑用生成函数解决这个问题。
设由若干个数形成 \(k\) 个圆排列的生成函数是 \(F_k\)，这恰好是我们要求的。
因为用来形成圆排列的数是可以区分的，所以这个生成函数表示的应该是排列而不是组合（或者可以这么理解，设 \(x_1\) 个数形成 \(y_1\) 个圆排列的方案数为 \(z_1\)，\(x_2\) 个数形成 \(y_2\) 个圆排列的方案数为 \(z_2\)，那么由 \(x_1+x_2\) 个数形成 \(y_1+y_2\) 个圆排列的方案数并不是 \(z_1\times z_2\)，而需要额外乘上一个组合数 \(\begin{pmatrix}x_1+x_2 \\ x_1\end{pmatrix}\)），故 \(F_k\) 是指数型生成函数。
假设我们现在已经知道了 \(F_1\)，那么 \(F_k=\frac{F_1^k}{k!}\)，即先生成 \(k\) 个有序的圆排列，然后把序去掉。
\(F_1\) 很容易知道，即 \(\sum_{i>0}(i-1)!\frac{x^i}{i!}\) 。化简一下就是 \(\sum_{i>0} \frac{x^i}{i}\) 。
那么我们就可以通过多项式快速幂得到 \(F_k\)。
至此我们就已经可以得到某一列的第一类斯特林数的值，但是这个式子有那么一点点丑，考虑把它美化一下。
仔细观察一下 \(\sum_{i>0} \frac{x^i}{i}\) 这个式子，会发现似乎这个东西有亿点点眼熟。先把它求导，得到 \(\sum_{i\geq 0}x^i=\frac{1}{1-x}\)，再积分，就得到了 \(-\ln(1-x)\)（实际上，博主是通过对 \(-\ln(1-x)\) 求导积分得到 \(\sum_{i>0} \frac{x^i}{i}\) 的）。
所以 \(F_k=\frac{(-\ln(1-x))^k}{k!}\) 。（虽然这并不能简化运算量，甚至还加大了难度（因为需要手动展开 \(\ln\)），但是它变得好看了）。
第二类斯特林数·行
第二类斯特林数有一个人尽皆知的式子 \(n^m=\sum_{i=1}^n\begin{pmatrix}n \\ i \end{pmatrix}\begin{Bmatrix}m \\ i \end{Bmatrix}i!\) 。
设 \(g(n)=n^m,f(i)=\begin{Bmatrix}m \\ i \end{Bmatrix}i!\)，对原式使用二项式反演得到 \(\begin{Bmatrix}m \\ n \end{Bmatrix}n!=\sum_{i=1}^n(-1)^{n-i}\begin{pmatrix}n \\ i \end{pmatrix}i^m\) 。把组合数展开，不难发现右边是一个卷积的形式，所以可以通过 FFT 在 \(n \log n\) 的时间内求得第二类斯特林数的一行。
第二类斯特林数·列
同第一类斯特林数一样，用生成函数解决这个问题。
设把若干个数分到 \(k\) 个集合的生成函数是 \(F_k\)，这恰好是我们要求的。
同样的，用分析第一类斯特林数的方法来分析第二类斯特林数，可以发现 \(F_k\) 也是指数型生成函数（可以参考上文理解）。
假设我们知道了 \(F_1\)，那么 \(F_k=\frac{F_1^k}{k!}\)，即先形成 \(k\) 个有序的集合，然后把序去掉。
\(F_1\) 很容易知道，即 \(\sum_{i>0}\frac{x^i}{i!}\) ，特别的，它的第 \(0\) 项为 \(0\)。
这样我们就可以通过多项式快速幂得到 \(F_k\)。
然后这个式子还不够美观，考虑把它美化一下。
根据常识，\(\sum_{i>0}\frac{x^i}{i!}=e^x-1\)。
所以 \(F_k=\frac{(e^x-1)^k}{k!}\) 。
贝尔数
定义：对 \(n\) 个数集合划分的数目。符号 \(B_n\)。
根据定义不难得到 \(B_n\) 是第二类斯特林数第 \(n\) 行的和。
递推式
枚举第 \(n\) 个数所在集合大小，有 \(B_n=\sum_{i=0}^{n-1}\begin{pmatrix}n-1 \\ i \end{pmatrix}B_{n-i-1}\)。因为 \(\begin{pmatrix}n \\ i \end{pmatrix}=\begin{pmatrix}n \\ n-i \end{pmatrix}\)，为了美观一般把递推式写成 \(B_n=\sum_{i=0}^{n-1}\begin{pmatrix}n-1 \\ i \end{pmatrix}B_i\) 。
生成函数
设 \(B_n\) 的生成函数为 \(G\)。
上文中，对于第二类斯特林数的第 \(k\) 列，有 \(F_k=\frac{(e^x-1)^k}{k!}\)，其中第 \(n\) 项是 \(\begin{Bmatrix}n \\ k \end{Bmatrix}\)。那么 \(\sum_{k\geq 0}F_k\) 中第 \(n\) 项就是第 \(n\) 行斯特林数的和，就是 \(G\)。
\(G=\sum_{k\geq 0}F_k=\sum_{k\geq 0}\frac{(e^x-1)^k}{k!}=e^{e^x-1}\) 。