二项式系数

## 二项式系数 本博客内容大部分来源于对《具体数学》第五章的整理，略去了其中有关超几何变换的部分。 需要掌握一些 $\sum$ 的处理技巧，有限微积分和泰勒展开（泰勒展开只在证明用一点点，不会也没事）。 upd. 评论区有人指出上指标求和的组合意义错了，已订正。 upd. $(13)$ 的推导中一个地方除写成乘了，已订正。 为了有一定实力的同学可以略过基本恒等式，为了您的方便，我把出现的十个恒等式列出供您参考： $$\boxed{\begin{aligned}\dbinom{n}{k}&=\dfrac{n^{\underline{k}}}{k!}=\dfrac{n!}{k!(n-k)!}\qquad\qquad\qquad\qquad\qquad\qquad(1)\\(a+b)^r&=\sum_k\dbinom{r}{k}a^kb^{r-k}(r\in\mathbb{N}\;或\;|\frac{a}{b}|<1,r\in\mathbb{R})\qquad(4)\\\dbinom{n}{k}&=\dbinom{n}{n-k},n\in\mathbb{N},k\in\mathbb{Z}\qquad\qquad\qquad\quad\ \ \qquad(5)\\\dbinom{r}{k}&=\dfrac{r}{k}\dbinom{r-1}{k-1},k\in\mathbb{Z},k\ne 0\qquad\qquad\qquad\ \ \ \qquad(6)\\\dbinom{r}{k}&=\dbinom{r-1}{k}+\dbinom{r-1}{k-1},k\in\mathbb{Z}\qquad\qquad\quad\ \ \qquad(9)\\\sum_{k\le n}\dbinom{r+k}{k}&=\dbinom{r+n+1}{n},n\in\mathbb{Z}\qquad\qquad\qquad\qquad\ \qquad(10)\\\sum_{0\le k\le n}\dbinom{k}{m}&=\dbinom{n+1}{m+1},n,m\in\mathbb{N}\qquad\qquad\qquad\qquad\ \qquad(11)\\\dbinom{r}{k}&=(-1)^k\dbinom{k-r-1}{k},k\in\mathbb{Z}\qquad\qquad\quad\ \ \ \qquad(13)\\\dbinom{r}{m}\dbinom{m}{k}&=\dbinom{r}{k}\dbinom{r-k}{m-k},m,k\in\mathbb{Z}\qquad\qquad\qquad\qquad\ (14)\\\sum_{k}\dbinom{r}{k}\dbinom{s}{n-k}&=\dbinom{r+s}{n},n\in\mathbb{Z}\qquad\qquad\qquad\qquad\qquad\qquad(15)\end{aligned}}$$ ### 基本恒等式 $\dbinom{n}{k}$ 被称为二项式系数，其组合意义为从 $n$ 个数的集合中选取大小为 $k$ 的子集的方案数。显然通过定义，我们知道定义域为 $n,k\in\mathbb{N}$，并能得到其定义式： $$\dbinom{n}{k}=\dfrac{n^{\underline{k}}}{k!}=\dfrac{n!}{k!(n-k)!}\tag{1}$$ $n^{\underline{k}}$ 意思是随便选取 $k$ 个元素，排除掉 $k!$ 种重复的情况就是上式。除此之外，二项式系数之所以被称为二项式系数，是因为有二项式定理： $$(a+b)^n=\sum_{k=0}^n\dbinom{n}{k}a^kb^{n-k}\tag{2}$$ 可以从组合意义给予证明，$a^kb^{n-k}$ 产生这一项只能通过从 $n$ 个 $(a+b)$ 中选取 $k$ 个 $a$ 和 $n-k$ 个 $b$ 达到，而方案数是 $\dbinom{n}{k}$。但我们不仅对正整数定义了指数，同时也对负整数，实数等定义了指数。当我们想展开这类的二项式时，现在的定义域就不够用了，我们需要把 $n,k$ 的取值范围拓展一下。事实上，拓展到 $n\in\mathbb{R},k\in\mathbb{Z}$ 是有益的，即： $$\dbinom{r}{k}=\begin{cases}\dfrac{r^{\underline{k}}}{k!}&k\ge 0\\0&k<0\end{cases}\tag{3}$$ 其中为了表示上指标可以取任意实数，我们用 $r$ 而不是 $n$ 表示上指标（事实上也可以取复数，但本文不讨论，之后如无特殊说明实数成立的结论对复数都成立）。这里为了避免歧义，再给出底数为实数，指数为非负整数的下降幂定义： $$r^{\underline{k}}=r(r-1)(r-2)\cdot\cdot\cdot(r-k+1)(k\in \mathbb{N},r\in \mathbb{R})$$ 显然，这种情况下，对于某些取值二项式定理就失去了组合意义，但收获了很大的数学意义。实践证明，后者的收获要远大于前者的损失。 介绍完二项式系数的基本定义后，我们先来对一个 **单独的二项式系数** $\dbinom{r}{k}$ 做些观察。首先通过定义，我们能发现 $\dbinom{r}{k}$ 是关于 $r$ 的 $k$ 次多项式，这能在估计复杂度，推导一些数学公式时用到。然后我们来看 $\dbinom{n}{n}(n\in\mathbb{Z})$ 的值，看起来它总等于 $1$，但事实上，当 $n<0$ 时，根据定义我们有 $\dbinom{n}{n}=0$。在观察更复杂的情况前，我们先来看看 $r,k$ 较小的情况： $$\begin{array}{c|c|c|c|c|c|c|c|}\mathbf{n}&\mathbf{\binom{n}{0}}&\mathbf{\binom{n}{1}}&\mathbf{\binom{n}{2}}&\mathbf{\binom{n}{3}}&\mathbf{\binom{n}{4}}&\mathbf{\binom{n}{5}}&\mathbf{\binom{n}{6}}&\cdot\cdot\cdot\\\mathbf{0}&1&0&0&0&0&0&0&\cdot\cdot\cdot\\\mathbf{1}&1&1&0&0&0&0&0&\cdot\cdot\cdot\\\mathbf{2}&1&2&1&0&0&0&0&\cdot\cdot\cdot\\\mathbf{3}&1&3&3&1&0&0&0&\cdot\cdot\cdot\\\mathbf{4}&1&4&6&4&1&0&0&\cdot\cdot\cdot\\\mathbf{5}&1&5&10&10&5&1&0&\cdot\cdot\cdot\\\mathbf{6}&1&6&15&20&15&20&1&\cdot\cdot\cdot\\\cdot\cdot\cdot&\cdot\cdot\cdot&\cdot\cdot\cdot&\cdot\cdot\cdot&\cdot\cdot\cdot&\cdot\cdot\cdot&\cdot\cdot\cdot&\cdot\cdot\cdot&\cdot\cdot\cdot\end{array}$$ 这就是大名鼎鼎的杨辉三角了，记住这些数列的特征可以当我们在实战中遇到类似的数列时往二项式系数方面考虑。除此之外，我们还可以观察到三个显然的恒等式： $$\dbinom{r}{0}=1,\dbinom{r}{1}=r,\dbinom{r}{2}=\dfrac{r(r-1)}{2}$$ 证明根据定义显然得证。除此之外，因为 $n\in\mathbb{R}$，我们可以再观察一下当 $n<0$ 时表格的值： $$\begin{array}{c|c|c|c|c|c|c|c|}\mathbf{n}&\mathbf{\binom{n}{0}}&\mathbf{\binom{n}{1}}&\mathbf{\binom{n}{2}}&\mathbf{\binom{n}{3}}&\mathbf{\binom{n}{4}}&\mathbf{\binom{n}{5}}&\mathbf{\binom{n}{6}}&\cdot\cdot\cdot\\\mathbf{0}&1&0&0&0&0&0&0&\cdot\cdot\cdot\\\mathbf{-1}&1&-1&1&-1&1&-1&1&\cdot\cdot\cdot\\\mathbf{-2}&1&-2&3&-4&5&-6&7&\cdot\cdot\cdot\\\mathbf{-3}&1&-3&6&-10&15&-21&28&\cdot\cdot\cdot\\\mathbf{-4}&1&-4&10&-20&35&-56&84&\cdot\cdot\cdot\\\cdot\cdot\cdot&\cdot\cdot\cdot&\cdot\cdot\cdot&\cdot\cdot\cdot&\cdot\cdot\cdot&\cdot\cdot\cdot&\cdot\cdot\cdot&\cdot\cdot\cdot&\cdot\cdot\cdot\end{array}$$ 如果您从左上向右下看的话，是能够看到类似正数情况的杨辉三角的。具体为什么是这样，可以等到之后我们研究完更多二项式系数恒等式时再回来解释。 接下来让我们更靠近看一看 **二项式定理** ，这个二项式系数名称的来源恒等式。上文在没有拓展上下指标定义域时，给出了它的比较狭义的式子 $(2)$： $$(a+b)^n=\sum_{k=0}^n\dbinom{n}{k}a^kb^{n-k}(n\in\mathbb{N})\tag{2}$$ 但注意到，当 $ab=0$ 或 $a+b=0$ 时，会出现 $f(x)=x^0$ 在 $f(0)$ 处取什么值的问题。这里我们并不讨论具体细节，而是发现如果令 $f(0)=1$，则一些恒等式就能成立且是正确的。因为这些恒等式太重要了，所以我们就强制规定 $f(x)=x^0$ 在 $f(0)$ 的取值为 $1$。举个例子，比如令 $a=1,b=-1$ 我们就可以得到： $$0^n=\sum_{k=0}^n(-1)^k\dbinom{n}{k}=[n=0]$$ 这意味着杨辉三角除了第一行外，其余所有行符号交错相加均能得到 $0$。除此之外，在 OI 中，我们还能用到以下的一些特殊情况： 1. $a=b=1$，我们有： $$2^n=\sum_{k=0}^n\dbinom{n}{k}$$ 可以把一堆二项式系数变为一项幂，也可以把一个幂变成一堆二项式系数。也可以用来估算时间复杂度。 2. $a=1,b=2$，我们有： $$3^n=\sum_{k=0}^n2^k\dbinom{n}{k}$$ 估计枚举子集的复杂度。 除此之外，在观察到形如一个 $\sum$ 带上一个二项式系数再带上一个幂的形式，也可以往套二项式定理方面想，在推导到二项式无法继续进行时，也可以考虑二项式定理爆拆。 刚刚说了，给出的形式是比较狭义的，因为它只允许指数是自然数。而既然我们已经把上指标拓展到全体实数了，这里也理应有一个更广义的形式： $$(a+b)^r=\sum_k\dbinom{r}{k}a^kb^{r-k}(r\in\mathbb{N}\;或\;|\frac{a}{b}|<1,r\in\mathbb{R})\tag{4}$$ 这里有一些需要注意的地方。首先这个和式是对所有整数 $k$ 求和，但如果我们限制了 $r\in\mathbb{N}$，那就只有满足 $0\le k\le r$ 的 $k$ 是非 $0$ 的，是有限和式。而如果不限制 $r$ 的取值，和式就是无限的了，则我们就要有 $|\frac{a}{b}|<1$ 来保证和式收敛。至于为什么是 $|\frac{a}{b}|<1$ 和广义二项式定理的证明，让我们考虑 $b=1,a\in\mathbb{R}$ 的情况，即： $$(1+a)^r=\sum_k\dbinom{r}{k}a^k,|a|<1$$ 考虑记左边为 $f(a)=(1+a)^r$，并把 $f(a)$ 在 $0$ 处泰勒展开掉： $$\begin{aligned}f(a)&=\dfrac{f(0)}{0!}a^0+\dfrac{f'(0)}{1!}+\dfrac{f''(0)}{2!}a^2+\cdot\cdot\cdot\\&=\sum_{k\ge 0}\dfrac{f^{(k)}(0)}{k!}a^k\end{aligned}$$ 注意到 $f(a)$ 的导数比较好做，事实上，$f^{(k)}(a)=r^{\underline{k}}(1+a)^{r-k}$，因为每次求导都会给指数减去 $1$ 并把指数乘下来。这样我们令 $a=0$ 就得到了上式： $$f(a)=\sum_{k\ge 0}\dfrac{r^{\underline{k}}}{k!}a^k=\sum_{k}\dbinom{r}{k}a^k,|a|<1$$ 而根据达朗贝尔审敛法，对于一个幂级数 $f(x)=\sum_{n\ge 0}a_nx^n$ 我们记 $$\rho=\lim _{n\rightarrow\infty}\dfrac{|a_{n+1}|}{|a_n|}$$ 则收敛半径 $R$ 为： $$\begin{cases}\dfrac{1}{\rho}&\rho\in\mathbb{R}_+\\+\infty&\rho=0\end{cases}$$ 而套用到我们的式子上，有： $$\rho=\lim_{k\rightarrow\infty}\dfrac{|\binom{r}{k+1}|}{|\binom{r}{k}|}=\lim_{k\rightarrow\infty}\dfrac{|\frac{r^{\underline{k+1}}}{(k+1)!}|}{|\frac{r^{\underline{k}}}{k!}|}=\lim_{k\rightarrow\infty}\left|\dfrac{r-k}{k+1}\right|$$ 注意到 $r<k$，所以可以去掉绝对值符号： $$\lim_{k\rightarrow\infty}\left|\dfrac{r-k}{k+1}\right|=\lim_{k\rightarrow\infty}\dfrac{k-r}{k+1}=\lim_{k\rightarrow\infty}\dfrac{k+1-r-1}{k+1}=1+\lim_{k\rightarrow\infty}\dfrac{-r-1}{k+1}=1$$ 这样我们得到，$(1+a)^r$ 的收敛半径 $R=1$。所以当 $|a|<1$ 时原式收敛。 现在我们暂时告别二项式定理，来看看其他的关于二项式系数的恒等式。首先是著名的 **对称性** ： $$\dbinom{n}{k}=\dbinom{n}{n-k},n\in\mathbb{N},k\in\mathbb{Z}\tag{5}$$ 可以从组合意义来看，即选 $k$ 个出来等于选 $n-k$ 个不出来。但要特别注意的是 $n$ 的取值范围是 $\mathbb{N}$ 而不是 $\mathbb{Z}$。（不可能是 $\mathbb{R}$，因为在后面一项中它跑到了下指标）对于 $n<0$ 的情况，大家可以自己举一些反例，这里不再赘述。从数学意义来看，当 $k<0$ 或 $k>n$ 时两边均为 $0$。（如果 $n<0$ 这个条件显然不成立）而当 $k\in[0,n]$ 时，根据定义式我们有： $$\dbinom{n}{k}=\dfrac{n!}{k!(n-k)!}=\dfrac{n!}{(n-(n-k))!(n-k)!}=\dbinom{n}{n-k}$$ 这个对称恒等式可以用来小范围改变下指标，凑一些形式。 然后是将一些东西移进或者移出二项式系数的 **吸收恒等式** ： $$\dbinom{r}{k}=\dfrac{r}{k}\dbinom{r-1}{k-1},k\in\mathbb{Z},k\ne 0\tag{6}$$ 很好记，形式挺整齐。令 $k\ne 0$ 是为了避免 $0$ 作除数。当 $k<0$ 时两边均为 $0$，否则可以从定义推出： $$\dbinom{r}{k}=\dfrac{r^{\underline{k}}}{k!}=\dfrac{r}{k}\dfrac{(r-1)^{\underline{k-1}}}{(k-1)!}=\dfrac{r}{k}\dbinom{r-1}{k-1}$$ 此外，如果把两边同时乘 $k$，还能得到不限制 $k\ne 0$ 的吸收恒等式： $$k\dbinom{r}{k}=r\dbinom{r-1}{k-1},k\in\mathbb{Z}\tag{7}$$ 除此之外，这个恒等式还有另一种形式，它可以保证下指标不变： $$(r-k)\dbinom{r}{k}=r\dbinom{r-1}{k},k\in\mathbb{Z}\tag{8}$$ 推导的话可以利用对称性： $$\begin{aligned}(r-k)\dbinom{r}{k}&=(r-k)\dbinom{r}{r-k}（根据\;(5)）\\&=r\dbinom{r-1}{r-k-1}（根据\;(7)）\\&=r\dbinom{r-1}{k}（根据\;(5)）\end{aligned}$$ 这样就证完了……吗？并不，在应用 $(5)$ 时，我们需要的前提是 $r\in\mathbb{N}_+$，但却没有在推导的条件中写明这一点，这是漏洞吗？不，我们需要对此作一番陈述。注意到两边均为关于 $r$ 的 $k+1$ 次多项式，而一个 $d$ 次多项式至多有 $d$ 个零点，（对于 $d$ 次多项式函数 $f(x)$，其可以表示为 $f(x)=k\prod_{i=1}^d(x+a_i),k\ne 0$ 的形式，当 $a_i$ 两两不同时有最多的零点）所以两个 $d$ 次多项式相减也至多有 $d$ 个零点， **或有无穷多个零点**，此时相减出来的多项式为常数多项式 $f(x)=0$，即两个多项式完全相等。而刚刚，我们证明了上述式子在 $r\in\mathbb{N}_+$ 时成立，所以已经有了无穷多个零点，这样等式左右两边就一定完全相等了。这种推理方法被称为 **多项式推理** 法，其对于将两边均为多项式的等式从整数推向实数时非常好用。但注意像 $(5)$ 那样两边就不是多项式的等式就不能用了。 我们再来练习一下多项式推理法，就以这个最重要的恒等式之一 **加法公式** 为例吧： $$\dbinom{r}{k}=\dbinom{r-1}{k}+\dbinom{r-1}{k-1},k\in\mathbb{Z}\tag{9}$$ 从 OI 来讲，它最大的用处之一就是帮助我们 $\mathcal{O}(nk)$ 递推组合数。而我们现在要从数学意义更进一步观察这个式子。就从证明开始吧，我们考虑先假设 $r\in\mathbb{N}_+$ 利用组合意义证明，再通过多项式推理法对 $r\in\mathbb{R}$ 证明。对于 $r\in\mathbb{N}_+$，我们可以把 $\dbinom{r}{k}$ 理解为从 $r$ 个球中选出 $k$ 个的方案数，而假设这 $r$ 个球中恰包含一个红球其余均为白球。则全选白色的方案数为 $\dbinom{r-1}{k}$，选到红色的方案数为 $\dbinom{r-1}{k-1}$，两项加起来就是随便选的方案数 $\dbinom{r}{k}$。而由于 $(9)$ 中两边相减为关于 $r$ 的 $k$ 次多项式，所以通过多项式推理法，我们得到其对于 $r\in\mathbb{R}$ 均成立。 除此之外，我们还可以应用刚刚看到的恒等式 $(7),(8)$ 证明，两式相加有： $$(r-k)\dbinom{r}{k}+k\dbinom{r}{k}=r\dbinom{r-1}{k}+r\dbinom{r-1}{k-1}$$ 左边就是 $r\dbinom{r}{k}$，这样等式两边同时除以 $r$ 就得到了 $(9)$。当然这种推理对 $r=0$ 时不成立，简单代入验证一下就好。顺带一提，我们还能用定义来证明 $(9)$，大家可以自己试试。这些证明虽然截然不同，但本质是相同的，因为不同恒等式之间可以相互推导。 加法公式非常有用，可以以它为起点我们可以归纳出许多其他的恒等式。考虑把反复展开具有最小下指标的项： $$\begin{aligned}\dbinom{5}{3}&=\dbinom{4}{3}+\dbinom{4}{2}\\&=\dbinom{4}{3}+\dbinom{3}{2}+\dbinom{3}{1}\\&=\dbinom{4}{3}+\dbinom{3}{2}+\dbinom{2}{1}+\dbinom{2}{0}\\&=\dbinom{4}{3}+\dbinom{3}{2}+\dbinom{2}{1}+\dbinom{1}{0}+\dbinom{1}{-1}\end{aligned}$$ 好了，现在 $\dbinom{1}{-1}$ 没了，推导到此停止。通过归纳，我们可以证明以下的一般公式，称为 **平行求和法**： $$\sum_{k\le n}\dbinom{r+k}{k}=\dbinom{r+n+1}{n},n\in\mathbb{Z}\tag{10}$$ 注意这里并不限制 $k$ 的下限，因为所有 $k<0$ 对应的项均为 $0$。除此之外，我们通过反复展开具有最大指标的项，（留给读者自行展开）可以归纳证明： $$\sum_{0\le k\le n}\dbinom{k}{m}=\dbinom{n+1}{m+1},n,m\in\mathbb{N}\tag{11}$$ 这一恒等式被称为 **上指标求和**。这一恒等式中需要限制 $k$ 的下限 $0$，因为 $k<0$ 的项并不为 $0$。这一恒等式有组合意义，表示从编号为 $0\sim n$ 的球中选出 $m+1$ 个，则选出的球编号最大为 $k$ 时方案数有 $\dbinom{k}{m}$ 种。 对于上述两个恒等式，我们不仅能通过归纳法证明，还可以相互证明，具体来讲有： $$\begin{aligned}\sum_{k\le n}\dbinom{m+k}{k}&=\sum_{-m\le k\le n}\dbinom{m+k}{k}（因为所有\;k<0\;的项均为\;0）\\&=\sum_{-m\le k\le n}\dbinom{m+k}{m}（根据\;(5)）\\&=\sum_{0\le k\le m+n}\dbinom{k}{m}（用\;k\;替换\;m+k）\\&=\dbinom{m+n+1}{m+1}（根据\;(11)）\\&=\dbinom{m+n+1}{n}（根据\;(5)）\end{aligned}$$ 这样我们就通过 $(11)$ 证明出了 $(10)$。而通过 $(10)$ 证明 $(11)$ 思路是类似的，都是通过整理和式来满足形式，留作练习。这里需要特别强调的一点是为什么在第一步非得限制一下 $k$ 的下限，这是因为如果我们要在第二步应用 $(5)$ 就得保证 $m+k\ge 0$。 刚刚我们给出了上指标求和的公式，联想有限微积分，这又是一个比较整齐的和式，有没有可能通过有限微积分来找到封闭形式呢？那我们要考虑找到 $\dbinom{k}{m}$ 的差分，即： $$\Delta\left(\dbinom{k}{m}\right)=\dbinom{k+1}{m}-\dbinom{k}{m}=\dbinom{k}{m-1}（根据\;(5)）$$ 这样，应用有限微积分的技术，我们能得到： $$\sum\dbinom{k}{m}\delta k=\dbinom{k}{m+1}+C\tag{12}$$ 我们看了很多二项式的恒等式了，是时候回过头研究一下当上指标是负整数时二项式系数的取值了。回忆上文所画的表格，我们可以发现负数和正数对应的表格都有杨辉三角的形式，只不过方向不一样。所以上指标为正数时和负数时一定有些转化关系，事实上，我们有： $$\dbinom{r}{k}=(-1)^k\dbinom{k-r-1}{k},k\in\mathbb{Z}\tag{13}$$ 证明非常简单。当 $k\ge 0$ 时，我们有 **上指标反转** 的公式： $$\begin{aligned}r^{\underline{k}}&=r(r-1)(r-2)\cdot\cdot\cdot(r-k+1)\\&=(-1)^k(-r)(1-r)(2-r)\cdot\cdot\cdot(k-r-1)\\&=(-1)^k(k-r-1)^{\underline{k}}\end{aligned}$$ 两边同时除 $k!$ 即得 $(13)$。$k<0$ 时两边均为 $0$。上指标反转非常重要，它可以推导出许多其他的恒等式且不需要附加额外条件。 比如根据： $$\begin{aligned}&\dbinom{n+m}{n}=(-1)^n\dbinom{-m-1}{n}\\&\dbinom{n+m}{m}=(-1)^m\dbinom{-n-1}{m}\end{aligned},n,m\in\mathbb{N}$$ 我们有： $$(-1)^n\dbinom{-m-1}{n}=(-1)^m\dbinom{-n-1}{m},n,m\in\mathbb{N}$$ 这能让我们在上下指标位置之间移动量。 除此之外，我们还能找到在杨辉三角的每一行中的一部分交错符号相加的结果： $$\begin{aligned}\sum_{k\le m}(-1)^k\dbinom{r}{k}&=\sum_{k\le m}\dbinom{k-r-1}{k}（根据\;(13)）\\&=\dbinom{-r+m}{n}（根据\;(10)）\\&=(-1)^m\dbinom{r-1}{m}（根据\;(13)）\end{aligned}$$ 现在我们大多处理的是关于二项式系数的和式，如果出现乘积呢？这里有一个 **三项式版恒等式**： $$\dbinom{r}{m}\dbinom{m}{k}=\dbinom{r}{k}\dbinom{r-k}{m-k},m,k\in\mathbb{Z}\tag{14}$$ 当 $k=1$ 时，$(14)$ 跟 $(7)$ 其实是相同的。证明我们依然可以采用先对 $r\ge m\ge k\ge 0$ 的特殊情况证明，然后用多项式推理法推到 $\mathbb{R}$。根据定义展开，我们有： $$\begin{aligned}\dbinom{r}{m}\dbinom{m}{k}&=\dfrac{r!}{m!(r-m)!}\dfrac{m!}{k!(m-k)!}\\&=\dfrac{r!}{k!(r-m)!(m-k)!}\\&=\dfrac{r!}{k!(r-k)!}\dfrac{(r-k)!}{(r-m)!(m-k)!}\\&=\dbinom{r}{k}\dbinom{r-k}{m-k}\end{aligned}$$ 当 $k,m<0$ 时，$(14)$ 的两边均为 $0$。所以这个等式对于 $k,m\in\mathbb{Z},r\in\mathbb{N}$ 成立了，而因为两边均为关于 $r$ 的 $m$ 次多项式，所以通过多项式推理法，它对 $r\in\mathbb{R}$ 也成立。通常来讲，这个等式两边总会有一边更容易计算。比如如果我们是关于 $m$ 求和，可能就更想要右边的式子而不是左边的，因为右式仅有一个 $m$。 接下来来点更恐怖的，也是本文介绍的最后一个恒等式，是关于求和和乘积结合的范德蒙德卷积： $$\sum_{k}\dbinom{r}{k}\dbinom{s}{n-k}=\dbinom{r+s}{n},n\in\mathbb{Z}\tag{15}$$ 说它是卷积是因为它的下指标有卷积的形式，可以利用这点方便记忆。证明依然是老套路，我们假设 $r,s\in\mathbb{N}$，则该式具有组合意义。$\dbinom{r+s}{n}$ 表示从 $r$ 个红球 $s$ 个白球拿出 $n$ 个球的方案数。而 $\sum_{k}\dbinom{r}{k}\dbinom{s}{n-k}$ 表示拿出 $k$ 个红球，$n-k$ 个白球的方案数，对 $k$ 求和就得到所有的方案数。那因为两边均为关于 $r,s$ 的 $n$ 次多项式，多项式推理法告诉我们 $r,s\in\mathbb{R}$ 的情况也成立。 范德蒙德卷积的用处在于可以通过前面的恒等式稍作变化，简化一些（或者让它们暂时变复杂）一些和式加乘积的形式。举个例子，证明： $$\sum_k\dbinom{l}{m+k}\dbinom{s}{n+k}=\dbinom{l+s}{l-m+n},l\in\mathbb{N},m,n\in\mathbb{Z}\tag{16}$$ 看起来有范德蒙德卷积的形式，但还不太像，因为多了一个字母 $m$。不过没关系，我们用 $k$ 代替 $k+m$，$n$ 代替 $n-m$，立马可以得到： $$\sum_k\dbinom{l}{k}\dbinom{s}{n+k}=\dbinom{l+s}{l+n}$$ 还是不太像，下指标之和不是定值。不过没有关系，我们对 $\dbinom{l}{k}$ 运用 $(5)$ 对称性： $$\sum_k\dbinom{l}{l-k}\dbinom{s}{n+k}=\dbinom{l+s}{l+n}$$ 搞定，这就是范德蒙德卷积的形式了。不过从上面的推导我们可以看出，有时给范德蒙德卷积多一个变量是有益的，这样不用因为要给推导的恒等式少一个变量头疼了。具体来讲，我们设 $m\in\mathbb{Z}$，则用 $k+m$ 代替 $k$ 可以得到： $$\sum_k\dbinom{r}{k+m}\dbinom{s}{n-m-k}=\dbinom{r+s}{n}$$ 用 $n$ 代替 $n-m$ 可以得到更好看的式子： $$\sum_k\dbinom{r}{k+m}\dbinom{s}{n-k}=\dbinom{r+s}{n+m}\tag{17}$$ 这样我们在推导上面那个恒等式时，直接对 $\dbinom{l}{m+k}$ 用对称性，套 $(16)$ 就可以证明了。 注意 $(16)$ 和 $(17)$ 的相似性和区别性。相似的是，它们均由两个二项式系数相乘带上一个和式得到，且两个二项式系数下指标中均有求和指标。不同的是，它们下指标中求和指标的符号不同。这提示我们遇到类似范德蒙德卷积的式子时根据求和指标的位置和符号选择合适的恒等式，这里给出由范德蒙德卷积导出的 $4$ 个恒等式，注意观察求和指标的位置和符号： $$\boxed{\begin{aligned}\sum_k\dbinom{l}{m+k}\dbinom{s}{n+k}&=\dbinom{l+s}{l-m+n},l\in\mathbb{N},m,n\in\mathbb{Z}\qquad\quad(16)\\\sum_k\dbinom{l}{m+k}\dbinom{s+k}{n}(-1)^k&=(-1)^{l+m}\dbinom{s-m}{n-l},l\in\mathbb{N},n,m\in\mathbb{Z}\quad(18)\\\sum_{k\le l}\dbinom{l-k}{m}\dbinom{s}{k-n}(-1)^k&=(-1)^{l+m}\dbinom{s-m-1}{l-m-n},l,m,n\in\mathbb{N}\quad\ (19)\\\sum_{-q\le k\le l}\dbinom{l-k}{m}\dbinom{q+k}{n}&=\dbinom{l+q+1}{m+n+1},n,m,l+q\in\mathbb{N}\quad\qquad(20)\end{aligned}}$$ 如果记不住也可以寄希望于人类智慧，用的时候通过对称性，反转上指标之类的由范德蒙德卷积推导。 这就是《具体数学》上给出的最重要的十个二项式系数恒等式的介绍了，接下来我们来看点练习。 ### 练习和技巧 我们先来看一些利用前面恒等式的练习题，然后会有三个技巧。 #### 第一道练习 化简： $$\sum_{k=0}^nk\dfrac{\binom{m-k-1}{m-n-1}}{\binom{m}{n}},m,n\in\mathbb{N},m>n$$ 这看起来非常恐怖，首先我们就可以注意到，分母里不含任何求和指标，所以可以把它直接移出和式，现在我们要化简的和式为： $$\sum_{k=0}^n k\dbinom{m-k-1}{m-n-1}$$ 但看起来还是很棘手。不过观察到 $k$ 只在上指标中出现了，如果没有多出来的 $k$，我们可以改变一下求和指标的意义后用上指标求和 $(11)$。而面对这个多出来的 $k$，我们可以考虑用吸收恒等式那一套把 $k$ 给吸收进去。但很遗憾，看完所有的吸收恒等式后，会发现没有一个能用的。但是，如果我们用 $m-k$ 代替 $k$，就能用恒等式 $(7)$ 得到： $$(m-k)\dbinom{m-k-1}{m-n-1}=(m-n)\dbinom{m-k}{m-n}$$ 这样 $k$ 就只在二项式系数中出现了。在原式中，我们可以把 $k$ 改写为 $m-(m-k)$ 从而避免烦人的指标变换： $$\begin{aligned}\sum_{k=0}^n k\dbinom{m-k-1}{m-n-1}&=\sum_{k=0}^n m\dbinom{m-k-1}{m-n-1}-\sum_{k=0}^n (m-k)\dbinom{m-k-1}{m-n-1}\\&=m\sum_{k=0}^m\dbinom{m-k-1}{m-n-1}-(m-n)\sum_{k=0}^n\dbinom{m-k}{m-n}\end{aligned}$$ 接下来就简单了，化简两个和式里面的内容就好。我们先看看起来比较简单的 $\sum_{k=0}^n\dbinom{m-k}{m-n}$，只需让 $k$ 代替 $m-k$，有： $$\begin{aligned}\sum_{k=0}^n\dbinom{m-k}{m-n}&=\sum_{k=m-n}^m\dbinom{k}{m-n}\\&=\sum_{k=0}^m\dbinom{k}{m-n}\\&=\dbinom{m+1}{m-n+1}（上指标求和\;(11)）\end{aligned}$$ 另一个很类似，只需用 $m$ 代替 $m+1$ 就好，所以原式又等于： $$m\dbinom{m}{m-n}-(m-n)\dbinom{m+1}{m-n+1}$$ 因为 $\binom{m+1}{m-n+1}=\frac{(m+1)!}{(m-n+1)!n!}=\frac{m+1}{m-n+1}\frac{m!}{n!(m-n)!}=\binom{m}{m-n}$，所以有： $$\begin{aligned}m\dbinom{m}{m-n}-(m-n)\dbinom{m+1}{m-n+1}&=(m-(m-n)\dfrac{m+1}{m-n+1})\dbinom{m}{m-n}\\&=\dfrac{n}{m-n+1}\dbinom{m}{m-n}\end{aligned}$$ 带回原式有： $$\sum_{k=0}^nk\dfrac{\binom{m-k-1}{m-n-1}}{\binom{m}{n}}=\dfrac{\frac{n}{m-n+1}\binom{m}{m-n}}{\binom{m}{n}}=\dfrac{n}{m-n+1}$$ #### 第二道练习 定义： $$Q_n=\sum_{k\le 2^n}\dbinom{2^n-k}{k}(-1)^k,n\in\mathbb{N}$$ 求 $Q_{10^6}$ 的值。 看起来非常棘手，想开始写代码求解的同学先坐下，我们数学推导完就可以 $\mathcal{O}(1)$ 求解了。好吧，看起来这题没什么思路，您可以试一下上述所有的恒等式，在这里面都不会化简太多。当我们没思路的时候，可以考虑观察一下小数据，事实上，通过手玩我们有： $$Q_0=1,Q_1=0,Q_2=-1,Q_3=0,\cdot\cdot\cdot$$ 看起来非常有规律，但也仅仅停留在非常有规律，我们还是什么都不知道。事实上，我们想找到一个递归式，但这就需要把 $Q_n$ 和比较近的项关联，但 $Q_n,Q_{n-1}$ 中的二项式系数上指标相差是指数级别的，我们根本不可能用像加法公式这样的恒等式计算。一个 Key Observation 是，$n$ 出现的情况均为 $2^n$，所以可以考虑换元。令 $m=2^n$ 有： $$R_m=\sum_{k\le m}\dbinom{m-k}{k}(-1)^k$$ 我们有 $Q_n=R_{2^n}$，所以当我们对 $R$ 找到封闭形式时，$Q$ 也能找到。而 $R$ 中的二项式系数更加友好了，我们可以尝试使用加法公式找到递归式： $$\begin{aligned}R_m&=\sum_{k\le m}\dbinom{m-k}{k}(-1)^k\\&=\sum_{k\le m}\dbinom{m-k-1}{k}(-1)^k+\sum_{k\le m}\dbinom{m-k-1}{k-1}(-1)^k\\&=\sum_{k\le m}\dbinom{m-k-1}{k}(-1)^k+\sum_{k\le m-1}\dbinom{m-2-k}{k}(-1)^{k+1}\\&=\left(\sum_{k\le m-1}\dbinom{m-1-k}{k}(-1)^k+\dbinom{-1}{m}(-1)^m\right)\\&\quad+(-1)\left(\sum_{k\le m-2}\dbinom{m-2-k}{k}(-1)^k+\dbinom{-1}{m-1}(-1)^{m-1}\right)\\&=R_{m-1}+(-1)^{2m}-R_{m-2}-(-1)^{(2(m-1))}=R_{m-1}-R_{m-2}\end{aligned}$$ 这里的推导有几个需要注意的地方。首先倒数第二步我们用了 $\dbinom{-1}{m}=(-1)^m$ 的结论，事实上，它可以由上指标反转 $(13)$ 这样推出： $$\dbinom{-1}{m}=(-1)^m\dbinom{m-(-1)-1}{m}=(-1)^m$$ 注意到我们这里能说 $\dbinom{m}{m}=1$ 是因为 $m\ge 0$。然后是这个推导的思路，我们通过加法公式将 $R_m$ 变成了好几项，并尝试凑出 $R$ 的格式，这类似于处理和式时的扰动法。这样，只要 $m\ge 3$，我们就有： $$R_m=R_{m-1}-R_{m-2}=(R_{m-2}-R_{m-3})-R_{m-2}=-R_{m-3}$$ 这样，只要 $m\ge 6$，就有 $R_m=R_{m-6}$。所以 $R$ 是以 $6$ 为循环节循环的。可以根据上述递推式快速求出 $m=0\sim 5$ 时 $R_m$ 的值，从而得出总的封闭形式： $$R_m=\begin{cases}1\\1\\0\\-1\\-1\\0\end{cases}，如果\;m\bmod6=\begin{cases}0\\1\\2\\3\\4\\5\end{cases}$$ 最后，我们从 $R$ 的封闭形式尝试找到 $Q$ 的封闭形式。也就是找到 $2^n\bmod6$ 的规律。事实上，它是这样的序列：$\left<1,2,4,2,4,2,4\cdot\cdot\cdot\right>$。所以 $Q$ 的封闭形式为： $$Q_n=\begin{cases}1&n=0\\0&n\equiv1\pmod{2}\\-1&\mathtt{otherwise}\end{cases}$$ 回到最初的问题，显然我们有 $Q_{10^6}=-1$。 #### 第三道练习题 化简： $$\sum_k\dbinom{n}{k}\dbinom{s}{k}k,n\in\mathbb{N}$$ 还记得刚刚证明过的恒等式 $(16)$ 吗？注意到这个式子下指标里都有求和指标 $k$ 且符号相同，可以尝试往那个方面套。显然我们的最大阻碍还是游离的 $k$，依然考虑吸收恒等式 $(7)$： $$\sum_k\dbinom{n}{k}\dbinom{s}{k}k=s\sum_k\dbinom{n}{k}\dbinom{s-1}{k-1}$$ 这样就可以用恒等式 $(16)$ 并直接得出答案了： $$s\sum_k\dbinom{n}{k}\dbinom{s-1}{k-1}=s\dbinom{n+s-1}{n-1}$$ 当然，这道题的想法都是比较直接的，为什么我要把它拿出来说呢？注意到其实我们第一步选择吸收恒等式的时候有两种选择，可以把 $k\dbinom{s}{k}$ 当做一个整体，可以把 $k\dbinom{n}{k}$ 当做一个整体，但我们却选择了前者。是等价的吗？不，我们只能选择前者。因为如果选择后者，我们会得到： $$n\sum_k\dbinom{s}{k}\dbinom{n-1}{k-1}$$ 而注意到 $s$ 是没有取值限制的，$n-1$ 是可能取负数的。但 $(16)$ 要求上指标至少一个是非负数，所以就无法套用了。这个式子提醒我们在套用恒等式时注意取值范围。 #### 一些技巧 《具体数学》上还有 $3$ 道练习，大家如果觉得刚刚三题不够的话可以再去练一练。我们接下来要进入处理技巧了。 首先是形如 $\dbinom{n-\frac{1}{2}}{k},n,k\in\mathbb{Z}$ 的式子，它可以被转化为两个二项式系数相乘的形式，从而推导出一类新的恒等式。首先，我们有 **加倍公式**： $$r^{\underline{k}}\left(r-\dfrac{1}{2}\right)^{\underline{k}}=\dfrac{(2r)^{\underline{2k}}}{2^{2k}},k\in\mathbb{N}\tag{21}$$ 证明比较显然，将左边的式子展开就好： $$\begin{aligned}r\left(r-\dfrac{1}{2}\right)(r-1)\left(r-\dfrac{3}{2}\right)&\cdot\cdot\cdot(r-k+1)\left(r-k+\dfrac{1}{2}\right)\\&=\dfrac{(2r)(2r-1)\cdot\cdot\cdot(2r-2k+1)}{2^k}\end{aligned}$$ 现在我们在加倍公式的两边同时除以 $(k!)^2$，则有： $$\dbinom{r}{k}\dbinom{r-\frac{1}{2}}{k}=\dfrac{\dbinom{2r}{2k}\dbinom{2k}{k}}{2^{2k}},k\in\mathbb{N}\tag{22}$$ 其中可能引起迷惑的是 $\dfrac{(2r)^{\underline{2k}}}{(k!)^2}=\dbinom{2r}{2k}\dbinom{2k}{k}$ 这一步。事实上，它不过是在分子分母同时乘上 $(2k)^{\underline{k}}$ 得到的结果。言归正传，如果我们令 $k=r=n,n\in\mathbb{N}$，则有： $$\dbinom{n-\frac{1}{2}}{n}=\dfrac{\dbinom{2n}{n}}{2^{2n}}$$ ~~突然发现好像卡特兰数，有没有人出道题~~ 而如果我们对左边反转上指标，有： $$\begin{aligned}\dbinom{n-(n-\frac{1}{2})-1}{n}(-1)^n&=\dfrac{1}{2^{2n}}\dbinom{2n}{n}\\\dbinom{-\frac{1}{2}}{n}&=\left(-\dfrac{1}{4}\right)^n\dbinom{2n}{n},n\in\mathbb{N}\tag{22}\end{aligned}$$ 除此之外，如果我们根据范德蒙德卷积 $(15)$，则有： $$\sum_k\dbinom{-\frac{1}{2}}{k}\dbinom{-\frac{1}{2}}{n-k}=\dbinom{-1}{n}=(-1)^n,n\in\mathbb{N}$$ 代入 $(22)$ 有： $$\dbinom{-\frac{1}{2}}{k}\dbinom{-\frac{1}{2}}{n-k}=\left(-\dfrac{1}{4}\right)^k\dbinom{2k}{k}\left(-\dfrac{1}{4}\right)^{n-k}\dbinom{2(n-k)}{n-k}$$ 代回，有： $$\sum_k\dbinom{2k}{k}\dbinom{2n-2k}{n-k}\left(-\dfrac{1}{4}\right)^n=(-1)^n$$ 即： $$\sum_k\dbinom{2k}{k}\dbinom{2n-2k}{n-k}=4^n,n\in\mathbb{N}$$ 通过上面对加倍公式的相关阐释，我们得到的技巧是，面对形如 $\dbinom{2k}{k}$ 的二项式系数时，可以考虑转化为 $\dbinom{n-\frac{1}{2}}{k}$ 的形式，其中 $n$ 是某个适当的整数（如 $0,1,k$ 等），这样再根据上面的恒等式或其他恒等式化简就会简单得多。 技巧二是是利用高阶差分，也就是研究有限微积分中定义的算子 $\Delta$ 和二项式系数之间的关系。我们定义函数 $f$ 在 $x$ 点的差分 $\Delta f$ 为： $$\Delta f(x)=f(x+1)-f(x)$$ 既然要研究高阶差分，我们就先来研究研究小数据。再次利用差分，我们可以得到二阶差分： $$\Delta^2f(x)=f(x+2)-2f(x+1)+f(x)$$ 好像有点杨辉三角的影子？我们再尝试再多用几次差分： $$\begin{aligned}\Delta^3f(x)&=f(x+3)-3f(x+2)+3f(x+1)-f(x)\\\Delta^4f(x)&=f(x+4)-4f(x+3)+6f(x+2)-4f(x+1)+f(x)\end{aligned}$$ 现在我们完全看到杨辉三角的样子了，我们可以猜测结论： $$\Delta^nf(x)=\sum_k\dbinom{n}{k}(-1)^{n-k}f(x+k)\tag{23}$$ 通过归纳，我们可以很方便的证明。但我们还有更简单的方法。我们定义平移算子 $\text{E}$ 为： $$\mathrm{E}f(x)=f(x+1)$$ 定义恒等算子 $1$ 为： $$1f(x)=f(x)$$ 则显然有：$\Delta=\mathrm{E}-1$，则有： $$\Delta^n=(\mathrm{E}-1)^n=\sum_k\dbinom{n}{k}\mathrm{E}^k(-1)^{n-k}$$ 由于 $\mathrm{E}^k f(x)=f(x+k)$，所以上式等价于 $(23)$。 我们来考虑负的下降幂，情况十分有趣，我们设 $f(x)=(x-1)^{-1}=\frac{1}{x}$，则根据有限微积分的结论： $$\Delta\left(x^{\underline{m}}\right)=mx^{\underline{m-1}}$$ 有： $$\Delta^n\left((x-1)^{\underline{-1}}\right)=(-1)^{\underline{n}}(x-1)^{\underline{-n-1}}=(-1)^n\dfrac{n!}{x^{\overline{n+1}}}$$ 如果代入 $(23)$ 中，我们有： $$\sum_k\dbinom{n}{k}\dfrac{(-1)^k}{x+k}=\dfrac{n!}{x^{\overline{n+1}}}=\dfrac{1}{x\binom{x+n}{n}},x\notin\{x|-n\le x\le 0,x\in\mathbb{Z}\}\tag{24}$$ 上面所有的等式如果变换不理解的话，均可以通过展开上升幂或者下降幂的方法证明。这样我们得到了一个关于二项式系数带分母交错求和的恒等式。 除此之外，我们还能研究正的下降幂，显然 $x^{\underline{d}}(d>0)$ 是关于 $x$ 的 $d$ 次不等式。则如果设 $f(x)=x^{\underline{d}}$，$\Delta^df(x)$ 就为一个常数，而当 $n>d$ 时，$\Delta^nf(x)=0$。事实上，上面的描述对所有 $d$ 次多项式均适用。这个结论在推导时可以帮助简化公式。 然后我们还能通过下降幂和通常幂的关系来找到一些关系（事实上，见到二项式系数和普通幂掺和到一起时，就要考虑转下降幂了，因为二项式系数和下降幂很搭，详见：[P6620 [省选联考 2020 A 卷] 组合数问题](https://www.luogu.com.cn/problem/P6620)），我们设 $$f(x)=\sum_{0\le k\le d}a_kx^k$$ 是一个 $d$ 次多项式，则根据： $$x^n=\sum_{k}\begin{Bmatrix}n\\k\end{Bmatrix}x^{\underline{k}}$$ 所以如果我们设 $b_k=\sum_{j}\begin{Bmatrix}k\\j\end{Bmatrix}$，则 $f(x)$ 还可以被表示为： $$f(x)=\sum_{0\le k\le d}b_kx^{\underline{k}}$$ 更进一步，如果我们设 $c_k=k!b_k$，则 $f(x)$ 又等于： $$f(x)=\sum_{0\le k\le d}c_k\dbinom{x}{k}$$ 从而，我们能把任意多项式表示为二项式系数的倍数之和，这种展开被称为 **牛顿级数**。根据加法公式 $(5)$，我们有： $$\Delta\left(\dbinom{x}{k}\right)=\dbinom{x}{k-1}$$ 则容易得到： $$\Delta^nf(x)=\sum_{0\le k\le d}c_k\dbinom{x}{k-n}$$ 如果我们令 $x=0$，则除了 $k=n$ 的那一项外，其余均为 $0$，即： $$\Delta^n f(0)=\begin{cases}c_n&n\le d\\0&n>d\end{cases}$$ 所以我们就有多项式 $f(x)$ 牛顿级数的另一种形式： $$f(x)=\sum_{0\le k\le d}\Delta^kf(0)\dbinom{x}{k}$$ 如果代入 $(23)$，我们还能得到另一种推导形式： $$f(x)=\sum_{0\le k\le d}\dbinom{n}{k}(-1)^kf(k)=(-1)^nc_n,n\in\mathbb{N}\tag{25}$$ 从而，我们可以证明： $$f(x)=\sum_{0\le k\le d}\dbinom{n}{k}(-1)k(a_0+a_1k+\cdot\cdot\cdot+a_nk^n)=(-1)^nn!a_n,n\in\mathbb{N}\ (26)$$ 它成立是因为多项式 $a_0+a_1k+\cdot\cdot\cdot+a_nk^n$ 能被牛顿级数 $c_0\dbinom{k}{0}+c_1\dbinom{k}{1}+\cdot\cdot\cdot+c_n\dbinom{k}{n}$ 表示，其中 $c_n=n!b_n=n!a_n$。 说了这么多，高阶差分到底有啥用呢，它可以用来化简一些无从下手的式子，比如这个： $$\sum_k\dbinom{n}{k}\dbinom{r-sk}{n}(-1)^k,n\in\mathbb{N}$$ 看起来很无从下手，但我们发现一个非常关键的地方，这里有 $\sum_k\dbinom{n}{k}(-1)^k$ 的形式，而如果我们设 $f(k)=\dbinom{r-sk}{n}$，则会有： $$f(k)=\dbinom{r-sk}{n}=\dfrac{1}{n!}(-1)^ns^nk^n+\cdot\cdot\cdot=(-1)^ns_n\dbinom{k}{n}+\cdot\cdot\cdot$$ 这个可以把二项式系数通过下降幂的形式展开，然后观察怎么得到 $k^n$ 项来找到 $n$ 次项的系数。如果我们把它换成牛顿级数的形式，因为 $c_n=n!b_n=n!a_n$，所以有 $(-1)^ns_n\binom{k}{n}$。然后不管是根据第一种形式套 $(26)$ 还是第二种形式套 $(25)$，结果都是一样的，均为： $$\sum_{k}\dbinom{n}{k}\dbinom{r-sk}{n}(-1)^k=s^n,n\in\mathbb{N}$$ 《具体数学》上之后对于高阶差分还有跟泰勒级数比较的讨论，但本文不再涉及。我们直接进入下一个技巧，二项式反演（本文这一部分会把重点放在 OI 相关）。那我们就先从人尽皆知的式子和证明开始吧。首先我们有基本式子： $$f_n=\sum_{i=0}^n\dbinom{n}{i}g_i \Leftrightarrow g_n=\sum_{i=0}^n\dbinom{n}{i}f_i(-1) ^{n-i},n\in\mathbb{N}\tag{27}$$ 这个公式可以完成从“至多”到“恰好”的转换（ $f_n$ 表示“至多”，$g_n$ 表示“恰好”。） $$f_k=\sum_{i=k}^n \dbinom{i}{k}g_i \Leftrightarrow g_k=\sum_{i=k}^n\dbinom{i}{k}f_i(-1)^{i-k},n\in\mathbb{N}\tag{28}$$ 这个公式可以完成从“至少”到“恰好”的转换（ $f_n$ 表示“至少”， $g_n$ 表示“恰好”。 ） 给出代数证明：（或者可以直接套牛顿级数的公式） $$\begin{aligned}g_n&=\sum_{i=0}^n \dbinom{n}{i}f_i(-1)^{n-i}=\sum_{i=0}^n(-1)^{n-i}\dbinom{n}{i}\sum_{j=0}^i\dbinom{i}{j}g_j （带入\ f_n\ 的定义）\\&=\sum_{j=0}^n g_j\sum_{i=j}^n(-1)^{n-i}\dbinom{n}{i}\dbinom{i}{j} （交换求和顺序）\\&=\sum_{j=0}^ng_j\sum_{i=j}^n (-1)^{n-i}\dbinom{n}{j}\dbinom{n-j}{i-j}（根据三项式版恒等式\ (14)）\\&=\sum_{j=0}^n g_j(1+(-1))^{n-j}\dbinom{n}{j}（根据二项式定理\ (2)）\\&=\sum_{j=0}^ng_j\dbinom{n}{j}[n=j] （当且仅当\ n=j\ 时\ (1+(-1))^{n-j}=1）\\&=g_n （当且仅当\ n=j\ 时原式有值，且\ \dbinom{n}{n}=1）\end{aligned}$$ 另一种公式证明类似。 来看一个实际问题，设一个排列 $\mathcal{P}=\left<1,2,\cdot\cdot\cdot,n\right>$，将 $\mathcal{P}$ 任意重排。设 $f_{n,k}$ 表示长为 $n$ 的排列重排后恰有 $k$ 个元素满足 $\mathcal{P}_i=i$ 的方案数。我们来研究一下这个 $f_{n,k}$。首先根据 OI 的做题经验，我们很容易想到把恰好给干掉，考虑设 $g_{n,k}$ 表示至少有 $k$ 个元素满足 $\mathcal{P}_i=i$ 的方案数。显然我们有 $g_{n,k}=\dbinom{n}{k}(n-k)!$ 即选 $k$ 个元素满足该条件，剩下的随便。则根据二项式反演，我们有： $$f_{n,k}=\sum_{i=k}^n\dbinom{i}{k}g_{n,i}(-1)^{i-k}=\sum_{i=k}^n\dbinom{i}{k}\dbinom{n}{i}(n-i)!(-1)^{i-k}$$ 利用三项式版恒等式，可以简化为： $$\sum_{i=k}^n\dbinom{n}{k}\dbinom{n-k}{i-k}(n-i)!(-1)^{i-k}=\dbinom{n}{k}\sum_{i=k}^n\dbinom{n-k}{i-k}(n-i)!(-1)^{i-k}$$ 这样，就可以做到 $\mathcal{O}(n)$ 计算了。其中后面那一坨 $\sum_{i=k}^n\dbinom{n-k}{i-k}(n-i)!(-1)^{i-k}$ 其实就是 $n-k$ 个元素的错排数。因为这个式子还有一种理解方式是，我钦定 $k$ 个满足 $\mathcal{P}_i=i$，其余均不满足，那方案数自然就是 $n-k$ 的错排。 再来看道例题吧： > [P4859 已经没有什么好害怕的了](https://www.luogu.com.cn/problem/P4859) > > 给出长度为 $n$ 的两个集合 $A=\{a_i\}$ 和 $B=\{b_i\}$ ，将它们两两配对，求在所有可能中，满足存在 $p$ 组 $(a_i,b_i)$ 使得 $b_i<a_i$ ，存在 $q$ 组$(a_i,b_i)$ 使得 $b_i>a_i$ 且 $p-q=k$ 的情况个数，对 $10^9+9$取模（ $1\le n\le 2000,0\le k\le n$ ）。 对于这种直接求不好求的题目，我们的方法还是像刚刚的例子一样，先钦定一个东西，再二项式反演搞一下。这题我们可以令 $g_i$ 表示钦定 $i$ 对满足 $a_i > b_i$ 的情况，$f_i$ 表示恰好存在 $i$ 对满足 $a_i >b_i$ 的情况。可以看出 $g_i$ 表示“至少”有 $i$ 个，$f_i$ 表示“恰好”有 $i$ 个，它们之间可以用二项式反演建立桥梁，而最终答案应该为 $f_{\frac{n+k}{2}}$。 接下来的问题就转移到求 $g_i$ 上了。观察到 $n$ 的范围较小，可以考虑二维dp。我们设 $dp_{i,j}$ 表示已经看到了 $A$ 的前 $i$ 位，已经钦定了 $j$ 个，且 $A$ 的 $[1,i]$ 位都已经与 $B$ 中不同的数配对。为了方便转移，我们先把 $A,B$ 排序，则状态转移方程易得: $dp_{i,j}=dp_{i-1,j}+dp_{i-1,j-1}\times(cnt-j+1)$，其中 $cnt$ 表示 $B$ 中比 $a_i$ 小的数有 $cnt$ 个，因为数组有序，所以可以通过一个指针维护当前比第一个大于等于 $a_i$ 的，指针一定单调增长且最多 增长 $n$ 次，这样可以做到均摊 $O(1)$ 求出 $cnt$。 这个转移方程方程的意思为如果此次不为 $a_i$ 钦定一个 $b_i$，则从 $dp_{i-1,j}$ 直接转移；如果钦定，则从 $dp_{i-1,j-1}$ 转移，方案数为总共可选的 $cnt$ 减去已经选过的 $j-1$ 个值。 求出 $dp$ 后，$g_i$ 就可求了，即 $g_i=dp_{n,i}\times (n-i)!$，因为钦定了 $i$ 个，剩余的 $(n-i)$ 个就可以随便选取了。接下来根据二项式反演的套路，把“至少”转化为“恰好”。$g_k=\sum_{i=k}^n \dbinom{i}{k}f_i \Leftrightarrow f_k=\sum_{i=k}^n\dbinom{i}{k}g_i(-1)^{i-k}$ 利用箭头右边的等式计算即可，组合数可以直接递推，复杂度 $\mathcal{O}(n^2)$，足以通过本题。 最后一道例题： > [P6478 [NOI Online #2 提高组] 游戏](https://www.luogu.com.cn/problem/P6478) > > 小 A 和小 B 在玩一个游戏：有一颗包含 $n=2m$ 个点的有根树，根为 $1$ ，初始时二人各有 $m$ 个点。每回合二人需要选出一个自己拥有且之前未被选过的点，若对手的点在自己点的子树内则自己获胜，若自己的点在对方的点的子树内则自己失败；其他情况视为平局。游戏共 $m$ 回合。 现在询问在二人随机选点的情况下，对于 $k=0,1,2,\cdot\cdot\cdot,m$ ，计算出非平局回合为 $k$ 的情况数。两种情况不同当且仅当存在一个小 A 拥有的点 $x$ 。小 B 在 $x$ 被小 A 选择的那个回合所选的点不同，情况数对 $998244353$ 取模（ $n\le 5000$ ）。 考虑转化，设 $g_i$ 表示钦定选了 $i$ 对有祖先关系的方案数， $f_i$ 表示恰好存在 $i$ 对有祖先关系的答案。可以发现 $g_i$ 为“至少”，$f_i$ 为恰好，可以通过二项式反演来建立桥梁，最终答案即为 $f_0,f_1,f_2,\cdot\cdot\cdot,f_m$。 问题落在了求 $g_i$ 上。观察到 $n$ 的范围不大，考虑二维树上dp。设 $dp_{i,j}$ 表示在以 $i$ 为根的子树中，钦定了 $j$ 对有祖先关系的点对的方案数。易得状态转移方程: - $dp_{i,j+k}=dp_{i,j}+\sum_{s\in son_i}dp_{s,k}$（不配对） - $dp_{i,j+k+1}=[a_i=0](dp_{i,j}+\sum_{s\in son_i}dp_{s,k}[a_s=1])$（$0$ 与 $1$ 配对） - $dp_{i,j+k+1}=[a_i=1](dp_{i,j}+\sum_{s\in son_i}dp_{s,k}[a_s=0])$ （$1$ 与 $0$ 配对） 可以通过恰当的安排循环条件将复杂度从 $\mathcal{O}(n^3)$ 降至 $\mathcal{O}(n^2)$。 #### 最后总结和闲话 那本文到此所有的知识点就都讲解完毕了~，写了 $2.5\rm w$ 字，总时长三天，还是很希望能让大家（当然还有我自己）学到新东西的。本文主要介绍了二项式恒等式及其简单练习，和与二项式相关的三个技巧。其中二项式反演的技巧跟书上差别蛮大，大家有兴趣可以去《具体数学》上看看他是怎么讲解的。 总之，二项式系数的东西不可能一篇文章全部写完，我已经尽量挑最基本的说了。而且这玩意没有题单之类的，有的就是平常在推式子时积累的经验，所以大家可以找来《具体数学》的练习题做，或者去做点难的计数题，慢慢就熟能生巧了，祝您早日成为数数大师！