营业日志 2020.10.3 杂谈——几个可以用生成函数做的超几何恒等式

· · 个人记录

大家国庆快乐！

题一

设 n\ge 0, \alpha \in \mathbb C \backslash \{0, 1, \dots, n-1\}，求算

\sum_{0\le k\le n} \frac{\binom n k}{\binom \alpha k}

我们首先用 Gamma 函数做一下变形

\begin{aligned} \sum_k \frac{\binom n k}{\binom \alpha k} &= \sum_k \frac{\frac{\Gamma(n+1)}{\Gamma(n-k+1)\Gamma(k+1)}}{\frac{\Gamma(\alpha+1)}{\Gamma(\alpha-k+1)\Gamma(k+1)}}\\ &= \frac{\Gamma(n+1)}{\Gamma(\alpha+1)} \sum_k \frac{\Gamma(\alpha-k+1)}{\Gamma(n-k+1)}\\ &= \binom{\alpha}{n}^{-1} \sum_k \binom{\alpha -k}{n-k} \end{aligned}

接下来就是常规推导了

\begin{aligned} &= \binom{\alpha}{n}^{-1} \sum_k [x^{n-k}] (1+x)^{\alpha-k}\\ &= \binom{\alpha}{n}^{-1} \sum_k [x^n] (1+x)^{\alpha-k}x^k\\ &= \binom{\alpha}{n}^{-1} [x^n] (1+x)^{\alpha} \sum_k \frac{x^k}{(1+x)^k}\\ &= \binom{\alpha}{n}^{-1} [x^n] (1+x)^{\alpha} \frac{1}{1-\frac{x}{1+x}}\\ &= \binom{\alpha}{n}^{-1} [x^n] (1+x)^{\alpha+1}\\ &= \binom{\alpha}{n}^{-1} \binom{\alpha+1}n\\ &= \frac{\alpha+1}{\alpha+1-n} \end{aligned}

另解

这个式子其实还等价于一个恒等式，我们将 \alpha 在无穷处展开，先把等式两边减一变成

\sum_{k} \frac{n^{\underline {k+1}}}{\alpha^{\underline {k+1}}} = \frac n{\alpha + (1 - n)}

注意

\frac1{\alpha(\alpha - 1) \cdots (\alpha - k)} = \sum_{j\ge 0} \left\{j\atop k\right\} \alpha^{-j-1}

而

\frac{n}{\alpha + (1-n)} = \sum_{j\ge 0} n(n-1)^j \alpha^{-j-1}

因此

\begin{aligned} [\alpha^{-j-1}]\sum_{k} \frac{n^{\underline {k+1}}}{\alpha^{\underline {k+1}}} &= [\alpha^{-j-1}] \frac n{\alpha + (1 - n)}\\ \sum_k n^{\underline {k+1}} \left\{j\atop k\right\} &= n(n-1)^j\\ \sum_k \binom{n-1}k k!\left\{j\atop k\right\} &= (n-1)^j \end{aligned}

上面的变形均可逆，因此我们通过斯特林降幂公式也是可以得到这个结论的。

题二

设 n,m\ge 0，求算

\sum_{k} \binom {n+k}{2k} \binom{2k}k \frac{(-1)^k}{k+1+m}

这个题如果我们硬刚 \binom{2k}k = [x^k](1-4x)^{-\frac 12} 的话非常吃力，我们考虑变形为

\binom{n+k}{2k} \binom{2k}k = \binom{n+k}k \binom n k

那么就有

\begin{aligned} &\quad \sum_{k} \binom {n+k}{2k} \binom{2k}k \frac{(-1)^k}{k+1+m}\\ & = \sum_{k} \binom {n+k}{k} \binom{n}k \frac{(-1)^k}{k+1+m}\\ &= \int_0^1 \sum_{k} \binom {n+k}{k} \binom{n}k (-t)^k t^m \,\mathrm{d}t\\ &= \int_0^1 \sum_{k} [x^0](1+x)^n \left(\frac{1+x}x\right)^k \binom{n}k (-t)^k t^m \,\mathrm{d}t\\ &= \int_0^1[x^0](1+x)^n \left(1-\frac{1+x}xt\right)^n t^m \,\mathrm{d}t\\ &= \int_0^1[x^n](1+x)^n (t+x(1-t))^n t^m \,\mathrm{d}t\\ &= \sum_k \binom n k [x^{n-k}]\int_0^1 (-t+x(1-t))^n t^m \,\mathrm{d}t\\ &= \sum_k \binom n k ^2 \int_0^1 (-1)^k(1-t)^{n-k} t^{m+k} \,\mathrm{d}t\\ \end{aligned}

我们要熟悉 Beta 积分 \int_0^1 (1-t)^a t^b \,\mathrm{d}t=\frac{a!b!}{(a+b+1)!}（事实上这由分部积分是很容易证明的），接下来我们继续：

\begin{aligned} &\quad\sum_k (-1)^k\binom n k^2 \frac{(n-k)!(m+k)!}{(n+m+1)!}\\ &= \frac 1{n+m+1}\binom{n+m}n^{-1} \sum_k(-1)^k \binom{m+k}m\binom nk\\ &= \frac 1{n+m+1}\binom{n+m}n^{-1} \sum_k \binom nk[x^0] (1+x)^m \left(-\frac{1+x}{x}\right)^k\\ &= \frac 1{n+m+1}\binom{n+m}n^{-1} [x^0] (1+x)^m \left(1-\frac{1+x}{x}\right)^n\\ &= \frac 1{n+m+1}\binom{n+m}n^{-1} [x^n] (1+x)^m\\ &= \frac 1{n+m+1}\binom{n+m}n^{-1} \binom mn \end{aligned}

题三

设 n,m,k\ge0，求

\sum_i (-1)^i \binom{m+n}{m+i}\binom {n+k}{n+i} \binom{k+m}{k+i}

为了用生成函数算这个东西，这里我们不妨介绍多元拉格朗日反演公式的一个直接推论——MacMahon 主定理。

MacMahon 主定理（MacMahon Master Theorem） 令 \mathbf A=[a_{i,j}]_{n\times n}, \mathbf X = \operatorname{diag} (x_1, \dots, x_n)，则有

[\mathbf x^{\mathbf k}] \prod_{i=1}^n (a_{i,1}x_1 + \cdots + a_{i,n}x_n)^{k_i} = [\mathbf x^\mathbf k] \vert \mathbf {I-XA} \vert^{-1}

其中 \mathbf k =(k_1, \dots, k_n) \ge \mathbf 0。

我们考虑和式

\left(1-\frac xz\right)^{m+n} \left(1-\frac yx\right)^{n+k} \left(1-\frac zy\right)^{k+m} = \sum_{a,b,c} (-1)^{a+b+c} \binom{m+n}a \binom{n+k}b \binom{k+m}c x^{a-b} y^{b-c}z^{c-a}

考虑其中 \binom{m+n}{m+i}\binom {n+k}{n+i} \binom{k+m}{k+i} 的项，是

(-1)^{m+n+k}\sum_i (-1)^i \binom{m+n}{m+i}\binom {n+k}{n+i} \binom{k+m}{k+i} x^{m-n}y^{n-k}z^{k-m}

我们只需提取 (-1)^{m+n+k}[x^{m-n}y^{n-k}z^{k-m}]\left(1-\frac xz\right)^{m+n}\left(1-\frac yx\right)^{n+k}\left(1-\frac zy\right)^{k+m} 即可。

即提取

(-1)^{m+n+k}[x^{m+k}y^{n+m}z^{k+n}](z-x)^{m+n}(x-y)^{n+k}(y-z)^{k+m}

整理一下，就是

(-1)^{m+n+k} [x^{k+m}y^{m+n}z^{n+k}](y-z)^{k+m}(z-x)^{m+n}(x-y)^{n+k}

符合 MacMahon 主定理的形式，说明它等于

(-1)^{m+n+k} [x^{k+m}y^{m+n}z^{n+k}] \left | \begin{matrix} 1 & -x & x\\ y & 1 & -y\\ -z & z & 1 \end{matrix} \right|^{-1}

化简可得

(-1)^{m+n+k}[x^{k+m}y^{m+n}z^{n+k}] (1+xy+yz+zx)^{-1}

注意到假设取到 (xy)^a (yz)^b(zx)^c，只有唯一解 a=m, b=n, c=k。因此答案就是

(-1)^{m+n+k} [u^mv^nw^k] (1+u+v+w)^{-1} = \binom{m+n+k}{m,n,k}

因此我们有

\sum_i (-1)^i \binom{m+n}{m+i}\binom {n+k}{n+i} \binom{k+m}{k+i}=\binom{m+n+k}{m,n,k}

Dixon's Identity 是它的一个特例：

Dixon's Identity

\sum_k (-1)^k \binom{2n}k ^3 = (-1)^n \binom{3n}{n,n,n}