counting · 乘法 / 加法原理

两条计数原理：分步相乘、分类相加

几乎所有「有多少种」的问题，都能拆到两条最基本的原理上。乘法原理(rule of product)：一件事需要依次完成若干步，若第一步有 a 种做法、每种做法下第二步都有 b 种……则总做法数是各步之积。加法原理(rule of sum)：一件事可以归入互斥的若干类，每类各自完成，则总做法数是各类之和。分清眼前是「分步」还是「分类」，是列式的第一步。

1 · 乘法原理：分步做，方案数相乘

rule of product · a × b

设想「配一份套餐」：先从 a 种主菜里选一种，再从 b 种饮料里选一种。第一步的每个选择，都能接上第二步的全部 b 种——于是选择树在第二层各自展开 b 个分支，叶子（完整套餐）共 $a \times b$ 个。拖动两步的选法数，看树如何变宽。

推广到 k 步：各步分别有 $n_1, n_2, \dots , n_k$ 种做法，总数是 $n_1 \times n_2 \times \dots \times n_k$ 。若每步都是从同样的 n 个里选（且可重复），就是 $n \times n \times \dots \times n = n^k$ ——这正是「有序、可放回」的取样。排列 P(n, k)则是每步从剩下的元素里选，方案数逐格收缩。

2 · 加法原理：分类做，方案数相加

rule of sum · p + q

换一种情形：从北京到上海，可以坐高铁（p 个班次）或坐飞机（q 个航班）。两类方式互斥——一次出行只属于其中一类，不像「先……再……」那样叠加。于是总方案数是两类之和 p + q，而非乘积。

判据只有一句：各部分之间是「而且（先做完这步再做下一步）」还是「或者（归入某一类即可）」。「而且」按步走，相乘；「或者」分类走，相加。复杂问题往往两者交织——先分类相加，每类内部再分步相乘。

3 · 相关链接

Rule of product — Wikipedia · en.wikipedia.org——乘法原理的表述与例子。
Rule of sum — Wikipedia · en.wikipedia.org——加法原理，以及它与容斥原理的关系。