十二重 Stirling 数恒等式

· · 个人记录

在《具体数学》第六章的第一节讲解了 Stirling 数，第 221 页给出了 15 条「扩展恒等式」。而除了其中的 3 条以外，其它的并不是那么显然，于是在此给出一些证明。

为方便表述，以下将「第一类 Stirling 数」和「第二类 Stirling 数」分别简称为 S1、S2。

在开始证明之前，我们有必要先回顾一些基础内容，首先是两类 Stirling 数的递推式：

\begin{Bmatrix} n \\ m \end{Bmatrix}=m\begin{Bmatrix} n-1 \\ m \end{Bmatrix}+\begin{Bmatrix} n-1 \\ m-1 \end{Bmatrix} \quad \texttt{(i)} \begin{bmatrix} n \\ m \end{bmatrix}=(n-1)\begin{bmatrix} n-1 \\ m \end{bmatrix}+\begin{bmatrix} n-1 \\ m-1 \end{bmatrix} \quad \texttt{(ii)}

以及 S1、S2 一列的 EGF：

\sum_{n\geq k} \frac{x^n}{n!}\begin{bmatrix} n \\ k \end{bmatrix}= \frac{(-\ln(1-x))^k}{k!} \quad \texttt{(iii)} \sum_{n\geq k}\frac{x^n}{n!}\begin{Bmatrix} n \\ k \end{Bmatrix}= \frac{(\text e^x-1)^k}{k!} \quad \texttt{(iv)}

S2 一列的 OGF 有简洁形式：

\sum_{n\geq k} x^n\begin{Bmatrix} n \\ k \end{Bmatrix}=\prod_{i=1}^k \frac{x}{1-ix} \quad \texttt{(v)}

然后是 Stirling 反演公式：

f_n=\sum_{k=0}^n \begin{bmatrix} n \\ k \end{bmatrix}g_k \Leftrightarrow g_n=\sum_{k=0}^n \begin{Bmatrix} n \\ k \end{Bmatrix}f_k(-1)^{n-k} \quad \texttt{(vi)}

作为辅助工具，还需要（另类）Lagrange 反演，以得到 S1、S2 一行的 EGF：

\begin{bmatrix} n \\ k \end{bmatrix}=\frac{n!}{k!}\frac kn [x^{n-k}]\left( \frac{x}{\text e^x-1}\right)^n \quad \texttt{(vii)} \begin{Bmatrix} n \\ k \end{Bmatrix}=\frac{n!}{k!}\frac{k}{n}[x^{n-k}]\left( \frac{x}{\ln(1+x)}\right)^n \quad \texttt{(viii)}

就这么多，让我们开始吧！

\begin{Bmatrix} n+1 \\ m+1 \end{Bmatrix}=\sum_{k=0}^n \binom nk \begin{Bmatrix} k \\ m \end{Bmatrix} \quad \texttt{(I)}

这显然是对 S2 一列的 EGF 和 \text e^x 做卷积，等式右边即

\begin{aligned} n![x^n]\text e^x\frac{(\text e^x-1)^m}{m!} & =n![x^n]\left( \frac{(\text e^x-1)^{m+1}}{(m+1)!}\right)' \\ &=(n+1)![x^{n+1}]\frac{(\text e^x-1)^{m+1}}{(m+1)!} \\ & =\begin{Bmatrix} n+1 \\ m+1 \end{Bmatrix}\end{aligned}

与 \texttt{(I)} 类似的还有一个等式：

\begin{bmatrix} n+1 \\ m+1\end{bmatrix}=\sum_{k=0}^n \begin{bmatrix} n \\ k \end{bmatrix} \binom km \quad \texttt{(II)}

根据 S1 的阶乘幂 \to 常幂变换，可以很容易处理此式。等式右边为

\begin{aligned}[x^m]\sum_{k=0}^n \begin{bmatrix} n \\ k \end{bmatrix}(1+x)^k&=[x^m](1+x)^{\overline n} \\ &=[x^m]\frac 1x x^{\overline{n+1}} \\ &=\begin{bmatrix}n+1 \\m+1 \end{bmatrix}\end{aligned}

接下来证明

\begin{Bmatrix} n+1 \\ m+1 \end{Bmatrix}=\sum_{k=0}^n \begin{Bmatrix} k \\ m \end{Bmatrix}(m+1)^{n-k} \quad \texttt{(III)}

这实际上就是利用了 S2 一列的 OGF，考虑

\begin{aligned}\begin{Bmatrix} n+1 \\ m+1 \end{Bmatrix}&=[x^{n+1}]\prod_{i=1}^{m+1}\frac{x}{1-ix} \\ &= \sum_{k=0}^n\left([x^k]\prod_{i=1}^m \frac{x}{1-ix}\right)\left([x^{n+1-k}] \frac{x}{1-(m+1)x} \right) \\ &= \sum_{k=0}^n\begin{Bmatrix} k \\ m \end{Bmatrix}(m+1)^{n-k}\end{aligned}

另一个与其类似的是

\begin{bmatrix} n+1 \\ m+1 \end{bmatrix} = \sum_{k=0}^n \begin{bmatrix} k \\ m \end{bmatrix} \frac{n!}{k!} \quad \texttt{(IV)}

利用 S1 一列的 EGF，等式右边可以写为

\begin{aligned}\frac{n!}{m!}[x^n] \frac{(-\ln(1-x))^m}{1-x} &= \frac{n!}{(m+1)!}[x^n]\left((-\ln(1-x))^{m+1}\right)' \\ &=\frac{(n+1)!}{(m+1)!}[x^{n+1}](-\ln(1-x))^{m+1} \\ &= \begin{bmatrix} n+1 \\m+1\end{bmatrix}\end{aligned}

接下来是两条 Stirling 数斜线上的等式，首先证明

\begin{Bmatrix} m+n+1 \\ m\end{Bmatrix}=\sum_{k=0}^m k \begin{Bmatrix} k+n \\ k\end{Bmatrix} \quad \texttt{(V)}

实际上还是使用了 S2 一列的 OGF 的变形：

\begin{Bmatrix} m+n+1 \\ m \end{Bmatrix} =[x^{n+1}]\prod_{i=1}^m \frac{1}{1-ix}

我们考虑递推式，初值为 f_0(x)=1，则 [x^{n+1}]f_m(x) 就对应了等式右边：

\begin{aligned} f_m(x) &= f_{m-1}(x) + mx \prod_{i=1}^m \frac{1}{1-ix} \\ \left( \prod_{i=1}^m(1-ix)\right)f_m(x) &= \left( \prod_{i=1}^{m-1}(1-ix)\right)(1-mx)f_{m-1}(x)+mx \\ g_m(x) &= (1-mx)g_{m-1}(x)+mx \end{aligned}

根据初值条件，很容易发现 g_m(x)=1，然后直接提取 f_m(x) 的 x^{n+1} 系数就是 \texttt{(V)} 的等式左边，命题得证。

与其类似的是

\begin{bmatrix} m+n+1 \\ m \end{bmatrix}=\sum_{k=0}^m (n+k)\begin{bmatrix} k+n \\ k \end{bmatrix} \quad \texttt{(VI)}

根据证明 \texttt{(V)}的经验，我们试图找出 S1 一列的 OGF，可是它似乎没有一个比较好处理的形式（存疑）。不过我们可以按 S1 原式的递推式不断展开：

\begin{aligned}\begin{bmatrix} m+n+1 \\ m \end{bmatrix}&=(n+m) \begin{bmatrix} m+n \\ m \end{bmatrix}+\begin{bmatrix} m+n\\ m-1 \end{bmatrix} \\ &=(n+m) \begin{bmatrix} m+n \\ m \end{bmatrix}+(n+m-1)\begin{bmatrix} m-1+n \\ m-1 \end{bmatrix}+\begin{bmatrix} m-1+n \\ m-2 \end{bmatrix} \\ &= \begin{bmatrix} m-d+n \\ m-d-1\end{bmatrix}+\sum_{k=0}^d(n+m-k)\begin{bmatrix}m-k+n \\m-k \end{bmatrix}\end{aligned}

令 d=m，命题得证。

然后是两个 两类 Stirling 数出现在同一侧 的等式：

\binom nm=\sum_{k=0}^n \begin{Bmatrix} n+1 \\ k+1\end{Bmatrix}\begin{bmatrix} k \\ m \end{bmatrix}(-1)^{m-k} \quad \texttt{(VII)}

这个形式让我们想到 Stirling 反演：

\binom {n-1}{m} = \sum_{k=1}^{n}\begin{Bmatrix} n \\ k\end{Bmatrix}\begin{bmatrix} k-1 \\ m \end{bmatrix}(-1)^{m-k+1}

这样就可以直接套公式：

\begin{bmatrix} n-1 \\ m\end{bmatrix}(-1)^{m-n+1}=\sum_{k=1}^n \begin{bmatrix} n \\ k\end{bmatrix}\binom{k-1}{m}(-1)^{n-k}

现在可能还是不便于观察，那这样呢？

\begin{bmatrix} n \\ m\end{bmatrix}=\sum_{k=0}^n \begin{bmatrix} n+1 \\ k+1 \end{bmatrix} \binom{k}{m}(-1)^{k-m}

然后我们发现这就是对 \texttt{(II)} 式使用二项式反演而已，直接得证。

另一个类似的式子是

n^{\underline{n-m}}[n \geq m]=\sum_{k=0}^n \begin{bmatrix} n+1 \\ k+1 \end{bmatrix} \begin{Bmatrix} k \\ m\end{Bmatrix}(-1)^{m-k} \quad \texttt{(VIII)}

这个形式与 \texttt{(VII)} 并不完全对称，具体做法有不少差别（也可能只是我没发现更好的做法），首先还是做 Stirling 反演，然后用 S2 一行的 EGF 推导：

\begin{aligned}\begin{Bmatrix} n-1 \\ m \end{Bmatrix}(-1)^{n+m-1}&=\sum_{k=0}^n \begin{Bmatrix} n \\ k \end{Bmatrix}(k-1)^{\underline{k-m-1}}[k-1\geq m](-1)^{n-k} \\ \begin{Bmatrix} n \\ m\end{Bmatrix}&=\sum_{k=m}^n \begin{Bmatrix} n+1 \\ k+1 \end{Bmatrix}(k-m)!\binom{k}{m}(-1)^{k-m} \\ (-1)^mm!\begin{Bmatrix} n \\ m\end{Bmatrix}&=\sum_{k=m}^n \begin{Bmatrix} n+1 \\ k+1 \end{Bmatrix}k!(-1)^k \\ (-1)^mm!\begin{Bmatrix} n \\ m\end{Bmatrix} &= n!\sum_{k=m}^n(-1)^k [x^{n-k}]\left(\frac{x}{\ln(1+x)} \right)^{n+1} \\ (-1)^mm!\begin{Bmatrix} n \\ m\end{Bmatrix} &= (-1)^nn![x^{n-m}]\frac{1}{1-x}\left(\frac{x}{\ln(1-x)} \right)^{n+1}\end{aligned}

到此处停顿一下，我们发现等式右边的部分似乎不好处理，这时就需要逆用 另类 Lagrange 反演 了，得到

(-1)^mm!\begin{Bmatrix} n \\ m\end{Bmatrix}=(-1)^n n! [x^n](1-\text e^x)^m

这个等式是显然成立的。

接下来考虑更复杂的情况：

\begin{Bmatrix} n \\ n-m\end{Bmatrix}=\sum_k \binom{m-n}{m+k}\binom{m+n}{n+k}\begin{bmatrix} m+k\\ k\end{bmatrix} \quad \texttt{(IX)}

我们可以直接用生成函数：

\begin{aligned}\begin{Bmatrix} n \\ n-m\end{Bmatrix}&=(n-1)^{\underline m}[x^m]\left( \frac{x}{\ln(1+x)}\right)^n \\ &= (n-1)^{\underline m}[x^m]\left(\frac{1}{\frac{\ln(1+x)-x}{x}+1} \right)^n \\ &=(n-1)^{\underline m}[x^m]\sum_{i=0}^m\left( 1-\frac{\ln(1+x)}{x}\right)^i\binom{i+n-1}{n-1} \\ &= (n-1)^{\underline m}[x^m]\sum_{i=0}^m\binom{i+n-1}{n-1}\sum_{j=0}^i \binom ij \left(-\frac{\ln(1+x)}{x} \right)^j \end{aligned}

接下来就要把 [x^m] 放进和式中提取系数了，同时交换求和次序得到

(n-1)^{\underline m} \sum_{j=0}^m[x^{m+j}](-\ln(1+x))^j\sum_{i=j}^m\binom{i+n-1}{n-1}\binom ij

然后要考虑化简内层和式，可以考虑

\frac{(i+n-1)!}{(n-1)!i!}\times \frac{i!}{j!(i-j)!}=\binom{i+n-1}{j,i-j,n-1}=\binom{i+n-1}{j+n-1}\binom{j+n-1}{n-1}

原式便化为

(n-1)^{\underline m} \sum_{j=0}^m[x^{m+j}](-\ln(1+x))^j\binom{j+n-1}{n-1}\binom{m+n}{j+n}

提取系数得到

(n-1)^{\underline m}\sum_{j=0}^m \frac{(-1)^{m+j}j!}{(m+j)!}\begin{bmatrix} m+j \\ j\end{bmatrix}\binom{j+n-1}{n-1}\binom{m+n}{j+n}

这个形式与 \texttt{(IX)} 的等式右边已经很接近了，我们只需要对 j\geq 0 证明

\frac{(-1)^{m+j} j!(n-1)^{\underline m}}{(m+j)!}\binom{j+n+1}{n-1}=\binom{m-n}{m+j}

先将等式左边化简为

(-1)^{m+j} \frac{j! (n-1)!}{(m+j)! (n-m-1)!} \frac{(j+n+1)!}{j!(n-1)!}=(-1)^{m-j}\binom{j+n+1}{m+j}

使用二项式系数的上指标反转就能直接证明。

与 \texttt{(IX)} 非常对称的是这样一个等式：

\begin{bmatrix} n \\ n-m\end{bmatrix}=\sum_k \binom{m-n}{m+k}\binom{m+n}{n+k}\begin{Bmatrix} m+k\\ k\end{Bmatrix} \quad \texttt{(X)}

几乎可以完全照搬其证明，这里就不展开写了。值得一提的是，若对 \texttt{(X)} 中的 Stirling 数同时使用反射公式，就能得到

\begin{Bmatrix} -n+m \\ -n\end{Bmatrix}=\sum_k \binom{m-n}{m+k}\binom{m+n}{n+k}\begin{bmatrix} -k \\-k-m \end{bmatrix}

可以发现两个等式不能说非常类似，只能说是 完 全 一 致。而且 \texttt{(IX)} 的证明中只需在最后证二项式相等时稍微调整，就可以证明 n 为负数的情形。

这篇文章临近尾声，只剩最后两个相对简单的等式了（其中 l\geq 0）：

\begin{Bmatrix}n \\ l+m \end{Bmatrix}\binom{l+m}{l}=\sum_k \binom nk \begin{Bmatrix}k \\ l \end{Bmatrix} \begin{Bmatrix}n-k \\ m \end{Bmatrix} \quad \texttt{(XI)}

虽然乍一看有点吓人，实际上等式右边就是个卷积而已：

n! \sum_k \left( [x^k] \frac{(\text e^x-1)^l}{l!}\right)\left( [x^{n-k}] \frac{(\text e^x-1)^m}{m!}\right)= \frac{n!}{l!m!}[x^n] (\text e^x-1)^{l+m}

这个结果显然是等于左侧的。

你应该也猜到了，与之形式类似的最后一个等式就是

\begin{bmatrix}n \\ l+m \end{bmatrix}\binom{l+m}{l}=\sum_k \binom nk \begin{bmatrix}k \\ l \end{bmatrix} \begin{bmatrix}n-k \\ m \end{bmatrix} \quad \texttt{(XII)}

仿照上一题的方法，使用 S1 一列的 EGF 便能直接得证。