具体数学 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}} \] 标签：frac,斯特林,sum,brack,证明,ge,binom,brace,式子 From： https://www.cnblogs.com/british-union/p/stir.html