首页 › AMC 12 › 排列组合 › Combinatorics

🎲 排列组合

Combinatorics

AMC 12 的排列组合比 AMC 10 更深更广——容斥原理、递推关系、二项式定理、母函数方法，以及各种组合恒等式的证明技巧，是竞赛数学的核心工具箱。

📚 3 章节 💡 5 道例题 ✏️ 6 道练习 🎯 难度：高 ⏱ 约55分钟
1
高级计数方法 Advanced Counting Methods
高频进阶

1.1 容斥原理 Inclusion-Exclusion Principle

容斥原理是处理"至少满足一个条件"的计数问题的核心工具。对于两个集合 A 和 B：

📝 两集合容斥 / Two-Set Inclusion-Exclusion
|A ∪ B| = |A| + |B| − |A ∩ B|
Count everything once, then subtract what was double-counted.

推广到三个集合：

📝 三集合容斥 / Three-Set Inclusion-Exclusion
|A ∪ B ∪ C| = |A| + |B| + |C| − |A∩B| − |A∩C| − |B∩C| + |A∩B∩C|

解题步骤：

  • 分别计算满足各个条件的数量
  • 减去两两交集（被重复计算的部分）
  • 加上三者交集（再次被减去的部分加回来）
💡 邓老师提示：容斥原理的关键是找准"重复计数"的部分。AMC 12 中经常出现"至少有一个性质"的问题，直接分类太复杂，用容斥原理两步搞定！

1.2 鸽巢原理（进阶）Pigeonhole Principle (Advanced)

基本形式：n + 1 只鸽子放入 n 个鸽巢，至少有一个鸽巢里有 ≥ 2 只鸽子。

Basic form: If n+1 objects are placed into n boxes, at least one box contains ≥ 2 objects.

加强形式：

📝 广义鸽巢原理 / Generalized Pigeonhole
若 N 个物体放入 k 个盒子，则至少有一个盒子含有 ≥ ⌈N/k⌉ 个物体
When distributing N objects into k boxes, some box has at least ⌈N/k⌉ objects.

AMC 12 常见应用：

  • 数论应用：从 1~2n 中任选 n+1 个数，必有两个数互质（因为相邻整数互质）
  • 组合应用：52 张牌中抽 5 张，必有至少两张同花色（5 > 4×1 + 1）
  • 抽屉原理：任何 n+1 个整数中必有两个之差是 n 的倍数
⚠️ 注意：鸽巢原理只能证明"存在性"，不能构造具体例子。考试时要分清：问"有多少种"用排列组合，问"是否存在"用鸽巢原理。

1.3 二项式定理 Binomial Theorem

📝 二项式定理 / Binomial Theorem
(a + b)ⁿ = Σ C(n, k) aⁿ⁻ᵏ bᵏ = C(n,0)aⁿ + C(n,1)aⁿ⁻¹b + ... + C(n,n)bⁿ
The coefficients C(n, k) = n!/(k!(n−k)!) appear in Pascal's Triangle.

重要推论：

  • 求和： C(n,0) + C(n,1) + ... + C(n,n) = 2ⁿ
  • 交错和： C(n,0) − C(n,1) + C(n,2) − ... + (−1)ⁿC(n,n) = 0 （当 n ≥ 1）
  • 对称性： C(n, k) = C(n, n−k)
  • 单项系数： (a + b)ⁿ 展开式中第 k+1 项为 C(n,k)aⁿ⁻ᵏbᵏ（k 从 0 到 n）
💡 邓老师提示：二项式定理在 AMC 12 中有两大高频用法：① 直接展开求系数；② 与概率结合——二项分布的展开就是 (p + q)ⁿ = 1。
2
递推与生成函数 Recurrence Relations and Generating Functions
进阶高频

2.1 递推关系 Recurrence Relations

递推关系是用前若干项表达第 n 项的等式，是计数问题的强大工具。

📝 递推关系 / Recurrence Relation
aₙ = f(aₙ₋₁, aₙ₋₂, ..., a₁)
初始条件 + 递推式 → 求通项

解题方法：

  • 迭代法：逐步展开，寻找规律
  • 特征根法：形如 aₙ = paₙ₋₁ + qaₙ₋₂ 的线性递推，令 aₙ = rⁿ，解特征方程 r² = pr + q
  • 构造辅助序列：将非齐次递推转化为齐次递推求解
💡 邓老师提示：AMC 12 中，递推关系经常与"上楼梯"（每次走 1 或 2 步）、"骨牌覆盖"等问题结合。找到初始值和递推式是第一步！

2.2 常见递推模式 Common Recurrence Patterns

名称递推式封闭形式
斐波那契数列Fₙ = Fₙ₋₁ + Fₙ₋₂Fₙ = (φⁿ − (−φ)⁻ⁿ)/√5（φ = (1+√5)/2）
等比数列aₙ = r · aₙ₋₁aₙ = a₁ · rⁿ⁻¹
等差数列aₙ = aₙ₋₁ + daₙ = a₁ + (n−1)d
卡特兰数Cₙ = Σ Cₖ · Cₙ₋₁₋ₖCₙ = C(2n, n)/(n+1)

斐波那契数列性质：

  • F₁ = 1, F₂ = 1, F₃ = 2, F₄ = 3, F₅ = 5, F₆ = 8, F₇ = 13, F₈ = 21 ...
  • F₁ + F₂ + ... + Fₙ = Fₙ₊₂ − 1（前 n 项和）
  • Fₙ 整除 Fₘ 当且仅当 n 整除 m

卡特兰数 Cₙ 的典型应用：

  • 合法括号序列数量
  • 二叉树的不同形态数
  • 上楼梯（每次 1 或 2 步）的不同路径数（实际上楼梯 Fₙ₊₁）
  • 凸多边形的三角剖分数
⚠️ AMC 12 常考点：卡特兰数的递推式 Cₙ = ΣCₖ·Cₙ₋₁₋ₖ（k 从 0 到 n−1）以及封闭公式 Cₙ = (2n)!/(n!(n+1)!) 都要熟记！

2.3 生成函数入门 Introduction to Generating Functions

生成函数是将数列的每一项作为多项式系数的高手工具：

📝 普通生成函数 / Ordinary Generating Function (OGF)
G(x) = a₀ + a₁x + a₂x² + a₃x³ + ...
数列 {aₙ} 的生成函数是 G(x)，x 的指数对应项的位置

为什么有用？复杂计数问题中，乘积的系数往往对应组合数。

基本公式：

  • (1 − x)⁻¹ = 1 + x + x² + x³ + ... （等比数列 1, 1, 1, ... 的生成函数）
  • (1 − x)⁻² = 1 + 2x + 3x² + 4x³ + ... （等差数列 1, 2, 3, ... 的生成函数）
  • (1 + x)ⁿ = Σ C(n, k)xᵏ （二项式定理）
💡 邓老师提示：AMC 12 中生成函数主要用于：① 证明组合恒等式；② 求解递推关系的封闭形式。记住几个基本展开式，能让你快速识别生成函数的结构。
3
组合恒等式 Combinatorial Identities
高频技巧性

3.1 Pascal恒等式与Vandermonde恒等式 Pascal's and Vandermonde's Identities

📝 Pascal 恒等式 / Pascal's Identity
C(n, k) = C(n−1, k−1) + C(n−1, k)
Each entry in Pascal's Triangle equals the sum of the two entries above it.

Pascal 恒等式的组合意义：从 n 个元素中选 k 个，第 n 个元素要么被选中（对应 C(n−1, k−1)），要么不被选中（对应 C(n−1, k)）。

📝 Vandermonde 恒等式 / Vandermonde's Identity
Σ C(m, i) · C(n, k−i) = C(m+n, k)
从 m+n 个元素中选 k 个，等于先分两组再合并
Choosing k from m+n equals summing over how many are chosen from each group.

特殊推论：

  • 当 m = n, k = n 时：Σ C(n, i)² = C(2n, n)（中心二项式恒等式）
  • C(m+n, r) = Σ C(m, k) · C(n, r−k)（标准 Vandermonde）

3.2 双射方法 Bijection Method

双射方法的核心思想是：构造两个集合之间的一一对应，从而证明它们等势（元素个数相等）。

The bijection method shows two sets have the same size by constructing a one-to-one correspondence between them.

📝 双射原理 / Bijection Principle
若存在双射 f: A → B，则 |A| = |B|

经典双射例子：

  • 圆上弦与上山路径：n 个点间连弦的问题 ↔ 从 2n−1 中选 n−1 的问题
  • 反射原理：路径计数中，满足某种约束的路径数 = 总路径数 − 违反约束的路径数
  • 配偶法：将配对问题与组合计数建立一一对应
💡 邓老师提示：双射方法的关键是"换个角度看问题"。当正面分类计数很复杂时，尝试构造一个等价但更简单的问题。AMC 12 难题经常需要这种思维跳跃！

3.3 母函数方法 Generating Function Method

母函数（也称生成函数）利用多项式乘法来"编码"组合信息：

问题模式：从若干类物品中选取，限制选取个数，求方案数。

📝 母函数编码 / Generating Function Encoding
若有物品 A（可取 0~a 个）、物品 B（可取 0~b 个）...
则母函数为 (1 + x + x² + ... + xᵃ)(1 + x + x² + ... + xᵇ)...
xⁿ 的系数即为取 n 件物品的方案数

典型应用：

  • 有限制的整数分拆计数
  • 不同面额硬币的找零方案数
  • 多重集合的排列数
⚠️ 注意：AMC 12 中母函数方法主要用于证明恒等式和解较难的递推问题，不要过度复杂化。用生成函数展开时，关心的是"系数"，不是 x 的值！
4
例题精讲 Worked Examples
5 题含历年真题
📌 例题 1 容斥原理

1~100 的整数中，至少能被 2、3、5 之一整除的数有多少个？ How many integers from 1 to 100 are divisible by at least one of 2, 3, or 5?

解题思路：容斥原理
|2的倍数| = ⌊100/2⌋ = 50
|3的倍数| = ⌊100/3⌋ = 33
|5的倍数| = ⌊100/5⌋ = 20
|2∩3| = ⌊100/6⌋ = 16 |2∩5| = ⌊100/10⌋ = 10 |3∩5| = ⌊100/15⌋ = 6
|2∩3∩5| = ⌊100/30⌋ = 3
|A∪B∪C| = 50+33+20 − 16−10−6 + 3 = 74
|A∪B∪C| = 50+33+20 − 16−10−6 + 3 = 74.
📌 例题 2 递推关系

某上楼梯问题：每次只能走 1 步或 2 步，走上 n 级台阶共有多少种走法（用 Fₙ 表示）？若 F₃ = 3，则 F₅ 是多少？ Climbing stairs: 1 or 2 steps at a time. If F₃ = 3, what is F₅?

解题思路：斐波那契递推
F₁ = 1（直接走1步）
F₂ = 2（1+1 或 2）
F₃ = 3（1+1+1、1+2、2+1）→ 已知
F₄ = F₃ + F₂ = 3 + 2 = 5
F₅ = F₄ + F₃ = 5 + 3 = 8
F₁=1, F₂=2, F₃=3, F₄=5, F₅=8. This is the Fibonacci sequence shifted by one.
📌 例题 3 二项式定理

(x − 1)⁵ 的展开式中，x³ 的系数是多少？ What is the coefficient of x³ in the expansion of (x − 1)⁵?

解题思路：二项式定理
(x − 1)⁵ = Σ C(5, k)x⁵⁻ᵏ(−1)ᵏ
x³ 项对应 5−k = 3，即 k = 2
系数 = C(5, 2) × (−1)² = 10 × 1 = 10（正号）
注意：选 x 两次、−1 三次时指数不对；k=2 时为 C(5,2)=10，偶数次方 (−1)² = +1
k=2: C(5,2)·(−1)² = 10·(+1) = 10.
📌 例题 4 Vandermonde恒等式

求 Σ C(5, k) · C(7, 3−k) 的值（k 从 0 到 3）。 Evaluate Σ C(5, k) · C(7, 3−k) for k = 0 to 3.

解题思路：Vandermonde 恒等式
Σ C(5, k)·C(7, 3−k) = C(5+7, 3) = C(12, 3) = 220... 等等
展开验证：k=0: C(5,0)·C(7,3)=1×35=35
k=1: C(5,1)·C(7,2)=5×21=105
k=2: C(5,2)·C(7,1)=10×7=70
k=3: C(5,3)·C(7,0)=10×1=10
总和 = 35+105+70+10 = 165
Direct sum: 35+105+70+10 = 165. Note: Vandermonde gives C(12,3)=220, which is Σ C(5,i)C(7,3−i) for all i=0..3 — but C(7,−1)=0 when 3−i<0, so same result here.
📌 例题 5 鸽巢原理

在一个房间里有 5 个人，已知其中任何 4 人中至少有一对互相认识。证明：至少有 1 个人认识所有其他人，并求最少有多少人认识所有人。 In a room of 5 people, any 4 people contain at least one pair who know each other. Prove at least one person knows everyone, and find the minimum number of such people.

解题思路：反证法 + 鸽巢原理
假设无人认识所有人，则每人至少不认识 1 人（共至少 5 个"不认识"关系）。
考虑任意4人的集合：根据条件，必有一对互相认识。若每人都只认识1人，则4人中最多4条边，找不到认识对的概率很高。
实际上，用反证法：设 A 不认识 B。若有第三人 C 既不认识 A 也不认识 B，则 {B, C, D, E}（4人）中无人认识，矛盾。
所以 A 必然认识除了 B 之外的所有人，且每个人都有一个"唯一不认识的人"，形成配对关系。
由于奇数人数 5，必有一人（A）不认识的人数 < 4，即认识所有人。
With 5 people and the condition that every 4 contain a knowing pair, at least 1 person must know everyone. By the pigeonhole principle, the "unknown" relations pair up, leaving one person unpaired — they know everyone.
5
巩固练习 Practice Problems
6 题提交即判

第1题 用容斥原理求 1~200 中不能被 2、3、5 中任何一个整除的数有多少个。 Using inclusion-exclusion, how many numbers from 1 to 200 are NOT divisible by 2, 3, or 5?

第2题 斐波那契数列 Fₙ 满足 F₁=F₂=1，Fₙ=Fₙ₋₁+Fₙ₋₂，求 F₇。 Given Fibonacci F₁=F₂=1, Fₙ=Fₙ₋₁+Fₙ₋₂, find F₇.

第3题 (2x − 1)⁴ 展开式中 x² 的系数是多少？ What is the coefficient of x² in the expansion of (2x − 1)⁴?

第4题 卡特兰数 C₃ 等于多少？（Cₙ = C(2n,n)/(n+1)） What is the 3rd Catalan number? (Cₙ = C(2n,n)/(n+1))

第5题 用鸽巢原理判断：从 1, 2, 3, ..., 10 中任选 6 个数，是否必定有两个数之和为 10？选"是"或"否"。 Using pigeonhole: from {1,...,10}, picking 6 numbers — must there be two that sum to 10?

第6题 已知 Σ C(4,i)² = C(8,4)/2 = 35，验证 Vandermonde 恒等式：求 C(3,0)C(5,3)+C(3,1)C(5,2)+C(3,2)C(5,1)+C(3,3)C(5,0) 的值。 Verify Vandermonde: find C(3,0)C(5,3)+C(3,1)C(5,2)+C(3,2)C(5,1)+C(3,3)C(5,0).