排列与组合 — 顺序算不算,决定了要不要除
这一章讲三件事: 把 n 样东西排成一排有多少种排法; 只取其中几样时怎么算; 以及「不管顺序」的时候为什么要除一下、除的到底是什么。
它在全书链条里的位置: 第 09 章的四条法则管的是「有多少个」, 这一章管的是「有多少种排法、取法」——同一批东西,问法不同,答案差好几倍。 第 12 章的帕斯卡三角形、第 13 章的指数爆炸都要用到这一章的数。 需要的基础: 第 09 章的乘法法则。
1. 先看现象:三张牌能排出几种顺序
手上 A、B、C 三张牌,排成一排,有几种排法?
六种:ABC、ACB、BAC、BCA、CAB、CBA1。
六是怎么来的?一位一位地想2:
第 1 张:从 A、B、C 里挑,3 种选法
第 2 张:剩下 2 张里挑,2 种选法
第 3 张:只剩 1 张,1 种选法
3 × 2 × 1 = 6
图说:每挑走一张,后面可挑的就少一张 —— 这是这一章所有算法的起点。
用的正是第 09 章的乘法法则。
把 n 样东西按顺序排成一排,这件事叫置换3。
全章的主走查:手上五张牌 A、B、C、D、E
─────────────────────────────────────────────────────────
§2 五张全排一遍 5 × 4 × 3 × 2 × 1 = 120 种
§4 只取三张排一排 5 × 4 × 3 = 60 种
§5 只取三张,不管顺序 60 ÷ 6 = 10 种
§6 三个数的关系 6 × 10 = 60
─────────────────────────────────────────────────────────
图说:120、60、10 —— 同一副五张牌,三种问法,三个数。
每往下一格,都只是「除掉一些重复」。
2. 五张牌全排一遍:120 种,而这串连乘有个名字
这一节走主走查的第一步。
五张牌 A 到 E 全部排成一排,有几种? 思路和三张一模一样4:
5 × 4 × 3 × 2 × 1 = 120 种
这种「从 n 开始一路减到 1 连乘」的写法太常用了,所以给了它一个名字:阶乘,
写成 5!,读作「5 的阶乘」5。名字的来由是乘数呈阶梯状递减。
| 式子 | 值 |
|---|---|
5! | 120 |
4! | 24 |
3! | 6 |
2! | 2 |
1! | 1 |
0! | 1 ← 注意 |
最后一行值得停一下:0 的阶乘不是 0,而是被定义成 16。
这条定义和第 01 章那条是同一件事:值是被挑出来的,准绳是「让规则不分叉」。 原书在这里留了一段师生对话:学生说「0! 应该是 0 才对」, 老师回答「这样的话可是推倒不了第一张多米诺骨牌的」, 并说等讲到阶乘的递归定义时再讨论7。这笔账第 11 章还。
顺带看一眼规模:一副 52 张牌摆成一排,有多少种摆法?
52! = 80 658 175 170 943 878 571 660 636 856 403 766 975 289 505 440 883 277 824 000 000 000 000
这是一个 68 位的数8。对比一下:13 张牌的排法(13!)就已经超过 62 亿了—— 从 13 张到 52 张,只多了 39 张牌,数值却涨到了几乎无法书写的程度。 原书的说法是:随着 n 增大,阶乘的结果呈爆炸式增长9。(第 13 章专讲这件事。)
3. 顺便修一个容易读岔的地方
这一节很短,但不写会留下一个坑。
「置换」这个词在这一章有个特定用法:它指「把全部 n 样东西排成一排」。 下一节的「排列」指的是「从 n 样里取出 k 样排成一排」。 两者的区别只有一处:取不取全部。
中文里这两个词很容易混,而原书是按日文数学教材的习惯分的。 读的时候只要盯住那句「取几样」就不会错。
4. 只取三张:60 种
这一节走主走查的第二步。
五张牌里取三张排成一排,有几种?
还是一位一位挑,只不过挑到第三张就停10:
第 1 张:5 种
第 2 张:4 种
第 3 张:3 种 → 5 × 4 × 3 = 60 种
60 种11。从 n 样里取 k 样排成一排,这件事叫排列12。
注意排列和置换一样,是要考虑顺序的: ABD 和 ADB 由同样三张牌组成,但顺序不同,算两种13。
这里有一个细节原书特意叮嘱要看仔细:连乘一共有几项。
从 n 开始往下乘 k 项,最后一项是 n − k + 1——
把它写成 n − (k − 1) 就明白了:减去的数从 0 排到 k − 1,正好 k 项14。
原书说,这里用到的正是本章开头那道植树问题的思路15—— 「从 0 数到 k−1 一共 k 个」和「10 米路 11 棵树」是同一件事。
5. 不管顺序:除掉重复度,10 种
这一节走主走查的第三步,也是这一章的核心动作。
同样是五张里取三张,但这次不管顺序——ABE 和 BAE 算同一组。有几种?
办法分两步16:
① 先按「管顺序」的算法数一遍 → 60 种(上一节的结果)
② 再除掉重复的倍数 → 60 ÷ 6 = 10 种
关键是那个 6 从哪来。 同样三张牌 A、B、C,按顺序数的时候被数成了 ABC、ACB、BAC、BCA、CAB、CBA 六种;而不管顺序时它们是同一种。 所以每一组都被重复数了 6 次,这个 6 就叫重复度17。
而这个 6 正是「三张牌能排出几种顺序」,也就是 3! = 3 × 2 × 1。
60 ÷ 6 = 10 种
图说:分子是「管顺序的种数」,分母是「同一组能排出几种顺序」。
除完之后,每一组只剩一个代表。
这种不管顺序的取法叫组合18。五张取三张的组合有 10 种: ABC、ABD、ABE、ACD、ACE、ADE、BCD、BCE、BDE、CDE19。
「先按顺序数,再除以重复度」这套动作,是算组合最常用的办法20—— 记住这个动作比记住公式有用,因为后面两道难题都要靠它。
6. 三个数的关系:6 × 10 = 60
这一节走主走查的第四步,把三个数串起来。
「三张牌的全排」 × 「五张取三张的组合」 = 「五张取三张的排列」
3! = 6 × 10 = 60
图说:先决定「取哪三张」(10 种),再决定「这三张怎么排」(6 种),
两步一乘就是排列。所以组合 = 排列 ÷ 全排,除的就是那 6。
这条关系原书用一张 10 行 6 列的表画了出来: 左边 10 行是十种取法,每一行往右摊开成 6 种顺序,一共 60 格21。
读懂这张表,这一章就通了: 「组合」是选,「置换」是排,选完再排就是「排列」。
7. 换一道难题:同一种药可以放好几粒
这一节另起一处走查,展示上面那套动作怎么用在不那么标准的题上。
题目:三种药 A、B、C,一共取 100 粒配一副新药,每种至少 1 粒,不考虑顺序。有几种配法?22
这题的难处在于「同一种药可以放好几粒」,不能直接套组合。 原书的办法是先把问题缩小:改成一共取 5 粒23。
五个盘子排成一排,在盘子之间插两块隔板:
○ ○ │ ○ ○ │ ○
A A 隔 B B 隔 C
图说:第一块隔板左边的盘子放 A,两块隔板之间放 B,右边放 C。
隔板一插,每种药各几粒就定死了 —— 于是「配药的方法」
和「隔板的插法」一一对应。
五个盘子之间有 4 个空隙,要在这 4 处里挑 2 处插隔板—— 这就变成了标准的组合题:4 选 224。
放大回 100 粒: 100 个盘子之间有 99 个空隙,三种药要插 2 块隔板, 所以是从 99 处里挑 2 处25:
99 × 98 ÷ (2 × 1) = 4851 种
4851 种26。这一处的收益是那句「一一对应」: 把一道不会算的题,换成一道会算的题——前提是那个换法必须一一对应,不漏不重。
8. 再换一道:两种解法都算 42
这一节另起第二处走查,它示范了「同一道题两条路」。
题目:五张牌,其中两张是王牌(不区分大小王),另外三张是 J、Q、K。 排成一排,左端或右端至少有一端是王牌的排法有多少种?27
第一条路,用第 09 章的容斥原理28:
| 情况 | 算式 | 结果 |
|---|---|---|
| 左端是王牌 | 2 种王牌选法 × 剩下 4 张的全排 4! | 2 × 24 = 48 |
| 右端是王牌 | 左右对称 | 48 |
| 两端都是王牌 | 两张王牌的排法 2! × 剩下 3 张的全排 3! | 2 × 6 = 12 |
「至少有一端」= 左端 + 右端 − 两端都是(否则两端都是的情况被数了两次), 再除以两张王牌不区分带来的重复度 2:
(48 + 48 − 12) ÷ 2 = 84 ÷ 2 = 42 种
第二条路,用第 04 章的逻辑29。「至少有一端是王牌」的否定是「两端都不是王牌」, 所以拿全部排法减去「两端都不是」就行:
全部排法 :5! ÷ 2 = 120 ÷ 2 = 60
两端都不是王牌:两端从 J、Q、K 里取 2 张排(3 × 2 = 6),
剩下 3 张全排(3! = 6),再除重复度 2 → 36 ÷ 2 = 18
60 − 18 = 42 种
两条路都得到 4230。这一处值得记住的不是 42,是「正面不好数就数反面」—— 它和第 04 章那句「A ⇒ B 等于 ¬A ∨ B」是同一种换个方向的思路。
9. 作者的判断、我们的判断,以及这一章的边界
| 说法 | 书里给了什么 |
|---|---|
| 置换、排列、组合各自的算法(一套步骤明确、照着做就一定能得到结果的办法) | 全都给了推导过程,而不是直接给公式:一位一位挑、挑到第 k 位停、除掉重复度 |
| 0! = 1 | 给了定义,理由留到第 11 章的递归定义才说 |
| 三者的关系 | 给了一张 10 行 6 列的表,把 6 × 10 = 60 画了出来 |
| 隔板法 | 给了缩小规模的完整过程(先做 5 粒再放大到 100 粒) |
| 「死记硬背毫无意义」 | 是作者的态度,原文说重要的是理解这些方法的意义 |
判断(我们的,不是书里的):这一章真正该带走的,是「先按顺序数,再除掉重复度」 这个动作,而不是那几个符号。 组合的公式(带一堆阶乘的那个)会忘,但「我这么数是不是把同一件事数了好几遍、 每件被数了几遍」这个问题,一旦养成习惯就忘不掉。 隔板法和「数反面」也是同一类:把不会算的换成会算的。 如果错,会错在: 如果一个人的工作里根本不需要估算「有多少种情况」 (比如只写业务增删改查),那这一章确实用不上。 判据是:你有没有写过或读过组合搜索、把测试用例一个不漏地列出来、抽奖概率这类代码。
这一章的边界:
- 原书用的记号是
Pⁿₖ和Cⁿₖ,而不同国家、不同教材的写法不一样 (英文教材常写成 P(n,k)、C(n,k) 或 n 上面一个 k 的括号形式)——这一点原书没提; - 重复组合只讲了 隔板法这一种视角,没有讲它的一般公式的推导;
- 没有讲概率——这一章数的仍然是「多少种」;
- 没有讲怎么把这些数真的算出来(阶乘一大就溢出,实际编程要绕开直接算
n!); - 0! = 1 的理由留到了下一章,这一章只是给了定义。
10. 可带走的
- 每挑走一样,后面可挑的就少一样——这是这一章所有算法的起点;
- 五张牌全排 = 5 × 4 × 3 × 2 × 1 = 120;这串连乘叫阶乘,写成
5!; - 0! = 1,不是 0——理由和第 01 章定义 10⁰ 一样:让规则不分叉;
- 52 张牌的排法是一个 68 位的数;13 张牌的排法就已经超过 62 亿;
- 只取三张排一排 = 5 × 4 × 3 = 60——连乘乘 k 项就停;
- 不管顺序时要除掉重复度:60 ÷ 6 = 10,那个 6 是「三张牌能排出几种顺序」;
- 三者的关系:选(10 种)× 排(6 种)= 排列(60 种);
- 「先按顺序数、再除以重复度」这个动作比公式值钱;
- 不会算就换一道会算的:配药题换成插隔板题(4851 种),前提是换法要一一对应;
- 正面不好数就数反面:「至少有一端是王牌」= 全部 − 两端都不是 = 42 种。
11. 原文地图
| 主题 | 原书章 | 原文位置 |
|---|---|---|
| 三张牌的六种排法 | 第5章 排列组合 | text/10-ch05.txt:346(搜「3 张牌共有 6 种排法」) · :357(搜「第 1 张牌（最左边的牌）」) |
| 置换与阶乘 | 第5章 排列组合 | text/10-ch05.txt:355(搜「按顺序进行排列称为置换」) · :391(搜「称为 5 的阶乘」) · :401(搜「而被定义为 1」) |
| 0! 的师生对话 | 第5章 排列组合 | text/10-ch05.txt:407(搜「为什么 0! 是 1 呢」) · :413(搜「推倒不了第一张多米诺骨牌」) |
| 52! 与爆炸式增长 | 第5章 排列组合 | text/10-ch05.txt:428(搜「80 658 175 170 943 878」) · :433(搜「呈爆炸式增长」) |
| 排列 | 第5章 排列组合 | text/10-ch05.txt:450(搜「答案：60 种」) · :505(搜「取出 3 张的排列」) · :531(搜「这个式子很重要，一定要看仔细」) · :539(搜「植树问题」) |
| 组合与重复度 | 第5章 排列组合 | text/10-ch05.txt:674(搜「这种取法称为组合」) · :682(搜「则会产生 6 倍的重复计数」) · :701(搜「然后除以重复度的方法」) |
| 三者的关系 | 第5章 排列组合 | text/10-ch05.txt:818(搜「从 5 张中取 3 张的排列」) · :813(搜「置换和组合相结合就是排列」) |
| 重复组合(隔板) | 第5章 排列组合 | text/10-ch05.txt:851(搜「隔板」) · :856(搜「调剂 5 粒药品的组合总数 」) · :882(搜「由此得出调剂方法共有 4851 种」) |
| 至少有一端是王牌 | 第5章 排列组合 | text/10-ch05.txt:901(搜「首先按区分大小王牌计数」) · :933(搜「王牌的重复度」) · :939(搜「也就是「两端都不是王牌」的否定」) |