Permutations and combinations

排列与组合（课程大纲主题 11）

欢迎来到附加数学（Additional Mathematics）中最实用且最迷人的章节之一！排列与组合的核心就是“如何计算可能性”。无论是设置安全密码、计算彩票中奖率，还是在书架上排列书籍，这些数学原理都能准确告诉你有多少种实现的方式。

如果起初觉得有些复杂，请不要担心。我们将把这些复杂的计数方法拆解为两个简单的类别：顺序很重要的情形（排列，Permutations）和顺序无关的情形（组合，Combinations）。让我们开始计数之旅吧！

1. 计数基础：阶乘与基本原理

1.1 计数基本原理（乘法原理）

这是最基础的法则。如果你有多个独立的步骤或选择，只需将每个步骤的选项数量相乘，即可得到总的可能性数量。

• 法则： 如果事件 A 有 \(m\) 种实现方式，事件 B 有 \(n\) 种实现方式，那么 A 和 B 同时发生共有 \(m \times n\) 种方式。

示例： 设想搭配一套衣服。如果你有 3 件不同的衬衫和 4 条不同的裤子，那么你总共可以搭配出 \(3 \times 4 = 12\) 种不同的服装。

1.2 阶乘符号 (\(n!\))

正整数 \(n\) 的阶乘记作 \(n!\)，是指所有小于或等于 \(n\) 的正整数的乘积。当我们对一组物品进行全排列（全部取出排列）时，会用到阶乘。

• 定义： \(n! = n \times (n-1) \times (n-2) \times \dots \times 2 \times 1\)

示例： 4 本不同的书在书架上排列，有多少种方式？

\(4! = 4 \times 3 \times 2 \times 1 = 24\) 种

特殊情况（必记）：
零的阶乘定义为 1：\(0! = 1\)。这看起来可能很奇怪，但正是这个定义让排列和组合的公式能够完美运作。

关键总结： 计算可能性始于乘法（基本计数原理），而阶乘则是排列所有物品时的快捷方式。

---

2. 排列：有序排列（顺序很重要）

2.1 什么是排列？

排列（Permutation）是指物品的排列方式，其中顺序或位置至关重要。

• 关键词： 排列、顺序。
• 类比： 想象一场赛跑（第 1、2、3 名是同一组人的不同排列方式）或者一个数字密码（123 与 321 是完全不同的密码）。

当我们从 \(n\) 个物品中取出 \(r\) 个物品，且这 \(r\) 个物品的排列顺序会产生不同结果时，我们使用排列公式。

2.2 排列公式 (\(^nP_r\))

从 \(n\) 个不同物品中取出 \(r\) 个进行排列的方案数公式为：

\(^{n}P_{r} = P(n, r) = \frac{n!}{(n-r)!}\)

其中：
\(n\) 是可供选择的总物品数。
\(r\) 是被选择并排列的物品数。

2.3 逐步示例：排列

题目： 一个俱乐部有 8 名成员，选出主席、副主席和财务主管，有多少种方式？

第一步：判断顺序是否重要。 是的，担任主席与担任副主席是不同的身份。这是一个排列问题。
第二步：确定 \(n\) 和 \(r\)。 总成员数 \(n=8\)，需填补职位数 \(r=3\)。
第三步：代入公式。

\(^{8}P_{3} = \frac{8!}{(8-3)!} = \frac{8!}{5!}\) \(^{8}P_{3} = \frac{8 \times 7 \times 6 \times 5!}{5!} = 8 \times 7 \times 6 = 336\)
填补这三个职位共有 336 种方式。

---

3. 组合：选组（顺序不重要）

3.1 什么是组合？

组合（Combination）是指从物品中进行挑选，其中顺序无关紧要。

• 关键词： 挑选、小组、团队。
• 类比： 想象选择 3 种口味的冰淇淋（巧克力、草莓、香草与香草、草莓、巧克力属于同一种组合）。

当我们从 \(n\) 个物品中取出 \(r\) 个，且只关心形成了哪个组，而不关心它们被选出的先后顺序时，我们使用组合公式。

3.2 组合公式 (\(^nC_r\))

从 \(n\) 个不同物品中取出 \(r\) 个进行组合的方案数公式为：

\(^{n}C_{r} = C(n, r) = \binom{n}{r} = \frac{n!}{r!(n-r)!}\)

请注意这个公式与排列公式的联系：
\(\text{组合} = \frac{\text{排列}}{r!}\)
之所以要除以 \(r!\)，是因为对于每组选出的 \(r\) 个物品，它们内部有 \(r!\) 种排列方式，而在组合中，我们只把它们视为“同一组”，所以要剔除这些重复计数。

3.3 逐步示例：组合

题目： 一个俱乐部有 8 名成员，选出 3 个人的委员会，有多少种方式？

第一步：判断顺序是否重要。 不是，选出 Alice、Bob 和 Carol 组成委员会，与选出 Bob、Carol 和 Alice 是一样的。这是一个组合问题。
第二步：确定 \(n\) 和 \(r\)。 总成员数 \(n=8\)，需选人数 \(r=3\)。
第三步：代入公式。

\(^{8}C_{3} = \frac{8!}{3!(8-3)!} = \frac{8!}{3!5!}\) \(^{8}C_{3} = \frac{8 \times 7 \times 6 \times 5!}{3 \times 2 \times 1 \times 5!} = \frac{8 \times 7 \times 6}{6} = 56\)
选择委员会共有 56 种方式。

---

4. 解题技巧：区分排列与组合

本章（11.1）最大的挑战就是辨别题目究竟需要使用排列还是组合。

4.1 “顺序检查法”

使用这个简单的测试：

设想你已经选好了那 \(r\) 个物品。如果你改变它们的顺序，结果会发生变化吗？

• 如果“是”，结果不同： 使用排列（顺序很重要）。
  例子：颁发金、银、铜牌。改变排列顺序，获奖者拿到的奖牌就不同了。
• 如果“否”，结果相同： 使用组合（挑选很重要）。
  例子：选出 3 个彩票号码。选出 1、5、10 与选出 10、5、1 是同一组号码。

4.2 涉及多步骤的复杂问题

有时，题目既需要使用乘法原理，又需要进行多次排列或组合计算。

分步挑选示例（两次运用组合）：

一个班级有 10 个男生和 8 个女生。挑选 3 个男生和 2 个女生组成团队，有多少种方式？

第一步：挑选男生。 顺序不重要（这是团队成员）。
\(n_B = 10\), \(r_B = 3\)。
男生选择方案：

\(^{10}C_{3} = \frac{10!}{3!7!} = 120\)

第二步：挑选女生。 顺序不重要。
\(n_G = 8\), \(r_G = 2\)。
女生选择方案：

\(^{8}C_{2} = \frac{8!}{2!6!} = 28\)

第三步：结合结果。 使用基本计数原理（将独立事件的选择数相乘）。
总方案数 = 男生选择方案 \(\times\) 女生选择方案
总方案数 = \(120 \times 28 = 3360\)

4.3 常见误区

• 公式混淆： 永远检查一下是否应该除以 \(r!\)（组合）还是不除（排列）。
• 搞混 \(n\) 和 \(r\)： \(n\) 永远是较大的那个数字（总数），\(r\) 是较小的那个数字（要取出的个数）。
• 忽略“与”或“或”的关系： 如果选择是同时发生的（“与”），你需要相乘（这是基本计数原理）。

4.4 课程安全检查（无需担心的问题）

0606 课程大纲（11.3）明确排除了某些复杂的题型。你不必担心以下情况：

• 重复对象的排列： 例如，排列单词 MISSISSIPPI 中的字母（其中包含相同的字母）。你遇到的所有问题都将涉及不同（唯一）的物品。
• 环形排列： 不需要掌握圆桌排座等公式。
• 单步骤中混合使用 P 和 C： 如果你使用了排列，通常不会在同一个选择步骤中用到组合，反之亦然。（但是，像上面 3 男 2 女这种分步计算后再相乘的题目是要求掌握的）。

你知道吗？ 阶乘增长的速度惊人！\(69!\) 是普通计算器在超出显示位前所能处理的最大阶乘。这就是为什么这些方法在计算大规模现实系统中的概率时至关重要。

关键总结： 动笔前先问一句：“顺序有区别吗？”如果有，用排列；如果没有，用组合。

---

排列与组合学习笔记结束