第二类斯特林数$\left\{\begin{matrix}n\\m\end{matrix}\right\}$表示把含有$n$个不同的数的集合划分为$m$个非空子集的方案数

递推式$\left\{\begin{matrix}n\\m\end{matrix}\right\}=m\left\{\begin{matrix}n-1\\m\end{matrix}\right\}+\left\{\begin{matrix}n-1\\m-1\end{matrix}\right\}$，边界$\left\{\begin{matrix}n\\0\end{matrix}\right\}=[n=0]$，可以这样看：已经分好了$n-1$个数，第$n$个数可以单独分成一个子集，也可以分到之前的$m$个子集中（因为这些子集中有数，所以它们是不同的）

一个固定$n$的通项公式$\begin{align*}\left\{\begin{matrix}n\\m\end{matrix}\right\}=\dfrac1{m!}\sum\limits_{k=0}^m(-1)^k\binom mk(m-k)^n\end{align*}$，相当于从不管非空子集限制的方案（$m^n$）中容斥掉有$k$个空子集的方案

它具有卷积的形式（写成真·卷积应该是$\begin{align*}\left\{\begin{matrix}n\\m\end{matrix}\right\}=\sum\limits_{k=0}^m\dfrac{(-1)^k}{k!}\dfrac{(m-k)^n}{(m-k)!}\end{align*}$），可以用FFT在$O(m\log_2m)$的时间内算出$\left\{\begin{matrix}n\\1\end{matrix}\right\}\cdots\left\{\begin{matrix}n\\m\end{matrix}\right\}$

第二类斯特林数可以用于转化幂：$\begin{align*}x^n=\sum\limits_{k=1}^n\left\{\begin{matrix}n\\k\end{matrix}\right\}x^\underline k\end{align*}$，可以用归纳法证明

$\begin{align*}x^n&=x\sum\limits_{k=1}^{n-1}\left\{\begin{matrix}n-1\\k\end{matrix}\right\}x^\underline k\\&=\sum\limits_{k=1}^{n-1}\left\{\begin{matrix}n-1\\k\end{matrix}\right\}(x^\underline{k+1}+kx^\underline k)\\&=\sum\limits_{k=1}^n\left\{\begin{matrix}n-1\\k-1\end{matrix}\right\}x^\underline k+\sum\limits_{k=1}^n\left\{\begin{matrix}n-1\\k\end{matrix}\right\}kx^\underline k\\&=\sum\limits_{k=1}^n\left\{\begin{matrix}n\\k\end{matrix}\right\}x^\underline k\end{align*}$

（因为$x^\underline{k+1}=(x-k)x^\underline k$所以$xx^\underline k=x^\underline{k+1}+kx^\underline k$）

第一类斯特林数$\left[\begin{matrix}n\\m\end{matrix}\right]$表示把$n$个不同的数划分为$m$个非空轮换的方案数

递推式$\left[\begin{matrix}n\\m\end{matrix}\right]=(n-1)\left[\begin{matrix}n-1\\m\end{matrix}\right]+\left[\begin{matrix}n-1\\m-1\end{matrix}\right]$，边界$\left[\begin{matrix}n\\0\end{matrix}\right]=[n=0]$，可以这样看：已经分好了$n-1$个数，第$n$个数可以单独分成一个轮换，也可以分到之前的轮换中，我们把它插到每个轮换的每一个数后面都可以形成新的轮换，所以有$n-1$种方法

它的另一个定义是$\begin{align*}x^\underline n=\sum\limits_{k=0}^n(-1)^{n-k}\left[\begin{matrix}n\\k\end{matrix}\right]x^k\end{align*}$，用归纳法易证它满足上面的递推性质

$\begin{align*}x^\underline n&=(x-n+1)x^\underline{n-1}\\&=(x-n+1)\sum\limits_{k=0}^{n-1}(-1)^{n-1-k}\left[\begin{matrix}n-1\\k\end{matrix}\right]x^k\\&=\left(\sum\limits_{k=1}^n(-1)^{n-k}\left[\begin{matrix}n-1\\k-1\end{matrix}\right]x^k\right)+\left(\sum\limits_{k=0}^{n-1}(-1)^{n-k}(n-1)\left[\begin{matrix}n-1\\k\end{matrix}\right]x^k\right)\\&=\sum\limits_{k=0}^n(-1)^{n-k}\left((n-1)\left[\begin{matrix}n-1\\k\end{matrix}\right]+\left[\begin{matrix}n-1\\k-1\end{matrix}\right]\right)x^k\end{align*}$

好像没有通项，但是要求还是可以的，考虑计算$x^\underline n$的各项系数，我们采用分治的做法，先算$x^\underline n$和$(x-n)^\underline n$，然后做乘法求出$x^\underline{2n}$，我们可以在$O(n\log_2^2n)$的时间内算出$\left[\begin{matrix}n\\1\end{matrix}\right]\cdots\left[\begin{matrix}n\\n\end{matrix}\right]$，如果想要算不带符号的第一类斯特林数，算上升幂$x^\overline n$的系数就好了

$\newcommand{\pretty}[1]{\begin{align*}#1\end{align*}}$2018.4.20求第一类斯特林数是有$O(n\log_2n)$的做法的，orzzjt

考虑求$x^\overline n$的系数，假设我们已经求出$x^\overline n$，现在要求$x^\overline{2n}$

假设$\pretty{x^\overline n=\sum\limits_{i=0}^na_ix^i}$，那么

$\pretty{(x+n)^\overline n&=\sum\limits_{i=0}^na_i(x+n)^i\\&=\sum\limits_{i=0}^na_i\sum\limits_{j=0}^i\binom ijx^jn^{i-j}\\&=\sum\limits_{j=0}^n\dfrac{x^j}{j!}\sum\limits_{i=j}^na_ii!\dfrac{n^{i-j}}{(i-j)!}}$

观察第二个sigma，如果我们有两个数列$x_i=a_ii!$和$y_i=\dfrac{n^i}{i!}$，那么这个sigma就是两个数列错位相乘后相加

把$x$翻转，我们得到卷积的形式

所以，我们把$a_ii!$翻转后和$\dfrac{n^i}{i!}$做卷积，得到的结果取第$n-j$项就是第二个sigma的值

这样我们就求出了$(x+n)^\overline n$，把它和$x^\overline n$乘起来，我们得到$x^\overline{2n}$，时间复杂度$O(n\log_2n)$，比分治FFT不知道快到哪里去了

$\newcommand{\stirfirst}[2]{\left[\begin{matrix}#1\\#2\end{matrix}\right]}$找不到第一类斯特林数的生成函数，但指数生成函数貌似是有的（来自）

$\begin{align*}(1+z)^u&=\sum\limits_{n=0}^\infty\binom unz^n\\&=\sum\limits_{n=0}^\infty\dfrac{z^n}{n!}u^\underline n\\&=\sum\limits_{n=0}^\infty\dfrac{z^n}{n!}\sum\limits_{k=0}^n(-1)^{n-k}\stirfirst nku^k\\&=\sum\limits_{k=0}^\infty u^k\sum\limits_{n=k}^\infty(-1)^{n-k}\stirfirst nk\dfrac{z^n}{n!}\end{align*}$

我们还有$\begin{align*}(1+z)^n=e^{u\log(1+z)}=\sum\limits_{k=0}^\infty\log^k(1+z)\dfrac{u^k}{k!}\end{align*}$

比较两个式子的$u^k$的系数，我们得到$\begin{align*}\dfrac{\log^k(1+z)}{k!}=\sum\limits_{n=k}^\infty(-1)^{n-k}\stirfirst nk\dfrac{z^n}{n!}\end{align*}$，即是说$\dfrac{\log^k(1+z)}{k!}$是带符号第一类斯特林数（$(-1)^{n-k}\stirfirst nk(n\geq0)$）的指数生成函数

上面就是这两个东西本身的性质，应用嘛...并没有想到什么

第一类斯特林数我只遇到过一个：，如果一道题中的自然数幂求和$n$很大并且是固定的，要求多个，甚至模数不同，那么就可以转成斯特林数$O(k^2)$做

很空虚==毕竟做题太少没什么题放出来