第5章 二项式系数 (Binomial Coefficients)
一、导读
5.1 本章学习目标
在本章结束时，你将能够：
- 理解二项式系数的组合意义和代数定义
- 运用帕斯卡三角形计算二项式系数
- 掌握二项式定理及其推广形式
- 应用组合恒等式简化复杂表达式
- 使用容斥原理解决计数问题
- 掌握范德蒙德卷积等重要恒等式
- 理解生成函数在组合数学中的作用
- 掌握卢卡斯定理进行模素数计算
5.2 为什么本章如此重要
二项式系数是组合数学的核心对象，记作 $\binom{n}{k}$，读作"n选k"。它出现在概率论、统计学、算法分析、代数等多个领域。
对于程序员而言，二项式系数的重要性体现在：
算法分析：许多算法的时间复杂度涉及二项式系数
概率计算：二项分布、超几何分布的基础
动态规划：组合计数问题的经典DP模型
密码学：某些加密方案基于组合恒等式
机器学习：特征选择、集成学习中的组合问题
计算机图形学：贝塞尔曲线、B样条的系数
《具体数学》用大量篇幅讨论二项式系数，因为它是连接离散数学与连续数学的桥梁。通过研究二项式系数，我们将学习强大的代数技巧和组合思维。二项式系数不仅是纯数学的对象，更是实际编程中经常遇到的工具——从子集枚举到概率模拟，从路径计数到多项式展开。
5.3 核心问题引导
二项式系数 $\binom{n}{k}$ 的组合意义是什么？
帕斯卡三角形的递推关系如何推导？
二项式定理的内容是什么？如何推广到负指数和分数指数？
什么是组合恒等式？常见的恒等式有哪些？
容斥原理如何解决包含排斥的计数问题？
生成函数如何将序列转化为代数对象？
范德蒙德卷积的直观解释是什么？
如何高效计算大组合数模素数？
二、核心概念详解
5.1 二项式系数的定义与性质
组合定义
定义：从 n 个不同元素中选取 k 个元素的方案数称为二项式系数，记作 $\binom{n}{k}$。
$$\binom{n}{k} = \frac{n!}{k!(n-k)!}$$
其中 n! = n × (n-1) × ... × 2 × 1 是 n 的阶乘，规定 0! = 1。
通俗地说：$\binom{n}{k}$ 告诉你从 n 个人中选出 k 个人组成委员会有多少种方法。
边界条件：
- $\binom{n}{0} = 1$（选0个元素只有1种方法：什么都不选）
- $\binom{n}{n} = 1$（选所有元素只有1种方法）
- $\binom{n}{k} = 0$ 当 k > n 或 k < 0
对称性：
$$\binom{n}{k} = \binom{n}{n-k}$$
直观解释：从 n 个人中选 k 个人进入委员会，等价于选 n-k 个人不进入委员会。
代数证明：
$$\binom{n}{n-k} = \frac{n!}{(n-k)!(n-(n-k))!} = \frac{n!}{(n-k)!k!} = \binom{n}{k}$$
帕斯卡恒等式
帕斯卡恒等式（Pascal's Identity）是二项式系数最重要的递推关系：
$$\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$$
组合证明：考虑 n 个人中的特定一人 A。从 n 个人中选 k 个人的方案可以分为两类：
A 被选中：需要从剩下的 n-1 个人中再选 k-1 个，有 $\binom{n-1}{k-1}$ 种
A 未被选中：需要从剩下的 n-1 个人中选 k 个，有 $\binom{n-1}{k}$ 种
两类互斥且穷尽所有情况，所以总数是两者之和。
代数证明：
$$\binom{n-1}{k-1} + \binom{n-1}{k} = \frac{(n-1)!}{(k-1)!(n-k)!} + \frac{(n-1)!}{k!(n-k-1)!}$$
$$= \frac{(n-1)! \cdot k + (n-1)! \cdot (n-k)}{k!(n-k)!} = \frac{(n-1)! \cdot n}{k!(n-k)!} = \binom{n}{k}$$
帕斯卡三角形
帕斯卡三角形（杨辉三角）是二项式系数的三角形排列：
1 n=0: C(0,0)
1 1 n=1: C(1,0) C(1,1)
1 2 1 n=2: C(2,0) C(2,1) C(2,2)
1 3 3 1 n=3: C(3,0) C(3,1) C(3,2) C(3,3)
1 4 6 4 1 n=4: ...
1 5 10 10 5 1
1 6 15 20 15 6 1每个数等于上方两数之和，这正是帕斯卡恒等式的体现。
有趣性质：
- 第 n 行的和为 2ⁿ
- 斜对角线的和形成斐波那契数列
- 将奇数标黑、偶数标白，形成谢尔宾斯基三角形分形图案
- 第 p 行（p 为素数）除了首尾的 1，其他所有数都能被 p 整除
5.2 二项式定理
定理陈述
二项式定理（Binomial Theorem）：
$$(x + y)^n = \sum_{k=0}^{n} \binom{n}{k} x^k y^{n-k}$$
特殊情形（令 x = 1, y = 1）：
$$2^n = \sum_{k=0}^{n} \binom{n}{k}$$
这给出了一个优美的恒等式：第 n 行帕斯卡三角形的所有元素之和等于 2ⁿ。
组合证明：(x+y)ⁿ = (x+y)(x+y)...(x+y)（共 n 个因子）。展开时，每一项是从每个因子中选择 x 或 y 相乘。选择 k 个 x 和 n-k 个 y 的方案数是 $\binom{n}{k}$，对应的项是 xᵏyⁿ⁻ᵏ。
示例展开
$$(x + y)^3 = \binom{3}{0}x^0y^3 + \binom{3}{1}x^1y^2 + \binom{3}{2}x^2y^1 + \binom{3}{3}x^3y^0 = y^3 + 3xy^2 + 3x^2y + x^3$$
验证：(x+y)³ = (x+y)(x²+2xy+y²) = x³+2x²y+xy²+x²y+2xy²+y³ = x³+3x²y+3xy²+y³。✓
更多例子：
- $(x+y)^4 = x^4 + 4x^3y + 6x^2y^2 + 4xy^3 + y^4$
- $(x-y)^3 = x^3 - 3x^2y + 3xy^2 - y^3$
牛顿广义二项式定理
牛顿将二项式定理推广到任意实数指数：
$$(1 + x)^\alpha = \sum_{k=0}^{\infty} \binom{\alpha}{k} x^k$$
其中广义二项式系数定义为：
$$\binom{\alpha}{k} = \frac{\alpha(\alpha-1)(\alpha-2)\cdots(\alpha-k+1)}{k!}$$
当 α 是非负整数 n 时，当 k > n 时分子为 0，级数退化为有限和，回到经典二项式定理。
示例：α = -1 时，
$$\binom{-1}{k} = \frac{(-1)(-2)\cdots(-k)}{k!} = (-1)^k$$
$$(1+x)^{-1} = \sum_{k=0}^{\infty} (-1)^k x^k = 1 - x + x^2 - x^3 + \cdots$$
这正是几何级数公式 $\frac{1}{1+x} = 1 - x + x^2 - x^3 + \cdots$（当 |x| < 1 时收敛）。
示例：α = 1/2 时，
$$\binom{1/2}{0} = 1, \binom{1/2}{1} = \frac{1}{2}, \binom{1/2}{2} = \frac{(1/2)(-1/2)}{2} = -\frac{1}{8}$$
$$\sqrt{1+x} = 1 + \frac{x}{2} - \frac{x^2}{8} + \frac{x^3}{16} - \cdots$$
这在数值分析和物理中有广泛应用。
多项式定理
二项式定理可以推广到多个变量：
$$(x_1 + x_2 + \cdots + x_m)^n = \sum_{k_1+\cdots+k_m=n} \frac{n!}{k_1!k_2!\cdots k_m!} x_1^{k_1}x_2^{k_2}\cdots x_m^{k_m}$$
其中 $\frac{n!}{k_1!k_2!\cdots k_m!}$ 称为多项式系数，记作 $\binom{n}{k_1,k_2,\ldots,k_m}$。
组合解释：将 n 个不同物品分配到 m 个不同的盒子中，第 i 个盒子放 kᵢ 个物品的方案数。
5.3 组合恒等式
吸收恒等式
吸收恒等式（Absorption Identity）：
$$k\binom{n}{k} = n\binom{n-1}{k-1}$$
证明：
$$k\binom{n}{k} = k \cdot \frac{n!}{k!(n-k)!} = \frac{n!}{(k-1)!(n-k)!} = n \cdot \frac{(n-1)!}{(k-1)!(n-k)!} = n\binom{n-1}{k-1}$$
组合解释：从 n 个人中选 k 个人并指定一人为队长。方法1：先选 k 人（$\binom{n}{k}$），再从中选队长（k 种），共 $k\binom{n}{k}$。方法2：先选队长（n 种），再从剩下 n-1 人中选 k-1 人（$\binom{n-1}{k-1}$），共 $n\binom{n-1}{k-1}$。
推论：
$$\binom{n}{k} = \frac{n}{k}\binom{n-1}{k-1}$$
这个公式常用于递归计算二项式系数。
上指标求和
恒等式：
$$\sum_{k=0}^{n} \binom{k}{m} = \binom{n+1}{m+1}$$
组合证明：从 {1, 2, ..., n+1} 中选 m+1 个数。设最大数为 k+1（m+1 ≤ k+1 ≤ n+1，即 m ≤ k ≤ n），则从 {1, ..., k} 中选剩下的 m 个数，有 $\binom{k}{m}$ 种。对所有可能的 k 求和即得左边，而右边是直接选择的方案数。
示例：$\binom{0}{2} + \binom{1}{2} + \binom{2}{2} + \binom{3}{2} + \binom{4}{2} = 0 + 0 + 1 + 3 + 6 = 10 = \binom{5}{3}$。✓
范德蒙德卷积
范德蒙德卷积（Vandermonde's Convolution）：
$$\sum_{k=0}^{r} \binom{m}{k}\binom{n}{r-k} = \binom{m+n}{r}$$
组合证明：从 m 个红球和 n 个蓝球中选 r 个球。方法1：直接选，有 $\binom{m+n}{r}$ 种。方法2：选 k 个红球和 r-k 个蓝球，对 k 求和，得到左边。
代数证明：考虑 (1+x)ᵐ⁺ⁿ = (1+x)ᵐ(1+x)ⁿ。比较两边 xʳ 的系数：
- 左边：$\binom{m+n}{r}$
- 右边：$(\sum_{i=0}^{m} \binom{m}{i}x^i)(\sum_{j=0}^{n} \binom{n}{j}x^j)$ 中 xʳ 的系数是 $\sum_{k=0}^{r} \binom{m}{k}\binom{n}{r-k}$
特例：令 m = n, r = n，得到：
$$\sum_{k=0}^{n} \binom{n}{k}^2 = \binom{2n}{n}$$
这是中心二项式系数的一个重要恒等式。
交错和恒等式
恒等式：
$$\sum_{k=0}^{n} (-1)^k \binom{n}{k} = 0 \quad \text{当 } n > 0$$
证明：在二项式定理中令 x = -1, y = 1：
$$(1-1)^n = \sum_{k=0}^{n} \binom{n}{k}(-1)^k = 0$$
这个恒等式在容斥原理中有重要应用。
加权版本：
$$\sum_{k=0}^{n} (-1)^k \binom{n}{k} k^m = \begin{cases} 0 & \text{if } m < n \\ (-1)^n n! & \text{if } m = n \end{cases}$$
朱世杰恒等式
恒等式：
$$\sum_{k=m}^{n} \binom{k}{m} = \binom{n+1}{m+1}$$
这实际上是上指标求和的另一种形式。
5.4 容斥原理
基本原理
容斥原理（Inclusion-Exclusion Principle）用于计算多个集合并集的大小。
两个集合：
$$|A \cup B| = |A| + |B| - |A \cap B|$$
三个集合：
$$|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|$$
一般形式：
$$\left|\bigcup_{i=1}^{n} A_i\right| = \sum_{i}|A_i| - \sum_{i<j}|A_i \cap A_j| + \sum_{i<j<k}|A_i \cap A_j \cap A_k| - \cdots + (-1)^{n+1}|A_1 \cap \cdots \cap A_n|$$
直观理解：加单个集合，减两两交集（因为被加了两次），加三三交集（因为被减多了），依此类推。
证明思路：考虑某个元素 x 属于 k 个集合。它在左边的贡献是 1（如果在并集中）。在右边，它被计算了 $\binom{k}{1} - \binom{k}{2} + \binom{k}{3} - \cdots = 1 - (1-1)^k = 1$ 次（当 k ≥ 1）。✓
应用：错排问题
错排（Derangement）是没有任何元素在其原始位置的排列。n 个元素的错排数 Dₙ 为：
$$D_n = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!}$$
推导：设 S 是所有排列的集合，Aᵢ 是第 i 个元素在其原始位置的排列集合。我们要求的是不在任何 Aᵢ 中的排列数。
由容斥原理：
$$D_n = n! - \binom{n}{1}(n-1)! + \binom{n}{2}(n-2)! - \cdots + (-1)^n\binom{n}{n}0!$$
$$= n!\left(1 - \frac{1}{1!} + \frac{1}{2!} - \cdots + \frac{(-1)^n}{n!}\right)$$
当 n → ∞ 时，$D_n \approx \frac{n!}{e}$。
前几个错排数：D₀=1, D₁=0, D₂=1, D₃=2, D₄=9, D₅=44, D₆=265。
递推关系：$D_n = (n-1)(D_{n-1} + D_{n-2})$。
组合解释：考虑元素 1 的位置。如果 1 放在位置 i（有 n-1 种选择），则：
- 如果 i 放在位置 1，剩下 n-2 个元素错排：Dₙ₋₂ 种
- 如果 i 不放在位置 1，相当于 n-1 个元素的错排：Dₙ₋₁ 种
应用：欧拉函数的计算
欧拉函数 φ(n) 也可以用容斥原理推导。φ(n) 是 1 到 n 中与 n 互质的数的个数。
设 n 的不同素因子为 p₁, p₂, ..., pₖ。令 Aᵢ 为 1 到 n 中被 pᵢ 整除的数的集合。
$$\phi(n) = n - \left|\bigcup_{i=1}^{k} A_i\right|$$
由容斥原理：
$$\left|\bigcup_{i=1}^{k} A_i\right| = \sum_i \frac{n}{p_i} - \sum_{i<j} \frac{n}{p_i p_j} + \cdots$$
$$\phi(n) = n\left(1 - \sum_i \frac{1}{p_i} + \sum_{i<j} \frac{1}{p_i p_j} - \cdots\right) = n\prod_{i=1}^{k}\left(1-\frac{1}{p_i}\right)$$
5.5 生成函数入门
定义
生成函数（Generating Function）是将序列编码为幂级数的工具。对于序列 a₀, a₁, a₂, ...，其普通生成函数定义为：
$$A(x) = \sum_{n=0}^{\infty} a_n x^n$$
二项式系数的生成函数
二项式系数 $\binom{n}{0}, \binom{n}{1}, \ldots, \binom{n}{n}$ 的生成函数是：
$$\sum_{k=0}^{n} \binom{n}{k} x^k = (1+x)^n$$
这正是二项式定理（令 y = 1）。
应用：斐波那契数列
斐波那契数列 F₀=0, F₁=1, Fₙ=Fₙ₋₁+Fₙ₋₂ 的生成函数为：
$$F(x) = \sum_{n=0}^{\infty} F_n x^n = \frac{x}{1-x-x^2}$$
通过部分分式分解，可以导出比内公式（Binet's Formula）：
$$F_n = \frac{\phi^n - \psi^n}{\sqrt{5}}$$
其中 $\phi = \frac{1+\sqrt{5}}{2}$，$\psi = \frac{1-\sqrt{5}}{2}$。
推导：由递推关系 Fₙ - Fₙ₋₁ - Fₙ₋₂ = 0，乘以 xⁿ 并求和：
$$\sum_{n=2}^{\infty} F_n x^n = \sum_{n=2}^{\infty} F_{n-1} x^n + \sum_{n=2}^{\infty} F_{n-2} x^n$$
$$F(x) - x = x(F(x)) + x^2 F(x)$$
$$F(x)(1-x-x^2) = x$$
$$F(x) = \frac{x}{1-x-x^2}$$
5.6 卢卡斯定理
卢卡斯定理（Lucas' Theorem）提供了计算 $\binom{n}{k} \mod p$（p 为素数）的高效方法。
定理：设 p 是素数，n 和 k 的 p 进制表示为：
$$n = n_m p^m + n_{m-1} p^{m-1} + \cdots + n_0$$
$$k = k_m p^m + k_{m-1} p^{m-1} + \cdots + k_0$$
则：
$$\binom{n}{k} \equiv \prod_{i=0}^{m} \binom{n_i}{k_i} \pmod{p}$$
其中如果某个 kᵢ > nᵢ，则 $\binom{n_i}{k_i} = 0$。
应用：快速判断 $\binom{n}{k}$ 是否能被素数 p 整除。如果 k 的 p 进制表示中有任何一位大于 n 的对应位，则 $\binom{n}{k}$ 能被 p 整除。
示例：计算 $\binom{10}{3} \mod 3$。
10 = 101₃，3 = 010₃。
$\binom{10}{3} \equiv \binom{1}{0}\binom{0}{1}\binom{1}{0} = 1 \times 0 \times 1 = 0 \pmod{3}$。
验证：$\binom{10}{3} = 120$，120 mod 3 = 0。✓
三、程序员的视角
5.1 在算法分析中的应用
子集枚举
枚举 n 个元素的所有子集需要 2ⁿ 次操作，因为 $\sum_{k=0}^{n} \binom{n}{k} = 2^n$。
在回溯算法中，如果需要枚举所有大小为 k 的子集，复杂度为 $\binom{n}{k}$。
动态规划
许多DP问题涉及二项式系数，如：
- 组合计数：dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
- 路径计数：网格中从 (0,0) 到 (m,n) 的路径数是 $\binom{m+n}{m}$
- 背包问题的变种
概率计算
二项分布的概率质量函数：
$$P(X = k) = \binom{n}{k} p^k (1-p)^{n-k}$$
这在A/B测试、质量控制、可靠性分析中有广泛应用。
贝塞尔曲线
计算机图形学中的贝塞尔曲线使用二项式系数作为权重：
$$B(t) = \sum_{i=0}^{n} \binom{n}{i} (1-t)^{n-i} t^i P_i$$
其中 Pᵢ 是控制点。
5.2 常见陷阱
陷阱1：阶乘溢出
计算 $\binom{n}{k}$ 时，n! 可能非常大。应使用递推关系或约分技巧。
解决方案：使用乘法公式 $\binom{n}{k} = \frac{n(n-1)\cdots(n-k+1)}{k!}$，在计算过程中不断约分。
陷阱2：浮点精度
使用浮点数计算大组合数时可能丢失精度。应使用整数算术或高精度库。
陷阱3：模运算中的除法
在模素数 p 下计算 $\binom{n}{k} \mod p$ 时，不能直接做除法。需要使用模逆元或卢卡斯定理。
5.3 与其他领域的联系
- 统计学：二项分布、超几何分布
- 量子计算：量子态的叠加涉及组合系数
- 编码理论：汉明码等纠错码的设计
- 金融数学：期权定价的二项式模型
四、代码实战
5.1 二项式系数计算
class BinomialCoefficients:
"""二项式系数计算工具"""
@staticmethod
def compute_direct(n, k):
"""直接计算：使用乘法公式避免溢出"""
if k < 0 or k > n:
return 0
if k == 0 or k == n:
return 1
# 利用对称性减少计算
k = min(k, n - k)
result = 1
for i in range(k):
result = result * (n - i) // (i + 1)
return result
@staticmethod
def compute_dp(n_max):
"""使用DP构建帕斯卡三角形"""
C = [[0] * (n_max + 1) for _ in range(n_max + 1)]
for n in range(n_max + 1):
C[n][0] = 1
for k in range(1, n + 1):
C[n][k] = C[n-1][k-1] + C[n-1][k]
return C
@staticmethod
def compute_mod(n, k, p):
"""计算 C(n,k) mod p，p为素数，使用卢卡斯定理"""
def small_binomial(n, k, p):
"""当 n < p 时直接计算"""
if k > n:
return 0
num = 1
den = 1
for i in range(k):
num = num * (n - i) % p
den = den * (i + 1) % p
# 费马小定理求逆元
return num * pow(den, p - 2, p) % p
if k > n:
return 0
result = 1
while n > 0 or k > 0:
ni = n % p
ki = k % p
if ki > ni:
return 0
result = result * small_binomial(ni, ki, p) % p
n //= p
k //= p
return result
@staticmethod
def derangement(n):
"""计算错排数 D_n"""
if n == 0:
return 1
if n == 1:
return 0
# 使用递推关系: D_n = (n-1) * (D_{n-1} + D_{n-2})
d_prev2, d_prev1 = 1, 0
for i in range(2, n + 1):
d_curr = (i - 1) * (d_prev1 + d_prev2)
d_prev2, d_prev1 = d_prev1, d_curr
return d_prev1
@staticmethod
def inclusion_exclusion_example():
"""容斥原理示例：计算1到100中能被2、3或5整除的数的个数"""
n = 100
count_2 = n // 2
count_3 = n // 3
count_5 = n // 5
count_6 = n // 6 # lcm(2,3) = 6
count_10 = n // 10 # lcm(2,5) = 10
count_15 = n // 15 # lcm(3,5) = 15
count_30 = n // 30 # lcm(2,3,5) = 30
result = count_2 + count_3 + count_5 - count_6 - count_10 - count_15 + count_30
return result
@staticmethod
def binomial_distribution_pmf(n, p, k):
"""二项分布 PMF: P(X=k)"""
import math
return BinomialCoefficients.compute_direct(n, k) * p**k * (1-p)**(n-k)
# 测试
bc = BinomialCoefficients()
print("=== 二项式系数测试 ===")
print(f"C(10, 3) = {bc.compute_direct(10, 3)}")
print(f"C(20, 10) = {bc.compute_direct(20, 10)}")
print(f"C(100, 50) = {bc.compute_direct(100, 50)}")
print("\n帕斯卡三角形:")
C = bc.compute_dp(8)
for n in range(9):
row = [C[n][k] for k in range(n+1)]
print(f"n={n}: {row}")
print(f"\n错排数:")
for n in range(11):
print(f"D_{n} = {bc.derangement(n)}")
print(f"\n1到100中能被2、3或5整除的数: {bc.inclusion_exclusion_example()}")
print(f"\n卢卡斯定理测试: C(10,3) mod 3 = {bc.compute_mod(10, 3, 3)}")
print(f"卢卡斯定理测试: C(10,3) mod 7 = {bc.compute_mod(10, 3, 7)}")
print(f"\n二项分布 B(10, 0.5):")
for k in range(11):
prob = bc.binomial_distribution_pmf(10, 0.5, k)
print(f"P(X={k}) = {prob:.4f}")5.2 生成函数实验
def generate_binomial_gf(n):
"""生成 (1+x)^n 的系数"""
coefficients = []
for k in range(n + 1):
coeff = BinomialCoefficients.compute_direct(n, k)
coefficients.append(coeff)
return coefficients
# 测试
for n in range(6):
coeffs = generate_binomial_gf(n)
print(f"(1+x)^{n}: {coeffs}")
# 验证卷积：(1+x)^m * (1+x)^n = (1+x)^{m+n}
m, n = 3, 4
coeffs_m = generate_binomial_gf(m)
coeffs_n = generate_binomial_gf(n)
# 卷积
convolved = [0] * (m + n + 1)
for i in range(m + 1):
for j in range(n + 1):
convolved[i + j] += coeffs_m[i] * coeffs_n[j]
coeffs_sum = generate_binomial_gf(m + n)
print(f"\n卷积验证: (1+x)^{m} * (1+x)^{n} = (1+x)^{m+n}")
print(f"卷积结果: {convolved}")
print(f"直接计算: {coeffs_sum}")
print(f"匹配: {convolved == coeffs_sum}")5.3 路径计数问题
def count_paths(m, n):
"""计算从(0,0)到(m,n)只向右或向下走的路径数"""
return BinomialCoefficients.compute_direct(m + n, m)
# 测试
print(f"\n路径计数:")
print(f"从(0,0)到(3,3): {count_paths(3, 3)}") # C(6,3) = 20
print(f"从(0,0)到(5,5): {count_paths(5, 5)}") # C(10,5) = 252五、深入思考
5.1 历史背景
帕斯卡三角形在中国南宋数学家杨辉的《详解九章算法》（1261年）中已有记载，比帕斯卡早约400年。二项式定理的一般形式由牛顿发现。容斥原理的思想可以追溯到棣莫弗和蒙莫尔。卢卡斯定理由法国数学家爱德华·卢卡斯于1878年提出。
5.2 未解决的问题
中心二项式系数的渐近行为：$\binom{2n}{n} \sim \frac{4^n}{\sqrt{\pi n}}$
二项式系数的整除性：Kummer定理描述了素数 p 整除 $\binom{n}{k}$ 的次数
q-二项式系数：在量子群和统计力学中的应用
5.3 延伸阅读
《具体数学》第5章 - Graham, Knuth, Patashnik
《Concrete Mathematics》相关章节
《组合数学》 - Richard Brualdi
《generatingfunctionology》 - Herbert Wilf
六、实验笔记
实验一：帕斯卡三角形的可视化
目标：绘制帕斯卡三角形并用颜色表示奇偶性。
步骤：
生成前32行的帕斯卡三角形
将奇数标记为黑色，偶数标记为白色
观察形成的谢尔宾斯基三角形图案
尝试用其他模数（如3、5）着色，观察图案
思考题：
- 为什么会出现分形图案？
- 不同模数下的图案有什么规律？
实验二：容斥原理的实际应用
目标：使用容斥原理解决实际的计数问题。
问题：有多少个1到1000的整数不能被2、3、5、7中任何一个整除？
扩展：
- 改变除数集合，观察结果变化
- 实现一个通用函数，接受任意除数集合
实验三：错排问题的模拟
目标：通过随机模拟验证错排数的理论值。
步骤：
生成大量随机排列
统计其中错排的比例
与理论值 Dₙ/n! ≈ 1/e 比较
七、本章小结
关键公式：
- 二项式系数：$\binom{n}{k} = \frac{n!}{k!(n-k)!}$
- 帕斯卡恒等式：$\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$
- 二项式定理：$(x+y)^n = \sum_{k=0}^{n} \binom{n}{k} x^k y^{n-k}$
- 范德蒙德卷积：$\sum_{k} \binom{m}{k}\binom{n}{r-k} = \binom{m+n}{r}$
- 错排数：$D_n = n!\sum_{k=0}^{n} \frac{(-1)^k}{k!}$
核心思想：
组合解释提供直觉
代数推导保证严谨
生成函数统一处理
容斥原理解决复杂计数
实用技巧：
- 使用对称性减少计算量
- 用递推关系避免大数溢出
- 模素数时使用卢卡斯定理
八、习题
基础题
习题 5.1：计算 $\binom{15}{5}$。
提示：使用乘法公式，注意约分。
习题 5.2：证明 $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$。
提示：给出组合证明和代数证明两种方法。
习题 5.3：展开 (x+2)⁴。
提示：使用二项式定理，注意系数。
习题 5.4：计算 D₆（6个元素的错排数）。
提示：使用递推关系或直接公式。
进阶题
习题 5.5：[ME] 证明 $\sum_{k=0}^{n} k\binom{n}{k} = n2^{n-1}$。
提示：使用吸收恒等式 $k\binom{n}{k} = n\binom{n-1}{k-1}$，然后求和。
习题 5.6：[ME] 使用容斥原理计算：有多少个1到100的整数不被2、3、5中任何一个整除？
提示：计算能被至少一个整除的数，然后用100减去。
习题 5.7：[ME] 证明 $\sum_{k=0}^{n} \binom{n}{k}^2 = \binom{2n}{n}$。
提示：使用范德蒙德卷积，令 m = n, r = n。
挑战题
习题 5.8：[HM25] 证明范德蒙德卷积的代数形式。
提示：比较 (1+x)ᵐ⁺ⁿ = (1+x)ᵐ(1+x)ⁿ 两边 xʳ 的系数。
习题 5.9：[HM30] 推导错排数的渐近公式 $D_n \sim \frac{n!}{e}$。
提示：使用泰勒级数 $e^{-1} = \sum_{k=0}^{\infty} \frac{(-1)^k}{k!}$。
习题 5.10：[HM40] 研究卢卡斯定理：证明 $\binom{n}{k} \mod p$ 的计算方法。
提示：使用生成函数 $(1+x)^n \mod p$ 和费马小定理。
本章完