斯特林数对普通幂、阶乘幂的转化和斯特林反演公式的推导

标签：begin end Bmatrix 斯特林 sum 数对 乘幂 bmatrix aligned

PS：首先%周克 字号过小时无法显示上升幂下降幂 记得开SVG渲染

\(n!=\sum_{k=0}^n\begin{bmatrix}n\\k\end{bmatrix}\\\)

证明：一种排列对应一种置换

\(m^n=\sum_{k=0}^m\begin{Bmatrix}n\\k\end{Bmatrix}\begin{pmatrix}n\\k\end{pmatrix}k!=\sum_{i=0}^m\begin{Bmatrix}n\\k\end{Bmatrix}m^{\underline k}\\\)

证明：考虑组合意义 \(n\)个小球放到\(m\)个盒子里 要求每个盒子非空的方案数 先划分小球 方案数为第二类斯特林数 再选取盒子 方案数为下降幂

\(x^{\underline n}=\sum\limits_{i=0}^n\begin{bmatrix}n\\i \end{bmatrix}(-1)^{n-i}x^i\\\)

证明：

\[\begin{aligned} x^{\underline{n+1}}&=(x-n)x^{\underline n}\\ &=(x-n)\sum_i\begin{bmatrix}n\\i\end{bmatrix}(-1)^{n-i}x^i\\ &=\sum_i\begin{bmatrix}n\\i\end{bmatrix}(-1)^{n-i}x^{i+1}-n\sum_i\begin{bmatrix}n\\i\end{bmatrix}(-1)^{n-i}x^i\\ &=\sum_i\begin{bmatrix}n\\i-1\end{bmatrix}(-1)^{n+1-i}x^i+n\sum_i\begin{bmatrix}n\\i\end{bmatrix}(-1)^{n+1-i}x^i\\ &=\sum_i\left(\begin{bmatrix}n\\i-1\end{bmatrix}+n*\begin{bmatrix}n\\i\end{bmatrix}\right)(-1)^{n+1-i}x^i\\ &=\sum_i\begin{bmatrix}n+1\\i\end{bmatrix}(-1)^{n+1-i}x^i\\ \end{aligned}\]

\(x^{\overline n}=\sum_{i=0}^n\begin{bmatrix}n\\i\end{bmatrix}x^i\\\)

证明：

\[\begin{aligned} x^{\overline{n+1}}&=(x+n)x^{\underline n}\\ &=(x+n)\sum_i\begin{bmatrix}n\\i\end{bmatrix}x^i\\ &=\sum_i\begin{bmatrix}n\\i\end{bmatrix}x^{i+1}+n\sum_i\begin{bmatrix}n\\i\end{bmatrix}x^i\\ &=\sum_i\begin{bmatrix}n\\i-1\end{bmatrix}x^i+n\sum_i\begin{bmatrix}n\\i\end{bmatrix}x^i\\ &=\sum_i\left(\begin{bmatrix}n\\i-1\end{bmatrix}+n*\begin{bmatrix}n\\i\end{bmatrix}\right)x^i\\ &=\sum_i\begin{bmatrix}n+1\\i\end{bmatrix}x^i\\ \end{aligned}\]

\(\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]\\\)

证明：

\[\begin{aligned} m^{\underline n}&=\sum_{i=0}^n\begin{bmatrix}n\\i\end{bmatrix}(-1)^{n-i}m^i\\ &=\sum_{i=0}^n\begin{bmatrix}n\\i\end{bmatrix}(-1)^{n-i}\sum_{j=0}^i\begin{Bmatrix}i\\j\end{Bmatrix}m^{\underline j}\\ &=\sum_{i=0}^n m^{\underline i}\sum_{j=i}^n(-1)^{n-j}\begin{bmatrix}n\\j\end{bmatrix}\begin{Bmatrix}j\\i\end{Bmatrix}\\ \end{aligned}\]

\[\begin{aligned} m^n&=\sum_{i=0}^n\begin{Bmatrix}n\\i\end{Bmatrix}m^{\underline i}\\ &=\sum_{i=0}^n\begin{Bmatrix}n\\i\end{Bmatrix}\sum_{j=0}^i(-1)^{i-j}\begin{bmatrix}i\\j\end{bmatrix}m^j\\ &=\sum_{i=0}^n m^i\sum_{j=i}^n(-1)^{j-i}\begin{bmatrix}j\\i\end{bmatrix}\begin{Bmatrix}n\\j\end{Bmatrix}\\ \end{aligned}\]

代入\(i=j=n\)观察式子即可得证

斯特林反演

若\(g(n)=\sum_{k=0}^n(-1)^{n-k}\begin{bmatrix}n\\k\end{bmatrix}f(k)\\\)

\[\begin{aligned} f(n)&=\sum_{k=0}^n[k=n]f(k)\\ &=\sum_{k=0}^n\sum_{j=k}^n\begin{Bmatrix}n\\j\end{Bmatrix}\begin{bmatrix}j\\k\end{bmatrix}(-1)^{j-k}f(k)\\ &=\sum_{j=0}^n\begin{Bmatrix}n\\j\end{Bmatrix}\sum_{k=0}^j(-1)^{j-k}\begin{bmatrix}j\\k\end{bmatrix}f(k)\\ &=\sum_{j=0}^n\begin{Bmatrix}n\\j\end{Bmatrix}g(j)\\ \end{aligned}\]

即：

\(g(n)=\sum_{k=0}^n(-1)^{n-k}\begin{bmatrix}n\\k\end{bmatrix}f(k)\\\)

\(f(n)=\sum_{k=0}^n\begin{Bmatrix}n\\k\end{Bmatrix}g(k)\\\)

通过一系列操作 如代换 \(g(n)=(-1)^n g'(n)\quad f(n)=(-1)^n f'(n)\) 等操作 还可以得到其他形式：

\(g(n)=\sum_{k=0}^n(-1)^k\begin{bmatrix}n\\k\end{bmatrix}f(k)\\\)

\(f(n)=\sum_{k=0}^n(-1)^k\begin{Bmatrix}n\\k\end{Bmatrix}g(k)\\\)

和：

\(g(n)=\sum_{k=0}^n\begin{bmatrix}n\\k\end{bmatrix}f(k)\\\)

\(f(n)=\sum_{k=0}^n(-1)^{n-k}\begin{Bmatrix}n\\k\end{Bmatrix}g(k)\\\)

标签：begin,end,Bmatrix,斯特林,sum,数对,乘幂,bmatrix,aligned
From： https://www.cnblogs.com/Sakura-Lu/p/17100938.html