计数、排列组合与概率计算
上一节我们一直在做一件事：先把随机实验的所有可能结果摆出来，再圈出自己关心的事件。可是一旦结果变多，“全部列出来”就不现实了。
一个 6 位数字密码有多少种？从 49 个号码中选 6 个有多少种？一个房间里有多少人时，出现同一天生日才真正值得警惕？这些问题如果靠手写清单，很快就会把纸写满。计数的作用，就是在不漏、不重的前提下，直接算出清单本来会有多长。
概率里常见的那条分数仍然没变：
难点通常不在除法，而在上下两个“结果数”到底该怎样数。排列组合也不是一袋互不相干的公式。它们都是从同一个问题长出来的：一个结果究竟由哪些选择构成，换一种顺序还算不算原来的结果？
本节讨论的计数公式本身不要求结果等可能；但要把“结果个数之比”直接当成概率，必须再确认每个基本结果等可能。计数负责数清楚，概率模型负责说明这些结果的机会是否一样。这两件事不能混为一谈。
先问三句话，再决定用什么公式
遇到计数题，先别从题目里找“排列”“组合”这样的关键词。最稳的做法是连续问三句。
顺序重要吗？
从 8 名同学中选 3 人组成同一个调查小组，甲乙丙和丙乙甲是同一组。名单换了书写顺序，小组成员没有变，所以顺序不重要。
还是这 8 名同学，如果要安排主持人、记录员和计时员，甲主持、乙记录、丙计时，与丙主持、乙记录、甲计时显然不是同一种安排。角色不同，顺序就成了结果的一部分。
判断时可以直接做一个交换实验：把已经选出的两个对象换位置，结果有没有变？有变化，按有序结果数；没变化，按无序结果数。
是否放回，或者是否允许重复？
输入 4 位取件码时，同一个数字通常可以重复，所以输过一次 7，并不会让后面的 7 消失。每一位仍有 10 种选择。
从袋里不放回抽球就不同。第一只球抽走以后，袋中少了一只，下一步的选择数会减少。这里的“放回”不是一个小细节，它会直接改变乘法中的每一个因子。
基本结果等可能吗？
公平骰子的 6 个面可以看成等可能。充分混匀后从 10 张编号不同的票里抽一张，每张票也可以看成等可能。
但“下雨”和“不下雨”虽然只有两个结果，却不自动各占一半；常用密码 123456 和一串真正随机生成的 6 位数字，也不一定在人们实际设置密码时同样常见。
这第三问决定的不是“能不能计数”，而是计数之后能不能直接用个数相除求概率。
把整节压缩成一张检查卡，就是三问：顺序是否重要？是否放回或允许重复？基本结果是否等可能？前两问决定怎样数，第三问决定能不能把计数结果直接变成概率。
两条最基本的计数原理
排列和组合都建立在两条更朴素的规则上：分类时相加，分步时相乘。
加法原理：这条路或那条路
学校抽奖准备了 4 张电影票和 6 张书店券，每位中奖者只拿其中一张。抽到电影票与抽到书店券不会同时发生，所以奖品票一共有：
这里能直接相加，是因为两类结果互不重叠。一个具体结果只会被算进其中一类。
如果类别会重叠，就要把重复算到的部分减回来。标准扑克牌中，“A 或红桃”的牌数不能写成 ，因为红桃 A 同时属于两类，被算了两遍。正确计数是：
这和概率加法公式背后的逻辑完全一样：先把两类加起来，再修正交集里的重复。
乘法原理：先走这一步，再走下一步
一家餐厅有 3 种主食、4 种饮品和 2 种甜点。一份套餐要求每类各选一种。你不是在三类中“任选一类”，而是要连续完成三步，因此总数是：
这条规则并不要求后一步的选择数永远不变。只要我们知道每条已经走到的路径，下一步分别还有多少种走法，就能沿着路径继续数。
例如，从 5 名同学中依次选班长和副班长。班长有 5 种选法；选定班长后，副班长剩 4 种选法，所以一共有：
“或”常让人想到加法，“并且”“然后”常让人想到乘法，但不要只凭字面套规则。先确认题目是在分互不重叠的类别，还是在完成连续步骤。类别有重叠时不能直接相加；分步选择会相互影响时，也要写出每一步真实剩下的选择数。
树图与槽位法：把乘法看见
公式写成 很短，可是它为什么代表 24 条完整路径？树图和槽位法能把这件事画出来。
树图适合看分支
回到套餐问题。树的第一层分出 3 种主食；每一条主食分支再分出 4 种饮品，于是第二层有 条路径；每条路径最后再接 2 种甜点，完整路径就变成 条。
树图的好处，是能直接看出“每个最终结果是一条从起点走到终点的完整路径”。它尤其适合下面几种题：
- 步骤不多，但每一步有不同选择；
- 后一步的选择数会随着前面的结果改变；
- 除了计数，还要在下一节给每条分支标上条件概率。
树很快也会长得很大。6 位密码如果每位有 10 种选择，完整树有 条路径，当然不值得真的画完。树图负责建立直觉，乘法原理负责把整棵树压缩成一个乘积。
槽位法适合看位置
要组成一个 4 位数字密码，可以先画四个空槽：
如果允许重复，而且第一位可以是 0，每个槽都有 10 种选择：
如果四位不能重复，选择数就会逐格减少：
如果题目说的是“四位整数”而不是“密码”，第一位又不能是 0。即使仍要求数字不重复，槽位数也会变成：
第一格有 9 种，是因为只能从 1 到 9 中选；第二格仍有 9 种，是因为 0 现在可以使用，而第一格用掉的那个非零数字不能再用。这个例子很好地说明：槽位法不是机械地写递减数字，而是逐格问“此刻还有哪些对象能放进来”。
树图从“路径”看乘法，槽位法从“位置”看乘法。两种画法没有本质区别：树的每一层就是一个槽，每条完整路径就是一次完整填槽。
阶乘：把一路递减写短
把 5 本不同的书排成一行，第一格有 5 种放法，第二格有 4 种，接着是 3、2、1：
这种从某个正整数一直乘到 1 的乘积经常出现，所以用阶乘来缩写：
于是 ，，。
为什么规定零的阶乘等于 1
初看 很古怪：什么都没有，怎么会得到 1？关键是我们数的不是“对象有几个”，而是“安排方式有几种”。
把 0 个对象排成一列，只有一种做法：什么都不放。它叫空排列。类似地，从一组对象中一个都不选，也只有一种选法：空集。
这个约定还能让递推关系保持一致。因为：
而 ，所以必须有：
不表示“零等于一”。它表示“安排零个对象的方式数是一种”。阶乘是计数函数，不能只把感叹号当成装饰符号。
阶乘增长得非常快。，而 已经超过 。这也解释了为什么只要密码长度稍微增加，理论上的搜索空间就会迅速膨胀。不过“理论空间大”不等于“现实密码一定安全”，因为人们往往集中选择生日、连续数字和常见短语，这些选择并不等可能。
排列：选出来以后，还要分清先后
从 个不同对象中取出 个，并把这 个对象放进有区别的位置，结果数叫做排列数。
第一个位置有 种选择，第二个位置剩 种，一直填到第 个位置：
也常写成 。用阶乘可以压缩成：
例题：安排前三位发言者
7 名同学中选 3 名依次发言，有多少种发言安排？
先确认一个结果是什么。这里的结果不仅包含哪 3 人发言，还包含谁第一个、谁第二个、谁第三个。交换两人的发言位置，结果就变了，所以顺序重要。
发言者不能重复。第一个位置有 7 种选择，第二个剩 6 种，第三个剩 5 种。
用乘法原理得到：
最后用数量级检查。只选第一人时有 7 种，再增加两个有区别的位置，结果数应比 7 大很多；210 符合这种直觉。
全排列只是排列的特殊情形
如果把 个不同对象全部排好，就是取 ：
所以 6 本不同的书排成一行有 种。这里 正好让公式不需要另写一个例外。
组合：同一批对象的内部顺序要合并
如果从 个不同对象中取出 个，只关心选中了谁，不关心书写顺序，结果数叫做组合数，记作：
也常写成 ，读作“ 选 ”。
组合公式可以从排列得到。先按顺序选，会有 个结果；但同一组 个对象在有序名单中会出现 次。
例如甲、乙、丙这个小组会被写成：
六个有序名单其实是同一个无序小组。因此要除以 ：
例题：组成调查小组
8 名志愿者中选 3 人组成同一个调查小组，有多少种选法？
先做交换检查。小组不设职位，甲乙丙和丙乙甲的成员完全相同，所以顺序不重要。
如果先按有序方式填三个槽，会有 个名单。
每个实际小组在这份名单中重复了 次，所以：
这一步的“除以 6”不是公式魔法，而是在删除同一组人的六种书写顺序。
选中与没选中是一回事
从 人中选 人，同时也唯一决定了哪 人没被选。因此：
例如，从 10 人中选 8 人，等价于决定哪 2 人不进小组：
计算时选择较小的那个数，通常更省事。
这个交互只在 的范围内计算，并使用整数运算得到排列数和组合数。切换“顺序重要”和“顺序不重要”时，观察两边为什么正好相差 倍。
顺序与重复交叉后，出现四种基本情形
很多题真正让人卡住的，不是排列和组合本身，而是“顺序”与“重复”同时出现。把两个问题交叉起来，会得到四种常见模型。
前三种现在已经很熟。第四种叫做可重复组合，入门阶段只需要理解一个经典画法。
可重复组合：星与隔板
有 3 种糖果口味，要拿 4 颗，允许同一种拿多颗，而且只看每种拿了几颗，不看拿取顺序。
用 4 颗星表示糖果，再用 2 块隔板把它们分成 3 类。例如：
表示第一种 2 颗、第二种 1 颗、第三种 1 颗。每一种选法都对应一串由 4 颗星和 2 块隔板组成的排列。我们只需从 6 个位置中选出 2 个放隔板：
等价地，也可以选出 4 个位置放星，所以写成 也一样。
可重复组合不是“看到允许重复就套一个新公式”。如果顺序重要，仍然是逐个槽位选择，通常得到 ；只有“允许重复且顺序不重要”时，才需要把每种对象出现多少次作为结果。
对象有相同的：先当作不同，再除掉重复
到目前为止，排列里的对象都互不相同。如果对象本身有重复，直接用 会把肉眼看不出区别的交换也算成新结果。
假设要把 5 张颜色卡排成一行，其中 2 张红卡完全相同，2 张蓝卡完全相同，另有 1 张绿卡。
如果先给每张卡偷偷编号，就有 个排列。但两张红卡交换不会得到新图案，两张蓝卡交换也不会得到新图案。因此每个真实图案被重复计算了 次：
一般地， 个对象中有若干类相同对象，数量分别为 ，并且：
不同排列数是：
这个公式和组合“除掉组内顺序”的思想是一回事：先把东西暂时看成不同，数出过多的结果，再除去那些不会造成真实变化的交换。
组合数为什么会出现在重复试验里
做 5 次互不影响、成功概率都为 的试验，恰好成功 3 次。先固定一种顺序，例如：
这条具体路径的概率是：
可成功的 3 个位置不止这一种。要从 5 个位置中选出 3 个放“成功”，共有：
条路径。每条路径都有相同的概率 ，所以恰好成功 3 次的概率是：
组合数在这里做的工作很具体：它不是给成功“加权”，而是在数成功可以出现在哪些位置。以后学习二项分布时，这个系数会反复出现。
补集计数：正面难数，就从反面绕过去
“至少一个”“出现重复”“不是全部”这类事件，直接分类往往很麻烦。补集提供了一条更短的路：先数它完全不发生的情况，再用总数减掉。
如果全集共有 个结果，事件 的补集为 ，那么计数关系是：
在等可能模型中，对应的概率关系是：
例题：四位密码中至少有一个数字重复
考虑从 0000 到 9999 的四位密码，每一位都独立地从 0 到 9 等可能生成。求至少有一个数字重复的概率。
直接数“恰好一对”“两对”“三个相同”“四个相同”会分出很多类别。补集只有一种情形：四位数字全不相同。
全部密码共有：
四位全不相同的密码数是：
至少有一处重复的密码数是：
因为题目明确说每一位都是等可能随机生成，所以可以用个数相除：
这个答案很反直觉：只有 4 个槽，数字却有 10 个，出现重复的概率已经接近一半。人类直觉常盯着“还有很多数字没用”，却低估了任意两格发生碰撞的机会。
生日问题：23 人为什么已经超过一半
生日问题是补集计数最经典的例子。先忽略闰年，并暂时假设每个人的生日独立、365 天等可能。问一个房间里有 个人时，至少两人同生日的概率。
很多人会想：“365 天那么多，要到一百多人甚至 183 人才容易撞吧？”这忽略了一件事：我们不是拿某一个人的生日和所有人比较，而是在看房间里任意一对人会不会撞上。
23 个人之间已经有：
对关系可以比较。253 次潜在碰撞，比直觉里“一人与另外 22 人比较”多得多。
用补集完整计算
先把人数范围说清楚。下面的递减乘积只用于整数 ；当 时，把没有任何因子的空乘积记为 1。如果 ，就不用再算了：365 个日期要容纳至少 366 个人，按抽屉原理一定有两人生日相同，所以碰撞概率直接等于 1。继续把乘积往后写，不仅多余，还会出现没有实际意义的负数因子。
把房间里的人编号。第一个人的生日随意；第二个人要避开第一个人的生日，有 364 种安全选择；第三个人要避开前两个生日，有 363 种，一直继续。
所有生日序列共有：
所有人生日都不同的序列有：
因此：
至少两人同生日就是它的补集：
当 时：
也就是说，23 人的房间里，出现生日碰撞已经比完全不碰撞略微更可能。
现实中的生日并不在 365 天上完全均匀，也可能有双胞胎等依赖关系。这里的 来自一个简化模型。这个例子真正要建立的直觉是：当“任意两者发生碰撞”都算成功时，可比较的配对数量增长得很快。
从计数走到概率：分母和分子必须说同一种语言
计数完成以后，不能马上把两个数字一除。先做三项检查：
- 分母里的每个基本结果是否等可能？
- 分子和分母数的是不是同一种对象？
- 有没有在分子按无序计数、分母却按有序计数，或者反过来？
第三项尤其常见。只要分子和分母的结果定义不一致，即使两个计数分别算对，概率也会错。
抽签：奖项相同与奖项不同
10 名同学中不放回抽 3 人获得同样的纪念品。因为三份奖品没有区别，一个基本结果是一组 3 人：
如果改成一等奖、二等奖、三等奖，角色有区别，甲得一等奖和甲得三等奖不是同一结果。这时基本结果变成有序安排：
同样是“抽 3 人”，只因为奖项是否区分，样本空间就差了 倍。
现在问：小林在 10 人中获得三份相同纪念品之一的概率是多少？所有 3 人组等可能。包含小林的小组，需要再从其他 9 人中选 2 人：
这个结果也符合对称直觉：10 人中抽 3 人，每个人的机会都应是 。
彩票：一张固定号码到底有多难中
某种号码游戏从 1 到 49 中不放回选出 6 个号码，公布时不区分顺序。你提前选定一组 6 个号码，完全命中的概率是多少？
一个基本结果是一组 6 个号码，不是 6 个号码的开奖先后。所有号码组共有：
你的固定号码只对应其中 1 组，因此：
如果误用排列 作分母，却仍把有利结果写成 1，就把同一组开奖号码的 种顺序都当成不同分母结果，却没有在分子做同样处理，答案会被错误地缩小 720 倍。
彩票号码看起来可以有“冷号”“热号”，但在公平、独立的开奖模型下，每一组固定的 6 个号码机会相同。1、2、3、4、5、6 看起来不够随机，却和任何另一组指定号码拥有相同的中奖概率。真正特殊的是人们选择它的方式可能不均匀：如果很多人都选同一组，中奖后可能要和更多人分奖。这影响的是奖金分配，不是该号码被开出的概率。
密码：理论空间与真实安全不是一回事
一个允许重复的 6 位数字密码，理论上有：
种。如果系统真正均匀随机生成，每个密码的概率都是百万分之一。
但人自己设置密码时，生日、重复数字和连续数字更常见。这时“所有字符串一共有一百万种”仍然是正确计数，却不能推出“攻击者每次猜中的机会都是百万分之一”。攻击者会先猜更常见的选择。
“共有 种可能”只有在这 种基本结果等可能时，才意味着某个固定结果的概率是 。计数空间大，不代表现实选择分布均匀。这正是三问中“是否等可能”不能省略的原因。
一个完整的多步例题：先选人，再分角色
某社团有 6 名女生和 4 名男生，要选出 3 人负责一次活动，其中至少有 1 名男生。选出的 3 人中还要确定 1 名负责人，其余两人职位相同。共有多少种安排？
这题同时用了补集、组合与乘法原理。
先决定 3 人小组。总人数是 10，不限制性别时有：
“至少 1 名男生”的补集是“3 人全是女生”。全女生小组有：
因此满足性别要求的小组有：
每个合格小组中，再选 1 人担任负责人，有 3 种选择。小组选择和负责人选择是连续两步，所以相乘：
最后检查重复。每种结果都由“一组 3 人”和“其中哪一人负责”唯一确定；其余两人职位相同，交换书写顺序不会产生新结果，所以没有多算。
也可以按“恰好 1 名男生、恰好 2 名男生、恰好 3 名男生”分类相加，但补集路线更短。好的计数方法往往不在于公式更多，而在于先找到不重不漏、步骤最少的描述。
最常见的重复计数错误
把同一组人的书写顺序当成不同结果
题目只要 3 人小组，却算成 。这会把每个小组重复算 次。
修正方法不是死记“看到小组就除以 6”，而是明确重复从哪里来：同一组三人在三个临时槽里有 6 种排列，所以除以 6。
分子按组合数，分母按排列数
彩票开奖顺序不影响中奖时，分子数“某一组号码”，分母却数“所有有序号码序列”，两边的基本结果不一致。
你当然也可以两边都按有序结果来数。固定的一组 6 个号码对应 个开奖顺序，于是：
只要分子分母语言一致，答案相同。
看到“或”就直接相加
“抽到 A 或红桃”中的红桃 A 属于两类。直接写 会重复一次。先问两类是否互斥；不互斥时，要减去交集。
忘记第一位的限制
“4 位密码”通常允许 0 开头，“4 位整数”通常不允许。两个题看起来只差一个词，第一格却从 10 种变成 9 种。
把“允许重复”误读成“必须重复”
每位数字可以重复，表示 1123 合法，也表示 4827 合法。它不是说密码里一定要出现重复数字。
默认所有结果等可能
从装有不同重量球的装置里滚出一种颜色，或者统计人们自选密码，基本结果未必等可能。排列组合仍能告诉你结果种类有多少，却不能单靠种类数给出概率。
计数完成后，最好用一句话定义基本结果，再做一次“能否唯一还原”的检查：每个现实结果是否只对应你的计数过程中的一条路径？如果对应多条，就是重复计数；如果有现实结果没有路径，就是漏数。
练习：先判断模型，再动笔计算
练习一：套餐与加法
一家店的早餐只能在“4 种面包”或“3 种粥”中选一份；另可从 5 种饮品中选一杯。共有多少种“主食加饮品”的早餐？
练习二：允许重复的取件码
一个 5 位数字取件码允许 0 开头，也允许数字重复。共有多少个取件码？
练习三：不重复的四位整数
用数字 0 到 9 组成四位整数，数字不能重复。共有多少个？
练习四：不同职位
从 9 人中选出 1 名组长、1 名记录员和 1 名联络员，一共有多少种安排？
练习五：无职位小组
从 9 人中选 3 人组成同一个小组，不设职位，一共有多少种选法？并说明它与练习四为什么相差 6 倍。
练习六：相同颜色卡片
把 3 张相同红卡、2 张相同蓝卡排成一行，有多少种不同颜色序列？
练习七：至少一人中奖
10 张票中有 2 张中奖票。甲、乙两人依次不放回各抽 1 张。求至少一人中奖的概率。
练习八：恰好三次成功
某个互不影响的重复试验做 5 次，每次成功概率都是 。求恰好成功 3 次的概率。
收束：先把结果数对，才有可靠的概率
计数问题不该从背公式开始。更可靠的顺序是：
先定义一个基本结果。它是一串有先后的密码、一个不看顺序的小组，还是带有不同职位的人员安排？
再问顺序是否重要、是否允许重复。需要连续填槽就用乘法；有序且不重复时得到排列，无序且不重复时得到组合。
遇到“至少一个”“出现重复”时，先试着数补集。反面往往比正面只有更少的类别。
最后才把计数变成概率，并检查基本结果是否等可能，分子和分母是否采用同一种结果定义。
到这里，我们已经能数清多步随机过程的路径了。不过，当抽签不放回、第一张牌已经翻开，或者检测结果已经出现时，后一步的概率会因为前面的信息而改变。下一节要做的，就是把树图上的“走到这里以后”写成正式的概率语言：条件概率。