具体数学 221 页给了很多斯特林恒等式，但是没有给出证明，现在我们来证明一下。
前置知识
斯特林数的递推公式
\[{n\brace k}={n-1\brace k-1}+k{n-1\brace k}
\]
\[{n\brack k}={n-1\brack k-1}+(n-1){n-1\brack k}
\]
斯特林数的生成函数：
\[\sum_{i\ge 0}{n\brace i}x^i=(\sum_{k\ge 0}\frac{k^nx^k}{k!})(\sum_{k\ge 0}\frac{(-1)x^k}{k!})
\]
\[\sum_{i\ge 0}{i\brace m}\frac{x^i}{i!}=\frac{(e^x-1)^m}{m!}
\]
\[\sum_{i\ge 0}{n\brack i}x^i=x^{\overline n}
\]
\[\sum_{i\ge 0}{i\brack m}\frac{x^i}{i!}=\frac{(-\ln(1-x))^m}{m!}
\]
证明可以参考洛谷四个斯特林数模板题的题解区。
斯特林反演
\[f(n)=\sum_{i}{n\brace i}g(i)\iff g(n)=\sum_{i}(-1)^{n-i}{n\brack i}f(i)
\]
代入即证。（？）
启动
这里只证明一组恒等式之一（两类斯特林数证明应本质相同）
公式的另一个形式参考《具体数学》
证明：
\[\sum_{k}{n\brace k}{k\brack m}(-1)^{n-k}=\sum_{k}{n\brack k}{k\brace m}(-1)^{n-k}=[m=n](6.30)
\]
把下降幂和上升幂拆开形式互相代入即证。
证明：
\[{n+1\brace m+1}=\sum_k\binom{n}{k}{k\brace m}(6.15)
\]
\[\text{RHS's EGF}=e^x\frac{(e^x-1)^m}{m!}
\]
这个不好搞，但是可以把 \(e^x\) 的常数项分开计算。
就变成了
\[RHS=[\frac{x^n}{n!}](e^x-1)\frac{(e^x-1)^m}{m!}+{n\brace m}\\
=\frac{(e^x-1)^{m+1}}{m!}+{n\brace m}\\
=[\frac{x^n}{n!}](m+1)\frac{(e^x-1)^{m+1}}{(m+1)!}+{n\brace m}\\
=(m+1){n\brace m+1}+{n\brace m}
\]
证明：
\[{n\brace m}=\sum_k\binom{n}{k}{k+1\brace m+1}(-1)^{n-k}
\]
显然 EGF。
\[RHS=\sum_k\binom{n}{n-k}{k+1\brace m+1}(-1)^{n-k}\\
\]
先需要知道
\[\sum_i{i+1\brace m}\frac{x^i}{i!}\\
=(\sum_i{i+1\brace m}\frac{x^{i+1}}{(i+1!})'\\
=\frac{e^x(e^x-1)^{m-1}}{(m-1)!}
\]
\[\therefore \text{RHS's EGF}=e^{-x}\times \frac{e^x(e^x-1)^{m}}{m!}\\=\frac{(e^x-1)^m}{m!}=\text{LHS's EGF}
\]
证明：
\[m!{n\brace m}=\sum_k\binom{m}{k}k^n(-1)^{m-k}(6.19)
\]
一般幂转下降幂，二项式反演即可。是第二类斯特林数·行的原理。
证明：
\[{n+1\brace m+1}=\sum_{k=0}^n{k\brace m}(m+1)^{n-k}(6.20)
\]
看起来只能 OGF，但是斯特林数的列 OGF 很糟糕。但是我们尝试考虑比值：
\[t=\frac{\sum_{k\ge 0}{k+1\brace m+1}x^k}{\sum_{k\ge 0}{k\brace m}x^k}\\
=\frac{\sum_{k\ge 0}{k\brace m}x^k+(m+1)\sum_{k\ge 0}{k\brace m+1}x^k}{\sum_{k\ge 0}{k\brace m}x^k}\\
=1+\frac{(m+1)\sum_{k\ge 0}{k\brace m+1}x^k}{\sum_{k\ge 0}{k\brace m}x^k}\\
=1+\frac{(m+1)x\sum_{k\ge 0}{k+1\brace m+1}x^k}{\sum_{k\ge 0}{k\brace m}x^k}\\
\therefore 1+(m+1)tx=t\\
t=\frac{1}{1-(m+1)x}=\sum_{k\ge 0}(m+1)^kx^k
\]
然后发现
\[\text{RHS's OGF}=\left(\sum_{k\ge 0}{k\brace m}x^k\right)\times\left(\sum_{k\ge 0}(m+1)^kx^k\right)\\
=\sum_{k\ge 0}{k+1\brace m+1}x^k=\text{LHS's OGF}
\]
证明：
\[\binom{n}{m}=\sum_k{n+1\brace k+1}{k\brack m}(-1)^{m-k}(6.24)
\]
对 \({n+1\brace k+1}\) 斯特林反演化为 \((6.18)\)。
证明：
\[{n\brace n-m}\sum_k\binom{m-n}{m+k}\binom{m+n}{n+k}{m+k\brack k}(6.26)
\]
不会。
证明：（远古写的）
\[{n\brace l+m}\binom{l+m}{l}=\sum_k{k\brace l}{n-k\brace m}\binom{n}{k}(6.28)
\]
\[\iff{n\brack l+m}\binom{l+m}{l}\frac{x^n}{n!}=\sum_k{k\brack l}{n-k\brack m}\binom{n}{k}\frac{x^n}{n!}
\]
\[\sum_k{k\brack l}{n-k\brack m}\binom{n}{k}\frac{x^n}{n!}=[x^n](\sum_k{k\brack m}\frac{x^k}{k!})(\sum_k{k\brack l}\frac{x^k}{k!})
\]
\[RHS=[x^n/n!]\frac{(-\ln(1-x))^m}{m!}\times \frac{(-\ln(1-x))^l}{l!}=\frac{(-\ln(1-x))^{m+l}}{m!l!}
\]
\[\frac{RHS}{\binom{l+m}{l}}=[x^n/n!]\frac{(-\ln(1-x))^{m+l}}{(m+l)!}={n\brack l+m}=\frac{LHS}{\binom{l+m}{l}}
\]