斯特林数

记一些公式。

斯特林反演：

在幂之间转换：

\[x^n = \sum_{k = 0} ^ n\begin{Bmatrix}n\\k\end{Bmatrix}x^{\underline{k}}=\sum_{k = 0} ^ n\begin{Bmatrix}n\\k\end{Bmatrix}{x \choose k}k! = \sum_k{\begin{bmatrix}n\\k\end{bmatrix}}(-1) ^ k x^{\overline{k}} \]

反转公式：

\[\sum_k\begin{Bmatrix}n\\k\end{Bmatrix}\begin{bmatrix}k\\m\end{bmatrix} = \sum_k\begin{bmatrix}n\\k\end{bmatrix}\begin{Bmatrix}k\\m\end{Bmatrix} = [m = n] \]

计算斯特林数：

递归式：

\[\begin{Bmatrix}n\\k\end{Bmatrix} = k\begin{Bmatrix}n - 1\\k\end{Bmatrix} + \begin{Bmatrix}n - 1\\k - 1\end{Bmatrix} \]

\[\begin{bmatrix}n\\k\end{bmatrix} = (n - 1)\begin{bmatrix}n - 1\\k\end{bmatrix} + \begin{bmatrix}n - 1\\k - 1\end{bmatrix} \]

求单个第二类斯特林数：

\[m!\begin{Bmatrix}n\\m\end{Bmatrix} = \sum_{k}{m \choose k}(-1)^{m - k}k^n \]

（其实就是直接考虑容斥。）

一次算一个太逊了，来点好玩的。

把组合数拆开：

\[m!\begin{Bmatrix}n\\m\end{Bmatrix} = \sum_{k}\dfrac{m!}{k!(m-k)!}(-1)^{m - k}k^n \]

整理一下：

\[\begin{Bmatrix}n\\m\end{Bmatrix} = \sum_{k}\dfrac{k^n}{k}\cdot\dfrac{(-1)^{m - k}}{(m - k)!} \]

直接上幂级数科技就能一次算一行了。