分步乘法计数原理

教材原文

完成一件事需要两个步骤

做第1步有m种不同的方法，做第2步有n种不同的方法，那么完成这件事共有

$N = m \times n$

①无论第1步采用哪种方法，与之对应的第2步都有相同的方法数.

要点

• 两个前提，和分类那两条对称：
  1. 步骤要完整——把所有步骤都做完，这件事才算做完。少一步就不是”做完”，多一步就重复计数。
  2. 后一步的方法数不随前一步的选择而变（课本那条脚注）。这是最容易破掉的一条： “先选正组长再选副组长”里第 2 步恒为 $4$ 种（因为不管第 1 步选了谁，都恰好剩 4 人），合格； 但”从 $0\sim9$ 里排一个三位数”若先排个位再排百位，百位能选几个就要看个位是不是 $0$ 了，不合格—— 换个步骤顺序常常就能把这条修好。
• 推广到 $n$ 步：$N=m_1\times m_2\times\cdots\times m_n$。
• 判据是”和”：题面里的关联词是”和”（既要这个和那个）时用乘法。
• 每一步的方法数要按「轮到这一步时还剩几种」来写，不是按”原本有几种”写。

与加法原理的关系

课本用一句话把两者接上：乘法是加法的简写。第 1 步的 $m$ 种方法把整件事切成 $m$ 类，每一类里都还剩 $n$ 种做法，于是 $N=\underbrace{n+n+\cdots+n}_{m\ \text{个}}=m\times n .$ 所以分步乘法计数原理并不是一条独立的新公理，而是分类加法计数原理在”每一类都一样大”这个特例下的省写—— 而”每一类都一样大”正是那条脚注前提。前提一破，就只能老老实实分类相加。

常见用法

• 填空位：排列数 $A_n^m$ 的推导就是一次分步——$m$ 个空位依次填，第 $k$ 个空位有 $n-k+1$ 种填法。
• 每个对象独立选归宿：把 $k$ 件不同的东西分给 $n$ 个人（不限每人几件），就是 $k$ 步、每步 $n$ 种，共 $n^{k}$ 种。 这一条是”分配问题”最省事的入口，代价是要另外扣掉违反限制的那些分法。

关于上面那段引文

课本原句是「完成一件事需要两个步骤 ①，做第1步有…」，「两个步骤」后面挂着脚注号 ①，脚注内容即上面引的最后一行。上面把带上标的那个记号拆成两段引，是因为课本页里它写成行内公式，整段搬过来会被渲染成乱码。