19.2
分步乘法计数原理
把完成任务的连续步骤分别计数后相乘。
本文章目录
01 · 出发点
完整方案往往由连续步骤组成
选择一套服装需要先选上衣，再选下装；生成一个账号可能要先定用户名，再定密码。每一步单独完成都不等于任务结束，必须把所有步骤依次完成。
分步乘法计数原理统计的是有序的选择链。前一步的每种选择都可以与后一步的所有选择配对，于是完整方案数表现为各步选择数的乘积。
02 · 概念
分步乘法计数原理
完成一件事需要依次经过 k 个步骤，第 i 步有 m_i 种选择，并且每一种前序选择都能接上所统计的后续选择，则完整方案数为 m_1m_2…m_k。
若后一步可选数量依赖前一步，不能机械地乘同一个数。此时应按前一步的不同结果分类，分别计算后续数量，再把各类乘积相加。
03 · 方法
把复杂任务拆成选择链
- 01
按时间或结构顺序拆分必要步骤，确保不漏掉任何限制。
- 02
计算每一步在既定前序选择下的可选数量，判断数量是否恒定。
- 03
恒定时直接相乘；不恒定时先分类，再在每一类内部相乘。
04 · 例题
把方法落到具体问题
用数字 1、2、3、4 组成没有重复数字的三位数，共有多少个？
解
- 1
组成三位数需要依次确定百位、十位和个位，三个位置都确定才完成。
- 2
百位有 4 种选择；选定百位后，十位剩 3 种选择。
- 3
再选定十位后，个位剩 2 种选择，因此三个步骤的选择数依次为 4、3、2。
05 · 辨析
容易忽略的条件与边界
回看
本节小结
- 分步乘法对应“所有步骤都完成”的任务结构。
- 每个因子必须表示一个必要步骤的可选数量。
- 选择数依赖前序结果时，应采用分类与分步相结合的方法。