去图书馆可以步行,也可以乘公交。步行有 条路线,公交有 条线路,总共有 种选择。若必须先选公交线路,再从两个站口之一出站,则每条线路都能搭配两个站口,共有 种方案。
“加”对应从若干互斥类别中任选一类即可完成任务;“乘”对应所有步骤都完成才得到一个完整方案。先弄清任务结构,比背口诀更重要。
- 理解分类加法计数原理,分类必须不重不漏。
- 理解分步乘法计数原理,每步完成后任务仍未结束。
- 会在同一问题中综合使用分类与分步。
- 会用树状图、列表或编号检查计数过程。
- 会用补集法处理“至少一个”“不能全是”等限制。
一、分类加法计数原理
完成一件事有若干类互不重叠的方案:第一类有 种,第二类有 种,直至第 类有 种;每一类中的任何一种方法都能独立完成任务,则不同方法总数为
“分类”强调不同类别之间互斥,同一完整方案只能归入一类;所有类别还要覆盖全部可能。若分类有交叉,直接相加会重复;若某些情形未归类,就会遗漏。
常见分类依据包括首位取值、某元素是否出现、特殊位置由谁占据等。好的分类标准应在同一层级保持一致。例如按“首位是数字”与“末位是字母”分类会交叉,不适合直接相加。
二、分步乘法计数原理
完成一件事必须依次经过 个步骤,第一步有 种方法,第二步对第一步的每种选择都有 种方法,依此类推,则完整方法数为
每一步只是完成任务的一部分,所有步骤的选择组合起来才是一种完整方案。若后一步的可选数依赖前一步,就不能机械地乘同一个数,应按分支分别计算,或重新分类。
例如用数字 组成无重复的两位数:十位有 种,选定后个位只剩 种,共 种。若数字中包含 ,十位不能为零,第一步和第二步的可选数就要分别核对。
判断加法还是乘法,要问完整方案之间是什么关系:任选一种途径即可完成,用分类相加;一个方案必须包含所有环节,用分步相乘。复杂问题通常是“先分类,每类再分步”。
三、分类与分步的综合
许多题既有限制又有多个位置。常用策略是优先处理受限制最强的元素或位置,再在每一类中分步。例如组成偶数时,可先按个位数字分类;安排座位时,可先讨论特殊人物是否相邻。
树状图能把每个阶段的分支显示出来。从根到叶的一条路径对应一个完整方案,同一节点发出的分支互不相同。叶子总数就是方案总数。规模较小时,可用列表和树状图核对;规模较大时,则把树的每层分支数转化为乘法。
若不同分支的后续选择数不同,应先算每个分支的叶子数,再相加。例如第一类后续有 种,第二类后续有 种,总数是 ,不能把各层数字随意相乘。
四、补集计数与限制条件
当“至少一个”“不全相同”等正面分类很繁琐时,可先数无约束总数,再减去不符合条件的方案:
例如长度为 的二进制串共有 个,至少含一个 的串数为 ,减去的是全为 的唯一情形。
补集必须在同一个确定的全集中取。若总数允许重复,而“不符合”部分按不重复计数,两者口径不一致,减法就没有意义。遇到“恰有”“至少”“至多”时,应先准确写出事件的补集是什么。
用数字 组成无重复数字的三位偶数,共有多少个?
✏️ 查看分步解析
个位必须是偶数,按个位分类。
第一类,个位为 。百位可从 中选,有 种;十位从剩余 个非个位数字中选,有 种,共 种。
第二类,个位为 或 ,有 种。百位不能为零,也不能与个位相同,在其余三个非零数字中选,有 种;十位从剩余 个数字中选,有 种,共 种。
两类互斥且覆盖所有偶数,所以总数为 。不能先说百位有 种、个位有 种,因为个位选零与非零时后续数量不同。
由 个不同字母和 个不同数字组成长度为 的口令,允许字符重复,要求至少出现一个数字。共有多少个口令?
✏️ 查看分步解析
每个位置可从全部 个字符中选,允许重复,所以无约束总数为
“不含数字”就是三个位置全部选字母,每个位置有 种,共
因此至少含一个数字的口令数为
补集法避免了分别计算恰有一个、两个和三个数字。若题目不允许重复,总数与补集都要改用逐步减少的可选数。
- 分类要互斥且完整;分类交叉时直接相加会重复计数。
- 分步要求所有步骤共同组成方案,不能把任选一步误作完整任务。
- 后一步选择数若依赖前一步,应分类或画树,不能机械连乘。
- 组成多位数时首位不能为零,零往往需要单独讨论。
- 补集法中的总数与排除数必须使用同一全集和同一重复规则。
账号命名、车牌编码和产品选配都需要计数。若一台电脑必须选择处理器、内存和硬盘,三个环节用乘法;若运输可任选公路或铁路,两类方案用加法。实际系统还可能有兼容限制,例如某处理器只能搭配两种主板,此时各分支选择数不同,应按兼容组合分类统计,不能把所有选项数直接相乘。
五、自测与解析
1. 分类还是分步
某人可从 条陆路或 条水路中任选一条到达目的地,共有多少种方式?
✏️ 查看答案
任选一条路线即可完成任务,两类互斥,所以共有 种。
2. 分步计数
从 件上衣和 条裤子中各选一件,有多少种搭配?
✏️ 查看答案
一套搭配必须同时完成两步,每件上衣都可配三条裤子,共 种。
3. 补集法
长度为 的二进制串中,不全为 的有多少个?
✏️ 查看答案
全部有 个,全为 只有一个,所以符合条件的有 个。