斯特林数
定义：
自行百度
递推式：
\[ \begin{Bmatrix}n\\k \end{Bmatrix}=\begin{Bmatrix}n-1\\k-1\end{Bmatrix}+k\cdot \begin{Bmatrix}n-1\\k \end{Bmatrix}\\ \begin{bmatrix}n\\k \end{bmatrix}=\begin{bmatrix}n-1\\k-1 \end{bmatrix}+(n-1)\cdot \begin{bmatrix}n-1\\k \end{bmatrix} \]
第二类斯特林数
一个组合数意义清晰的式子：
\[ \displaystyle n^m=\sum_{k=0}^m\begin {Bmatrix}m\\k \end{Bmatrix}C_n^kk!\\ \] 通过二项式反演的得到（这里是将m看作一个常数)：\[ k!\begin {Bmatrix}m\\k \end{Bmatrix}=\sum_{i=0}^k(-1)^{k-i}C_k^ii^m\\ \] 上述式子用容斥原理也很好理解。我们还可以将上述的式子化为卷积的形式：
\[ \begin{align} \begin {Bmatrix}m\\k \end{Bmatrix}&=\frac{1}{k!}\sum_{i=0}^k(-1)^{k-i}\frac{k!}{i!(k-i)!}i^m\\ &=\sum_{i=0}^k\frac{(-1)^{k-i}}{(k-i)!}\frac{i^m}{i!}\\ \end{align} \]第二类斯特林数的应用：
斯特林数与阶乘幂之间的关系：
第二类斯特林数与下降阶乘幂的关系：
\[ C_n^kk!=n^{\underline k}\\ 所以：\displaystyle n^m=\sum_{k=0}^m\begin {Bmatrix}m\\k \end{Bmatrix}C_n^kk!=\sum_{k=0}^m\begin {Bmatrix}m\\k \end{Bmatrix}n^{\underline k}\\ \]
当然也有第一类斯特林数与上升阶乘幂的关系：
\[ \displaystyle x^{\overline{n}}=\sum_k \begin{bmatrix}n\\k \end{bmatrix}x^k \]
证明使用数学归纳法证明的：
首先我们有\((x+n-1)\cdot x^k=x^{k+1}+(n-1)x^k\)。
所以：
\[ \begin{align} \displaystyle x^{\overline{n}}&=(x+n-1)x^{\overline{n-1}}\\ &=(x+n-1)\sum_k \begin{bmatrix}n-1\\k \end{bmatrix}x^k\\ &=\sum_k \begin{bmatrix}n-1\\k \end{bmatrix}x^{k+1}+\sum_k \begin{bmatrix}n-1\\k \end{bmatrix}x^k (n-1)\\ &=\sum_k \begin{bmatrix}n-1\\k-1 \end{bmatrix}x^{k}+\sum_k \begin{bmatrix}n-1\\k \end{bmatrix}x^k (n-1)\\ &=\sum_k x^k (\begin{bmatrix} n-1\\k-1\end{bmatrix}+(n-1)\begin{bmatrix}n-1\\k\end{bmatrix})\\ &=\sum_k x^k\begin{bmatrix}n\\k\end{bmatrix} \end{align} \]斯特林反演：
\[ \displaystyle f(n)=\sum_{k=0}^n \begin{Bmatrix}n\\k \end{Bmatrix}g(k) \Longleftrightarrow g(n)=\sum_{k=0}^n(-1)^{n-k}\begin {bmatrix} n\\k \end{bmatrix}f(k) \]
首先我们要证明一个叫反转公式的东西：
\[ \displaystyle \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] \]
在这之前，我们先考虑如何建立上升阶乘幂与下降阶乘幂之间的关系。
先给出结论：
\[ x^{\underline{n}}=(-1)^n(-x)^{\overline{n}}\\ x^{\overline{n}}=(-1)^n(-x)^{\underline{n}} \] 证明：\[ \begin{align} (-1)^n(-x)^{\overline{n}}&=(-1)^n(-x)(-x+1)...(-x+n-1)\\ &=(-1)^n(-x)(-(x-1))...(-(x-n+1))\\ &=x(x-1)...(x-n+1)=x^{\underline{n}} \end{align} \] 对于\(x^{\overline{n}}=(-1)^n(-x)^{\underline{n}}\)证明方法相同。\[ \begin{align} \displaystyle n^m&=\sum_{k=0}^{m}\begin{Bmatrix}m\\k\end{Bmatrix}n^{\underline{k}}\\ &=\sum_{k=0}^{m}\begin{Bmatrix}m\\k\end{Bmatrix}(-1)^k(-n)^{\overline{k}} \end{align} \] 将下式带入：\[ \displaystyle x^{\overline{n}}=\sum_k \begin{bmatrix}n\\k \end{bmatrix}x^k \] 得：\[ \begin{align} \displaystyle n^m&=\sum_{k=0}^{m}\begin{Bmatrix}m\\k\end{Bmatrix}(-1)^k(-n)^{\overline{k}}\\ &=\sum_{k=0}^{m}\begin{Bmatrix}m\\k\end{Bmatrix}(-1)^k\sum_{j=0}^k\begin{bmatrix}k\\j\end{bmatrix}(-n)^j\\ &=\sum_{j=0}^mn^j\sum_{k=j}^{m}\begin{Bmatrix}m\\k\end{Bmatrix}\begin{bmatrix}k\\j\end{bmatrix}(-1)^{k-j} \end{align} \] 于是我们就得到了一个反转公式，另一个证明方法类似，反过来带入就可以了。\[ \sum_{k=j}^m\begin{Bmatrix}m\\k\end{Bmatrix}\begin{bmatrix}k\\j\end{bmatrix}(-1)^{k-j}=[j=m] \] 然后我们就可以证明斯特林反演了：\[ \begin{align} \displaystyle 若满足g(n)&=\sum_{j=0}^n(-1)^{n-j}\begin{bmatrix}n\\j\end{bmatrix}f(j)\\ 则f(n)&=\sum_{j=0}^n[j==n]f(j)\\ &=\sum_{j=0}^n\sum_{k=j}^n\begin{Bmatrix}n\\k\end{Bmatrix}\begin{bmatrix}k\\j\end{bmatrix}(-1)^{k-j}f(j)\\ &=\sum_{k=0}^n\begin{Bmatrix}n\\k\end{Bmatrix}\sum_{j=0}^k(-1)^{k-j}\begin{bmatrix}k\\j\end{bmatrix}f(j)\\ &=\sum_{k=0}^n\begin{Bmatrix}n\\k\end{Bmatrix}g(k) \end{align} \]