计数原理

贡献者：零穹

预备知识　集合的基数

　　¹本节介绍组合学里两个一般性的原则——加法原则和乘法原则。

　　以下假设 $A$ 和 $B$ 是两类不同、互不关联的事件。

1. 加法原则

　　 加法原则：设事件 $A$ 有 $m$ 种选取方式，事件 $B$ 有 $n$ 种选取方式，则选 $A$ 或 $B$ 共有 $m + n$ 种方式。

　　用集合的语言可将加法原则描述成如下定理（定理 4 ）：

定理 1　

　　设 $A, B$ 为有限集，且 $A \cap B = \emptyset$ ，则

\begin{matrix} (1) & | A \cup B | = | A | + | B | . \end{matrix}

推论 1　

　　设 $n$ 个有限集合 $A_{1}, \dots, A_{n}$ 满足

\begin{matrix} (2) & A_{i} \cap A_{j} = \emptyset, 1 \leq i \neq j \leq n, \end{matrix}

则

\begin{matrix} (3) & | ⋃_{i = 1}^{n} A_{i} | = \sum_{i = 1}^{n} | A_{i} | . \end{matrix}

2. 乘法原则

　　 乘法原则：设事件 $A$ 有 $m$ 种选取方式，事件 $B$ 有 $n$ 种选取方式，那么选取 $A$ 以后再选取 $B$ 共有 $m \cdot n$ 种方式。

　　同样，用集合的语言可将乘法原则描述成如下的定理：

定理 2　

　　设 $A, B$ 为有限集， $| A | = m, | B | = n$ ，则

\begin{matrix} (4) & | A \times B | = | A | \times | B | = m \cdot n . \end{matrix}

　　 证明：若 $m = 0$ 或 $n = 0$ ，则式 4 的两边均为 0，故等式成立。

　　设 $m > 0, n > 0$ ，并且记

\begin{matrix} (5) & A = {a_{1}, \dots, a_{m}}, B = {b_{1}, \dots, b_{n}} . \end{matrix}

定义映射

\begin{matrix} (6) & φ : (a_{i}, b_{j}) \to (i - 1) n + j (1 \leq i \leq m, 1 \leq j \leq n), \end{matrix}

则

φ

是

A \times B

到集合

{1, 2 \dots, m n - 1, m n}

上的一一映射（试证明），根据集合基数的定义（定义 1 ），式 4 成立。

　　 证毕！

　　注：乘法原则之所以能用定理 2 描述，是因为在乘法原则的描述中，选取 $A$ 以后再选取 $B$ ，这意味着 $A$ 与 $B$ 是有顺序的，这便使得选取 $A$ 再选取 $B$ 的方式能用笛卡尔积 $A \times B$ （子节 2 ）来描述（即二者一一对应）。比如：选取 $A$ 得到 $a_{i}$ ，再选取 $B$ 得到 $b_{j}$ 这样一种选取，可记为 $(a_{i}, b_{j})$ ；或将 $(a_{i}, b_{j})$ 理解为选取 $A$ 得到 $a_{i}$ ，再选取 $B$ 得到 $b_{j}$ 这样一种选取。

推论 2　

　　设 $A_{1}, \dots, A_{n}$ 为 $n$ 个有限集合，则

\begin{matrix} (7) & | A_{1} \times A_{2} \dots A_{n} | = | A_{1} | \times | A_{2} | \times \dots \times | A_{n} | . \end{matrix}

1. ^ 许胤龙，孙淑玲。组合数学引论（第二版）,中国科学技术大学出版社.2010.