🗺️ 知识地图

AIME 知识体系 › 组合与概率 › 🎲 组合数学 1 / 3

1组合数学 2概率与期望 3高级计数

🎲 组合数学

Combinatorics

组合数学是 AIME 中的重要内容，涉及排列、组合、二项式定理、容斥原理等多个概念。掌握这些理论，对于解决复杂的计数问题至关重要。

📖 3 章节 💡 4 道例题 🎯 难度：进阶 ⏱ 约30分钟

排列与组合 Permutations and Combinations

进阶高频

排列与组合是组合数学中的基础概念，涉及从有限集合中选取元素的不同方式。

Permutations and combinations are basic concepts in combinatorics, involving different ways of selecting elements from a finite set.

📝 排列与组合的定义 / Definitions of Permutations and Combinations

排列与组合的定义：

1. 排列：从 n 个不同元素中取出 r 个元素的排列数，记为 P(n, r) = n! / (n - r)!

2. 组合：从 n 个不同元素中取出 r 个元素的组合数，记为 C(n, r) = n! / [r! (n - r)!]

Definitions of permutations and combinations

排列与组合的区别：

排列：考虑顺序，不同的顺序算不同的排列
组合：不考虑顺序，不同的顺序算相同的组合

💡 提示： 排列与组合是组合数学中的基础概念，需要熟练掌握其计算方法。

例题 1 Example 1

📝 AIME 2021 I Problem 9 难度：中等

从 5 个不同的元素中取出 3 个元素的排列数是多少？ How many permutations are there when selecting 3 elements from 5 distinct elements?

解答：

排列数 P(5, 3) = 5! / (5 - 3)! = 5 × 4 × 3 = 60。

所以从 5 个不同的元素中取出 3 个元素的排列数是 60。

The number of permutations is P(5, 3) = 5! / (5 - 3)! = 5 × 4 × 3 = 60.

💡 关键思路： 直接应用排列数公式计算。

二项式定理与组合恒等式 Binomial Theorem and Combinatorial Identities

进阶必考

二项式定理与组合恒等式是组合数学中的重要内容，涉及二项式展开、组合恒等式的证明和应用。

Binomial theorem and combinatorial identities are important content in combinatorics, involving binomial expansion, proof and application of combinatorial identities.

📝 二项式定理 / Binomial Theorem

二项式定理：

(a + b)^n = Σ (from k=0 to n) C(n, k) a^(n - k) b^k

Binomial theorem

📝 常见组合恒等式 / Common Combinatorial Identities

常见组合恒等式：

1. C(n, k) = C(n, n - k)

2. C(n, k) = C(n - 1, k - 1) + C(n - 1, k)

3. Σ (from k=0 to n) C(n, k) = 2^n

4. Σ (from k=0 to n) (-1)^k C(n, k) = 0

Common combinatorial identities

⚠️ 注意： 二项式定理和组合恒等式是组合数学中的重要内容，需要熟练掌握。

例题 2 Example 2

📝 AIME 2020 II Problem 10 难度：中等

求 (x + y)^5 展开式中 x²y³ 的系数。 Find the coefficient of x²y³ in the expansion of (x + y)^5.

解答：

根据二项式定理，(x + y)^5 展开式中 x²y³ 的系数为 C(5, 3) = 10。

所以 x²y³ 的系数是 10。

According to the binomial theorem, the coefficient of x²y³ in the expansion of (x + y)^5 is C(5, 3) = 10.

💡 关键思路： 应用二项式定理直接计算系数。

容斥原理与鸽巢原理 Inclusion-Exclusion Principle and Pigeonhole Principle

困难选考

容斥原理与鸽巢原理是组合数学中的重要原理，涉及计数问题的解决方法。

Inclusion-exclusion principle and pigeonhole principle are important principles in combinatorics, involving methods for solving counting problems.

📝 容斥原理 / Inclusion-Exclusion Principle

容斥原理：

|A ∪ B| = |A| + |B| - |A ∩ B|

|A ∪ B ∪ C| = |A| + |B| + |C| - |A ∩ B| - |A ∩ C| - |B ∩ C| + |A ∩ B ∩ C|

Inclusion-exclusion principle

📝 鸽巢原理 / Pigeonhole Principle

鸽巢原理：

如果有 n 个鸽子放进 m 个鸽巢，且 n > m，那么至少有一个鸽巢中有至少两个鸽子。

Pigeonhole principle

容斥原理的应用：

计算集合的并集大小
解决排列组合中的限制问题
计算概率

鸽巢原理的应用：

证明存在性问题
解决组合优化问题
分析算法复杂度

💡 提示： 容斥原理和鸽巢原理是解决组合数学问题的有力工具，需要熟练掌握其应用方法。

例题 3 Example 3

📝 AIME 2019 I Problem 10 难度：困难

从 1 到 100 的整数中，能被 2 或 3 整除的数有多少个？ How many integers from 1 to 100 are divisible by 2 or 3?

解答：

使用容斥原理计算：

能被 2 整除的数的个数：⌊100/2⌋ = 50

能被 3 整除的数的个数：⌊100/3⌋ = 33

能被 2 和 3 同时整除的数的个数：⌊100/6⌋ = 16

所以能被 2 或 3 整除的数的个数：50 + 33 - 16 = 67

Using the inclusion-exclusion principle: Number of integers divisible by 2: ⌊100/2⌋ = 50, number divisible by 3: ⌊100/3⌋ = 33, number divisible by both: ⌊100/6⌋ = 16. Thus the total is 50 + 33 - 16 = 67.

💡 关键思路： 应用容斥原理计算集合的并集大小。

综合练习

练习题 1：从 6 个不同的元素中取出 2 个元素的组合数是多少？ How many combinations are there when selecting 2 elements from 6 distinct elements?

✅ 回答正确！

❌ 回答错误，请再试一次。

练习题 2：求 (x + y)^4 展开式中 x³y 的系数。 Find the coefficient of x³y in the expansion of (x + y)^4.

✅ 回答正确！

❌ 回答错误，请再试一次。

练习题 3：从 1 到 50 的整数中，能被 3 或 5 整除的数有多少个？ How many integers from 1 to 50 are divisible by 3 or 5?

✅ 回答正确！

❌ 回答错误，请再试一次。