分类加法计数原理与分步乘法计数原理

分类加法计数原理与分步乘法计数原理处理两种不同结构：一个结果属于哪一类，或一个结果由哪些步骤共同完成。先说清“一个结果”究竟是什么，再决定相加还是相乘。

分类：互不重叠的结果相加

学校举办一场讲座，入场方式只有纸质票或电子票。若有效纸质票有 18 张、有效电子票有 12 张，且一张票只属于其中一种，则有效票一共 $18 + 12 = 30$ 张。把结果集合记为 $A$ 、 $B$ ，条件是 $A \cap B = \emptyset$ ，结论为 $| A \cup B | = | A | + | B |$ 。

若同一人可以同时持两种票，而所数对象是“可入场的人”，简单相加会重复数到双票持有人。此时应减去交集，见容斥原理。分类必须互斥，而且合在一起覆盖全部待数结果。

分步：每个完整结果都有一条选择路径

一张校园卡可选 3 种底色，每种底色都可配 2 种字样。完整设计由“底色、字样”一对选择确定，所以有 $3 \cdot 2 = 6$ 种。记底色集合为 $C$ 、字样集合为 $D$ ，结果集合就是笛卡尔积 $C \times D$ ，因而 $| C \times D | = | C | | D |$ 。

乘法要求每个前序选择后，后续可选数都按已说明的规则计算。若红色底只准配白字，另两种底色各可配两种字样，结果不是 $3 \cdot 2$ ，而是 $1 + 2 + 2 = 5$ 。图中从各底色分别伸出的枝条，就是这五个完整结果；先按底色分类，再在每类内数可用字样。

左侧红、蓝、绿三种底色各自连到右侧字样，红色只有一条连线，蓝色和绿色各有两条，合计五条完整路径 — 限制使三类分支数分别为 1、2、2；按底色相加得 5。

一般若第一步有 $m$ 种，而且不论第一步选什么第二步均有 $n$ 种，则结果数为 $m n$ 。有三步且每步可选数固定为 $m_{1}, m_{2}, m_{3}$ 时为 $m_{1} m_{2} m_{3}$ 。若后续选择数依赖前一步，先对第一步的每个分支单独数完，再把互斥分支相加： $\sum_{i} N_{i}$ 。这是一条由分类和分步共同得到的公式，而不是第三种计数原理。

先定义结果，再检查重复

从 6 人中选一位主持人与一位记录员，且不能兼任。结果是有职务次序的二人组，主持人有 6 种，记录员随后有 5 种，因此共有 $6 \cdot 5 = 30$ 种。若只选两名不分职务的志愿者，同一个二人组在刚才的 30 种中出现两次，答案应为 15。顺序是否重要将在排列与组合里正式处理。

试算。一份套餐可从米饭、面条中选一种主食。米饭可配 3 种菜，面条只可配其中 2 种。完整套餐数为 $3 + 2 = 5$ ，不能写成 $2 \cdot 3$ ；但若每种主食都能配这 3 种菜，才是 $2 \cdot 3 = 6$ 。两次计算的差别恰在“每个分支是否同样多”。

参考资料

MIT 6.042J《Mathematics for Computer Science》计数章节：分类、分步与一一对应。