做计数题时，先弄清有多少种选择，再检查有没有把同一个结果重复计数。

Cardinality

有限集 $A$ 的 cardinality 记作 $|A|$，表示 $A$ 中的元素个数。例如，

$$A=\{2,5,7\} \qquad\Longrightarrow\qquad |A|=3.$$

Empty set 没有元素，而以 empty set 为唯一元素的集合含有一个元素：

$$|\varnothing|=0 \qquad\text{but}\qquad |\{\varnothing\}|=1.$$

这里 $|A|$ 中的竖线表示 cardinality，不是 absolute value。

Product principle

当一个结果由连续几步选择组成时，可以使用 product principle，也叫 multiplication principle。如果第一步有 $m$ 种选择，而且无论第一步选什么，第二步都有 $n$ 种选择，那么共有

$$m\cdot n$$

种选择结果。步骤更多时，把每一步的选择数相乘。每一步的选择数必须对前面所有可行的选择都相同，才能直接这样相乘。

对有限集 $A$、$B$，这就给出了 Cartesian product 的 cardinality：

$$|A\times B|=|A|\,|B|.$$

若 $A=\{2,5,7\}$ 且 $B=\{1,2\}$，则

$$|A\times B|=3\cdot2=6.$$

例：加拿大邮政编码的格式

用一个简化模型来计数：设 $L$ 是 26 个大写字母组成的集合，$D$ 是 10 个数字组成的集合：

$$L=\{\mathrm A,\mathrm B,\ldots,\mathrm Z\}, \qquad D=\{0,1,\ldots,9\}.$$

加拿大邮政编码采用字母、数字交替的格式：

$$L\,D\,L\;D\,L\,D.$$

这个模型暂不考虑实际邮政编码对字母及位置的限制。三个字母位置和三个数字位置都可以独立选择，并允许字符重复，因此符合这个简化格式的字符串共有

$$26\cdot10\cdot26\cdot10\cdot26\cdot10 =26^3\cdot10^3 =17{,}576{,}000.$$

例如，圣诞老人的邮政编码 H0H 0H0 符合这个格式。其中的 0 都是数字零，不是字母 O。上面的结果是格式模型的计数，不是实际可用邮政编码的数量。

为什么 power set 有 $2^n$ 个元素

Power set $\mathcal P(A)$ 包含 $A$ 的所有 subset。设

$$A=\{a_1,a_2,\ldots,a_n\}.$$

选择一个 subset $X\subseteq A$ 时，对每个元素 $a_i$ 都要作一个决定：

• 把 $a_i$ 放入 $X$；或
• 不把 $a_i$ 放入 $X$。

一共有 $n$ 个元素，每个都有两种选择，所以 product principle 给出

$$|\mathcal P(A)|=2^n=2^{|A|}.$$

对 empty set，这个公式也成立：

$$|\mathcal P(\varnothing)|=2^0=1,$$

因为 $\mathcal P(\varnothing)=\{\varnothing\}$。

Sum principle

如果是在几种互不重叠的情况中任选一种，就把各情况的数量相加。

两个集合没有共同元素时，称它们 disjoint：

$$A\cap B=\varnothing.$$

对 disjoint finite sets，sum principle（也叫 addition principle）给出

$$|A\cup B|=|A|+|B|.$$

集合不重叠，因此不会重复计数。同一规则适用于任意有限多个两两 disjoint 的有限集。

例：长度为 6、7 或 8 的用户名

假设用户名可以使用大写字母、小写字母和数字，那么可用字符共有

$$26+26+10=62$$

种。

用 $S_n$ 表示长度为 $n$ 的所有有效用户名组成的集合。允许重复使用字符，所以 product principle 给出

$$|S_6|=62^6, \qquad |S_7|=62^7, \qquad |S_8|=62^8.$$

一个字符串不可能同时有两种长度，因此 $S_6$、$S_7$、$S_8$ 两两 disjoint。由 sum principle，

$$|S_6\cup S_7\cup S_8| =62^6+62^7+62^8 =221{,}918{,}520{,}426{,}688.$$

Complement principle

设 $A\subseteq B$，且 $B$ 是有限集。Complement principle 用总数减去不需要的部分，得到属于 $B$ 但不属于 $A$ 的元素个数：

$$|B\setminus A|=|B|-|A|.$$

这是因为 $B$ 可以拆成两个不重叠的部分：

$$B=A\cup(B\setminus A).$$

$A$ 和 $B\setminus A$ 不重叠，所以 sum principle 给出

$$|B|=|A|+|B\setminus A|.$$

把这个等式移项，解出 $|B\setminus A|$，就得到了 complement principle。

例：至少含有一个数字的用户名

“至少有一个数字”的反面是“一个数字都没有”。后者只需要数纯字母的用户名，再从总数中减去它们。

设 $B$ 是长度为 6、7 或 8 的所有有效用户名组成的集合，$A\subseteq B$ 则只包含没有数字的用户名。$B$ 中的用户名可以使用全部 62 种字符，$A$ 中的用户名只能使用 52 个字母。因此，

$$\begin{aligned} |B|&=62^6+62^7+62^8,\\ |A|&=52^6+52^7+52^8. \end{aligned}$$

$B\setminus A$ 恰好包含至少有一个数字的用户名。由 complement principle，

$$\begin{aligned} |B\setminus A| &=(62^6+62^7+62^8)-(52^6+52^7+52^8)\\ &=167{,}410{,}949{,}583{,}040. \end{aligned}$$

两个集合的 inclusion–exclusion

如果有限集 $A$ 和 $B$ 有重叠，直接相加 $|A|+|B|$ 会把 $A\cap B$ 中的每个元素算两次：在 $A$ 中算一次，在 $B$ 中又算一次。

Inclusion–exclusion principle 把重叠部分减去一次，修正重复计数：

$$|A\cup B|=|A|+|B|-|A\cap B|.$$

1. Count A2. Add B3. The overlap was counted twice4. Subtract one copy of A ∩ B

也可以把 union 拆成三个互不重叠的区域来理解这个公式：

$$A\setminus B, \qquad A\cap B, \qquad B\setminus A.$$

这些区域互不重叠，可以直接把它们的大小相加：

$$\begin{aligned} |A\cup B| &=|A\setminus B|+|A\cap B|+|B\setminus A|\\ &=(|A|-|A\cap B|)+|A\cap B|+(|B|-|A\cap B|)\\ &=|A|+|B|-|A\cap B|. \end{aligned}$$

例：bit strings

一个 bit 只能是 $0$ 或 $1$。长度为 8 的 bit string 中，有多少个以 $1$ 开头或以 $00$ 结尾？

设

$$A=\{\text{length-8 bit strings that start with }1\}$$

以及

$$B=\{\text{length-8 bit strings that end with }00\}.$$

对 $A$，第一位已经固定，剩下七位可以自由选择，所以

$$|A|=2^7.$$

对 $B$，最后两位已经固定，剩下六位可以自由选择，所以

$$|B|=2^6.$$

$A\cap B$ 中的字符串既以 $1$ 开头，又以 $00$ 结尾，剩下五个位置可以自由选择，因此

$$|A\cap B|=2^5.$$

由 inclusion–exclusion，

$$|A\cup B|=2^7+2^6-2^5=160.$$

三个及更多集合的 inclusion–exclusion

对三个有限集，inclusion–exclusion 写成

$$\begin{aligned} |A\cup B\cup C| ={}&|A|+|B|+|C|\\ &-|A\cap B|-|A\cap C|-|B\cap C|\\ &+|A\cap B\cap C|. \end{aligned}$$

先加上三个集合的大小，再减去三个两两 intersection。一个同时属于三个集合的元素，先被加了三次，又被减了三次，此时完全没有被算进去，所以还要把 triple intersection 加回一次。

对有限集 $A_1,A_2,\ldots,A_n$，可以把这个规律展开为

$$\begin{aligned} |A_1\cup A_2\cup\cdots\cup A_n| ={}&|A_1|+|A_2|+\cdots+|A_n|\\ &-\bigl(|A_1\cap A_2|+|A_1\cap A_3|+\cdots+|A_{n-1}\cap A_n|\bigr)\\ &+\bigl(|A_1\cap A_2\cap A_3|+\cdots+|A_{n-2}\cap A_{n-1}\cap A_n|\bigr)\\ &-\text{all quadruple intersections}\\ &+\text{all quintuple intersections}-\cdots\\ &+(-1)^{n+1}|A_1\cap A_2\cap\cdots\cap A_n|. \end{aligned}$$

参与 intersection 的集合越多，符号就这样交替：

1. 加上每个集合的大小；
2. 减去所有两两 intersection 的大小；
3. 加上所有 triple intersection 的大小；
4. 减去所有 quadruple intersection 的大小；
5. 加上所有 quintuple intersection 的大小，之后继续交替。

对四个集合，具体就是：加上四个集合的大小，减去六个两两 intersection，加上四个 triple intersection，最后减去四个集合共同的 intersection。

例：三个条件都不满足的整数

从 1 到 1000 的整数中，有多少个既不是 perfect square，也不是 perfect cube，还不是 7 的倍数？

设

$$U=\{1,2,\ldots,1000\},$$

并定义

$$\begin{aligned} A&=\{n\in U\mid n=k^2\text{ for some integer }k\},\\ B&=\{n\in U\mid n=k^3\text{ for some integer }k\},\\ C&=\{n\in U\mid 7\text{ divides }n\}. \end{aligned}$$

这里 $A$ 包含 perfect squares，$B$ 包含 perfect cubes，$C$ 包含 7 的倍数。

Floor function $\lfloor x\rfloor$ 表示不超过 $x$ 的最大整数。这里要数的是整数平方根、整数立方根的可选个数，所以用 floor function 得到

$$|A|=\left\lfloor\sqrt{1000}\right\rfloor=31, \qquad |B|=\left\lfloor\sqrt[3]{1000}\right\rfloor=10,$$

以及

$$|C|=\left\lfloor\frac{1000}{7}\right\rfloor=142.$$

接着计算各个 intersection：

• 一个正整数既是 square 又是 cube，当且仅当它是 sixth power，所以 $$|A\cap B|=\left\lfloor\sqrt[6]{1000}\right\rfloor=3.$$
• 一个 square 若能被 7 整除，它的平方根也能被 7 整除。在 $1,2,\ldots,31$ 中有四个 7 的倍数，因此 $$|A\cap C|=4.$$
• 一个 cube 若能被 7 整除，它的立方根也能被 7 整除。在 $1,2,\ldots,10$ 中只有 $7$ 符合条件，所以 $$|B\cap C|=1.$$
• 同时属于三个集合的数必须是 sixth power，而且底数能被 7 整除。最小的正整数候选是 $7^6=117{,}649>1000$，因此 $$|A\cap B\cap C|=0.$$

由 inclusion–exclusion，

$$|A\cup B\cup C| =31+10+142-3-4-1+0 =175.$$

题目要的是三个集合之外的数，因此从 $U$ 的大小中减去 union 的大小：

$$\begin{aligned} |U\setminus(A\cup B\cup C)| &=|U|-|A\cup B\cup C|\\ &=1000-175\\ &=825. \end{aligned}$$