数学知识：和式的处理及二项式系数的运用

数学

〇、 参考资料

这段时间看了一部分《具体数学》上的内容，正如第一章中所说，这本书的主要目的是：

说明不具备超人洞察力的人如何求解问题

也就是说，这本书主要讲述的是“那些本应该被讲授的硬数学技巧”。或者说是一种数学领域的通用技术，这也是“具体数学”名称的来源。

一、 和式

记号

---

与平时所用的$\sum_{k=1}^n$记号不同，这本书建议使用更加方便的形如$\sum_{1\le k\le n}$的记号，这可以使你在变量替换时不容易出错。

一个特殊的地方是逻辑判断深入和式：用方括号包含的逻辑命题，如果为真则为1，如果为假则为0。这对于(cpp)程序编写是非常友好的。

运算律

---

和式满足下面三种基本运算律：

1. 分配律(提公因式)：
   $$\sum_{k\in K} ca_k = c\sum_{k\in K}a_k$$
2. 结合律(和式的合并)：
   $$\sum_{k\in K}(a_k+b_k)=\sum_{k\in K}a_k + \sum_{k\in K} b_k$$

3. 交换律(变量替换)：
   

   $$\sum_{k\in K}a_k=\sum_{p(k)\in K}a_{p(k)}$$

   $p(k)$为一个置换

---

多重和式具有一些特殊的性质，例如：

1. 合并和分离：
   $$\sum_{1\le i\le n}\sum_{i\le j\le n} a_{i,j} = \sum_{1\le i\le j\le n} a_{i,j}$$
2. 交换求和顺序：
   $$\sum_{1\le i\le n}\sum_{i\le j\le n} a_{i,j} = \sum_{1\le j\le n}\sum_{1\le i\le j} a_{i,j}$$
3. 一般分配律：
   $$\sum_{j\in J, k\in K}a_jb_k=\left(\sum_{j\in J}a_j\right)\left(\sum_{k\in K}b_k\right)$$

这些性质虽然是显然的，但将在处理时带来巨大的方便。第二条有助于化简和式，第三条则可以在一些“求乘积的和”的计算时减小计算量。

一般技术

---

1. 猜测+归纳法

虽然名字不是很好听，但这在OI中是一种实用的策略。因为计算机暴力处理的速度是很快的，如果规律明显，往往可以一眼看出。而归纳证明就非常简单了。

2. 扰动法

扰动法的动机是在和式中加入一项，并用一个新和式表达之，从而解方程得出通解。用两个例子来解释这种方法：

(一): 几何级数

$$S_n = \sum_{0\le k\le n}a^k$$

的封闭形式。

用扰动法加入一项：

$$S_n + a^{n+1} = 1 + \sum_{0\le k\le n}a^{k+1} = 1+aS_n$$

解方程可以得出 $S_n = \frac {a^{n+1}-1}{a-1}$。对这个公式两边微分可以得到一个有用的公式：

$$\sum_{1\le k\le n}ka^{k-1} = \frac {1-(n+1)x^n+nx^{n+1}}{(1-x)^2}$$

当$|a|<1$时可以收敛成：

$$\sum_{1\le k\le n}ka^{k-1}=\frac 1{(1-a)^2}$$

(二): 平方和公式

考虑求

$$S_n = \sum_{1\le k\le n} k^2$$

的封闭形式。

如果仍然用刚才的思路，我们会发现$S_n$在两边抵消了。但如果我们用三次方和$V_n$进行扰动：

$$V_n + (n+1)^3 \\ = \sum_{0\le k\le n} (k+1)^3\\ = \sum_{0\le k\le n}k^3+3\sum_{0\le k\le n}k^2+3\sum_{0\le k\le n}k+\sum_{0\le k\le n}1\\ = V_n+3S_n+\frac {3n(n+1)}{2}+n+1$$

两边的$V_n$可以抵消，我们解出了$S_n$。即：

$$S_n = \frac {n(n+1)(2n+1)}{6}$$

3. 待定系数法

如果已知解的形式，我们可以用待定系数法得到原和式的封闭形式。例如：

$$\sum_{1\le k\le n}k^3$$

先验知识告诉我们答案是一个$4$次多项式。我们只要代入$n=0,1,2,3$建立关于一般四次多项式的$4$个方程即可求解。事实上，如果用拉格朗日插值法或高阶差分法，可以在$O(n^2)$的时间内完成，是非常高效的。

4. 有限微积分

下一部分详细介绍。

有限微积分

基本定义

---

有限微积分是离散数学对于微积分的回应，这种技术给出了求解和式的“不需要思考”的系统方法。考虑熟悉的微分算子的定义：

$$Df(n)=\lim_{h\rightarrow 0}\frac {f(n+h)-f(n)}{h}$$

而离散中的“极限”就是1，自然地定义差分算子：

$$\Delta f(n) = f(n+1)-f(n)$$

“算子(operator)”这个新概念是作用在函数上的运算，他给出了一个新函数。

简单的公式

---

微积分之所以方便是因为它有形如：

$$D(x^m) = mx^{m-1}$$

这样的优美公式，同样，有限微积分也有对应的优美的公式：

$$\Delta(x^{\underline{m}}) = mx^{\underline{m-1}}$$

其中：$x^{\underline{m}} = x(x-1)(x-2)\dots (x-m+1)$(m个)，被称为下降阶乘幂。由于可以证明任何的$x^k$都在$O(k^2)$内可以写成阶乘幂的和（具体方法为从高到低贪心的取），因此他的能力十分强大。

求和——离散的“积分”

---

微积分中可以用微分算子定义不定积分，也就是：

$$\int g(x)dx = f(x)+C\iff g(x)=Df(x)$$

我们用同样的方式定义不定和式：

$$\sum g(x)\delta x=f(x)+C\iff g(x) = \Delta f(x)$$

微积分基本定理指出：

$$\int_a^bg(x)dx = f(b)-f(a)$$

同样有有限微积分基本定理：

$$\Sigma_a^b g(x) \delta x = f(b)-f(a)$$

但这些记号的直观意义是什么呢？不难证明：

$$\Sigma_a^b g(x) \delta x = \sum_{a\le i<b}g(i), b\ge a$$

这是最有用的定理之一（如果之前学习过数列差分这几乎是显然的）。我们正要用他解决序列求和的问题。

负指数下降阶乘幂

---

通过类比可以定义负指数下降阶乘幂：

$$x^{-m} = \frac 1 {(x+1)(x+2)\dots (x+m)}, m>0$$

可以证明仍然满足差分公式。而且这使得下降幂拥有了良好的性质：

$$x^\underline{m+n}=x^\underline m(x-m)^\underline n$$

重新发现平方和公式

---

这次我们用新的武器来重新发现这个公式：

$$S_n = \Sigma_0^{n+1} x^2\delta x$$

用下降阶乘幂$x^2 = x^\underline 2+x^\underline 1$，用线性性质：

$$S_n = \Sigma_0^{n+1} x^\underline 2\delta x+\Sigma_0^{n+1}x^\underline 1 \delta x$$

两边的不定和式分别是：

$$\sum x^\underline 2\delta x = \frac 1 3x^\underline 3$$

$$\sum x^\underline 1\delta x = \frac 1 2x^\underline 2$$

那么原和式就变成：

$$S_n = \frac 1 3 (n+1)^\underline 3+\frac 1 2(n+1)^\underline 2$$

展开和上面的公式完全相同。（但在具体应用中我们不必展开，因为阶乘幂也可以用类似霍纳法则的方法将求值降到$O(n)$。）

乘法公式和分部求和公式

---

微积分中的链式法则在有限微积分中很难推广，唯一的一个是：

$$f^\underline m(n) = mf^\underline {m-1}(n)$$

$f(x)$是任一函数。但这显然不能满足我们的要求，一个更强大的是乘法公式，即：

$$\Delta(uv) = u\Delta v+Ev\Delta u$$

其中$Ef(x) = f(x+1)$，被称为移位算子。（有趣的是：$\Delta = E-1$）。

证明十分简单，只要从定义出发就可以。我们看一些应用：

练习： 利用乘法公式求$\Delta kH_k$，其中$H_k$是前$k$个调合数的和。

容易发现：

$$\Delta kH_k = k\Delta H_k+H_{k+1}\Delta k = \frac k {k+1}+H_{k+1}$$

和从定义出发得到了相同的结果。

---

这个公式真正有用的地方是推出了广为称道的“分部求和法”，求公式两边求不定和式并整理得到：

$$\sum u\Delta v=uv-\sum Ev\Delta u$$

这个公式大大拓展了求和的范围。对于两个式子的乘积，先求一个的不定和式，再用公式展开求另一个（特别是负指数阶乘幂时不定和式会降低幂次）。用一个例子来解释：

例题
求

$$f(n) = \sum_{0\le k < n} \frac {H_k} {(k+1)(k+2)}$$

的封闭形式。

利用裂项转化：

$$f(n) = \sum_{0\le k < n} H_k(\frac 1 {k+1}-\frac 1 {k+2})$$

注意到（$\Delta^2$表示二阶差分，正如$D^2$表示二阶导数）：

$$-\Delta^2(H_k) = \frac 1 {k+1}-\frac 1 {k+2}$$

则只要求不定和式

$$-\sum H_k \Delta^2(H_k)$$

利用分部求和公式：

$$-(H_k\Delta H_k-\sum \Delta(H_{k+1})\Delta(H_k))$$

化简后得到

$$-\left(\frac {H_k} {k+1}-\sum \frac 1 {(k+1)(k+2)}\right)$$

用阶乘幂表示并化简

$$-\frac {H_k+1} {k+1}$$

根据有限微积分基本定理：

$$f(n) = g(n)-g(0) = \frac {k-H_k} {k+1}$$

在后面对二项式恒等式的处理中，也可以看到有限微积分的强大威力。

二、 二项恒等式

基本定义

---

二项式系数是最常用的组合数，${n\choose k}$表示从n个物品中取出k个的方案数。他的代数定义则更加直接：

$${r\choose k} = \frac {r^\underline k} {k!}$$

特别指出，如果$k<0$，有${r\choose k} = 0$。

二项恒等式

---

下面是十个最重要的二项恒等式。

1. 展开式：
   $${n\choose k} = \frac {n!} {k!(n-k)!}$$
2. 对称恒等式：
   $${n\choose k} = {n\choose n-k}$$
3. 吸收/提取恒等式：
   $${r\choose k} = \frac r k{r-1 \choose k-1}, k\ne 0$$
4. 归纳恒等式：
   $${r\choose k} = {r-1\choose k}+{r-1\choose k-1}$$
5. 上指标反转：
   $${r\choose k} = (-1)^k{k-r-1\choose k}$$
6. 三项式版恒等式：
   $${r\choose m}{m\choose k} = {r\choose k}{r-k\choose m-k}$$
7. 二项式定理：
   $$(x+y)^n = \sum_{0\le k\le n}{n\choose k}x^ky^{n-k}$$
8. 平行求和法：
   $$\sum_{k\le n}{r+k\choose k} = {r+n+1\choose n}$$
9. 上指标求和：
   $$\sum_{k\le n}{k\choose m} = {n+1\choose m+1}, m,n\ge 0$$
10. 范德蒙德卷积公式
    $$\sum_k{r\choose k}{s\choose n-k} = {r+s\choose n}$$

有限微积分证明二项恒等式

如果我们发现了一个不是很好处理的二项式，却又恰巧忘记了对应的恒等式，那么处理就变的棘手了。幸而我们有有限微积分的强大武器。

例题

不用归纳法，证明上指标求和法：

$$\sum_{0\le k\le n}{k\choose m} = {n+1\choose m+1}(*)$$

解：设$f(x) = \sum {k\choose m}\delta k$，有

$$(*) = f(n+1)-f(0)$$

而根据有限微积分：

$$\sum {k\choose m} \delta k = \sum \frac {k^\underline m} {m!} \delta k\\=\frac 1 {m!}\frac 1 {m+1}k^{m+1}\\ = \frac 1 {(m+1)!}k^{m+1}\\ = {k\choose m+1}$$

则

$$(*) = f(n+1)-f(0) = {n+1\choose m+1}$$

一个陷阱： 和微积分一样，要注意常量和变量的区别，否则将得出错误的答案。

利用标准技术求解惊悚的和式

---

例题：

这是一个实际问题：求

$$S = \sum_{0\le k\le n}k{m-k-1\choose m-n-1}$$

的封闭形式。

解：考虑两个东西乘积的和，首先考虑用吸收恒等式将其合并，而方法就是凑出上指标。不难发现：

$$S = \sum_{0\le k\le n}(m-(m-k)){m-k-1\choose m-n-1}$$

展开并整理，得到：

$$S = \sum_{0\le k\le n}m{m-k-1\choose m-n-1}-\sum_{0\le k\le n}(m-k){m-k-1\choose m-n-1}$$

前后分别处理，第一个和式考虑用上指标求和，替换枚举变量$k\rightarrow m-k-1$以便在上面得到简单的形式：

$$u = m\sum_{0\le m-k-1\le n}{k\choose m-n-1}$$

化简得到：

$$u = m\sum_{m-n-1\le k\le m-1}{k\choose m-n-1}$$

这次可以动用上指标求和法：

$$u = m{m\choose m-n}$$

这时在考虑第二部分，用吸收恒等式化简之，得到：

$$v = (m-n)\sum_{0\le k\le n}{m-k\choose m-n}$$

仍然仿照上面的处理，得到：

$$v = (m-n){m+1\choose m-n+1} = \frac {(m-n)(m+1)}{m-n+1}{m\choose m-n}$$

则

$$S = u-v = \frac {m(m-n+1)-(m-n)(m+1)}{m-n+1}{m\choose m-n}\\ = \frac n {m-n+1}{m\choose n}$$

二项式反演

---

有时候一个问题是难于求解的，但其容斥的结果是便于求解的，也就是说，待求解的函数$g(n)$和一个简单的函数$f(n)$构成：

$$f(n) = \sum_{0\le k\le n}(-1)^k {n\choose k}g(k)$$

的关系，就可以用解方程的手段在$O(n^3)$求得$g(n)$。但反演定理允许我们在$O(n)$的时间内解决这一问题（不包含预处理组合数），即：

$$g(n) = \sum_{0\le k\le n}(-1)^k {n\choose k}f(k)$$

这个公式前后完全对称，既具有美感又便于记忆。下面我们考虑用已有的知识证明之。

证明反演定理

注意：在证明中我们更关心细节和过程，以便在遇到更复杂的问题时尽快找到突破口。

$$f(n) = \sum_{0\le k\le n}(-1)^k {n\choose k}g(k)\iff g(n) = \sum_{0\le k\le n}(-1)^k {n\choose k}f(k)$$

由于定理左右对称，只需要证明$\Rightarrow$即可。根据定义，右边=

$$\sum_{0\le i\le n}(-1)^i{n\choose i}\sum_{0\le j\le i}(-1)^j{i\choose j}g(j)$$

整理：

$$\sum_{0\le i\le n}\sum_{0\le i\le j}(-1)^{i+j}{n\choose i}{i\choose j}g(j)$$

我们不希望一个未知的$g(n)$深入在和式中，而希望将他提出内层和式，从而用已有知识处理后面的部分，运用三项式版恒等式，并交换求和次序，提公因式后得到：

$$\sum_{0\le j\le n}{n\choose j}g(j)\sum_{j\le i\le n}(-1)^{i+j}{n-j\choose i-j}(*)$$

这时后面的部分就独立出来了，我们只需要处理后半部分。我们希望二项式下边尽可能简单，以便使用平行求和法。替换循环变量$i\rightarrow i-j$，并化简后得到：

$$\sum_{0\le i\le n-j}(-1)^{i+2j}{n-j\choose i}$$

为了处理讨厌的$(-1)^{i+2j}$，应该提出一个$(-1)^i$来消去之，对内部翻转上指标：

$$\sum_{0\le i\le n-j}(-1)^{2i+2j}{i-(n-j)-1\choose i}$$

整理得到：

$$\sum_{0\le i\le n-j}{i+(-n+j-1)\choose i}$$

终于发现了熟悉的平行求和法的形式，这一项的结果可以立即书写出，就是：

$${j\choose n} = [j=n]$$

即当且仅当$j=n$时，该式为1，则原式：

$$(*) = \sum_{0\le j\le n}{n\choose j}g(j)[j=n] = g(j)$$

因此原命题成立。

错排公式——二项式反演的应用

---

考虑一个问题：n个人将帽子高高扔起，并捡起一个帽子，问每个人都不拿到自己帽子的情况有多少种。

这个问题等价于问不存在长度为1的循环的置换总数的计数。一种方便的解决方案是：设$f(n)$为$n$个帽子的情况总数，则有递推式：

$$f(n) = (n-1)(f(n-1)+f(n-2))$$

这个递推式很容易找到一个组合解释，但这不在本文讨论的范畴。现在我们要用二项式反演的技术来解决这个问题，设$f(n)$为$n$排列的总数，显然为$f(n) = n!$；设$g(n)$为$n$错排公式。记$K(i)$为“至少有i个错排的排列方案数”，则根据定义有

$$K(i)={n\choose i}g(i)\times (n-i)!$$

由于“至少有$n$个”被“至少有$n-1$个”真包含，因此要用容斥原理。“至少有0个”包含一切，之后符号交替出现，即：

$$f(n) = \sum_{0\le k\le n}(-1)^kK(k)$$

整理后也就是：

$$f(n) = \sum_{0\le k\le n}(-1)^k{n\choose k}g(k)(n-i)!$$

这可以用反演定理变化为：

$$g(n)(n-n)! = \sum_{0\le k\le n}(-1)^k{n\choose k}f(k)$$

也就是：

$$g(n) = \sum_{0\le k\le n} (-1)^k{n\choose k}k!$$

经过检验，这个方程和上面的递推式在初始的几项有相同的结果。我们大概可以相信获得了一个正确的答案。

高阶差分法

---

当我们已经知道一个数列符合一个多项式，或者组合数时，如何快速求出数列的通项公式？一个方法是所谓“拉格朗日插值法”，但我们也可以用有限微积分和组合数的武器解决。回忆分析中的泰勒级数：

$$g(a+x) = \sum_{k\ge 0}\frac {D^kg(a)} {k!}x^k$$

应该可以想到有限微积分也有类似的公式“牛顿级数”，形式和泰勒级数相同：

$$g(a+x) = \sum_{k\ge 0}\frac {\Delta^kg(a)}{k!}x^\underline k$$

为了便于计算取$a = 0$，根据组合数的定义也就是：

$$g(x) = \sum_{k\ge 0}\Delta^kg(0){x \choose k}$$

还记得物理必修一中的“逐差法”测加速度吗？其深层次的数学原理就在于此。用一个小情景来验证这个定理：

$$y = f(x) = x^3+2x^2+x+4$$

取值如下表所示：

x	0	1	2	3	4	5	6	...
y = f(x)	4	8	22	52	104	184	298	...

$$\Delta^0 f(0) = 4\\ \Delta^1 f(0) = 4 \\ \Delta^2 f(0) = 10\\ \Delta^3 f(0) = 6\\ \Delta^4 f(0) = 0$$

根据公式：

$$f(x) = 4{x\choose 0}+4{x\choose 1}+10{x\choose 2}+6{x\choose 3}\\ = x^3+2x^2+x+4$$

这个方法的一个好处是：一旦通过$O(n^2)$的时间知道了组合数前的系数，由于同一行的组合数可以根据下式线性递推求得，可以在$O(n)$时间内求出$f(x)$的值。

$${n\choose m} = {n\choose m-1}+{n-1\choose m-1} \\ = {n\choose m-1}+\frac m n{n\choose m}$$

即：

$${n\choose m} =\frac n {n+m}{n\choose m-1}$$

生成函数

---

在多项式系数中蕴含组合性质是有理由的，因为“多项式乘法”由于二项式定理被赋予了组合性质。更重要的是，两个n次多项式相乘只需要$O(n\lg n)$的时间复杂度。正式的，一个数列$\left<a_0, a_1, a_2, \dots\right>$的生成函数$A(x)$为：

$$A(x) = \sum_{k\ge 0} a_kx^k$$

生成函数的简单运用可以分为：

1. 利用运算证明恒等式
2. 利用封闭形式求解组合问题
3. 利用多项式乘法（卷积）处理组合问题

证明恒等式

考虑之前的范德蒙德卷积公式：

$$\sum_k{r\choose k}{s\choose n-k} = {r+s\choose n}$$

每当出现$k, n-k$或$k, k-n$出现时要考虑卷积。

考虑$(1+x)^r$和$(1+x)^s$所表达的生成函数：

$$\sum_{0\le k\le r}{r\choose k}x^k\\ \sum_{0\le k\le s}{s\choose k}x^k$$

两式分别相乘，取次数为$n$的系数，得到：

$$\sum_k{r\choose k}{s\choose n-k} = {r+s\choose n}$$

就是原来的公式。

利用封闭形式解决问题

---

如果一个生成函数可以被表示成封闭形式，那当然可以为我们解决许多问题。考虑数列$\left<1,1,1,1,\dots\right>$的生成函数，设其为$T$，满足：

$$T = 1+xT$$

解得：$T = \frac 1 {1-x}$

而数列$\left<1,2,3,4,5,\dots\right>$，可以通过这个公式两边求导并得到，就是：

$$\sum_{k\ge 0} kx^{k-1} = \frac 1 {(1-x)^2}$$

另一个常用的数列$\left<1,-1,1,-1,1,-1,\dots \right>$，他的生成函数是：

$$T = 1-xT$$

解得$T = \frac 1 {1+x}$。

考虑只包含$n$的倍数的数列的生成函数，即

$$\sum_{k\ge 0}[k=np,p\in n]x^k$$

容易发现

$$T = 1+x^nT$$

解得：$T = \frac 1 {1-x^n}$

如果一个数列为二项式系数的一行，即$\left< {n\choose 0}, {n\choose 1}, {n\choose 2}\dots\right>$，根据二项式定理，其生成函数为：$(1+x)^n$。

封闭形式的乘积恰好表示了所代表序列的卷积，这是个很好的性质，有时候将帮助我们寻找问题的答案。仍然用那个经典的例题做解释：

例题： 我们要从苹果、香蕉、橘子和梨中拿一些水果出来，要求苹果只能拿偶数个，香蕉的个数要是5的倍数，橘子最多拿4个，梨要么不拿，要么只能拿一个。问按这样的要求拿n个水果的方案数。

解：分别用生成函数表示所有情景：

$$1+x^2+x^4+\dots = \frac 1 {1-x^2}\\ 1+x^5+x^{10}+\dots = \frac 1 {1-x^5}\\ 1+x+x^2+x^3+x^4 = \frac {1-x^5} {1-x}\\ 1+x$$

将他们全部乘起来，得到：

$$\frac {1+x} {1-x-x^2+x^3}$$

由于我们坚信出题人是仁慈的，这个分式一定可以化简。用长除法可以得出：

$$\frac 1 {(1-x)^2} = 1+2x+3x^3+\dots$$

这样答案就有了，取$n$个的方案是$n+1$。

完了

参(zhao)考(ban)资(lai)料(yuan)

• 《具体数学》
• 《组合数学》