二项式系数

特别注意
二项式的对称形式 (rm)=(rr−m)\displaystyle\binom{r}{m} = \binom{r}{r-m} 只能在 r⩾0r \geqslant 0 时成立

恒等式

吸收恒等式

首先，根据二项式系数定义，有 (rk)=rk(r−1k−1),  k≠0\displaystyle \binom{r}{k} = \frac{r}{k} \binom{r-1}{k-1}, \ \ k \neq 0
那么我们有如下式子成立

k(rk)=r(r−1k−1),  k∈Zk\binom{r}{k} = r \binom{r-1}{k-1}, \ \ k \in \mathbb{Z}

有一种比较快的记忆方法，将二项式 (rk)\binom{r}{k} 的 kk 看成分母，然后 ×k\times k，右边呢？右边剩下系数 rr
同时上下指标同时 −1-1，变成 (r−1k−1)\binom{r-1}{k-1}

其对应的下指标不变的相伴恒等式为

(r−k)(rk)=r(r−1k),  k∈Z(r-k) \binom{r}{k} = r\binom{r-1}{k}, \ \ k \in \mathbb{Z}

证明也很简单，(r−k)(rk)=(r−k)(rr−k)=r(r−1r−k−1)=r(r−1k)\displaystyle (r-k)\binom{r}{k} = (r-k)\binom{r}{r-k} = r\binom{r-1}{r-k-1} = r \binom{r-1}{k}

递推
递推有点老生常谈

(rk)=(r−1k)+(r−1k−1),  k∈Z\binom{r}{k} = \binom{r-1}{k} + \binom{r-1}{k-1}, \ \ k \in \mathbb{Z}

上指标求和
根据递推，实际上，(r+n+1n)=(r+nn)+(r+nn−1)=(r+nn)+(r+n−1n−1)+(r+n−1n−2)=⋯\displaystyle\binom{r+n+1}{n} = \binom{r+n}{n} + \binom{r+n}{n-1} = \binom{r+n}{n} + \binom{r+n-1}{n-1} + \binom{r+n-1}{n-2} = \cdots

可以这样一直做下去，可以得到一般的公式

∑k⩽n(r+kk)=(r0)+(r+11)+⋯+(r+nn)=(r+n+1n),  n∈Z\sum_{k \leqslant n} \binom{r+k}{k} = \binom{r}{0} + \binom{r+1}{1} + \cdots + \binom{r+n}{n} = \binom{r+n+1}{n}, \ \ n \in \mathbb{Z}

实际上，更常用的是上指标求和，在二项式系数 (nk)\binom{n}{k} 中，每一次展开有最大下指标 kk 的项

(53)=(43)+(42)=(33)+(32)+(42)=(23)+(22)+(32)+(42)=⋯⋯=(03)+(02)+(12)+(22)+(32)+(42)\begin{aligned} \binom{5}{3} &= \binom{4}{3} + \binom{4}{2} \\ &= \binom{3}{3} + \binom{3}{2} + \binom{4}{2} \\ &= \binom{2}{3} + \binom{2}{2} + \binom{3}{2} + \binom{4}{2} \\ &= \cdots \cdots \\ &= \binom{0}{3} + \binom{0}{2} + \binom{1}{2} + \binom{2}{2} + \binom{3}{2} + \binom{4}{2} \end{aligned}

∑0⩽k⩽n(km)=(0m)+(1m)+⋯+(nm)=(n+1m+1), (n,m⩾0)\sum_{0 \leqslant k \leqslant n} \binom{k}{m} = \binom{0}{m} + \binom{1}{m} + \cdots + \binom{n}{m} = \binom{n+1}{m+1}, \ (n, m \geqslant 0)

组合解释
想从 n+1n+1 张票（编号为 0→n0 \to n）中选取 m+1m+1 张票，所选取的最大号码恰好是 kk 时的方案数为 (km)\displaystyle\binom{k}{m}

微积分方法

Δ(xm‾)=(x+1)m‾−xm‾=(x+1)(x)⋯(x−m+2)−x⋯(x−m+2)(x−m+1)=mx(x−1)⋯(x−m+2)\begin{aligned} \Delta(x^{\underline{m}}) &= (x+1)^{\underline{m}} - x^{\underline{m}} \\ &= (x+1)(x)\cdots (x-m+2) - x\cdots (x-m+2)(x-m+1) \\ &= mx(x-1)\cdots (x-m+2) \end{aligned}

所以我们有 Δ(xm‾)=mxm−1‾\Delta(x^{\underline{m}}) = mx^{\underline{m-1}}

这里有一个定理
g(x)=Δf(x)g(x) = \Delta f(x) 当且仅当 ∑g(x)δx=f(x)+C\displaystyle\sum g(x) \delta x = f(x) + C，这里 ∑g(x)δx\displaystyle\sum g(x) \delta x 是 g(x)g(x) 的不定和式
是差分等于 g(x)g(x) 的一个函数类，这里的 CC 不是不定积分的 CC，而是满足 p(x+1)=p(x)p(x+1) = p(x) 的任意一个函数 p(x)p(x)
比如 C(x)=a+bsin⁡2πxC(x) = a + b\sin 2\pi x，这样作差分的时候，C(x)C(x) 就被消去了

同样，这里对 ∑0⩽k⩽n(km)=(n+1m+1)\displaystyle \sum_{0 \leqslant k \leqslant n} \binom{k}{m} = \binom{n+1}{m+1}

如果两边同时 ×m!\times m!，那么有

∑0⩽k⩽nkm‾=(n+1)m+1‾m+1,  m,n⩾0\displaystyle \sum_{0 \leqslant k \leqslant n} k^{\underline{m}} = \frac{(n+1)^{\underline{m+1}}}{m+1}, \ \ m, n \geqslant 0

另外有 Δ((xm))=(x+1m)−(xm)=(xm−1)\displaystyle \Delta \left(\binom{x}{m}\right) = \binom{x+1}{m} - \binom{x}{m} = \binom{x}{m-1}

实际上，(xm)=Δ(xm+1)\displaystyle \binom{x}{m} = \Delta \binom{x}{m+1}，应用差分定理

∑(xm)δx=(xm+1)+C\displaystyle \sum\binom{x}{m} \delta x = \binom{x}{m+1} + C

上指标反转
上指标反转也是一个老生常谈的了，处理二项式中 r<0r<0 的情况

(rk)=(−1)k(k−r−1k),k∈Z\binom{r}{k} = (-1)^{k} \binom{k-r-1}{k}, \quad k \in \mathbb{Z}

证明很简单
rk‾=r(r−1)⋯(r−k+1)=(−1)k(−r)(−r+1)⋯(k−r−1)=(−1)k(k−r−1)k‾\displaystyle \begin{aligned}r^{\underline{k}} = r(r-1)\cdots (r-k+1) &= (-1)^{k}(-r)(-r+1)\cdots(k-r-1) \\ &= (-1)^k (k-r-1)^{\underline{k}} \end{aligned}

记忆口诀
翻转 (rk)\displaystyle\binom{r}{k}，首先写下 (−1)k(-1)^k，然后立即写下 kk，写两次，上指标和下指标都写一次
接着上指标减去 rr，然后再减去 11

当然翻转上指标的逆过程也很容易，(−1)m(−n−1m)\displaystyle (-1)^m \binom{-n-1}{m}，可以将上指标写成 −n−1-n-1 的形式
然后翻转后的上指标是 n+mn + m

(−1)m(−n−1m)=(−1)n(−m−1n)=(m+nn)\displaystyle (-1)^m \binom{-n-1}{m} = (-1)^n \binom{-m-1}{n} = \binom{m+n}{n}

杨辉三角

利用上指标反转，可以做出如下推导

∑k⩽m(rk)(−1)k=(r0)−(r1)+⋯+(−1)m(rm)=∑k⩽m(k−r−1k)=(−r+mm)=(−1)m(r−1m)\displaystyle \begin{aligned} \sum_{k \leqslant m}\binom{r}{k}(-1)^k &= \binom{r}{0} - \binom{r}{1} + \cdots + (-1)^m \binom{r}{m} \\ &= \sum_{k \leqslant m} \binom{k-r-1}{k} = \binom{-r+m}{m} = (-1)^m \binom{r-1}{m} \end{aligned}

注意最后一步用了上指标求和公式中的第一个公式

杨辉三角部分和
杨辉三角中，一行的部分和不存在封闭形式，列的部分和有封闭形式，上指标求和公式中的第二个公式，给出了封闭形式
但是，每一行元素 ×元素离开中心的距离\times \text{元素离开中心的距离}，就有一种形式

∑k⩽m(rk)(r2−k)=m+12(rm+1)\displaystyle\sum_{k \leqslant m} \binom{r}{k} \left(\frac{r}{2} - k\right) = \frac{m+1}{2} \binom{r}{m+1}

证明的方法是对 mm 归纳
∑k⩽m+1(rk)(r2−k)=∑k⩽m(rk)(r2−k)+(rm+1)(r2−m−1)\sum_{k \leqslant m+1} \binom{r}{k} \left(\frac{r}{2}-k \right) = \sum_{k \leqslant m} \binom{r}{k}(\frac{r}{2}-k) + \binom{r}{m+1} \left(\frac{r}{2}-m-1\right)
⇒m+12(rm+1)+(r2−m−1)(rm+1)=(rm+1)(m+12+r2−m−1)\Rightarrow \frac{m+1}{2}\binom{r}{m+1} + \left(\frac{r}{2}-m-1\right)\binom{r}{m+1} = \binom{r}{m+1} \left(\frac{m+1}{2} + \frac{r}{2} - m - 1\right)

关键步骤是 rr−m−1‾(r−m−2)!⋅12=m+22⋅(r(r−1)⋯(m+3)(r−m−2)!)=m+22(rm+2)\displaystyle\frac{r^{\underline{r-m-1}}}{(r-m-2)!} \cdot \frac{1}{2} = \frac{m+2}{2} \cdot \left(\frac{r(r-1)\cdots (m+3)}{(r-m-2)!}\right) = \frac{m+2}{2}\binom{r}{m+2}

二项级数的部分和

∑k⩽m(m+rk)xkym−k=∑k⩽m(−rk)(−x)k(x+y)m−k,m∈Z\displaystyle \sum_{k \leqslant m} \binom{m+r}{k} x^k y^{m-k} = \sum_{k \leqslant m} \binom{-r}{k} (-x)^k (x+y)^{m-k}, \quad m \in \mathbb{Z}

其实很好证明，对于左边
(x+y)m+r=∑k(m+rk)xkym+r−k\displaystyle (x+y)^{m+r} = \sum_{k} \binom{m+r}{k} x^k y^{m+r-k}

⟹(x+y)m+r⋅y−r=∑k(m+rk)xkym−k\displaystyle \Longrightarrow (x+y)^{m+r} \cdot y^{-r} = \sum_{k} \binom{m+r}{k}x^{k} y^{m-k}

对于右边，同样

(−x+x+y)−r=∑k(−rk)(−x)k(x+y)−r−k\displaystyle(-x+x+y)^{-r} = \sum_{k} \binom{-r}{k}(-x)^k (x+y)^{-r-k}

⟹(x+y)m+r⋅(−y)r=∑k(−rk)(−x)k(x+y)m−k\displaystyle \Longrightarrow (x+y)^{m+r} \cdot (-y)^{r} = \sum_{k} \binom{-r}{k} (-x)^{k}(x+y)^{m-k}

另外，当然要求 0⩾r⩾−m0 \geqslant r \geqslant -m

这里讲一下其他证明方法，记左边的和为 SmS_m，用组合数加法展开
Sm=∑k⩽m(m−1+rk)xkym−k+∑k⩽m(m−1+rk−1)xkym−kS_m = \displaystyle \sum_{k \leqslant m}\binom{m-1+r}{k}x^{k} y^{m-k} + \sum_{k \leqslant m}\binom{m-1+r}{k-1} x^{k} y^{m-k}

注意到 ySm−1=∑k⩽m−1(m−1+rk)xkym−1−k⋅yyS_{m-1} = \displaystyle \sum_{k \leqslant m-1} \binom{m-1+r}{k} x^{k}y^{m-1-k} \cdot y，所以

∑k⩽m(m−1+rk)xkym−k=ySm−1+(m−1+rm)xm\displaystyle \sum_{k \leqslant m} \binom{m-1+r}{k}x^{k}y^{m-k} = yS_{m-1} + \binom{m-1+r}{m}x^m

另外，xSm−1=∑k⩽m−1(m−1+rk)xk+1ym−1−kxS_{m-1} = \displaystyle \sum_{k \leqslant m-1} \binom{m-1+r}{k}x^{k+1}y^{m-1-k}，令 k′←k+1k' \leftarrow k+1
那么接下来所有的 kk 用 k−1k-1 代换即可

xSm−1=∑k⩽m(m−1+rk−1)xkym−k\displaystyle xS_{m-1} = \sum_{k \leqslant m} \binom{m-1+r}{k-1}x^k y^{m-k}

代入并反转上指标，可得

Sm=(x+y)Sm−1+(−rm)(−x)m\displaystyle S_m = (x+y)S_{m-1} + \binom{-r}{m}(-x)^m

二项级数可以推出的一些结论
在上述的部分和式中，令 x=−1,y=1x = -1, y = 1，可以得到

∑k⩽m(m+rk)(−1)k=(−rm), m⩾0\displaystyle \sum_{k \leqslant m}\binom{m+r}{k} (-1)^k = \binom{-r}{m}, \ m \geqslant 0

等式右边成立的原因是，仅有 k=mk = m 这一项不为 00

令 x=y=1, r=m+1x = y = 1, \ r = m+1，可以得到

∑k⩽m(2m+1k)=∑k⩽m(m+kk)2m−k\displaystyle \sum_{k \leqslant m} \binom{2m+1}{k} = \sum_{k \leqslant m} \binom{m+k}{k} 2^{m-k}，化简时候用了上指标反转

注意到上式左边，对杨辉三角二项式系数一半进行求和，结果为 12(1+1)2m+1=22m\displaystyle \frac{1}{2} (1+1)^{2m+1} = 2^{2m}

由此可以得到一个公式

∑k⩽m(m+kk)2−k=2m, m⩾0\displaystyle \sum_{k \leqslant m} \binom{m+k}{k}2^{-k} = 2^m, \ m \geqslant 0

三项式

三项式恒等式
这个法则比较重要

(rm)(mk)=(rk)(r−km−k),m,k∈Z\displaystyle \binom{r}{m}\binom{m}{k} = \binom{r}{k} \binom{r-k}{m-k}, \quad m, k \in \mathbb{Z}

三项式定理
(x+y+z)n=∑0⩽a,b,c⩽na+b+c=n(a+b+c)!a!b!c!xaybzc=∑0⩽a,b,c⩽na+b+c=n(a+b+cb+c)(b+cc)xaybzc\displaystyle \begin{aligned}(x+y+z)^n &=\sum_{\begin{aligned}0 \leqslant a, b, c \leqslant n \\ a+b+c = n \end{aligned}} \frac{(a+b+c)!}{a!b!c!}x^ay^bz^c \\ &= \sum_{\begin{aligned}0 \leqslant a, b, c \leqslant n \\ a+b+c = n \end{aligned}} \binom{a+b+c}{b+c} \binom{b+c}{c} x^ay^bz^c \end{aligned}

卷积

范德蒙德卷积
卷积的证明可以用二项式生成函数

∑k(rm+k)(sn−k)=(r+sm+n),m,n∈Z\displaystyle \sum_{k}\binom{r}{m+k} \binom{s}{n-k} = \binom{r+s}{m+n}, \quad m, n \in \mathbb{Z}

更一般意义的表示

∑k(rk)(sn−k)=(r+sn),n∈Z\displaystyle \sum_{k} \binom{r}{k} \binom{s}{n-k} = \binom{r+s}{n}, \quad n \in \mathbb{Z}

组合解释是，从 rr 个男人和 ss 个女人中选 nn 个人的方法数，等于任意的 kk 的和
其中 kk 表示从 rr 个男人中选 kk 个男人，然后再从 ss 个女人中选 n−kn-k 个女人

卷积推广
(1)\textbf{(1)}
∑k(lm+k)(sn+k)=(l+sl−m+n),l⩾0\displaystyle \sum_k \binom{l}{m+k} \binom{s}{n+k} = \binom{l+s}{l-m+n}, \quad l \geqslant 0

注意，这里必须 l⩾0,m,n∈Zl \geqslant 0, m, n \in \mathbb{Z}

证明很简单，只要 (lm+k)⟶(ll−m−k)\binom{l}{m+k} \longrightarrow \binom{l}{l-m-k}，再用范德蒙卷积即可

(2)\textbf{(2)}
∑k(lm+k)(s+kn)(−1)k=(−1)l+m(s−mn−l),l⩾0\displaystyle \sum_k \binom{l}{m+k} \binom{s+k}{n} (-1)^k = (-1)^{l+m} \binom{s-m}{n-l}, \quad l \geqslant 0

一开始看可能比较棘手，先考虑简单情况，再归纳出封闭形式
不妨设 s+k⩾0s+k \geqslant 0

(−1)k(s+kn)→(−1)k(s+ks+k−n)→(−1)s−n(−n−1s+k−n)(-1)^k\binom{s+k}{n} \to (-1)^k \binom{s+k}{s+k-n} \to (-1)^{s-n} \binom{-n-1}{s+k-n}

原式可以如下化简，注意中间一步用了 (1)\textbf{(1)}，然后进行上指标反转

(−1)s−n∑k(lm+k)(−n−1s−n+k)=(−1)s−n(l−n−1l−m+s−n)=(−1)l−m(s−ml−n−m+s)(-1)^{s-n} \sum_k \binom{l}{m+k} \binom{-n-1}{s-n+k} = (-1)^{s-n} \binom{l-n-1}{l-m+s-n} = (-1)^{l-m}\binom{s-m}{l-n-m+s}
假设 s−m⩾0s-m \geqslant 0，那么有 (−1)l+m(s−mn−l)(-1)^{l+m} \binom{s-m}{n-l}

至于这个结果，是否对所有的 kk 都成立？可以用归纳法证明
根据加法公式
∑k(l−1m+k)(s+kn)(−1)k+∑k(l−1m+k−1)(s+kn)(−1)k\sum_k \binom{l-1}{m+k} \binom{s+k}{n} (-1)^k + \sum_k \binom{l-1}{m+k-1}\binom{s+k}{n} (-1)^k

对 ll 进行归纳

(−1)l−1+m(s−mn−l+1)+(−1)l+m(s−m+1n−l+1)(-1)^{l-1+m} \binom{s-m}{n-l+1} + (-1)^{l+m} \binom{s-m+1}{n-l+1}，再用一次加法公式，就可以得到右边

(3)\textbf{(3)}
∑k⩽l(l−km)(sk−n)(−1)k=(−1)l+m(s−m−1l−m−n),l,m,n⩾0\displaystyle \sum_{k \leqslant l} \binom{l-k}{m} \binom{s}{k-n}(-1)^k = (-1)^{l+m} \binom{s-m-1}{l-m-n}, \quad l, m,n \geqslant 0

证明很简单
(l−km)→(l−kl−k−m)→(−1)l−k−m(−m+1l−k−m)\binom{l-k}{m} \to \binom{l-k}{l-k-m} \to (-1)^{l-k-m} \binom{-m+1}{l-k-m}，然后用范德蒙卷积

(4)\textbf{(4)}
∑−q⩽k⩽l(l−km)(q+kn)=(l+q+1m+n+1)m,n⩾0,l+q⩾0\displaystyle \sum_{-q \leqslant k \leqslant l} \binom{l-k}{m} \binom{q+k}{n} = \binom{l+q+1}{m+n+1} \quad m, n \geqslant 0, l+q \geqslant 0

首先令 k′=k+q, l′=l+qk' = k+q, \ l' = l+q
∑k′⩽l′(l′−k′m)(k′k′−n)=∑k′⩽l′(l′−k′m)(−1)k′−n(−n−1k′−n)\sum_{k' \leqslant l'} \binom{l'-k'}{m} \binom{k'}{k'-n} = \sum_{k' \leqslant l'} \binom{l'-k'}{m} (-1)^{k'-n} \binom{-n-1}{k'-n}

=(−1)n∑k′⩽l′(l′−k′m)(−n−1k′−n)(−1)k= (-1)^n \sum_{k' \leqslant l'} \binom{l'-k'}{m} \binom{-n-1}{k'-n} (-1)^k

然后用 (3)\textbf{(3)}

=(−1)n(−1)l′+m(−n−1−m−1l′−m−n)=(−1)l′−m−n(−n−1−m−1l′−m−n)= (-1)^n (-1)^{l'+m} \binom{-n-1-m-1}{l'-m-n} = (-1)^{l'-m-n} \binom{-n-1-m-1}{l'-m-n}

反转上指标

=(−1)l′−m−n(l′+1l′−m−n)=(l+q+1l+q−m−n)=(l+q+1m+n+1)= (-1)^{l'-m-n} \binom{l'+1}{l'-m-n} = \binom{l+q+1}{l+q-m-n} = \binom{l+q+1}{m+n+1}

其他二项式系数和式

∑kij(−1)∑i<jkij(∏1⩽i<j<n(ai+ajaj+kij))(∏1⩽j<n(aj+anan+∑i<jkij−∑i>jkji))\sum_{k_{ij}}(-1)^{\sum_{i < j} k_{ij}} \left(\prod_{1 \leqslant i < j < n} \binom{a_i + a_j}{a_j + k_{ij}} \right) \left(\prod_{1 \leqslant j < n} \binom{a_j + a_n}{a_n + \sum_{i < j} k_{ij} - \sum_{i > j} k_{ji}} \right)

=(a1+⋯+ana1,a2,⋯ ,an),(a1,a2,⋯ ,an⩾0)= \binom{a_1 + \cdots + a_n}{a_1, a_2, \cdots, a_n}, \quad (a_1, a_2, \cdots, a_n \geqslant 0)

这里的和式是对 (n−12)\displaystyle \binom{n-1}{2} 个指标变量 kij(1⩽i<j<n)k_{ij} (1 \leqslant i < j < n) 求和的

比如 n=4n = 4，(a1,a2,a3,a4)←(a,b,c,d), (k12,k13,k23)=(i,j,k)(a_1, a_2, a_3, a_4) \leftarrow (a, b, c, d), \ (k_{12}, k_{13}, k_{23}) = (i, j, k)

∑i,j,k(−1)i+j+k=(a+bb+i)(a+cc+j)(b+cc+k)(a+dd−i−j)(b+dd+i−k)(c+dd+j+k)\sum_{i, j, k} (-1)^{i+j+k} = \binom{a+b}{b+i} \binom{a+c}{c+j} \binom{b+c}{c+k} \binom{a+d}{d-i-j} \binom{b+d}{d+i-k} \binom{c+d}{d+j+k}

=(a+b+c+d)!a!b!c!d!,a,b,c,d⩾0= \frac{(a+b+c+d)!}{a!b!c!d!}, \quad a,b,c, d \geqslant 0

上式的左边是 n(n−1)n(n-1) 个分数的乘积

∏1⩽i,j⩽n, i≠j(1−zizj)ai\prod_{1\leqslant i, j \leqslant n, \ i \neq j} \left(1-\frac{z_i}{z_j}\right)^{a_i}

完全展开成 zz 的幂时，z10z20⋯zn0z_1^0z_2^0\cdots z_n^0 的系数

证明如下，注意是对 1⩽i<j<n1 \leqslant i < j < n 的 kijk_{ij} 求和
考虑 n(n−1)n(n-1) 个指标变量 lijl_{ij} 的展开，不妨令 kij=lij−ljik_{ij} = l_{ij} - l_{ji}，其中 1⩽i<j<n1 \leqslant i < j < n
因为求 z0z^0 的系数，幂次为 00
那么 ∑i≠j(lij−lji)=0\sum_{i \neq j} (l_{ij} - l_{ji}) = 0，对所有 i<ni < n 成立

实际上，∑i<jkij−∑i>jkji=0,(i<n)\displaystyle\sum_{i < j} k_{ij} - \sum_{i > j} k_{ji} = 0, \quad (i < n)

对于 i=ni = n 的情况，此时 (1−zjzn)aj\displaystyle \left(1-\frac{z_j}{z_n}\right)^{a_j} 的展开指标为 (ajljn)\displaystyle\binom{a_j}{l_{jn}}
为了使得 zn,zjz_n, z_j 的幂次均为 00

(1−znzj)an\displaystyle \left(1-\frac{z_n}{z_j} \right)^{a_n} 的展开指标也要是 (anljn)\displaystyle \binom{a_n}{l_{jn}}

∑ljn(anan−ljn)(ajljn)=(an+ajan+0)=(an+ajan+∑i<jkij−∑i>jkji)\displaystyle \sum_{l_{jn}} \binom{a_n}{a_n - l_{jn}} \binom{a_j}{l_{jn}} = \binom{a_n + a_j}{a_n + 0} = \binom{a_n + a_j}{a_n + \sum_{i < j} k_{ij} - \sum_{i > j} k_{ji}}

对于 i<ni < n，可以直接利用范德蒙德卷积

∑lij(ailij)(ajlji)=∑lij(ailij)(ajaj−lji)=(ai+ajaj+(lij−lji))\displaystyle \sum_{l_{ij}} \binom{a_i}{l_{ij}} \binom{a_j}{l_{ji}} = \sum_{l_{ij}}\binom{a_i}{l_{ij}} \binom{a_j}{a_j - l_{ji}} = \binom{a_i+a_j}{a_j + (l_{ij} - l_{ji})}

=(ai+ajaj+kij)= \displaystyle \binom{a_i+a_j}{a_j + k_{ij}}

将所有的情况乘起来，就得到了左边

再来看其他的一些性质
如果 z1,⋯ ,znz_1,\cdots, z_n 是不同的复数，那么多项式

f(z)=∑k=1n∏1⩽j⩽n,  k≠jz−zjzk−zj\displaystyle f(z) = \sum_{k = 1}^{n} \prod_{1 \leqslant j \leqslant n, \ \ k \neq j} \frac{z-z_j}{z_k - z_j} 恒等于 11

考虑 g(z)=f(z)−1g(z) = f(z) - 1
先看外层的求和，对于每一个确定的 kk，zjz_j 的取值有 n−1n-1 种，所以乘积 ∏(z−zj)\prod(z-z_j)，对应的多项式幂次 <n< n

另外由于 nn 个 ∏z−zjzk−zj\displaystyle \prod \frac{z-z_j}{z_k - z_j} 相乘，所以 f(z)=1f(z) = 1 最多有 nn 个根

由此可知，g(z)=0g(z) = 0 恒成立，即 f(z)=1f(z) = 1 恒成立

可以得到的递归式
令 C(a1,a2,⋯ ,an)C(a_1, a_2, \cdots, a_n) 表示把 n(n−1)n(n-1) 个因子完全展开成 ∏1⩽i,j⩽n,i≠j(1−zizj)ai\displaystyle \prod_{1\leqslant i,j \leqslant n, i \neq j} \left(1-\frac{z_i}{z_j} \right)^{a_i} 时
z10,z20,⋯ ,zn0z_1^0, z_2^0, \cdots, z_n^0 的系数

C(a1,a2,⋯ ,an)=C(a1−1,a2,⋯ ,an)+C(a1,a2−1,⋯ ,an)+⋯C(a1,a2,⋯ ,an−1)C(a_1, a_2, \cdots, a_n) = C(a_1-1, a_2, \cdots, a_n) + C(a_1, a_2-1, \cdots, a_n) + \cdots C(a_1, a_2, \cdots, a_n-1)

证明很简单

∏1⩽i,j⩽n,i≠j(1−zizj)ai=f(0)⋅∏1⩽i,j⩽n,i≠j(1−zizj)ai\displaystyle \prod_{1\leqslant i,j \leqslant n, i \neq j} \left(1-\frac{z_i}{z_j} \right)^{a_i} = f(0) \cdot \prod_{1\leqslant i,j \leqslant n, i \neq j} \left(1-\frac{z_i}{z_j} \right)^{a_i}

实际上，f(0)=∑k=1n∏1⩽j⩽n,k≠jzjzj−zk=∏1⩽j⩽n,k≠j(1−zkzj)−1\displaystyle f(0) = \sum_{k =1}^{n} \prod_{1 \leqslant j \leqslant n, k \neq j} \frac{z_j}{z_j - z_k} = \prod_{1 \leqslant j \leqslant n, k \neq j} \left(1 - \frac{z_k}{z_j} \right)^{-1}

∏1⩽i,j⩽n,i≠j(1−zizj)ai=∑k=1n∏1⩽i,j⩽n, i≠j(1−zizj)ai−[i=k]\displaystyle \prod_{1\leqslant i,j \leqslant n, i \neq j} \left(1-\frac{z_i}{z_j} \right)^{a_i} = \sum_{k = 1}^{n} \prod_{1 \leqslant i, j \leqslant n, \ i \neq j} \left(1- \frac{z_i}{z_j} \right)^{a_i - [i = k]}

比较等式两边的系数，即可知道结果

二项恒等式的构造方法

例1
∑j,k(−1)j+k(j+kk+l)(rj)(nk)(s+n−j−km−j)\displaystyle \sum_{j, k}(-1)^{j+k} \binom{j+k}{k+l} \binom{r}{j} \binom{n}{k} \binom{s+n-j-k}{m-j}

=(−1)l(n+rn+l)(s−rm−n−l),l,m,n∈Z,n⩾0\displaystyle = (-1)^l \binom{n+r}{n+l} \binom{s-r}{m-n-l}, \quad l, m, n \in \mathbb{Z}, n \geqslant 0

不难想到，还原出的二项式，有 −yj, −xk-y^j, \ -x^k 的项，因为有 (rj)(nk)\displaystyle\binom{r}{j} \binom{n}{k}

问题是，怎么和 (s+n−j−km−j)\displaystyle \binom{s+n-j-k}{m-j} 联系起来

实际上，(s+n−j−km−j)\displaystyle \binom{s+n-j-k}{m-j} 可以看作如下二项式

(1+y)s+n−j−kyj=yj(11+y)j+k(1+y)s+n\displaystyle (1+y)^{s+n-j-k} y^j = y^j (\frac{1}{1+y})^{j+k} (1+y)^{s+n}，展开求 ymy^m 的系数

同样可以根据 (j+kk+l)\displaystyle \binom{j+k}{k+l} 来构造，(1+x)j+kxk\displaystyle \frac{(1+x)^{j+k}}{x^k}，求 xlx^l 的系数

将 j+kj+k 的项合并，可以构造如下二项式

(1−(1+x)y(1+y))r(1−(1+x)(1+y)x)n(1+y)s+n\displaystyle \left(1 - \frac{(1+x)y}{(1+y)}\right)^r \left(1 - \frac{(1+x)}{(1+y)x}\right)^n (1+y)^{s+n}

原恒等式左边实际上就是 xlymx^l y^m 的系数

化简之后，(−1)n(1−xy)r+n(1+y)s−rx−n\displaystyle (-1)^n (1-xy)^{r+n} (1+y)^{s-r} x^{-n}，同样取 xlymx^l y^m 的系数

xlx^l，那么对应地是 (r+nl+n)\displaystyle \binom{r+n}{l+n} 这一项，同时这一项还带出来 yl+ny^{l+n}

那么还需要在 (1+y)s−r(1+y)^{s-r} 中取出 m−l−nm-l-n 项，即 (s−rm−l−n)\displaystyle \binom{s-r}{m-l-n}

综上所述，原恒等式证毕

例2
这个问题来源于 AtCoder Beginner Contest 230

需要找到生成函数对应的项

F(x,y)=(1−x)(1−y)1−2x−2y+2xy\displaystyle F(x, y) = \frac{(1-x)(1-y)}{1-2x-2y+2xy}

此时 xnynx^ny^n 对应的项系数是多少呢？

首先，(1−x)(1−y)(1-x)(1-y) 中 x,yx, y 的系数都是 −1-1，xyxy 的系数是 11

xaybx^ay^b 对应的项系数为

[xayb]11+2x+2y−2xy=∑i=0∞(2xy−2x−2y)i\displaystyle [x^ay^b]\frac{1}{1+2x+2y-2xy} = \sum_{i = 0}^{\infty} (2xy-2x-2y)^i

这是一个三项式展开，不妨设展开为 (2xy)p(−2x)q(−2y)r(2xy)^p (-2x)^q (-2y)^r
{p+q+r=ip+q=ap+r=b\displaystyle \begin{cases} p+q+r = i \\ p+q = a \\ p+r = b \end{cases}，另外有常数幂 2i(−1)q+r2^i (-1)^{q+r}

解出 p=a+b−i, q=i−b, r=i−a\displaystyle p = a+b-i, \ q = i-b, \ r = i - a，同时
i⩾a,i⩾b,i⩽a+bi \geqslant a, i \geqslant b, i \leqslant a+b，即 i∈[max⁡(a,b),a+b]i \in [\max(a, b), a+b]

根据三项式展开

∑i=max⁡(a,b)a+b(ia+b−i, i−b, i−a)2i(−1)a+b\displaystyle \sum_{i = \max(a, b)}^{a+b} \binom{i}{a+b-i, \ i-b, \ i-a} 2^i (-1)^{a+b} 是 [xayb][x^ay^b] 的系数

即 ∑i=max⁡(a,b)a+bi!(a+b−i)!(i−b)!(i−a)!2i(−1)a+b\displaystyle \sum_{i = \max(a,b)}^{a+b}\frac{i!}{(a+b-i)!(i-b)!(i-a)!} 2^i (-1)^{a+b}

再来看一个三项式恒等式

∑k(m−r+sk)(n+r−sn−k)(r+km+n)=(rm)(sn), m,n∈Z\displaystyle \sum_{k} \binom{m-r+s}{k}\binom{n+r-s}{n-k} \binom{r+k}{m+n} = \binom{r}{m} \binom{s}{n}, \ m, n \in \mathbb{Z}

首先将 (r+km+n)\binom{r+k}{m+n} 写成 ∑j(rm+n−j)(kj)\sum_{j} \binom{r}{m+n-j} \binom{k}{j}

整理一下，∑j(rm+n−j)∑k(m−r+sk)(kj)(n+r−sn−k)\sum_{j} \binom{r}{m+n-j} \sum_{k} \binom{m-r+s}{k}\binom{k}{j} \binom{n+r-s}{n-k}

利用三项式恒等式，化简成 ∑j(rm+n−j)(m−r+sj)∑k(m−r+s−jk−j)(n+r−sn−k)\sum_{j} \binom{r}{m+n-j} \binom{m-r+s}{j} \sum_k \binom{m-r+s-j}{k-j} \binom{n+r-s}{n-k}

根据范德蒙卷积，可以得到 ∑j(rm+n−j)(m−r+sj)(m+n−jn−j)\sum_{j} \binom{r}{m+n-j} \binom{m-r+s}{j} \binom{m+n-j}{n-j}

再利用一次三项式恒等式和范德蒙卷积

(rm)∑j(r−mr−n+j−m)(m−r+sj)=(rm)∑j(r−mn−j)(m−r+sj)=(rm)(sn)\binom{r}{m} \sum_{j} \binom{r-m}{r-n+j-m} \binom{m-r+s}{j} = \binom{r}{m} \sum_{j} \binom{r-m}{n-j} \binom{m-r+s}{j} = \binom{r}{m} \binom{s}{n}

化简方法

化为递归式

Qn=∑k⩽2n(2n−kk)(−1)k\displaystyle Q_n = \sum_{k \leqslant 2^n} \binom{2^n - k}{k}(-1)^k

这里令 m=2nm = 2^n，那么原问题化为

Rm=∑k⩽m(m−kk)(−1)k, m⩾0\displaystyle R_m = \sum_{k \leqslant m} \binom{m-k}{k} (-1)^k, \ m \geqslant 0

Rm=∑k⩽m(m−kk)(−1)k, m⩾0=∑k⩽m(m−1−kk)(−1)k+∑k⩽m(m−1−kk−1)(−1)k\displaystyle \begin{aligned}R_m &= \sum_{k \leqslant m} \binom{m-k}{k} (-1)^k, \ m \geqslant 0 \\ &= \sum_{k \leqslant m} \binom{m-1-k}{k}(-1)^k + \sum_{k\leqslant m}\binom{m-1-k}{k-1}(-1)^k \end{aligned}

令 k′←k−1k' \leftarrow k-1，Rm=∑k⩽m(m−1−kk)(−1)k+∑k+1⩽m(m−2−kk)(−1)k+1\displaystyle R_m = \sum_{k \leqslant m}\binom{m-1-k}{k}(-1)^k + \sum_{k+1 \leqslant m} \binom{m-2-k}{k}(-1)^{k+1}

观察下指标，Rm=∑k⩽m−1(m−1−kk)(−1)k+(−1m)(−1)m−∑k⩽m−2(m−2−kk)(−1)k−(−1m−1)(−1)m−1\displaystyle R_m = \sum_{k \leqslant m-1} \binom{m-1-k}{k} (-1)^k + \binom{-1}{m}(-1)^m - \sum_{k \leqslant m-2} \binom{m-2-k}{k} (-1)^k - \binom{-1}{m-1}(-1)^{m-1}

Rm=Rm−1−Rm−2\displaystyle R_m = R_{m-1} - R_{m-2}

这个递归式是有周期性的
Rm=(Rm−2−Rm−3)−Rm−2=−Rm−3\displaystyle R_m = (R_{m-2} - R_{m-3}) - R_{m-2} = -R_{m-3}
对于 m⩾6m \geqslant 6，有 Rm=Rm−6R_m = R_{m-6}

可以打表列出 Rm=[0→6]R_m = [0 \to 6] 所有值

我们有 Q(n)=R(2n)Q(n) = R(2^n)

n=0,R(2n mod 6)=R(1)=1n = 0, R(2^n \bmod 6) = R(1) = 1
n=1,R(2n mod 6)=R(2)=0n = 1, R(2^n \bmod 6) = R(2) = 0
n=2,R(2n mod 6)=R(4)=−1n = 2, R(2^n \bmod 6) = R(4) = -1
n=3,R(2n mod 6)=R(2)=0n = 3, R(2^n \bmod 6) = R(2) = 0
⋯⋯\cdots \cdots

实际上，我们递推的时候，对于 i→i+1i \to i+1
R(2i mod 6)→R(2i+1 mod 6)R(2^i \bmod 6) \to R(2^{i+1} \bmod 6)

如果设 2i=k2^i = k，R(k)→R(k⋅(2 mod 6))R(k) \to R(k \cdot (2 \bmod 6))
这样，R(2n)=R(m)R(2^n) = R(m)，m>1m > 1 时候的取值，只会在 2,42, 4 这两个剩余类中
并且是奇偶交替着变化，nn 为奇数时候对应 R(2)R(2)，nn 为偶数时对应 R(4)R(4)

Qn=R2n={R1=1n=0R2=0n & 1=1R4=−1n & 1=0, n>0Q_n = R_{2^n} = \begin{cases} R_1 = 1 & n = 0 \\ R_2 = 0 & n \ \& \ 1 = 1 \\ R_4 = -1 & n \ \& \ 1 = 0, \ n > 0 \end{cases}

基本练习

来看《具体数学》中的一个例子

求和式 Sm=∑k⩾0(n+k2k)(2kk)(−1)kk+1+m,m,n⩾0\displaystyle S_m = \sum_{k \geqslant 0} \binom{n+k}{2k} \binom{2k}{k} \frac{(-1)^k}{k+1+m}, \quad m,n \geqslant 0 的封闭形式

根据具体数学中问题 66 的分析，可以做如下化简

Sm=∑k⩾0(n+kk)(nk)(−1)kk+1+m=∑k⩾0(n+kk)(nk)(−1)kk+1k+1k+1+m\displaystyle S_m = \sum_{k \geqslant 0} \binom{n+k}{k} \binom{n}{k} \frac{(-1)^k}{k+1+m} = \sum_{k \geqslant 0} \binom{n+k}{k} \binom{n}{k} \frac{(-1)^k}{k+1} \frac{k+1}{k+1+m}

而之前已经有了一个恒等式 ∑j=0m(mj)(rj)−1=r+1r+1−m,m⩾0,r∉{0,1,⋯ ,m−1}\displaystyle \sum_{j = 0}^{m} \binom{m}{j} \binom{r}{j}^{-1} = \frac{r+1}{r+1-m}, \quad m \geqslant 0, r \notin \{0, 1, \cdots, m-1\}

用 −k−2-k-2 代替 rr 可以得到展开式

Sm=∑k⩾0(n+kk)(nk)(−1)kk+1∑j⩾0(mj)(−k−2j)−1\displaystyle S_m = \sum_{k \geqslant 0} \binom{n+k}{k} \binom{n}{k} \frac{(-1)^k}{k+1} \sum_{j \geqslant 0} \binom{m}{j} \binom{-k-2}{j}^{-1}

考虑将其直接展开，注意用上指标反转

Sm=∑k⩾0(n+k)!k!(n−k)!(−1)k+j∑j⩾0m!(m−j)!(j+k+1)!\displaystyle S_m = \sum_{k \geqslant 0} \frac{(n+k)!}{k!(n-k)!} (-1)^{k+j} \sum_{j \geqslant 0} \frac{m!}{(m-j)!(j+k+1)!}

接下来就考虑拼凑，首先将第一部分拼凑成

Sm=m!n!∑k⩾0(n+k)!n!k!(−1)k+j1(n−k)!∑j⩾01(m−j)!(j+k+1)!\displaystyle S_m = m!n! \sum_{k \geqslant 0} \frac{(n+k)!}{n!k!}(-1)^{k+j} \frac{1}{(n-k)!} \sum_{j \geqslant 0} \frac{1}{(m-j)!(j+k+1)!}

那么很显然第一部分有更加工整的形式 (n+kk)=(−1)k(−n−1k)\displaystyle \binom{n+k}{k} = (-1)^k \binom{-n-1}{k}，考虑第二部分

∑j⩾01(n−k)!1(m−j)!(j+k+1)!=∑j⩾0(n+j+1)!(n−k)!(j+k+1)!1(n+j+1)!(m−j)!\displaystyle \sum_{j \geqslant 0} \frac{1}{(n-k)!} \frac{1}{(m-j)!(j+k+1)!} = \sum_{j \geqslant 0} \frac{(n+j+1)!}{(n-k)!(j+k+1)!} \frac{1}{(n+j+1)!(m-j)!}

1(m+n+1)!∑j⩾0(n+j+1)!(n−k)!(j+k+1)!(m+n+1)!(n+j+1)!(m−j)!\displaystyle \frac{1}{(m+n+1)!} \sum_{j \geqslant 0} \frac{(n+j+1)!}{(n-k)!(j+k+1)!} \frac{(m+n+1)!}{(n+j+1)! (m-j)!}

整理之后，可以得到

Sm=m!n!(m+n+1)!∑j⩾0(−1)j(m+n+1n+j+1)∑k(n+j+1j+k+1)(−n−1k)\displaystyle S_m = \frac{m!n!}{(m+n+1)!} \sum_{j \geqslant 0} (-1)^j \binom{m+n+1}{n+j+1} \sum_{k} \binom{n+j+1}{j+k+1} \binom{-n-1}{k}

利用范德蒙卷积，可以将第二部分写成

Sm=m!n!(m+n+1)!∑j⩾0(−1)j(m+n+1n+1+j)(jn)\displaystyle S_m = \frac{m!n!}{(m+n+1)!} \sum_{j \geqslant 0} (-1)^j\binom{m+n+1}{n+1+j} \binom{j}{n}

根据卷积推广的 (2)\bold{(2)}，对于所有的 jj，式子中对应的 s=0s = 0，求和式为 00
因此 −Sm-S_m 对应 j<0j < 0 时的和式

j<0j < 0，即 j+1⩽0j+1 \leqslant 0，取 −k=j+1-k = j+1，讨论 k⩾0k \geqslant 0 时的情形
j←−k−1, k⩾0j \leftarrow -k-1, \ k \geqslant 0，可以推出

Sm=m!n!(m+n+1)!∑k⩾0(−1)k(m+n+1n−k)(−k−1n)\displaystyle S_m = \frac{m!n!}{(m+n+1)!} \sum_{k \geqslant 0} (-1)^k \binom{m+n+1}{n-k} \binom{-k-1}{n}

令 k←n−kk \leftarrow n-k

Sm=m!n!(m+n+1)!∑k⩽n(−1)n−k(m+n+1k)(k−n−1n)\displaystyle S_m = \frac{m!n!}{(m+n+1)!} \sum_{k \leqslant n} (-1)^{n-k} \binom{m+n+1}{k} \binom{k-n-1}{n}

整理之后，得到

Sm=m!n!(m+n+1)!∑k⩽2n(−1)k(m+n+1k)(2n−kn)\displaystyle S_m = \frac{m!n!}{(m+n+1)!} \sum_{k \leqslant 2n} (-1)^k \binom{m+n+1}{k} \binom{2n-k}{n}

利用卷积推广 (3)\textbf{(3)} 可以得到答案

Sm=(−1)nm!n!(m+n+1)!(mn)=(−1)nmn‾m−n−1‾\displaystyle S_m = (-1)^n \frac{m!n!}{(m+n+1)!} \binom{m}{n} = (-1)^n m^{\underline{n}} m^{\underline{-n-1}}

验证一下，对于 n=2n = 2，Sm=m(m−1)(m+1)(m+2)(m+3)\displaystyle S_m = \frac{m(m-1)}{(m+1)(m+2)(m+3)}