1. 排列与组合 · Mastering AMC 10/12

1.10%

阶乘

在本节中，你将能够 快速计算阶乘，并理解为什么 n! 是把 n 个不同的东西排成一排的方法数。

5 本不同的书立在书架上，有多少种放法？一个位置一个位置地填，看着选择越来越少。

第一个位置有 5 种选择，下一个有 4 种，一直减到 1。像 $5 \times 4 \times 3 \times 2 \times 1$ 这样的“倒数连乘” 太常见了，于是它有了自己的记号： $5!$ ，读作“5 的阶乘”。

注意：阶乘相除通常能约成一个很短的乘积：

10!/8! = 10 \times 9

。

动手探索先玩，再学公式

书4

待放区：点击书，把它放到下一个位置上

排好的顺序

4

3

2

1

每个位置下面的数，就是放它时有几种选择。

先放第一个书……

记住这些：0! 到 10!

为什么 0! = 1？什么都不排，恰好只有一种排法：什么也不做。这样 n! = n × (n − 1)! 在 n = 1 时也成立：1! = 1 × 0!。

试一试： 把 4 本书一本一本放上去。每个位置有几种选择？为什么每次少 1？
试一试： 设成 5 本书。放之前先预测有多少种顺序，再验证。
试一试： 打开阶乘表。7! 是 6! 的多少倍？10! 和 9! 比呢？

认识概念

定义 1.1.1 · 阶乘

一个正整数的阶乘，是所有小于或等于它的正整数的乘积。也就是说，

n! = n \times (n-1) \times (n-2) \times \cdots \times 1.

过关检测（第 1.1 节）

3 题中答对 2 题即可掌握本节。每题只有一次机会，没有提示。

1.20%

排列基础

在本节中，你将能够 数出排成一排、围成一圈，以及从 n 个中取 k 个排列的方法数。

让 5 个朋友先坐成一排，再围着一张圆桌坐。为什么圆桌的坐法更少？

排成一排，有 $5! = 120$ 种坐法。在圆桌旁，让每个人都向左挪一个座位，每个人的邻居都没变，所以这些坐法不是新的。窍门是：先把一个人固定在顶部，再排其他人。

如果只填其中一部分位置，倒数连乘就提前停下。这就是下面的排列公式。

动手探索先玩，再学公式

试一试： 按 5 次“旋转 ↻”。有没有人换了新邻居？那么有多少种排成一排的顺序会得到同一张桌子的坐法？
试一试： 打开“把 Alex 固定在顶部”。还剩几个人需要排？这和 (5 − 1)! = 24 一致吗？
试一试： 打开“镜像算作同一种”，然后按“镜像翻转 ⇋”。为什么要除以 2？

认识概念

定义 1.2.1 · 排列

排列是把一个集合中的物体排好的一种方式，其中物体的顺序是有区别的。

定理 1.2.2 · 物体的排序数

把 $n$ 个物体排成一排，方法数是 $n!$ 。

把 $n$ 个物体排成一圈，如果同一种排法旋转后不算不同，方法数是 $(n-1)!$ 。

把 $n$ 个物体排成一圈，如果同一种排法的旋转和镜像都不算不同，方法数是

\frac{(n-1)!}{2}.

定理 1.2.4 · 排列公式

从总共 $n$ 个物体中取出 $k$ 个排好，方法数是

{}^{n}P_{k} = \frac{n!}{(n-k)!}.

从 7 个人中选 3 位干部：7 × 6 × 5 = 7!/4!。

过关检测（第 1.2 节）

3 题中答对 2 题即可掌握本节。每题只有一次机会，没有提示。

1.30%

有限制的排列

在本节中，你将能够 先填限制最多的空位，数出带规则的排法。

首位是奇数、后面三位都是偶数、并且没有重复数字的 4 位数有多少个？

规则让有些空位比别的更挑剔。先填最挑剔的空位。这样其他每个空位的选择数都是固定的，不管你前面选了什么，直接相乘就行。

注意：如果某个空位的选择数“取决于”前面的选择，就换一个填空位的顺序。

动手探索先玩，再学公式

位数4

第 1 位

5

种选择

第 2 位

5

种选择

第 3 位

4

种选择

第 4 位

3

种选择

5 × 5 × 4 × 3 = 300

电脑验证（逐个列举）： 300例如 3426

试一试： 先填奇数空位，再填偶数空位。奇数数字占用了偶数的选择吗？
试一试： 现在关掉首位数字的规则。为什么各空位的选择数开始互相影响？
试一试： 下面的例 1.3：哪个空位限制最多？先填它，看看其他空位的选择数如何稳定下来。

看例题先预测，再揭晓

例 1.1

首位是奇数、其余 3 位都是偶数，并且各位数字互不相同的 4 位数有多少个？

1
首位有几种选择？

先预测一下：
你的预测

例 1.2

Omega Learn

Gauss、Pauli、Einstein、Newton、Edison 和 Faraday 围坐在一张圆桌旁。Einstein、Newton 和 Faraday 互相敌对，所以他们拒绝彼此相邻而坐。在这个条件下，如果旋转不算不同的坐法，这 6 位物理学家有多少种坐法？

1
没有这个条件时，有多少种坐法？

先预测一下：
你的预测

例 1.3

Omega Learn

各位数字互不相同，前 2 位数字都不小于 6，后 2 位数字都不大于 5，并且第 3 位数字是 7 的非零倍数的 6 位数有多少个？

位数6

第 1 位

4

种选择

第 2 位

3

种选择

第 3 位

?

要看情况（0–1）

第 4 位

7

种选择

第 5 位

?

要看情况（5–6）

第 6 位

?

要看情况（4–5）

要看情况！有些位的选择数会随前面的选择变化。

电脑验证（逐个列举）： ?例如 867924

注意：按这个顺序填的时候，某些位的选择数会随你前面的选择而变化。试着先填限制最多的那一位。

1
哪一位限制最多？它有几种选择？

先预测一下：
你的预测

在 YouTube 上打开

例 1.4

Peter 正在为 AMC 12 收拾笔袋。他要按某种顺序装入 3 支互不相同的铅笔、2 块互不相同的橡皮和 2 支互不相同的记号笔。但是，如果袋中某种物品的数量已经比另外某种物品多，他就不会再放这种物品。（例如：如果袋中铅笔已经比记号笔多，或者铅笔已经比橡皮多，Peter 就不会再放铅笔。）Peter 把物品放进笔袋，共有多少种不同的顺序？

1
Peter 只能放袋中数量并列最少的那一类。他放的前 3 件必须是什么？

先预测一下：
点击一个选项，或输入它的字母（A–E）。

在 YouTube 上打开

竞赛角真实竞赛题

习题 1.7.3

AMC 10

某州的车牌由 4 个数字（不一定互不相同）和 2 个字母（也不一定互不相同）组成。这六个字符可以按任意顺序出现，但两个字母必须相邻。可能的不同车牌有多少种？

习题 1.7.6

AMC 10

一个由小方格组成的 $3 \times 3$ 方格中，每个小方格涂成红、白、蓝、绿四色之一，使得每个 $2 \times 2$ 的正方形中四种颜色各有一个。下方右图给出了一种这样的涂法。共有多少种不同的涂法？

过关检测（第 1.3 节）

3 题中答对 2 题即可掌握本节。每题只有一次机会，没有提示。

1.40%

字母重排

在本节中，你将能够 数出含重复字母的单词、捆绑在一起的字母块的重排数，以及单词在字典序中的位置。

COMPUTER 有 8 个互不相同的字母，MISSISSIPPI 却不是。字母重复时，会有什么变化？

交换两个相同的字母，得到的还是同一个单词。所以如果把每个字母都当成不同的来数，每个单词就被数了太多次：它的重复字母有多少种交换方式，就被多数了多少次。把这些重复除掉。

同样的窍门适用于任何有重复的东西：瓷砖、积木，甚至是射手射击的那几列靶子。

动手探索先玩，再学公式

720 种带编号的排法

6! = 720

这 12 种带编号的排法拼出的都是同一个单词（只显示前 6 种）：

BA₁N₁A₂N₂A₃
BA₁N₂A₂N₁A₃
BA₁N₁A₃N₂A₂
BA₁N₂A₃N₁A₂
BA₂N₁A₁N₂A₃
BA₂N₂A₁N₁A₃

3 个 A 互换位置有 3! = 6 种方法；2 个 N 互换位置有 2! = 2 种方法。关掉编号，它们就合并成同一个单词。

小技巧：先点（或按回车选中）一张卡片，再点另一张，就能交换它们。

试一试： 打开“假装重复字母各不相同”，把 A 标成 1、2、3。有多少个带标号的单词拼出的都是同一个 BANANA？
试一试： 把标号关掉。刚才发生了哪一次除法？
试一试： 输入 MISSISSIPPI。按“使用”之前，先用公式预测排法数。

认识概念

定理 1.4.1 · 字母重排

一个单词的字母重排方法数是

\frac{n!}{d_1! \times d_2! \times d_3! \times \cdots}

其中 $n$ 是字母个数， $d_1, d_2, d_3, \ldots$ 是单词中每个出现不止一次的字母各自出现的次数。

注 1.4.2

这不只适用于单词！排列有重复的物体（或任何东西）时，方法数也由同一个公式给出。在例 1.6 中，“字母”就是各列的名字。

注 1.4.3

别忘了：按字典序排在 USAMO 之前的单词个数还要再加 1！

看例题先预测，再揭晓

例 1.5

把 COMPUTER 的字母重新排列，要求 C、O、M、P 挨在一起（顺序不一定不变），有多少种排法？

1
C、O、M、P 必须挨在一起，这个条件该怎么处理？

例 1.6

AIME

在一场射击比赛中，8 个泥靶挂成三列：两列各 3 个，一列 2 个。射手要按以下规则击碎所有泥靶：

射手先选一列，从这一列中击碎一个靶。
然后射手必须击碎所选列中剩下的最低的那个靶。

如果遵守这些规则，击碎这 8 个靶共有多少种不同的顺序？

1
在同一列里，射手能选先打哪个靶吗？

先预测一下：
点击一个选项，或输入它的字母（A–E）。

在 YouTube 上打开

例 1.7

AMC 10

用字母 A、M、O、S、U 可以组成五个字母的“单词”。如果把这些“单词”按字典序排列，那么“单词” USAMO 排在第几位？

(A) $112$
(B) $113$
(C) $114$
(D) $115$
(E) $116$

1
按字母顺序，这些字母是 A、M、O、S、U。哪些单词因为首字母就排在 USAMO 前面？有多少个？

先预测一下：
你的预测

在 YouTube 上打开

竞赛角真实竞赛题

习题 1.7.1

AMC 10

1 块棕色瓷砖、1 块紫色瓷砖、2 块绿色瓷砖和 3 块黄色瓷砖从左到右排成一排，可区分的排法有多少种？（同色的瓷砖不可区分。）

习题 1.7.2

AMC 10

一个孩子用形状相同、颜色不同的方块搭塔。用 2 个红色方块、3 个蓝色方块和 4 个绿色方块，他能搭出多少种高为 8 个方块的不同的塔？（会剩下一个方块不用。）

习题 1.7.11

AMC 12挑战

由 5 个 A、5 个 B 和 5 个 C 组成的 15 个字母的排列中，前 5 个字母中没有 A、中间 5 个字母中没有 B、最后 5 个字母中没有 C 的有多少种？

过关检测（第 1.4 节）

3 题中答对 2 题即可掌握本节。每题只有一次机会，没有提示。

1.50%

组合

在本节中，你将能够 数出不计顺序的选法，并把几次选择组合起来。

一家公司要从 6 位申请人中选 2 位经理。“先 Ana 后 Ben”和“先 Ben 后 Ana”是不同的选法吗？

不是：两者选出的是同一对经理。不计顺序时，每一组在有序选法中都出现 $k!$ 次，所以要除以 $k!$ 。这就是“ $n$ 选 $k$ ”。

动手探索先玩，再学公式

试一试： 数一数选 2 位经理的有序选法。然后按“不计顺序”。每一堆有多大？
试一试： 设 k = 3。现在有多少种有序选法合并成一组？为什么是 3!？
试一试： 在定理下方的杨辉三角里找到 C(8, 3) 和 C(8, 5)。它们为什么相等？

认识概念

定义 1.5.1 · 组合

组合是从一组物体中选出一些的一种方式，其中选取的顺序没有区别。

注 1.5.2

通常，“排列”“顺序有关”等说法表示排列，而“选”“挑选”“不计顺序”等说法表示组合。

定理 1.5.3 · 组合公式

从总共 $n$ 个物体中选出 $k$ 个，方法数是

\binom{n}{k} = \frac{n!}{k!\,(n-k)!} = \frac{n(n-1)\cdots(n-k+1)}{k!}.

通常读作“ $n$ 选 $k$ ”。

杨辉三角：第 8 行是 C(8, 0) 到 C(8, 8)。注意：C(8, 3) 和 C(8, 5) 左右对称。

看例题先预测，再揭晓

例 1.8

Omega Learn

有 6 位有经验的申请人和 7 位没有经验的申请人来应聘一份工作。从有经验的申请人中选出 2 位经理。再从所有没被选为经理的其他申请人（包括有经验的和没有经验的）中选出另外 4 名员工。共有多少种选法？

1
首先，选 2 位经理有多少种方法？

先预测一下：
你的预测

例 1.9

Omega Learn

你有 12 根互不相同的能量棒，要分给 3 个人：Alice、Betty 和 Chase。Alice 需要 3 根，Betty 需要 4 根，Chase 需要 5 根。满足他们的需要，分这 12 根能量棒共有多少种方法？

1
先从 Alice 开始。选她的 3 根有多少种方法？

先预测一下：
你的预测

在 YouTube 上打开

例 1.10

EMCC

把 4 个球放进一个 $4 \times 6$ 的方格中，使得每一列和每一行都至多有一个球，有多少种放法？（旋转和镜像都算作不同的放法。）

1
方格有 4 行。有几行会放球？

先预测一下：
你的预测

在 YouTube 上打开

例 1.11

Robert 有 4 枚不可区分的金币和 4 枚不可区分的银币。每枚硬币的一面刻有一张脸，另一面没有。他想把这 8 枚硬币在桌上叠成一摞，使得任意两枚相邻的硬币都不是脸对脸。求这 8 枚硬币可区分的叠法共有多少种。

1
先处理颜色。4 枚金币和 4 枚银币有多少种排法？

先预测一下：
你的预测

自己做

习题 1.7.12（补充题）

Omega Learn

12 名宇航员报名参加探索火星的任务。将从地球发射 2 枚不同的火箭：一枚载 3 人，另一枚载 4 人。这 12 名宇航员中有 4 名经验非常丰富，所以他们必须登上其中一枚火箭。把宇航员安排进火箭共有多少种方法？

竞赛角真实竞赛题

习题 1.7.4

AMC 10

一次聚会有 30 个人，其中 20 个人彼此都认识，另外 10 个人谁都不认识。互相认识的人拥抱，互不认识的人握手。这群人之间共握手多少次？

习题 1.7.8

AMC 10

从 $\{1, 2, 3, 4, 5, 6\}$ 中不放回地选出 $A, B, C$ 和 $D$ 的值（即任意两个字母的值都不同）。有多少种这样的选法，使得两条曲线 $y = Ax^2 + B$ 和 $y = Cx^2 + D$ 相交？（两条曲线的先后顺序无关紧要；例如，选 $A = 3, B = 2, C = 4, D = 1$ 和选 $A = 4, B = 1, C = 3, D = 2$ 算作同一种。）

习题 1.7.9

AIME

一个游戏使用一副 $n$ 张互不相同的牌，其中 $n$ 是整数，且 $n \geq 6$ 。从这副牌中可能抽出的 6 张牌的组数，是可能抽出的 3 张牌的组数的 6 倍。求 $n$ 。

习题 1.7.10

AMC 10A

把 1 到 14 这些数分成 7 对，使得每一对中较大的数至少是较小的数的 2 倍，共有多少种分法？

过关检测（第 1.5 节）

3 题中答对 2 题即可掌握本节。每题只有一次机会，没有提示。

1.60%

子集

在本节中，你将能够 用“每个元素 2 种选择”数子集，并巧妙地把子集两两配对。

一家汉堡店提供 8 种配料，你可以任意选一些。每种配料都是一个开关：开或关。

集合中的每个元素要么在你的子集里，要么不在。每个元素 2 种选择，所以一共有 $2 \times 2 \times \cdots \times 2$ 种。这个数包括空集，也就是所有开关都关着的情况。

动手探索先玩，再学公式

试一试： 把所有开关都关掉。这是一个子集吗？它算不算一个什么都不加的汉堡？
试一试： 关掉“计入空集”。个数有什么变化？为什么只少了 1？
试一试： 用“元素个数”的加号再加一个元素。为什么子集个数翻倍了？

认识概念

定理 1.6.1 · 子集的个数

一个有 $n$ 个元素的集合，子集个数是 $2^n$ 。

看例题先预测，再揭晓

例 1.12

AMC 10

从集合 $S = \{a, b, c, d, e\}$ 中选出两个子集，使它们的并集是 $S$ ，交集恰好含两个元素。如果选这两个子集的先后顺序无关紧要，共有多少种选法？

元素个数5

点一个元素，把它移到下一个区域。可选区域：只在 A、只在 B、A、B 都在。

A: {a, b, c}
B: {a, b, d, e}
A ∪ B: {a, b, c, d, e}
A ∩ B: {a, b}

A ∩ B 中恰好有 2 个元素：这一对符合要求。

先自己算出个数；分步讲解会揭晓答案。

1
把这两个子集叫作 $A$ 和 $B$ 。因为 $A \cup B = S$ ，每个元素有几个去处？

先预测一下：
你的预测

在 YouTube 上打开

例 1.13

AIME

对 $\{1, 2, 3, \ldots, n\}$ 及其每个非空子集，按如下方式定义唯一的交错和：把子集中的数按从大到小排列，然后从最大的数开始，交替地加上、减去后面的数。例如， $\{1, 2, 3, 6, 9\}$ 的交错和是 $9 - 6 + 3 - 2 + 1 = 5$ ，而 $\{5\}$ 的交错和就是 $5$ 。求 $n = 7$ 时所有这些交错和的总和。

元素个数3

你的子集 S

{1, 2}

2 − 1 = 1

搭档：S 加入或去掉 3

{1, 2, 3}

3 − 2 + 1 = 2

注意：这一对的和是 1 + 2 = 3。在最前面加上 3，其余每个符号都反过来，所以除了 3 全部抵消。

全部 4 对
不含 3 的 S	交错和	含 3 的 S	交错和	一对之和
∅	0	{3}	3	3
{1}	1	{1, 3}	2	3
{2}	2	{2, 3}	1	3
{1, 2}	1	{1, 2, 3}	2	3

1
可以全部手算再相加，但有更巧的办法。 $n = 3$ 时，所有交错和的总和是多少？

先预测一下：
你的预测

竞赛角真实竞赛题

习题 1.7.7

AMC 10

Henry's Hamburger Haven 的汉堡可以加以下配料：番茄酱、芥末酱、蛋黄酱、番茄、生菜、酸黄瓜、奶酪和洋葱。顾客可以选一块、两块或三块肉饼，以及任意一组配料。共可以点多少种不同的汉堡？

过关检测（第 1.6 节）

3 题中答对 2 题即可掌握本节。每题只有一次机会，没有提示。

1.7

练习题

在本节中，你将能够 在竞赛题中综合运用本章的所有工具。

该把所有方法混在一起用了。这些题会用到阶乘、组合数公式、字母重排和子集，有时一题全用上。每道题都有三条提示，卡住时可以看。

想在一页上看到本章所有题目？打开习题集。

竞赛角真实竞赛题

习题 1.7.5

AMC 10/12

在一次乒乓球比赛中，每位选手都和其他每位选手恰好比赛一次。虽然右手选手的人数是左手选手的两倍，但左手选手赢的场数比右手选手赢的场数多 $40\%$ 。（没有平局，也没有左右手都能用的选手。）一共进行了多少场比赛？

习题 1.7.13（补充题）

AIME

平面上给定 10 个点，其中任意三点不共线。随机选出连接这些点中某两点的 4 条不同线段，每条这样的线段被选中的可能性相同。其中某三条线段构成一个以给定的十个点中的点为顶点的三角形的概率是 $m/n$ ，其中 $m$ 和 $n$ 是互质的正整数。求 $m + n$ 。

习题 1.7.14（补充题）

AIME

从集合 $\{1, 2, 3, \ldots, 1000\}$ 中随机且不放回地抽出三个数 $a_1, a_2, a_3$ 。然后从剩下的 997 个数中随机且不放回地抽出另外三个数 $b_1, b_2, b_3$ 。设 $p$ 为这样的概率：经过适当的旋转后，尺寸为 $a_1 \times a_2 \times a_3$ 的砖块能放进尺寸为 $b_1 \times b_2 \times b_3$ 的盒子里，且砖块的各边与盒子的各边平行。如果把 $p$ 写成最简分数，分子与分母之和是多少？