计数原理

这正是把每种互不重叠的情形分别计数再相加这一日常做法的严格表述:之所以成立,正是因为不相交保证了没有结果会被重复计数。

第一步(基础情形 $k=2$):设 $A_1$ 与 $A_2$ 不相交,即 $A_1 \cap A_2 = \emptyset$。$A_1 \cup A_2$ 中的每个元素要么属于 $A_1$,要么属于 $A_2$,不相交排除了同时属于两者的可能。将 $A_1 \cup A_2$ 拆成两个不相交的部分 $A_1$ 与 $A_2$,各数一次即得 $|A_1 \cup A_2| = |A_1| + |A_2|$。

第二步(对 $k$ 归纳):假设公式对任意 $k-1$ 个两两不相交的集合已经成立,即 $|A_1 \cup \cdots \cup A_{k-1}| = |A_1| + \cdots + |A_{k-1}|$。令 $B = A_1 \cup \cdots \cup A_{k-1}$。由于 $A_k$ 与所有满足 $i < k$ 的 $A_i$ 不相交,它也与它们的并集 $B$ 不相交。对 $B$ 与 $A_k$ 应用基础情形,得到 $|B \cup A_k| = |B| + |A_k|$。

第三步(合并):把归纳假设中的 $|B|$ 代入上式,得到 $|A_1 \cup \cdots \cup A_k| = |A_1| + \cdots + |A_{k-1}| + |A_k|$,这正是 $k$ 个集合的加法原理。由于基础情形 $k=2$ 成立,且从 $k-1$ 到 $k$ 的每一步都保持公式成立,由归纳法可知该公式对所有 $k \geq 2$ 都成立。

由于每一步的选择数不依赖于前面的步骤,所以每一种选择组合都是一个不同的合法结果,组合的数目恰好像数矩形网格中的格子那样相乘。

第一步(基础情形 $k=1$):只有一个步骤时显然有 $N_1 = n_1$ 种方法,与 $k=1$ 时的公式一致。

第二步(基础情形 $k=2$):对完成第1步的 $n_1$ 种方法中的每一种,第2步仍然有 $n_2$ 种做法,因为它的数目不依赖于第1步的结果。这样,所有选择对被分成 $n_1$ 个不相交的组,每组大小为 $n_2$(每种第1步结果对应一组),于是加法原理给出总数为 $n_2$ 自加 $n_1$ 次,即 $N_2 = n_1 \cdot n_2$。

第三步(对 $k$ 归纳):假设公式对 $k-1$ 个步骤成立,即前 $k-1$ 个步骤合起来共有 $N_{k-1}$ 种结果。把这 $k-1$ 个步骤看成一个结果数为 $N_{k-1}$ 的“合成步骤”,把第 $k$ 步看成第二个独立步骤,结果数为 $n_k$(其数目仍不依赖于之前的选择)。对这两步应用两步的基础情形,得到 $N_k = N_{k-1} \cdot n_k$,即 $N_k = n_1 \cdot n_2 \cdots n_k$。由归纳法,该公式对所有 $k$ 都成立。