本节对应原书 PDF 第 208–216 页（印刷 p193–p201）。定义、定理、公式、例题及其原解答逐字取自原书；解释性文字为 AI 通俗化改写；标有「解读」的引用块为 AI 补充的额外直觉。

本节主要讨论组合数的性质、组合数序列的求和以及组合恒等式的证明等内容. 本节首先引入一个新的符号 \dbinom{n}{k}，当 n 与 k 都是自然数时，它就等于组合数 C(n,k). 在第 10 章将会看到，这个符号在 n 与 k 不是自然数时也有意义. 为了使得恒等式的结构看起来更为清晰，本节涉及的组合恒等式中大量使用了这个符号. 组合数 C(n,k) 与二项式展开式有着密切的联系，也称作二项式系数. 为了得到相关的组合恒等式，需要用到二项式定理.

解读：\dbinom{n}{k} 和 C(n,k) 在 n,k 为自然数时是同一个数，换符号只是为了让恒等式看起来更对称——把 C(n,k) 写成上下两层的形状，Pascal 公式 \dbinom{n}{k}=\dbinom{n-1}{k}+\dbinom{n-1}{k-1} 的「肩并肩相加」结构才一眼可见.

8.3.1 二项式定理

首先给出二项式定理.

定理 8.5（二项式定理） 设 n 是正整数，对一切 x 和 y，有

(x+y)^n=\sum_{k=0}^{n}\dbinom{n}{k}x^ky^{n-k}

证明一 对 n 进行归纳.

n=1，左边 =x+y，右边 =\dbinom{1}{0}x^0y^1+\dbinom{1}{1}x^1y^0=x+y，命题为真.

假设对于 n 命题为真，即 (x+y)^n=\sum\limits_{k=0}^{n}\dbinom{n}{k}x^ky^{n-k}，那么

\begin{aligned} (x+y)^{n+1}&=x\sum_{k=0}^{n}\dbinom{n}{k}x^ky^{n-k}+y\sum_{k=0}^{n}\dbinom{n}{k}x^ky^{n-k} \\ &=x^{n+1}+\sum_{k=0}^{n-1}\dbinom{n}{k}x^{k+1}y^{n-k}+\sum_{k=1}^{n}\dbinom{n}{k}x^ky^{n-k+1}+y^{n+1} \\ &=x^{n+1}+\sum_{k=1}^{n}\dbinom{n}{k-1}x^ky^{n+1-k}+\sum_{k=1}^{n}\dbinom{n}{k}x^ky^{n-k+1}+y^{n+1} \\ &=\dbinom{n+1}{0}x^0y^{n+1}+\sum_{k=1}^{n}\left(\dbinom{n}{k-1}+\dbinom{n}{k}\right)x^ky^{n+1-k}+\dbinom{n+1}{n+1}x^{n+1}y^0 \\ &=\sum_{k=0}^{n+1}\dbinom{n+1}{k}x^ky^{n+1-k} \end{aligned}

根据数学归纳法，命题得证.

注意，在以上证明最后一步的化简中使用了 Pascal 公式. 下面给出二项式定理的另一个更加简单的证明——组合证明.

证明二 组合证明.

当乘积被展开时其中的项都是下述形式：x^iy^{n-i}，i=0,1,2,\cdots,n. 而构成形如 x^iy^{n-i} 的项，必须从 n 个和 (x+y) 中选 i 个提供 x，其他的 n-i 个提供 y. 因此，x^iy^{n-i} 的系数是 \dbinom{n}{i}，定理得证.

解读：证明一是「算出来」，证明二是「数出来」. 组合证明的要点是：展开 (x+y)^n 时每个括号里只能挑一个字母，挑 i 个 x 的挑法数就是 \dbinom{n}{i}，所以系数自然就是它——不需要任何代数变形.

在二项式定理中令 y=1 可以得到以下推论.

推论 设 n 是正整数，则

(1+x)^n=\sum_{k=0}^{n}\dbinom{n}{k}x^k

利用二项式定理可以计算二项展开式中某些项的系数.

例 8.15 求在 (2x-3y)^{25} 的展开式中 x^{12}y^{13} 的系数.

解 由二项式定理

(2x+(-3y))^{25}=\sum_{i=0}^{25}\dbinom{25}{i}(2x)^{25-i}(-3y)^i

令 i=13 得到展开式中 x^{12}y^{13} 的系数，即

\dbinom{25}{13}2^{12}(-3)^{13}=-\dfrac{25!}{13!12!}2^{12}3^{13}

8.3.2 组合恒等式

下面给出有关二项式系数的恒等式，这些恒等式也称为组合恒等式.

第一组：递推式.

(1) \dbinom{n}{k}=\dbinom{n}{n-k}　　n,k\in\mathbf{N}，n\geqslant k

(2) \dbinom{n}{k}=\dfrac{n}{k}\dbinom{n-1}{k-1}　　n,k\in\mathbf{Z}^+，n\geqslant k

(3) \dbinom{n}{k}=\dbinom{n-1}{k}+\dbinom{n-1}{k-1}　　n,k\in\mathbf{Z}^+，n>k

以上公式的证明已经在 8.2 节给出过. 递推式在计算组合数的序列和或恒等式证明中经常用到，主要用于组合数的化简或者变形.

第二组：变下项的求和式.

(4) \sum\limits_{k=0}^{n}\dbinom{n}{k}=2^n　　n\in\mathbf{N}

(5) \sum\limits_{k=0}^{n}(-1)^k\dbinom{n}{k}=0　　n\in\mathbf{N}

上述公式的组合数 \dbinom{n}{k} 中的 n 不变，k 随项的标号而改变，简称为变下项的求和公式. 这些公式的证明主要使用二项式定理或者组合分析方法.

证明公式(4).

方法一：在二项式定理中令 x=y=1 即可.

方法二：组合分析法. 设 S=\{1,2,\cdots,n\}，下面计数 S 的所有子集. 一种方法就是分类处理，将所有的子集按照含有元素的多少进行分类. n 元集合的 k 子集个数是 \dbinom{n}{k}，根据加法法则，子集总数是 \sum\limits_{k=0}^{n}\dbinom{n}{k}. 另一种方法是分步处理，为构成 S 的子集 A，依次考虑元素 1，2，\cdots，n 是否加入 A. 每个元素有两种选择，根据乘法法则，子集总数是 2^n.

公式(5)的证明和公式(4)类似，也可以使用二项式定理和组合分析两种方法. 这里将证明留给读者思考.

以上的求和是简单和与交错和，其中恒等式的每项系数为 1 或者 -1. 在更为复杂的恒等式中组合数的下项以及系数都随项的序号而改变，这种和是变系数的和，下面的公式(6)和公式(7)就属于这种类型.

(6) \sum\limits_{k=0}^{n}k\dbinom{n}{k}=n2^{n-1}　　n\in\mathbf{Z}^+

(7) \sum\limits_{k=0}^{n}k^2\dbinom{n}{k}=n(n+1)2^{n-2}　　n\in\mathbf{Z}^+

公式(6)和公式(7)的证明方法有两种：可以使用二项式定理和有关级数求导的技术，也可以利用公式(2)消去变系数，再使用公式(4)或者公式(5)进行化简. 这里先使用前一种方法证明公式(6)，然后使用后一种方法证明公式(7).

证明公式(6). 由二项式定理有

(1+x)^n=\sum_{k=0}^{n}\dbinom{n}{k}x^k

两边求导数得

n(1+x)^{n-1}=\sum_{k=1}^{n}\dbinom{n}{k}kx^{k-1}

在上面的公式中令 x=1，且有 0\dbinom{n}{0}=0，于是得到公式(6).

证明公式(7).

\begin{aligned} \sum_{k=0}^{n}k^2\dbinom{n}{k}&=\sum_{k=1}^{n}k^2\dfrac{n}{k}\dbinom{n-1}{k-1} & &\text{消去变系数} \\ &=\sum_{k=1}^{n}kn\dbinom{n-1}{k-1} \\ &=n\sum_{k=1}^{n}[(k-1)+1]\dbinom{n-1}{k-1} & &\text{常量外提} \\ &=n\sum_{k=1}^{n}(k-1)\dbinom{n-1}{k-1}+n\sum_{k=1}^{n}\dbinom{n-1}{k-1} & &\text{拆项} \\ &=n\sum_{k=0}^{n-1}k\dbinom{n-1}{k}+n2^{n-1} & &\text{改变求和的下限} \\ &=n(n-1)2^{n-2}+n2^{n-1} \\ &=n(n+1)2^{n-2} & &\text{利用公式(6)} \end{aligned}

公式(4)\sim公式(7)主要用于有关组合数的求和与恒等式证明.

解读：公式(6)的技巧是「对 x 求导」，它把 \dbinom{n}{k} 前面的系数 k 从指数位置「拉」了下来；公式(7)的技巧是「用公式(2)把 k^2 拆成 k\cdot n/k」，从而把 k 消掉、把 n 提出来. 两条路都通，考试时优先选计算量小的那条.

第三组：变上项的求和式.

公式(8)中的组合数 \dbinom{l}{k} 中的下项 k 不变，而上项 l 随项的序号改变，是变上项的求和式.

(8) \sum\limits_{l=0}^{n}\dbinom{l}{k}=\dbinom{n+1}{k+1}　　n,k\in\mathbf{N}

证明公式(8). 使用组合分析的方法. 令 S=\{a_1,a_2,\cdots,a_{n+1}\} 为 n+1 元集合. 等式右边是 S 的 k+1 元子集数. 考虑另一种分类计数的方法. 将所有的 k+1 元子集分成如下 n+1 类：

第 1 类　含 a_1，剩下的 k 个元素取自 \{a_2,\cdots,a_{n+1}\}，有 \dbinom{n}{k} 种取法；

第 2 类　不含 a_1，含 a_2，剩下的 k 个元素取自 \{a_3,\cdots,a_{n+1}\}，有 \dbinom{n-1}{k} 种方法；

\vdots

第 n+1 类　不含 a_1,a_2,\cdots,a_n，含 a_{n+1}，剩下的 k 个元素取自空集，有 \dbinom{0}{k} 种方法.

根据加法法则，等式左边也是 S 的 k+1 子集个数.

实际上在上述公式中，等式左边的项当 l<k 时都等于 0.

公式(8)主要用于有关组合数序列的求和或者证明组合恒等式.

第四组：乘积项的转换公式.

(9) \dbinom{n}{r}\dbinom{r}{k}=\dbinom{n}{k}\dbinom{n-k}{r-k}　　n\geqslant r\geqslant k，n,r,k\in\mathbf{N}

可以使用已知的组合恒等式来证明上述公式，也可以使用组合分析的方法. 这里采用组合分析的方法.

证明公式(9). 公式左边计数了先从 n 元集 S 中选取 r 个元素，然后在这 r 个元素中再选 k 个元素的方法. 公式右边的 \dbinom{n}{k} 是从 S 中直接选取 k 子集的方法数. 显然前一种方法选择的同一个 k-子集会重复出现. 例如，从集合 \{a,b,c,d,e\} 中先选 4-子集，然后从这些 4-子集再选 3-子集. 那么 3-子集 \{b,c,d\} 可能被选出 2 次，一次是从 4-子集 \{a,b,c,d\} 中选出的，另一次是从 4-子集 \{b,c,d,e\} 中选出的. 下面计算采用第一种方法时同一个 k-子集重复出现的次数. 换句话说，就是计算有多少个 r-子集能够选出相同的 k-子集. 设 k-子集为 A，一个 r 子集中除了 A 的元素外，剩下的 r-k 个元素取自 S-A. 因此有 \dbinom{n-k}{r-k} 个 r-子集能生成相同的 k 子集. 这就证明了等式左边的值恰好是 \dbinom{n}{k} 的 \dbinom{n-k}{r-k} 倍.

这个公式能够改变组合数的上、下项，在组合数求和时经常会用到.

第五组：积之和.

公式(10)和公式(11)是组合数的积之和的形式.

(10) \sum\limits_{k=0}^{r}\dbinom{m}{k}\dbinom{n}{r-k}=\dbinom{m+n}{r}　　m,n,r\in\mathbf{N}，r\leqslant\min(m,n)

(11) \sum\limits_{k=0}^{n}\dbinom{m}{k}\dbinom{n}{k}=\dbinom{m+n}{m}　　m,n\in\mathbf{N}

注意到公式(11)是公式(10)的特例. 在公式(10)中令 r=n 就可以得到

\sum_{k=0}^{n}\dbinom{m}{k}\dbinom{n}{n-k}=\dbinom{m+n}{n}

其中，\dbinom{n}{n-k}=\dbinom{n}{k}，\dbinom{m+n}{n}=\dbinom{m+n}{m}.

对于公式(10)，可以使用二项式定理或组合分析的方法完成证明. 这里使用组合分析的方法. 考虑集合 A=\{a_1,a_2,\cdots,a_m\}，B=\{b_1,b_2,\cdots,b_n\}. 等式右边计数了从这两个集合中选出 r 个元素的方法. 将这些选法按照含有 A 中元素的个数 k 进行分类，k=0,1,\cdots,r. 考虑含有 A 中 k 个元素的选法数. 先确定 A 中的 k 个元素，有 \dbinom{m}{k} 种方式，接着确定 B 中的 r-k 个元素，有 \dbinom{n}{r-k} 种方法. 由乘法法则，恰含 k 个 A 中元素的方法有 \dbinom{m}{k}\dbinom{n}{r-k} 种，根据加法法则对 k 求和公式得证.

到此为止，已经给出了 11 个主要的组合恒等式. 总结有关组合恒等式的证明方法，大致有以下几种：

(1) 已知恒等式代入并化简；

(2) 使用二项式定理比较相同项的系数；

(3) 利用二项式定理以及幂级数的求导或者积分；

(4) 数学归纳法；

(5) 组合分析方法.

此外，涉及组合数的序列求和的方法主要有：

(1) 利用 Pascal 公式不断归并相关的项；

(2) 级数求和；

(3) 观察和的计算结果，然后使用归纳法证明；

(4) 利用已知的恒等式.

上述方法在计数问题中可能会用到，应该熟练掌握它们.

例 8.16 求和.

(1) \sum\limits_{l=0}^{k}\dbinom{n+l}{l}

(2) \sum\limits_{k=1}^{n}(-1)^{k+1}\dfrac{1}{k+1}\dbinom{n}{k}

解 (1) 将第一项 \dbinom{n}{0} 改写为 \dbinom{n+1}{0}，然后不断使用 Pascal 公式将最前面的两项合并.

\begin{aligned} \sum_{l=0}^{k}\dbinom{n+l}{l} &= \dbinom{n}{0} + \dbinom{n+1}{1} + \dbinom{n+2}{2} + \cdots + \dbinom{n+k}{k} \\ &= \left( \dbinom{n+1}{0} + \dbinom{n+1}{1} \right) + \dbinom{n+2}{2} + \cdots + \dbinom{n+k}{k} \\ &= \left( \dbinom{n+2}{1} + \dbinom{n+2}{2} \right) + \dbinom{n+3}{3} + \cdots + \dbinom{n+k}{k} \\ &= \cdots = \dbinom{n+k}{k-1} + \dbinom{n+k}{k} = \dbinom{n+k+1}{k} \end{aligned}

(2) 利用公式(2)消去变系数，然后利用公式(5)求和.

\begin{aligned} \sum_{k=1}^{n}(-1)^{k+1}\dfrac{1}{k+1}\dbinom{n}{k} &= \sum_{k=1}^{n}(-1)^{k+1}\dfrac{1}{k+1}\dfrac{n+1}{n+1}\dbinom{n}{k} \\ &= \sum_{k=1}^{n}(-1)^{k+1}\dfrac{1}{n+1}\dbinom{n+1}{k+1} \\ &= \dfrac{1}{n+1}\sum_{k=1}^{n}(-1)^{k+1}\dbinom{n+1}{k+1} \\ &= \dfrac{1}{n+1}\sum_{k=2}^{n+1}(-1)^{k}\dbinom{n+1}{k} \\ &= \dfrac{1}{n+1}\left[ \sum_{k=0}^{n+1}(-1)^{k}\dbinom{n+1}{k} - 1 + \dbinom{n+1}{1} \right] \\ &= \dfrac{1}{n+1}(-1 + n + 1) \\ &= \dfrac{n}{n+1} \end{aligned}

8.3.3 非降路径问题

非降路径问题有着广泛的应用，可以作为一种组合计数模型. 下面讨论这个计数问题的相关结果.

非降路径问题（组合计数模型 2） 考察图 8.3. 设 m, n 是正整数，从 (0, 0) 点到 (m, n) 点的非降路径是一条折线，这条折线由 m + n 次移动构成，每次允许向上或者向右移动一步. 问不同的非降路径有多少条？

不同的路径取决于 m + n 步的选择，其中包含 m 步向右，n 步向上. 这种路径条数等于从 m + n 个位置中选 m 个位置的方法数，即 \dbinom{m+n}{m} 或 \dbinom{m+n}{n}.

下面考虑这个问题的其他情况.

给定非负整数 a, b, m, n，其中 a \leqslant m，b \leqslant n. 从 (a, b) 点到 (m, n) 点的非降路径数等于从 (0, 0) 点到 (m-a, n-b) 点的非降路径数，这相当于坐标进行了平移. 根据上面的公式，这种路径条数等于 \dbinom{m-a+n-b}{m-a}.

设 a, b, c, d, m, n 是非负整数，其中 a \leqslant c \leqslant m，b \leqslant d \leqslant n. 从 (a, b) 点经过 (c, d) 点到 (m, n) 点的非降路径数等于从 (a, b) 点到 (c, d) 点的非降路径数与从 (c, d) 点到 (m, n) 点的非降路径数之积.

下面是带限制条件的非降路径问题，这种计数可以采用组合对应的方法解决.

考虑从 (0, 0) 点到 (n, n) 点除端点外中间不接触对角线 y = x 的非降路径数 N. 这种路径被对角线划分成条数相等的两半. 考虑对角线下方的路径. 如图 8.4 所示，这种路径经过 (1, 0) 点，再经过 (n, n-1) 点，最后到达 (n, n) 点. 路径数等于从 (1, 0) 点到 (n, n-1) 点非降路径总数减去其中那些从 (1, 0) 点到 (n, n-1) 点、中间接触过对角线的非降路径数 N_1.

原书图8.3 从 (0,0) 到 (m,n) 的非降路径

原书图8.4 从 (1,0) 到 (n,n-1) 的非降路径

根据上面的公式，非降路径总数等于 \dbinom{2n-2}{n-1}，下面计算 N_1. 一条接触过对角线的非降路径在对角线上可能接触不止一次，那么存在一个最后的接触点 A. A 把这条路径分成前后两个部分：从 (1, 0) 点到 A 的路径与从 A 到 (n, n-1) 点的路径. 将路径的前半部分按照对角线 y = x 反射成一条从 (0, 1) 点到 A 点的非降路径（如图中虚线所示）. 这就在对角线下方从 (1, 0) 点到 (n, n-1) 点且中间接触过对角线的路径与从 (0, 1) 点到 (n, n-1) 点的路径之间构造了一一对应. 因此 N_1 = \dbinom{2n-2}{n}. 从而得到

N = 2\left[ \dbinom{2n-2}{n-1} - \dbinom{2n-2}{n} \right] = \dfrac{2}{n}\dbinom{2n-2}{n-1}

可以使用非降路径数的计数模型证明组合恒等式，下面采用这种方法证明公式(10).

例 8.17 设 m, r, n 为正整数，其中 r \leqslant m, n，证明组合恒等式

\sum_{k=0}^{r}\dbinom{m}{k}\dbinom{n}{r-k} = \dbinom{m+n}{r}

证明 证明的关键是选择合适的非降路径模型. 等式右边计数了从 (0, 0) 点到 (m+n-r, r) 点的非降路径. 等式左边的和是分类计数非降路径，不同的类由参数 k 决定，其中 k = 0, 1, \cdots, r，表示这类非降路径经过某条直线上的点不同. 对于给定的 k，乘积则表示这条非降路径由两段构成. 正如图 8.5 所示，前一段是 (0, 0) 点到 (m-k, k) 点的路径，有 \dbinom{m}{k} 条. 后一段是从 (m-k, k) 点到 (m+n-r, r) 点的非降路径. 这些路径与从 (0, 0) 点到 (n-r+k, r-k) 点的非降路径一样多，有 \dbinom{n}{r-k} 条. 根据乘法法则和加法法则，左边的等式也恰好计数了从 (0, 0) 点到 (m+n-r, r) 点的非降路径.

利用非降路径模型也可以解决实际的组合计数问题. 请看下面的例子.

例 8.18 求集合 \{1, 2, \cdots, n\} 上的单调递增函数个数.

解 考虑集合 \{1, 2, \cdots, n\} 上的单调递增函数 f: \{1, 2, \cdots, n\} \rightarrow \{1, 2, \cdots, n\}. 如图 8.6 所示，可以将自变量看作横坐标，对应的函数值看作纵坐标，得到 n 个点. 在图上增加 (1, 1) 和 (n+1, n) 两个点，并按照下面的方法连接这 n+2 个点：如果 f(1) 不等于 1，那么从 (1, 1) 开始向上连接到 (1, f(1)) 点. 从 (1, f(1)) 点先向右再向上连接到 (2, f(2)) 点，依照「先向右，后向上」的规则顺次连接 (3, f(3))，\cdots，直到 (n+1, n) 点. 而这条连线恰好构成从 (1, 1) 点到 (n+1, n) 点的一条非降路径. 显然这种非降路径与单调函数是一一对应的，只需计数非降路径条数就得到所求的单调函数个数. 根据公式，非降路径数是 \dbinom{2n-1}{n}. 因此集合 \{1, 2, \cdots, n\} 上的单调递增函数个数也是 \dbinom{2n-1}{n}.

原书图8.5 例 8.17 的非降路径分解

原书图8.6 例 8.18 的单调递增函数与非降路径

可以将上述结论推广. 设 A = \{1, 2, \cdots, m\}，B = \{1, 2, \cdots, n\}，那么从 A 到 B 的单调函数个数等于从 (1, 1) 到 (m+1, n) 的非降路径数的两倍，即 2\dbinom{m+n-1}{m}.

例 8.19 在计算机算法的设计中，栈是一种很重要的数据结构. 下面考虑一个涉及栈输出的计数问题. 设有正整数 1, 2, \cdots, n，从小到大排成一个队列. 将这些整数按照排列的次序依次压入一个栈（即后进先出栈）. 当后面的整数进栈的时候，已经在栈中的整数可以在任何时刻输出. 问可能有多少种不同的输出序列？例如整数 1, 2, 3 可能的输出序列有 1, 2, 3；对应的操作是：1 进栈，1 出栈，2 进栈，2 出栈，3 进栈，3 出栈. 也可能输出 1, 3, 2；对应的操作是：1 进栈，1 出栈，2 进栈，3 进栈，3 出栈，2 出栈.

解 将进栈、出栈分别记作 x，y，一个输出对应了 n 个 x，n 个 y 的排列，且排列的任何前缀中的 x 的个数不少于 y 的个数. 考虑非降路径的模型，从 (0, 0) 点出发，将排列中的 x 看作向右走一步，y 看作向上走一步，就可以得到一条从 (0, 0) 点到 (n, n) 点的不穿过对角线的非降路径.

原书图8.7 栈输出问题对应的非降路径

如图 8.7 所示，任何一条从 (0, 0) 点到 (n, n) 点的穿过对角线的非降路径对应于一条从 (-1, 1) 点到 (n, n) 点的非降路径. 从 (0, 0) 点到 (n, n) 点的非降路径总数为 \dbinom{2n}{n} 条，从 (-1, 1) 点到 (n, n) 点的非降路径数为 \dbinom{2n}{n-1} 条，因此不同的输出序列个数是

\begin{aligned} N &= \dbinom{2n}{n} - \dbinom{2n}{n-1} = \dfrac{(2n)!}{n!n!} - \dfrac{(2n)!}{(n-1)!(n+1)!} \\ &= \dfrac{1}{n+1}\dbinom{2n}{n} \end{aligned}

这个问题也可以使用生成函数的方法求解，有关的说明将在 10.2 节给出.

解读：\dfrac{1}{n+1}\dbinom{2n}{n} 就是著名的 Catalan 数. 栈输出的计数、不穿对角线的路径数、n 对括号的合法匹配数，都是同一个数——它们之间靠「一一对应」这条线索连起来. 非降路径模型的价值就在于：把抽象的计数问题画成格子里的走法，再用「反射法」把不好数的部分变成好数的部分.