二项式系数

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

恒等式

吸收恒等式

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

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

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

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

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

证明也很简单,(rk)(rk)=(rk)(rrk)=r(r1rk1)=r(r1k)\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)=(r1k)+(r1k1),  kZ\binom{r}{k} = \binom{r-1}{k} + \binom{r-1}{k-1}, \ \ k \in \mathbb{Z}

上指标求和
根据递推,实际上,(r+n+1n)=(r+nn)+(r+nn1)=(r+nn)+(r+n1n1)+(r+n1n2)=\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

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

kn(r+kk)=(r0)+(r+11)++(r+nn)=(r+n+1n),  nZ\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}

0kn(km)=(0m)+(1m)++(nm)=(n+1m+1), (n,m0)\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 张票(编号为 0n0 \to n)中选取 m+1m+1 张票,所选取的最大号码恰好是 kk 时的方案数为 (km)\displaystyle\binom{k}{m}

微积分方法

Δ(xm)=(x+1)mxm=(x+1)(x)(xm+2)x(xm+2)(xm+1)=mx(x1)(xm+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)=mxm1\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 xg(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+bsin2πxC(x) = a + b\sin 2\pi x,这样作差分的时候,C(x)C(x) 就被消去了

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

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

0knkm=(n+1)m+1m+1,  m,n0\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)=(xm1)\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(kr1k),kZ\binom{r}{k} = (-1)^{k} \binom{k-r-1}{k}, \quad k \in \mathbb{Z}

证明很简单
rk=r(r1)(rk+1)=(1)k(r)(r+1)(kr1)=(1)k(kr1)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(n1m)\displaystyle (-1)^m \binom{-n-1}{m},可以将上指标写成 n1-n-1 的形式
然后翻转后的上指标是 n+mn + m

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

杨辉三角

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

km(rk)(1)k=(r0)(r1)++(1)m(rm)=km(kr1k)=(r+mm)=(1)m(r1m)\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{元素离开中心的距离},就有一种形式

km(rk)(r2k)=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 归纳
km+1(rk)(r2k)=km(rk)(r2k)+(rm+1)(r2m1)\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)+(r2m1)(rm+1)=(rm+1)(m+12+r2m1)\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)

关键步骤是 rrm1(rm2)!12=m+22(r(r1)(m+3)(rm2)!)=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}

二项级数的部分和

km(m+rk)xkymk=km(rk)(x)k(x+y)mk,mZ\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+rk\displaystyle (x+y)^{m+r} = \sum_{k} \binom{m+r}{k} x^k y^{m+r-k}

(x+y)m+ryr=k(m+rk)xkymk\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)rk\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)mk\displaystyle \Longrightarrow (x+y)^{m+r} \cdot (-y)^{r} = \sum_{k} \binom{-r}{k} (-x)^{k}(x+y)^{m-k}

另外,当然要求 0rm0 \geqslant r \geqslant -m

这里讲一下其他证明方法,记左边的和为 SmS_m,用组合数加法展开
Sm=km(m1+rk)xkymk+km(m1+rk1)xkymkS_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}

注意到 ySm1=km1(m1+rk)xkym1kyyS_{m-1} = \displaystyle \sum_{k \leqslant m-1} \binom{m-1+r}{k} x^{k}y^{m-1-k} \cdot y,所以

km(m1+rk)xkymk=ySm1+(m1+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

另外,xSm1=km1(m1+rk)xk+1ym1kxS_{m-1} = \displaystyle \sum_{k \leqslant m-1} \binom{m-1+r}{k}x^{k+1}y^{m-1-k},令 kk+1k' \leftarrow k+1
那么接下来所有的 kkk1k-1 代换即可

xSm1=km(m1+rk1)xkymk\displaystyle xS_{m-1} = \sum_{k \leqslant m} \binom{m-1+r}{k-1}x^k y^{m-k}

代入并反转上指标,可得

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

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

km(m+rk)(1)k=(rm), m0\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,可以得到

km(2m+1k)=km(m+kk)2mk\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}

由此可以得到一个公式

km(m+kk)2k=2m, m0\displaystyle \sum_{k \leqslant m} \binom{m+k}{k}2^{-k} = 2^m, \ m \geqslant 0

三项式

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

(rm)(mk)=(rk)(rkmk),m,kZ\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=0a,b,cna+b+c=n(a+b+c)!a!b!c!xaybzc=0a,b,cna+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)(snk)=(r+sm+n),m,nZ\displaystyle \sum_{k}\binom{r}{m+k} \binom{s}{n-k} = \binom{r+s}{m+n}, \quad m, n \in \mathbb{Z}

更一般意义的表示

k(rk)(snk)=(r+sn),nZ\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 个女人中选 nkn-k 个女人

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

注意,这里必须 l0,m,nZl \geqslant 0, m, n \in \mathbb{Z}

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

(2)\textbf{(2)}
k(lm+k)(s+kn)(1)k=(1)l+m(smnl),l0\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+k0s+k \geqslant 0

(1)k(s+kn)(1)k(s+ks+kn)(1)sn(n1s+kn)(-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)snk(lm+k)(n1sn+k)=(1)sn(ln1lm+sn)=(1)lm(smlnm+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}
假设 sm0s-m \geqslant 0,那么有 (1)l+m(smnl)(-1)^{l+m} \binom{s-m}{n-l}

至于这个结果,是否对所有的 kk 都成立?可以用归纳法证明
根据加法公式
k(l1m+k)(s+kn)(1)k+k(l1m+k1)(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)l1+m(smnl+1)+(1)l+m(sm+1nl+1)(-1)^{l-1+m} \binom{s-m}{n-l+1} + (-1)^{l+m} \binom{s-m+1}{n-l+1},再用一次加法公式,就可以得到右边

(3)\textbf{(3)}
kl(lkm)(skn)(1)k=(1)l+m(sm1lmn),l,m,n0\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

证明很简单
(lkm)(lklkm)(1)lkm(m+1lkm)\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)}
qkl(lkm)(q+kn)=(l+q+1m+n+1)m,n0,l+q0\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
kl(lkm)(kkn)=kl(lkm)(1)kn(n1kn)\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)nkl(lkm)(n1kn)(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(n1m1lmn)=(1)lmn(n1m1lmn)= (-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)lmn(l+1lmn)=(l+q+1l+qmn)=(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(1i<j<n(ai+ajaj+kij))(1j<n(aj+anan+i<jkiji>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,,an0)= \binom{a_1 + \cdots + a_n}{a_1, a_2, \cdots, a_n}, \quad (a_1, a_2, \cdots, a_n \geqslant 0)

这里的和式是对 (n12)\displaystyle \binom{n-1}{2} 个指标变量 kij(1i<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+ddij)(b+dd+ik)(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,d0= \frac{(a+b+c+d)!}{a!b!c!d!}, \quad a,b,c, d \geqslant 0

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

1i,jn, ij(1zizj)ai\prod_{1\leqslant i, j \leqslant n, \ i \neq j} \left(1-\frac{z_i}{z_j}\right)^{a_i}

完全展开成 zz 的幂时,z10z20zn0z_1^0z_2^0\cdots z_n^0 的系数

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

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

对于 i=ni = n 的情况,此时 (1zjzn)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

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

ljn(ananljn)(ajljn)=(an+ajan+0)=(an+ajan+i<jkiji>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)(ajajlji)=(ai+ajaj+(lijlji))\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=1n1jn,  kjzzjzkzj\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
先看外层的求和,对于每一个确定的 kkzjz_j 的取值有 n1n-1 种,所以乘积 (zzj)\prod(z-z_j),对应的多项式幂次 <n< n

另外由于 nnzzjzkzj\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(n1)n(n-1) 个因子完全展开成 1i,jn,ij(1zizj)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(a11,a2,,an)+C(a1,a21,,an)+C(a1,a2,,an1)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)

证明很简单

1i,jn,ij(1zizj)ai=f(0)1i,jn,ij(1zizj)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=1n1jn,kjzjzjzk=1jn,kj(1zkzj)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}

1i,jn,ij(1zizj)ai=k=1n1i,jn, ij(1zizj)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+njkmj)\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)(srmnl),l,m,nZ,n0\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+njkmj)\displaystyle \binom{s+n-j-k}{m-j} 联系起来

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

(1+y)s+njkyj=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(1xy)r+n(1+y)srxn\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)sr(1+y)^{s-r} 中取出 mlnm-l-n 项,即 (srmln)\displaystyle \binom{s-r}{m-l-n}

综上所述,原恒等式证毕

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

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

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

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

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

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

[xayb]11+2x+2y2xy=i=0(2xy2x2y)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+bi, q=ib, r=ia\displaystyle p = a+b-i, \ q = i-b, \ r = i - a,同时
ia,ib,ia+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+bi, ib, ia)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+bi)!(ib)!(ia)!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(mr+sk)(n+rsnk)(r+km+n)=(rm)(sn), m,nZ\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+nj)(kj)\sum_{j} \binom{r}{m+n-j} \binom{k}{j}

整理一下,j(rm+nj)k(mr+sk)(kj)(n+rsnk)\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+nj)(mr+sj)k(mr+sjkj)(n+rsnk)\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+nj)(mr+sj)(m+njnj)\sum_{j} \binom{r}{m+n-j} \binom{m-r+s}{j} \binom{m+n-j}{n-j}

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

(rm)j(rmrn+jm)(mr+sj)=(rm)j(rmnj)(mr+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=k2n(2nkk)(1)k\displaystyle Q_n = \sum_{k \leqslant 2^n} \binom{2^n - k}{k}(-1)^k

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

Rm=km(mkk)(1)k, m0\displaystyle R_m = \sum_{k \leqslant m} \binom{m-k}{k} (-1)^k, \ m \geqslant 0

Rm=km(mkk)(1)k, m0=km(m1kk)(1)k+km(m1kk1)(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}

kk1k' \leftarrow k-1Rm=km(m1kk)(1)k+k+1m(m2kk)(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=km1(m1kk)(1)k+(1m)(1)mkm2(m2kk)(1)k(1m1)(1)m1\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=Rm1Rm2\displaystyle R_m = R_{m-1} - R_{m-2}

这个递归式是有周期性
Rm=(Rm2Rm3)Rm2=Rm3\displaystyle R_m = (R_{m-2} - R_{m-3}) - R_{m-2} = -R_{m-3}
对于 m6m \geqslant 6,有 Rm=Rm6R_m = R_{m-6}

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

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

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

实际上,我们递推的时候,对于 ii+1i \to i+1
R(2imod6)R(2i+1mod6)R(2^i \bmod 6) \to R(2^{i+1} \bmod 6)

如果设 2i=k2^i = kR(k)R(k(2mod6))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=k0(n+k2k)(2kk)(1)kk+1+m,m,n0\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=k0(n+kk)(nk)(1)kk+1+m=k0(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+1m,m0,r{0,1,,m1}\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\}

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

Sm=k0(n+kk)(nk)(1)kk+1j0(mj)(k2j)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=k0(n+k)!k!(nk)!(1)k+jj0m!(mj)!(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!k0(n+k)!n!k!(1)k+j1(nk)!j01(mj)!(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(n1k)\displaystyle \binom{n+k}{k} = (-1)^k \binom{-n-1}{k}