斯特林数
第一类斯特林数
第一类斯特林数$s(n,k)$
定义为下面公式的系数：
\[x^{\underline{n}}=\sum_{k=0}^n s(n,k) x^k\]定义无符号斯特林数为：
\[c(n,k)= \left[ \begin{array}{c} n\\ k \end{array} \right] =|s(n,k)|\]可以利用下面公式通过无符号斯特林数计算有符号斯特林数：
\[s(n,k)=(-1)^{n-k}c(n,k)\]无符号斯特林数满足：
\[x^{\overline{n}}=\sum_{k=0}^n c(n,k) x^k\]无符号斯特林数的递推关系为：
\[\left[ \begin{array}{c} n+1\\ k \end{array} \right]= n \left[ \begin{array}{c} n\\ k \end{array} \right] + \left[ \begin{array}{c} n\\ k-1 \end{array} \right]\]有符号斯特林数的递推公式为：
\[s(n+1,k)=-ns(n,k)+s(n,k-1)\]无符号斯特林数的组合意义是：将$n$个元素分成$k$个环（都不空）的方案数为 \(\left[ \begin{array}{c} n\\ k \end{array} \right]\)
生成函数
对于给定的n，设$F^{(n)}$为第一类斯特林数的生成函数，即 \(F^{(n)}_i= \left[ \begin{array}{c} n\\ i \end{array} \right]\) 。由于无符号斯特林数满足：
\[x^{\overline{n}}=\sum_{k=0}^n c(n,k) x^k\]因此可以直接得到：
\[F^{(n)}(x)=x^{\overline{n}}=\prod_{i=0}^{n-1}(x+i)\]乘积符号内是n个多项式，我们可以用分治+FFT在$O(n(\log_2n)^2)$时间复杂度内计算得到。下面介绍用倍增+FFT在$O(n\log_2n)$的算法。
容易发现下面公式成立：
\[F^{(n)}(x)= \left\{ \begin{array}{ll} F^{(\frac{n}{2})}(x)F^{(\frac{n}{2})}(x+\frac{n}{2})&, 2|n\\ (x+n-1)F^{n-1}(x)&,else \end{array} \right.\]我们可以用倍增算法来解决。下面给出计算$F^{(n)}(x+n)$的方法：
\[\begin{aligned} &F^{(n)}(x+n)\\ =&\sum_{i=0}^nF^{(n)}_i(x+n)^i\\ =&\sum_{i=0}^nx^i\sum_{j=i}^nF^{(n)}_jn^{j-i}{j\choose i}\\ =&\sum_{i=0}^nx^i\sum_{j=i}^nF^{(n)}_jn^{j-i}\frac{j!}{i!(j-i)!}\\ =&\sum_{i=0}^n\frac{1}{i!}x^i\sum_{j=i}^n[F^{(n)}_jj!][\frac{n^{j-i}}{(j-i)!}]\\ \end{aligned}\]可以看出后面项是等差卷积，可以用FFT直接得到。
总的时间复杂度为
\[T(n)=T(\frac{n}{2})+O(n\log_2n)=O(n\log_2n)\]第二类斯特林数
第二类斯特林数 \(\begin{Bmatrix} n\\ k \end{Bmatrix}\) 的定义为下面公式的系数：
\[x^n = \sum_{k=0}^n \begin{Bmatrix} n\\ k \end{Bmatrix}x^{\underline{k}}\]第二类斯特林数的递推公式为：
\[\begin{Bmatrix} n+1\\ k \end{Bmatrix}= k \begin{Bmatrix} n\\ k \end{Bmatrix}+ \begin{Bmatrix} n\\ k-1 \end{Bmatrix}\]第二类斯特林数的直接计算公式为：
\[\begin{Bmatrix} n\\ k \end{Bmatrix}= \frac{1}{k!}\sum_{i=0}^k(-1)^i{k\choose i}(k-i)^n\]第二类斯特林数 \(\begin{Bmatrix} n\\ k \end{Bmatrix}\) 的可以用来表示将n个元素拆分成k个非空子集的方法数。
根据定义可以发现下面公式的成立：
\[\sum_{m=0}^n{n\choose m}\begin{Bmatrix} m\\ k \end{Bmatrix}=(k+1)\begin{Bmatrix} n\\ k+1 \end{Bmatrix}+\begin{Bmatrix} n\\ k \end{Bmatrix}\]生成函数
对于某个n，以及所有$0\leq k \leq n$计算 \(\begin{Bmatrix} n\\ k \end{Bmatrix}\) ，可以利用快速卷积在 \(O(n\log_2n)\) 的时间复杂度内实现。
观察下面第二类斯特林数的直接计算公式：
\[\begin{Bmatrix} n\\ k \end{Bmatrix}= \frac{1}{k!}\sum_{i=0}^k(-1)^i{k\choose i}(k-i)^n\\ =\sum_{i=0}^k(-1)^i(k-i)^n\frac{1}{i!(k-i)!}\\ =\sum_{i=0}^k[(-1)^i\frac{1}{i!}][(k-i)^n\frac{1}{(k-i)!}]\]记第二类斯特林数的生成函数为$F$， \(F_k=\begin{Bmatrix}n\\k\end{Bmatrix}\) 那么我们可以推出$F$是另外两个多项式的卷积：
\[F(x)=[\sum_{i=0}^n(-1)^i\frac{1}{i!}] \times [\sum_{i=0}^ni^n\frac{1}{i!}]\]因此利用快速卷积算法就可以得到第二类斯特林数的生成函数。
斯特林反演
反演内容：
\[f(n)=\sum_{k=0}^n \begin{Bmatrix}n\\k\end{Bmatrix}g(k) \Leftrightarrow g(n)= \sum_{k=0}^n s(n,k)f(k)= \sum_{k=0}^n (-1)^{n-k} \left[ \begin{array}{c} n\\ k \end{array}\right]f(k)\]以及反转公式：
\[\sum_{k=m}^n (-1)^{n-k}\begin{bmatrix}n\\k\end{bmatrix} \begin{Bmatrix}k\\m\end{Bmatrix}=[m=n]\\ \sum_{k=m}^n (-1)^{n-k}\begin{Bmatrix}n\\k\end{Bmatrix} \begin{bmatrix}k\\m\end{bmatrix}=[m=n]\]