Combinatorial Counting Methods and Applications | 组合计数方法及应用

📚 Combinatorial Counting Methods and Applications | 组合计数方法及应用

In mathematics, combinatorics is the art of systematic counting. Far from simple arithmetic, counting problems require a clear logical framework to avoid double-counting or omitting possibilities. This revision guide covers the essential combinatorial tools for A-Level mathematics, including permutations, combinations, and their practical applications in probability and the binomial theorem.

在数学中，组合数学是系统计数的艺术。计数远非简单的算术，它需要我们建立清晰的逻辑框架，以避免重复或遗漏。这篇复习指南涵盖 A-Level 数学中核心的组合计数方法，包括排列、组合，以及它们在概率和二项式定理中的实际应用。

1. The Fundamental Principles of Counting | 基本计数原理

The multiplication principle: if one task can be performed in m ways, and a second independent task can be performed in n ways, then performing both tasks in sequence gives m × n possible outcomes. This is also called the “and” rule, because we multiply when one event AND another must occur.

乘法原理：如果完成一项任务有 m 种方式，另一项独立任务有 n 种方式，则依次完成这两项任务共有 m × n 种可能结果。这也被称为“与”规则，因为当一个事件与另一个事件同时需要发生时，我们将方式数相乘。

The addition principle: if two events are mutually exclusive (they cannot both happen), and the first can occur in m ways while the second can occur in n ways, then the number of ways for either event to occur is m + n. This is the “or” rule.

加法原理：如果两个事件互斥（不能同时发生），第一个事件有 m 种发生方式，第二个事件有 n 种发生方式，则任一事件发生的方式总数为 m + n。这就是“或”规则。

For example, a restaurant offers 4 appetisers and 5 main courses. Choosing one appetiser and one main course gives 4 × 5 = 20 possible meals. If instead you may choose either an appetiser or a main course (but not both), the number of options is 4 + 5 = 9.

例如，一家餐厅提供 4 种前菜和 5 种主菜。选择一份前菜和一份主菜，共有 4 × 5 = 20 种可能的套餐。如果你只能选择前菜或主菜（不能同时选择），则选项数为 4 + 5 = 9。

2. Factorials and Permutations | 阶乘与排列

The factorial of a positive integer n, written as n!, is the product of all positive integers from 1 to n: n! = n × (n−1) × … × 2 × 1. By convention, 0! = 1. Factorials grow rapidly: 5! = 120, 6! = 720.

正整数 n 的阶乘写作 n!，表示从 1 到 n 所有正整数的乘积：n! = n × (n−1) × … × 2 × 1。按定义，0! = 1。阶乘增长很快：5! = 120，6! = 720。

A permutation is an ordered arrangement of objects. The number of ways to arrange r distinct objects chosen from n distinct objects is denoted nPr (or P(n,r)) and is given by:

排列是对物体的有序安排。从 n 个不同物体中选取 r 个进行有序排列的方法数记为 nPr（或 P(n,r)），其计算公式为：

nPr = n! / (n−r)!

For example, arranging 5 different books on a shelf: the first slot has 5 choices, the second 4, and so on, giving 5! = 120 arrangements. If you only want to select and arrange 3 of the 5 books, the number is 5P3 = 5! / 2! = 60.

例如，将 5 本不同的书摆上书架：第一个位置有 5 种选择，第二个位置有 4 种，依此类推，共 5! = 120 种排列。若只选取 5 本中的 3 本并排列，方法数为 5P3 = 5! / 2! = 60。

3. Combinations | 组合

A combination is a selection of objects where the order does not matter. The number of ways to choose r objects from n distinct objects is denoted nCr (or C(n,r) or \(\binom{n}{r}\)) and is calculated as:

组合是指不考虑顺序地选取物体。从 n 个不同物体中选取 r 个的方法数记为 nCr（或 C(n,r)、\(\binom{n}{r}\)），计算公式为：

nCr = n! / [r! (n−r)!]

Since a selection of r objects can be ordered in r! ways, every combination corresponds to r! different permutations, giving the relationship nCr = nPr / r!. For example, choosing 3 committee members from 10 candidates: 10C3 = 10! / (3! 7!) = 120.

因为 r 个被选出的物体可以按 r! 种顺序排列，所以每一个组合对应 r! 个不同的排列，得到关系式 nCr = nPr / r!。例如，从 10 位候选人中选出 3 人组成委员会：10C3 = 10! / (3! 7!) = 120。

4. Permutations with Restrictions | 有限制条件的排列

Many exam problems require arranging objects with extra conditions, such as certain items being together or separated.

许多考试题要求在有额外条件下排列物体，例如某些物体必须相邻或必须分开。

When certain items must be together, treat them as a single block. For example, arranging 5 people in a row where two specific people must sit together: treat the pair as one unit, giving 4 units to arrange (4!), then arrange the pair inside the block (2!), for a total of 4! × 2! = 48 arrangements.

当某些物体必须相邻时，把它们看作一个整体块。例如，5 个人排成一排，其中两人必须相邻：将这对人视为一个单元，于是 4 个单元进行排列（4!），再在块内排列这两个人（2!），总数为 4! × 2! = 48 种。

For “not together” restrictions, subtract the “together” arrangements from the total unrestricted arrangements. Suppose the two people must not sit together: total arrangements = 5! = 120, together = 48, so not together = 120 − 48 = 72.

对于“不能相邻”的限制，用无限制的排列总数减去“相邻”的情况。假设那两个人不能相邻：总排列数为 5! = 120，相邻为 48，因此不相邻为 120 − 48 = 72。

5. Permutations with Repeated Items | 含重复元素的排列

If a set contains identical objects, the number of distinct arrangements is reduced because swapping identical items does not create a new permutation. For n objects with p identical of one kind, q identical of another kind, and so on, the number of distinct permutations is:

如果集合中含有相同物体，则不同排列的数量会减少，因为交换相同的物体不会产生新的排列。对于 n 个物体，其中一类有 p 个相同，另一类有 q 个相同，依此类推，不同排列的数量为：

n! / (p! q! …)

For example, the letters of “STATISTICS” contain 10 letters with S repeated 3 times, T repeated 3 times, I repeated 2 times, and A and C unique. The number of distinct arrangements is 10! / (3! 3! 2!) = 50400.

例如，单词“STATISTICS”包含 10 个字母，其中 S 重复 3 次，T 重复 3 次，I 重复 2 次，A 和 C 各 1 次。不同排列数为 10! / (3! 3! 2!) = 50400。

This formula is essential when counting arrangements of words, multiset permutations, or arrangements of objects with identical copies.

这个公式在计算单词排列、多重集排列或含相同副本物体的排列时至关重要。

6. Combinations with Repetition | 可重复组合

Sometimes we allow repeated choices. For example, choosing 4 fruits from an unlimited supply of apples, bananas and oranges. The number of ways is given by the “stars and bars” method. If there are n identical items to distribute among r distinct groups, the number of ways is:

有时我们允许重复选择。例如，从无限供应的苹果、香蕉和橙子中选出 4 个水果。其方法数由“隔板法”给出。如果要将 n 个相同物品分配到 r 个不同组中，方法数为：

C(n+r−1, r−1)

Equivalently, the number of non-negative integer solutions to the equation x₁ + x₂ + … + xᵣ = n is C(n+r−1, r−1). For the fruit example, n = 4 and r = 3, so the number of ways is C(4+3−1, 3−1) = C(6,2) = 15.

等价地，方程 x₁ + x₂ + … + xᵣ = n 的非负整数解的数量为 C(n+r−1, r−1)。在水果例子中，n = 4，r = 3，因此方法数为 C(4+3−1, 3−1) = C(6,2) = 15。

This topic is an extension beyond the core A-Level syllabus for some boards, but it frequently appears in advanced problem-solving and STEP-style questions.

这个知识点是部分考试局 A-Level 核心大纲之外的扩展内容，但在高级解题和 STEP 风格问题中经常出现。

7. Binomial Coefficients and the Binomial Theorem | 二项式系数与二项式定理

Combinations form the coefficients in the binomial expansion. The binomial theorem states that for any positive integer n:

组合构成了二项式展开中的系数。二项式定理指出，对于任意正整数 n：

(a + b)ⁿ = Σₖ₌₀ⁿ C(n,k) aⁿ⁻ᵏ bᵏ

For example, (1 + x)⁴ = C(4,0) + C(4,1)x + C(4,2)x² + C(4,3)x³ + C(4,4)x⁴ = 1 + 4x + 6x² + 4x³ + x⁴. The coefficients 1, 4, 6, 4, 1 are precisely 4C0, 4C1, 4C2, 4C3, 4C4.

例如，(1 + x)⁴ = C(4,0) + C(4,1)x + C(4,2)x² + C(4,3)x³ + C(4,4)x⁴ = 1 + 4x + 6x² + 4x³ + x⁴。系数 1, 4, 6, 4, 1 恰好是 4C0, 4C1, 4C2, 4C3, 4C4。

The binomial coefficient C(n,k) can be interpreted as the number of ways to choose k occurrences of b from n factors in the expansion. This combinatorial interpretation underpins many probability calculations.

二项式系数 C(n,k) 可以理解为在展开式的 n 个因子中选取 k 个 b 的方式数。这种组合解释是许多概率计算的基础。

8. Pascal’s Triangle and Combinatorial Identities | 杨辉三角与组合恒等式

Pascal’s triangle is built by adding adjacent entries from the row above. It lists the binomial coefficients row by row, starting with n = 0 at the top.

杨辉三角通过将上一行相邻两项相加得到。它逐行列出二项式系数，从顶部的 n = 0 开始。

A key identity is Pascal’s rule:

一个重要恒等式是帕斯卡法则：

C(n,k) + C(n,k+1) = C(n+1,k+1)

For instance, C(4,2) + C(4,3) = 6 + 4 = 10 = C(5,3). This identity is useful for simplifying sums of combinations and for constructing the triangle.

例如，C(4,2) + C(4,3) = 6 + 4 = 10 = C(5,3)。该恒等式可用于简化组合数求和，也可用于构造杨辉三角。

Another helpful fact is symmetry: C(n,k) = C(n,n−k). Thus, choosing k objects is equivalent to choosing the n−k objects left out.

另一个有用的性质是对称性：C(n,k) = C(n,n−k)。因此，选取 k 个物体等同于选取余下的 n−k 个物体。

9. Applications in Probability | 在概率中的应用

Counting methods are central to classical probability. The probability of an event is the number of favourable outcomes divided by the total number of equally likely outcomes. Combinations and permutations give us the counts.

计数方法是经典概率的核心。事件的概率等于有利结果数除以所有等可能结果总数。排列与组合为我们提供了这些计数。

For example, the probability of drawing 2 red cards from a standard 52-card deck is:

例如，从一副 52 张的标准扑克牌中抽取 2 张红牌的概率为：

P = C(26,2) / C(52,2)

This equals (26 × 25 / 2) / (52 × 51 / 2) = 325 / 1326 ≈ 0.2451.

其值为 (26 × 25 / 2) / (52 × 51 / 2) = 325 / 1326 ≈ 0.2451。

In repeated independent trials, the binomial distribution gives the probability of exactly r successes in n trials: P(X = r) = C(n,r) pʳ (1−p)ⁿ⁻ʳ, where p is the probability of success on one trial. This formula directly uses the combination count of choosing which r trials succeed.

在重复独立试验中，二项分布给出 n 次试验中恰好 r 次成功的概率：P(X = r) = C(n,r) pʳ (1−p)ⁿ⁻ʳ，其中 p 是一次试验成功的概率。该公式直接使用了从 n 次试验中选择哪 r 次成功的组合计数。

10. Worked Examples and Exam Tips | 例题与考试技巧

Example: A committee of 3 is to be chosen from 6 men and 4 women. How many committees contain at least one woman?

例题：从 6 名男性和 4 名女性中选出 3 人组成委员会。其中至少包含 1 名女性的委员会有多少种？

Method 1: Subtract the all-male committee from total committees. Total = 10C3 = 120. All-male = 6C3 = 20. Therefore, at least one woman = 120 − 20 = 100.

方法一：用总委员会数减去全男性委员会数。总数 = 10C3 = 120。全男性 = 6C3 = 20。因此至少一名女性 = 120 − 20 = 100。

Method 2: Add the cases of exactly 1, 2, and 3 women: (4C1 × 6C2) + (4C2 × 6C1) + (4C3 × 6C0) = 4×15 + 6×6 + 4×1 = 60 + 36 + 4 = 100. Both methods agree.

方法二：将恰好 1 名、2 名、3 名女性的情况相加：(4C1 × 6C2) + (4C2 × 6C1) + (4C3 × 6C0) = 4×15 + 6×6 + 4×1 = 60 + 36 + 4 = 100。两种方法结果一致。

Exam tips: Always ask whether order matters. If it does, use permutations; if not, use combinations. For restrictions, count the complement when “at least” appears. Be careful with identical items. Write down the expression before evaluating to avoid arithmetic errors.

考试技巧：始终判断顺序是否重要。若顺序重要，用排列；若无所谓，用组合。遇到“至少”时，考虑用补集计数。小心重复元素。计算前先写出表达式，避免算术失误。

Published by TutorHao | Mathematics Revision Series | aleveler.com

更多咨询请联系16621398022（同微信）

Combinatorial Counting Methods and Applications | 组合计数方法及应用