两条计数原理

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

1 · 乘法原理

设想配一份套餐：先从 $a$ 种主菜里选一种，再从 $b$ 种饮料里选一种。第一步的每个选择都能接上第二步的全部 $b$ 种，于是选择树在第二层各自展开 $b$ 个分支，叶子即完整套餐共 $a \times b$ 个。

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

2 · 加法原理

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

判据只有一句：各部分之间是「而且」还是「或者」。「而且」按步走，相乘；「或者」分类走，相加。复杂问题往往两者交织，先分类相加，每类内部再分步相乘。

3 · 参考文献

1. Rule of product. Wikipedia. 乘法原理的表述与例子。https://en.wikipedia.org/wiki/Rule_of_product
2. Rule of sum. Wikipedia. 加法原理，以及它与容斥原理的关系。https://en.wikipedia.org/wiki/Rule_of_sum