6.4 二项式系数与恒等式

相关笔记： 6.3 排列与组合 | 6.5 广义排列与组合

概览

本节系统介绍了二项式系数 $(k n)$ 的定义、性质与恒等式。二项式系数是组合数学中最基本也最重要的计数对象之一，它同时具有组合意义（从 $n$ 个元素中选 $k$ 个的方案数）和代数意义（二项式展开中 $x^{n - k} y^{k}$ 的系数）。

帕斯卡三角形（Pascal’s Triangle）以三角形阵列直观展示二项式系数的递推关系 $(k n) = (k - 1 n - 1) + (k n - 1)$

二项式定理 $(x + y)^{n} = \sum_{k = 0}^{n} (k n) x^{n - k} y^{k}$ 是二项式系数的核心代数表达

重要恒等式包括：范德蒙德恒等式、上指标求和 $\sum_{k = 0}^{n} (r k) = (r + 1 n + 1)$ 、二项式系数的单峰性等

组合证明（combinatorial proof）是证明恒等式的重要方法，通过双重计数建立等式

一、知识结构总览

graph TB
    A["6.4 二项式系数与恒等式<br/>Binomial Coefficients and Identities"] --> B["二项式系数的定义"]
    A --> C["帕斯卡三角形"]
    A --> D["二项式定理"]
    A --> E["重要组合恒等式"]
    A --> F["组合证明方法"]

    B --> B1["组合定义 C(n,k)"]
    B --> B2["代数定义 n!/k!(n-k)!"]
    B --> B3["对称性 C(n,k)=C(n,n-k)"]

    C --> C1["递推构造"]
    C --> C2["行求和 = 2^n"]
    C --> C3["对角线性质"]

    D --> D1["展开公式"]
    D --> D2["特殊值代入"]
    D --> D3["推广：多项式定理"]

    E --> E1["范德蒙德恒等式"]
    E --> E2["上指标求和"]
    E --> E3["帕斯卡恒等式"]
    E --> E4["单峰性与最大值"]

    F --> F1["双重计数法"]
    F --> F2["组合论证 vs 代数推导"]

二、核心思想

核心思想

本节的核心思想是二项式系数的双重身份：它既是组合计数的结果（从 $n$ 个元素中选取 $k$ 个的方案数），又是代数运算的产物（二项式展开的系数）。这种双重身份使得我们可以用两种截然不同的方法来理解和证明关于二项式系数的恒等式——组合证明（counting arguments）和代数证明（algebraic manipulation）。帕斯卡三角形将这种双重身份以直观的几何形式呈现，其递推关系 $(k n) = (k - 1 n - 1) + (k n - 1)$ 正是组合加法原理的直接体现。

1. 二项式系数的定义

二项式系数（Binomial Coefficient）

设 $n$ 和 $k$ 为非负整数， $0 \leq k \leq n$ 。二项式系数 $(k n)$ （读作” $n$ 选 $k$ “）定义为：

$(k n) = \frac{n !}{k ! ( n - k )!}$

组合意义： $(k n)$ 等于从 $n$ 个不同元素的集合中选取 $k$ 个元素的方案数

也常记作 $C (n, k)$ 或 $_{n} C_{k}$

边界值： $(0 n) = (n n) = 1$ ， $(1 n) = (n - 1 n) = n$

对称性（Symmetry Identity）

对所有 $0 \leq k \leq n$ ：

$(k n) = (n - k n)$

证明：由定义出发： $(k n) = \frac{n !}{k ! ( n - k )!} = \frac{n !}{( n - k )! ( n - ( n - k ))!} = (n - k n)$

组合解释：从 $n$ 个元素中选 $k$ 个，等价于从 $n$ 个元素中选 $n - k$ 个不选的元素。

2. 帕斯卡三角形（Pascal’s Triangle）

帕斯卡三角形

帕斯卡三角形是一个三角形数字阵列，其中第 $n$ 行（从第 $0$ 行开始计数）包含二项式系数 $(0 n), (1 n), \dots, (n n)$ 。其递推构造规则为：

$(k n) = (k - 1 n - 1) + (k n - 1)$

其中约定 $(k n) = 0$ （当 $k < 0$ 或 $k > n$ 时）。

帕斯卡三角形的前 6 行

n=0:           1
n=1:          1 1
n=2:         1 2 1
n=3:        1 3 3 1
n=4:       1 4 6 4 1
n=5:      1 5 10 10 5 1

帕斯卡恒等式（Pascal's Identity）

对所有正整数 $n$ 和 $0 < k < n$ ：

$(k n) = (k - 1 n - 1) + (k n - 1)$

组合证明：考虑从 $n$ 个元素的集合 $S$ 中选 $k$ 个元素的方案数。固定一个特定元素 $a \in S$ ：

包含 $a$ 的方案：先选 $a$ ，再从剩余 $n - 1$ 个中选 $k - 1$ 个，共 $(k - 1 n - 1)$ 种

不包含 $a$ 的方案：直接从剩余 $n - 1$ 个中选 $k$ 个，共 $(k n - 1)$ 种

由加法原理，总方案数为 $(k - 1 n - 1) + (k n - 1)$

3. 二项式定理（Binomial Theorem）

二项式定理

设 $n$ 为非负整数，则：

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

展开式共有 $n + 1$ 项，其中第 $k$ 项（从 $k = 0$ 开始）为 $(k n) x^{n - k} y^{k}$ 。

展开 $(x + y)^{4}$

$(x + y)^{4} = (0 4) x^{4} + (1 4) x^{3} y + (2 4) x^{2} y^{2} + (3 4) x y^{3} + (4 4) y^{4}$ $= x^{4} + 4 x^{3} y + 6 x^{2} y^{2} + 4 x y^{3} + y^{4}$

二项式定理的推论

在二项式定理中令 $x = y = 1$ ，得： $2^{n} = \sum_{k = 0}^{n} (k n)$

令 $x = 1$ ， $y = - 1$ ，得： $0 = \sum_{k = 0}^{n} (- 1)^{k} (k n)$

即：所有偶数位置的二项式系数之和等于所有奇数位置的二项式系数之和，都等于 $2^{n - 1}$ 。

4. 重要组合恒等式

范德蒙德恒等式（Vandermonde's Identity）

设 $m, n, r$ 为非负整数，则：

$(r m + n) = \sum_{k = 0}^{r} (k m) (r - k n)$

组合证明：从 $m + n$ 个元素（分为两组，分别有 $m$ 个和 $n$ 个）中选 $r$ 个。按从第一组中选出的个数 $k$ 分类：从第一组选 $k$ 个（ $(k m)$ 种），从第二组选 $r - k$ 个（ $(r - k n)$ 种），对所有可能的 $k$ 求和。

上指标求和（Hockey-Stick Identity）

设 $n, r$ 为正整数， $n \geq r$ ，则：

$\sum_{k = r}^{n} (r k) = (r + 1 n + 1)$

也称为”曲棍球棒恒等式”，因为在帕斯卡三角形中，沿对角线求和的结果恰好位于对角线末端下方。

组合证明：考虑从 ${1, 2, \dots, n + 1}$ 中选 $r + 1$ 个元素，按最大元素 $k + 1$ 分类。最大元素为 $k + 1$ （其中 $r \leq k \leq n$ ）时，需从 ${1, \dots, k}$ 中选 $r$ 个，共 $(r k)$ 种。对所有 $k$ 求和即得。

二项式系数的单峰性

对于固定的 $n$ ，二项式系数 $(0 n), (1 n), \dots, (n n)$ 呈单峰分布：

当 $n$ 为偶数时，最大值为 $(n /2 n)$

当 $n$ 为奇数时，最大值为 $(( n - 1 ) /2 n) = (( n + 1 ) /2 n)$

从左到右先严格递增，到达最大值后再严格递减

5. 组合证明方法

组合证明（Combinatorial Proof）

组合证明是一种通过计数论证来证明恒等式的方法。其核心思想是：

找到一个合适的计数问题

用两种不同的方法计算同一个量

由于两种方法计算的是同一个量，因此结果相等

组合证明分为两类：

双重计数证明（double counting）：用两种方法计数同一个集合

双射证明（bijective proof）：在两个集合之间建立一一对应

三、补充理解与易混淆点

补充理解

补充1：帕斯卡三角形的历史与性质

帕斯卡三角形虽然以法国数学家 Blaise Pascal（1653）命名，但其发现远早于此。中国数学家杨辉在 1261 年的《详解九章算法》中就给出了类似的三角形（称为”杨辉三角”），更早可追溯到 11 世纪贾宪的”开方作法本源”。波斯数学家 Al-Karaji（约 953-1029）和印度数学家也独立发现了这一结构。

帕斯卡三角形中蕴含着丰富的数学性质：

第 $n$ 行所有数之和为 $2^{n}$

第 $n$ 行交替加减求和为 $0$ （ $n \geq 1$ ）

沿对角线方向可以读出三角形数、四面体数等

模 2 意义下的帕斯卡三角形呈现分形结构（Sierpinski 三角形）

Pascal’s Triangle - MathWorld — 帕斯卡三角形的全面介绍

Interactive Pascal’s Triangle — 帕斯卡三角形交互式探索

来源：Edwards, A. W. F. (2002). Pascal’s Arithmetical Triangle: The Story of a Mathematical Idea. Johns Hopkins University Press. 来源：Rosen, K. H. (2019). Discrete Mathematics and Its Applications (8th ed.), McGraw-Hill, Section 6.4.

补充2：二项式系数的广泛应用

二项式系数在计算机科学和数学中有广泛应用：

概率论：二项分布 $P (X = k) = (k n) p^{k} (1 - p)^{n - k}$ 直接使用了二项式系数

算法分析：快速排序的平均比较次数 $\frac{2 n !}{( n + 1 )!} \cdot 2^{n}$ 与二项式系数密切相关

多项式插值：伯恩斯坦多项式 $B_{k, n} (x) = (k n) x^{k} (1 - x)^{n - k}$ 是 Bezier 曲线的基础

编码理论：二项式系数出现在多种纠错码的参数计算中

Binomial Coefficient - Wikipedia — 二项式系数的百科全书式介绍

Combinatorial Identity Proofs — 组合恒等式证明集合

来源：Graham, R. L., Knuth, D. E. & Patashnik, O. (1994). Concrete Mathematics (2nd ed.), Addison-Wesley, Chapter 5. 来源：Rosen, K. H. (2019). Discrete Mathematics and Its Applications (8th ed.), McGraw-Hill, Section 6.4.

易混淆点

误区：排列与组合的混淆

❌ 将 $(k n)$ 与 $P (n, k)$ 混淆，忘记除以 $k!$

✅ $(k n) = \frac{P ( n , k )}{k !} = \frac{n !}{k ! ( n - k )!}$ ，组合不关心顺序，排列关心顺序

❌ 认为 $(k n) = (k n)$ 的对称性对所有 $k$ 都成立（实际上只对 $0 \leq k \leq n$ 有定义）

✅ 当 $k > n$ 或 $k < 0$ 时， $(k n) = 0$ （在组合意义下）

误区：组合证明与代数证明的等价性

❌ 认为组合证明”不够严格”，只有代数证明才可靠

✅ 组合证明与代数证明是等价的，组合证明往往更直观、更能揭示恒等式的本质含义

❌ 在组合证明中只给出计数公式而不解释计数逻辑

✅ 组合证明的关键是清晰地描述计数问题，并说明两种计数方法各自对应恒等式的哪一侧

四、习题精选

习题概览

题号范围核心考点难度
1-2 计算二项式系数的值 ⭐
3-6 利用帕斯卡恒等式求值 ⭐⭐
7-10 利用二项式定理展开 ⭐⭐
11-14 证明组合恒等式（代数法） ⭐⭐⭐
15-18 组合证明恒等式 ⭐⭐⭐
19-22 范德蒙德恒等式的应用 ⭐⭐⭐
23-26 上指标求和恒等式 ⭐⭐⭐
27-30 二项式系数的单峰性 ⭐⭐⭐

题号范围	核心考点	难度
1-2	计算二项式系数的值	⭐
3-6	利用帕斯卡恒等式求值	⭐⭐
7-10	利用二项式定理展开	⭐⭐
11-14	证明组合恒等式（代数法）	⭐⭐⭐
15-18	组合证明恒等式	⭐⭐⭐
19-22	范德蒙德恒等式的应用	⭐⭐⭐
23-26	上指标求和恒等式	⭐⭐⭐
27-30	二项式系数的单峰性	⭐⭐⭐

题1：利用二项式定理展开

题目

利用二项式定理展开 $(2 x - 3 y)^{5}$ 。

解答

由二项式定理： $(2 x - 3 y)^{5} = \sum_{k = 0}^{5} (k 5) (2 x)^{5 - k} (- 3 y)^{k}$

逐项计算：

$k = 0$ ： $(0 5) (2 x)^{5} = 32 x^{5}$

$k = 1$ ： $(1 5) (2 x)^{4} (- 3 y) = 5 \cdot 16 x^{4} \cdot (- 3 y) = - 240 x^{4} y$

$k = 2$ ： $(2 5) (2 x)^{3} (- 3 y)^{2} = 10 \cdot 8 x^{3} \cdot 9 y^{2} = 720 x^{3} y^{2}$

$k = 3$ ： $(3 5) (2 x)^{2} (- 3 y)^{3} = 10 \cdot 4 x^{2} \cdot (- 27 y^{3}) = - 1080 x^{2} y^{3}$

$k = 4$ ： $(4 5) (2 x) (- 3 y)^{4} = 5 \cdot 2 x \cdot 81 y^{4} = 810 x y^{4}$

$k = 5$ ： $(5 5) (- 3 y)^{5} = - 243 y^{5}$

因此： $(2 x - 3 y)^{5} = 32 x^{5} - 240 x^{4} y + 720 x^{3} y^{2} - 1080 x^{2} y^{3} + 810 x y^{4} - 243 y^{5}$

$■$

题2：证明组合恒等式

题目

证明恒等式 $\sum_{k = 0}^{n} (k n)^{2} = (n 2 n)$ 。

解答

方法一：利用范德蒙德恒等式

在范德蒙德恒等式 $(r m + n) = \sum_{k = 0}^{r} (k m) (r - k n)$ 中，令 $m = n$ ， $r = n$ ： $(n 2 n) = \sum_{k = 0}^{n} (k n) (n - k n) = \sum_{k = 0}^{n} (k n)^{2}$

最后一步利用了对称性 $(n - k n) = (k n)$ 。

方法二：组合证明

考虑从 $2 n$ 个元素中选 $n$ 个的方案数。将 $2 n$ 个元素分成两组，每组 $n$ 个。按从第一组中选出的个数 $k$ 分类：从第一组选 $k$ 个（ $(k n)$ 种），从第二组选 $n - k$ 个（ $(n - k n) = (k n)$ 种），对所有 $k$ 求和。

$■$

题3：上指标求和

题目

利用上指标求和恒等式计算 $\sum_{k = 3}^{10} (3 k)$ 。

解答

由上指标求和恒等式 $\sum_{k = r}^{n} (r k) = (r + 1 n + 1)$ ，令 $r = 3$ ， $n = 10$ ： $\sum_{k = 3}^{10} (3 k) = (4 11) = \frac{11 !}{4 ! \cdot 7 !} = \frac{11 \times 10 \times 9 \times 8}{4 \times 3 \times 2 \times 1} = 330$

$■$

题4：帕斯卡恒等式的应用

题目

用组合证明的方法证明： $(k + 1 n + 1) = \sum_{j = k}^{n} (k j)$ 。

解答

组合证明：考虑从 ${0, 1, 2, \dots, n}$ 中选 $k + 1$ 个元素。

方法一（直接计数）： $(k + 1 n + 1)$ 。

方法二（按最大元素分类）：设选出的 $k + 1$ 个元素中最大的为 $j + 1$ （其中 $k \leq j \leq n$ ）。那么还需要从 ${0, 1, \dots, j}$ 中选 $k$ 个（不含 $j + 1$ 本身），即从 ${0, 1, \dots, j - 1}$ 中选 $k$ 个，共 $(k j)$ 种。

对所有可能的 $j$ （从 $k$ 到 $n$ ）求和，得： $(k + 1 n + 1) = \sum_{j = k}^{n} (k j)$

$■$

题5：二项式系数的单峰性

题目

证明当 $n$ 为偶数时， $(n /2 n)$ 是第 $n$ 行的最大二项式系数。

解答

考虑相邻两项之比： $\frac{( k + 1 n )}{( k n )} = \frac{n !}{( k + 1 )! ( n - k - 1 )!} \cdot \frac{k ! ( n - k )!}{n !} = \frac{n - k}{k + 1}$

当 $\frac{n - k}{k + 1} > 1$ ，即 $k < \frac{n - 1}{2}$ 时， $(k + 1 n) > (k n)$ （递增）

当 $\frac{n - k}{k + 1} < 1$ ，即 $k > \frac{n - 1}{2}$ 时， $(k + 1 n) < (k n)$ （递减）

当 $\frac{n - k}{k + 1} = 1$ ，即 $k = \frac{n - 1}{2}$ 时， $(k + 1 n) = (k n)$

当 $n$ 为偶数时， $\frac{n - 1}{2}$ 不是整数，递增到 $k = \frac{n}{2} - 1$ 后递减，因此 $(n /2 n)$ 是唯一的最大值。

$■$

解题思路提示

二项式系数恒等式的解题方法论：

代数证明：利用定义 $(k n) = \frac{n !}{k ! ( n - k )!}$ 直接化简，或利用帕斯卡恒等式递推

组合证明：找到一个计数问题，用两种方法计数，关键在于选择合适的分类标准

二项式定理：通过在 $(x + y)^{n}$ 中代入特殊值（如 $x = y = 1$ ， $x = 1, y = - 1$ ）得到恒等式

范德蒙德恒等式：处理涉及两组元素的选择问题时，考虑按从第一组中选出的个数分类

上指标求和：处理 $\sum (r k)$ 形式的求和时，考虑”按最大元素分类”的组合论证

五、视频学习指南

视频资源

资源链接对应内容备注
Rosen 8e Section 6.4 教材原文完整定义、定理与例题英文教材
MIT 6.042J Lecture 5 链接组合计数与二项式系数英文，MIT开放课程
3Blue1Brown - 二项式定理链接二项式定理的直觉理解英文，可视化讲解

资源	链接	对应内容	备注
Rosen 8e Section 6.4	教材原文	完整定义、定理与例题	英文教材
MIT 6.042J Lecture 5	链接	组合计数与二项式系数	英文，MIT开放课程
3Blue1Brown - 二项式定理	链接	二项式定理的直觉理解	英文，可视化讲解

六、教材原文

教材原文

“The binomial theorem gives the coefficients of the expansion of powers of binomial expressions. The binomial coefficient $(k n)$ counts the number of ways to choose $k$ objects from a set of $n$ distinct objects. This connection between algebra and combinatorics is one of the most fruitful in all of mathematics.”

“Combinatorial proofs are often more enlightening than algebraic proofs because they reveal why an identity is true, not just that it is true. A combinatorial proof establishes that both sides of an identity count the same set of objects, just in two different ways.”

参见 Wiki

二项式系数 — 二项式系数的定义与性质
二项式定理 — 二项式定理及其推论
帕斯卡三角形 — 帕斯卡三角形的构造与性质
范德蒙德恒等式 — 范德蒙德恒等式及其证明
组合证明 — 组合证明方法详解

计数

CS Wiki

探索

6.4 二项式系数与恒等式

一、知识结构总览

二、核心思想

1. 二项式系数的定义

2. 帕斯卡三角形（Pascal’s Triangle）

3. 二项式定理（Binomial Theorem）

4. 重要组合恒等式

5. 组合证明方法

三、补充理解与易混淆点

补充理解

易混淆点

四、习题精选

题1：利用二项式定理展开

题2：证明组合恒等式

题3：上指标求和

题4：帕斯卡恒等式的应用

题5：二项式系数的单峰性

五、视频学习指南

六、教材原文

参见 Wiki

关系图谱

目录

反向链接