二项式定理
一、课上练习
编程练习
- 计算系数：L49996
二、知识总结
✨ 核心思想
二项式定理给出了 (a + b)^n 展开式的精确形式，将幂运算与组合数联系在一起。它不仅是代数计算的基础工具，在竞赛中更是推导组合恒等式、处理生成函数、解决计数问题的重要武器。
✨ 定理内容
(a + b)^n = Σ(k=0 to n) C(n, k) × a^(n-k) × b^k
展开后共 n+1 项，第 k 项（从 0 计数）为 C(n, k) × a^(n-k) × b^k。
特殊代入：
- a=1, b=1：C(n,0) + C(n,1) + ... + C(n,n) = 2^n
- a=1, b=-1：C(n,0) - C(n,1) + C(n,2) - ... = 0（当 n ≥ 1，奇数项和 = 偶数项和 = 2^(n-1)）
- a=1, b=x：(1+x)^n = Σ C(n,k) × x^k（生成函数的基础）
✨ 帕斯卡三角形（杨辉三角）
1行 0: 1
2行 1: 1 1
3行 2: 1 2 1
4行 3: 1 3 3 1
5行 4: 1 4 6 4 1
6行 5: 1 5 10 10 5 1性质：
- 第 n 行第 k 个数就是 C(n, k)
- 每个数等于左上方和右上方两个数之和：C(n,k) = C(n-1,k-1) + C(n-1,k)
- 第 n 行的和为 2^n
- 对角线上依次是自然数、三角形数、四面体数等
✨ 重要组合恒等式
由二项式定理可以推导出许多有用的恒等式：
1. 范德蒙德恒等式： C(m+n, r) = Σ(k=0 to r) C(m,k) × C(n, r-k)
证明：比较 (1+x)^m × (1+x)^n = (1+x)^(m+n) 两边 x^r 的系数。
2. 平行求和： C(r,r) + C(r+1,r) + ... + C(n,r) = C(n+1, r+1)
3. 二次方恒等式： Σ(k=0 to n) C(n,k)² = C(2n, n)
4. 带权求和： Σ(k=0 to n) k × C(n,k) = n × 2^(n-1)
证明：对 (1+x)^n = Σ C(n,k) × x^k 两边对 x 求导，再令 x=1。
✨ 代码实现
1#include <iostream>
2using namespace std;
3typedef long long ll;
4const int MOD = 1e9 + 7;
5const int MAXN = 1000005;
6
7ll qpow(ll base, ll exp, ll mod) {
8 ll result = 1;
9 base %= mod;
10 while (exp > 0) {
11 if (exp & 1) result = result * base % mod;
12 base = base * base % mod;
13 exp >>= 1;
14 }
15 return result;
16}
17
18ll fac[MAXN], inv_fac[MAXN];
19
20void init(int n) {
21 fac[0] = 1;
22 for (int i = 1; i <= n; i++)
23 fac[i] = fac[i-1] * i % MOD;
24 inv_fac[n] = qpow(fac[n], MOD - 2, MOD);
25 for (int i = n - 1; i >= 0; i--)
26 inv_fac[i] = inv_fac[i+1] * (i+1) % MOD;
27}
28
29ll C(int n, int k) {
30 if (k < 0 || k > n) return 0;
31 return fac[n] % MOD * inv_fac[k] % MOD * inv_fac[n-k] % MOD;
32}
33
34// 计算 (a + b)^n 展开式的第 k 项
35// 即 C(n,k) * a^(n-k) * b^k mod MOD
36ll binomial_term(int n, int k, ll a, ll b) {
37 return C(n, k) % MOD * qpow(a, n - k, MOD) % MOD * qpow(b, k, MOD) % MOD;
38}
39
40int main() {
41 int n;
42 ll a, b;
43 cin >> n >> a >> b;
44 init(n);
45
46 cout << "(" << a << " + " << b << ")^" << n << " 的展开：" << endl;
47 for (int k = 0; k <= n; k++) {
48 ll coeff = binomial_term(n, k, a, b);
49 cout << "第 " << k << " 项: C(" << n << "," << k << ") * "
50 << a << "^" << n - k << " * " << b << "^" << k
51 << " = " << coeff << endl;
52 }
53
54 // 验证：直接计算 (a+b)^n
55 ll total = qpow((a + b) % MOD + MOD, n, MOD);
56 cout << "总和: " << total << endl;
57
58 return 0;
59}1#include <iostream>
2using namespace std;
3typedef long long ll;
4const int MOD = 1e9 + 7;
5const int MAXN = 10005;
6
7ll fac[MAXN], inv_fac[MAXN];
8
9ll qpow(ll base, ll exp, ll mod) {
10 ll result = 1; base %= mod;
11 while (exp > 0) {
12 if (exp & 1) result = result * base % mod;
13 base = base * base % mod; exp >>= 1;
14 }
15 return result;
16}
17
18void init(int n) {
19 fac[0] = 1;
20 for (int i = 1; i <= n; i++) fac[i] = fac[i-1] * i % MOD;
21 inv_fac[n] = qpow(fac[n], MOD - 2, MOD);
22 for (int i = n-1; i >= 0; i--) inv_fac[i] = inv_fac[i+1] * (i+1) % MOD;
23}
24
25ll C(int n, int k) {
26 if (k < 0 || k > n) return 0;
27 return fac[n] % MOD * inv_fac[k] % MOD * inv_fac[n-k] % MOD;
28}
29
30int main() {
31 int n = 10;
32 init(2 * n);
33
34 // 恒等式1：Σ C(n,k) = 2^n
35 ll sum1 = 0;
36 for (int k = 0; k <= n; k++)
37 sum1 = (sum1 + C(n, k)) % MOD;
38 cout << "Σ C(" << n << ",k) = " << sum1
39 << ", 2^" << n << " = " << qpow(2, n, MOD) << endl;
40
41 // 恒等式2：Σ C(n,k)^2 = C(2n, n)
42 ll sum2 = 0;
43 for (int k = 0; k <= n; k++)
44 sum2 = (sum2 + C(n, k) % MOD * C(n, k)) % MOD;
45 cout << "Σ C(" << n << ",k)^2 = " << sum2
46 << ", C(" << 2*n << "," << n << ") = " << C(2*n, n) << endl;
47
48 // 恒等式3：Σ k*C(n,k) = n * 2^(n-1)
49 ll sum3 = 0;
50 for (int k = 0; k <= n; k++)
51 sum3 = (sum3 + (ll)k % MOD * C(n, k)) % MOD;
52 ll expected = (ll)n % MOD * qpow(2, n-1, MOD) % MOD;
53 cout << "Σ k*C(" << n << ",k) = " << sum3
54 << ", " << n << "*2^" << n-1 << " = " << expected << endl;
55
56 return 0;
57}✨ 应用示例
示例 1：展开 (2x + 3)^4
(2x+3)^4 = Σ(k=0 to 4) C(4,k) × (2x)^(4-k) × 3^k
= 1×16x⁴×1 + 4×8x³×3 + 6×4x²×9 + 4×2x×27 + 1×1×81
= 16x⁴ + 96x³ + 216x² + 216x + 81
示例 2：求 (1+x)^100 中 x^3 的系数
C(100, 3) = 100×99×98 / (3×2×1) = 161700
示例 3：证明奇数项和等于偶数项和
在 (a+b)^n 中令 a=1, b=-1：
(1+(-1))^n = 0^n = 0 = Σ C(n,k) × (-1)^k（当 n ≥ 1）
所以 C(n,0) + C(n,2) + ... = C(n,1) + C(n,3) + ... = 2^(n-1)
示例 4：求 11^n 的个位数
11^n = (10+1)^n = Σ C(n,k) × 10^(n-k)
当 n-k ≥ 1 时，10^(n-k) 的个位是 0。
只有 k=n 时贡献 C(n,n) × 10^0 = 1。
所以 11^n 的个位始终是 1。
✨ 解题步骤详解
- 识别二项式结构：看到 (a+b)^n 或需要展开多项式时考虑二项式定理
- 确定展开项：用 C(n,k) × a^(n-k) × b^k 写出需要的项
- 代入特殊值：x=1, x=-1 等，可以推导出组合恒等式
- 求导/积分技巧：对生成函数求导或积分可以引入/消去系数中的 k
- 数值计算：使用预处理阶乘 + 逆元高效计算
✨ 常见错误
- 展开式中 a 和 b 的指数方向搞反（a 的指数从 n 递减，b 的从 0 递增）
- 忘记第 k 项中还有 a^(n-k) 和 b^k，只写了 C(n,k)
- 帕斯卡三角形的行号和列号从 0 开始还是从 1 开始搞混
- 推导恒等式时代入值后的计算错误
- 大数计算时忘记取模
✨ 总结
二项式定理将组合数与多项式展开联系起来，是代数与组合的桥梁。在竞赛中的应用：
| 应用方向 | 示例 |
|---|---|
| 多项式展开 | 求 (a+b)^n 的特定项 |
| 组合恒等式 | 推导求和公式 |
| 数论 | 分析 (p+1)^n 模 p 的性质 |
| 生成函数 | (1+x)^n 作为组合数的生成函数 |
| 概率 | 二项分布的概率计算 |
掌握二项式定理及其衍生的恒等式，是处理组合数学问题的基础能力。