计数原理

前置

• naive-set-theory-2

基本计数原理

设 $n$ 为非负整数。记 $[n]=\{1,\dots ,n\}$，并约定 $[0]=\varnothing$。

称集合 $A$ 的基数为 $n$，记 $|A|=n$，若存在双射 $A\to [n]$。

引理. $|[n]|=n$。若 $|A|=m$ 且 $|A|=n$，则 $m=n$。若 $|A|=m$ 且存在双射 $A\to B$，则 $|B|=m$。

加法原理. 设 $A\cap B=\varnothing$，且 $|A|=m$，$|B|=n$。则 $|A\cup B|=m+n$。

proof

对 $n$ 归纳。

$n=0$ 时 $B=\varnothing$，故 $A\cup B=A$，而自然数加法给出 $m+0=m$。

设 $|B|=n$ 时结论成立。现在 $|B|=n+1$。取双射 $g:B\to [n+1]$，令 $b=g^{-1}(n+1)$。$g$ 在 $B\setminus \{b\}$ 上的限制是到 $[n]$ 的双射，故 $|B\setminus \{b\}|=n$。并且 $A\cap (B\setminus \{b\})=\varnothing$。由归纳假设，$|A\cup (B\setminus \{b\})|=m+n$。$b$ 不在这个并中。把双射 $A\cup (B\setminus \{b\})\to [m+n]$ 延拓，把 $b$ 映到 $m+n+1$，得到到 $[m+n+1]$ 的双射。因此 $|A\cup B|=(m+n)+1$。自然数加法给出 $(m+n)+1=m+(n+1)$。

乘法原理. 设 $|A|=m$，$|B|=n$。则 $|A\times B|=mn$。

proof

取双射 $f:A\to [m]$、$g:B\to [n]$。$(x,y)\mapsto (f(x),g(y))$ 是 $A\times B$ 到 $[m]\times [n]$ 的双射。因此只要证明 $|[m]\times [n]|=mn$。对 $n$ 归纳。

$n=0$ 时 $[m]\times [0]=\varnothing$，基数为 $0$，而 $m\cdot 0=0$。

设 $|[m]\times [n]|=mn$。则

$$[m]\times [n+1]=([m]\times [n])\cup ([m]\times \{n+1\}),$$

右边两项不交。$(i,n+1)\mapsto i$ 是 $[m]\times \{n+1\}$ 到 $[m]$ 的双射，故第二项基数为 $m$。由加法原理，基数为 $mn+m$。自然数乘法给出 $mn+m=m(n+1)$。

容斥原理

称集合 $A$ 为有限集，若存在非负整数 $m$ 使 $|A|=m$。

引理. 设 $|A|=m$，且 $B\subseteq A$。则存在整数 $k$，$0\le k\le m$，使得 $|B|=k$ 且 $|A\setminus B|=m-k$。从而 $|A|=|B|+|A\setminus B|$。

proof

取双射 $f:A\to [m]$。令 $C=f(B)$。则 $C\subseteq [m]$。$f$ 在 $B$ 上的限制是 $B$ 到 $C$ 的双射，在 $A\setminus B$ 上的限制是 $A\setminus B$ 到 $[m]\setminus C$ 的双射。因此只要证明：若 $C\subseteq [m]$，则存在整数 $k$，$0\le k\le m$，使 $|C|=k$ 且 $|[m]\setminus C|=m-k$。对 $m$ 归纳。

$m=0$ 时 $[0]=\varnothing$，故 $C=\varnothing$。取 $k=0$。$|[0]\setminus C|=0$，而 $0-0=0$。

设已对某个 $m$ 成立：凡 $C\subseteq [m]$，都有这样的 $k$。现在设 $C\subseteq [m+1]$。映射 $m+1\mapsto 1$ 是 $\{m+1\}$ 到 $[1]$ 的双射，故 $|\{m+1\}|=1$。

若 $m+1\notin C$，则 $C\subseteq [m]$。由归纳假设，$|C|=k$ 且 $|[m]\setminus C|=m-k$，其中 $0\le k\le m$。此时

$$[m+1]\setminus C=([m]\setminus C)\cup \{m+1\},$$

右边两项不交。由加法原理，$|[m+1]\setminus C|=(m-k)+1$。自然数减法给出 $(m-k)+1=(m+1)-k$。又 $k\le m$，故 $k\le m+1$。

若 $m+1\in C$，令 $C^{\prime }=C\setminus \{m+1\}$。则 $C^{\prime }\subseteq [m]$，且 $C=C^{\prime }\cup \{m+1\}$，这两项不交。由归纳假设，$|C^{\prime }|=k$ 且 $|[m]\setminus C^{\prime }|=m-k$。加法原理给出 $|C|=k+1$。又 $[m+1]\setminus C=[m]\setminus C^{\prime }$，故其基数为 $m-k$。自然数减法给出 $m-k=(m+1)-(k+1)$。这里 $0\le k\le m$，故 $0\le k+1\le m+1$。

由归纳，对一切 $m$ 与一切 $C\subseteq [m]$，这样的 $k$ 存在。设 $|C|=k$。取双射 $C\to [k]$，与 $B$ 到 $C$ 的双射复合，得到 $B$ 到 $[k]$ 的双射，故 $|B|=k$。同样 $|A\setminus B|=m-k$。自然数加法给出 $k+(m-k)=m$，因此 $|A|=|B|+|A\setminus B|$。

命题. 设 $A,B$ 为有限集。则

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

proof

$A\cap B\subseteq B$，且 $B\setminus A\subseteq B$。$B$ 有限，由引理，这两集有限。

$B=(A\cap B)\cup (B\setminus A)$，两项不交。由加法原理，$|B|=|A\cap B|+|B\setminus A|$。

$A\cup B=A\cup (B\setminus A)$，两项不交。由加法原理，$|A\cup B|=|A|+|B\setminus A|$。

把后一式两边加上 $|A\cap B|$，再用前一式替换 $|B\setminus A|+|A\cap B|$：

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

因此 $|A|+|B|$ 等于 $|A\cap B|$ 与非负整数 $|A\cup B|$ 之和。自然数减法给出 $|A\cup B|=|A|+|B|-|A\cap B|$。

定理. 设 $n\ge 1$，$A_1,\dots ,A_n$ 为有限集。则

$$\left|\bigcup _{i=1}^n{A}_i\right|=\sum _{\varnothing \ne S\subseteq [n]}(-1{)}^{|S|+1}\left|\bigcap _{i\in S}{A}_i\right|.$$

右端在整数中计算：$|S|$ 为奇数时该项相加，$|S|$ 为偶数时该项相减。

proof

$S\subseteq [n]$ 非空时，取 $j\in S$，则 ${\bigcap }_{i\in S}{A}_i\subseteq A_j$。由引理，这个交有限。

对 $n$ 归纳。

$n=1$ 时，非空子集只有 $\{1\}$。映射 $1\mapsto 1$ 是 $\{1\}$ 到 $[1]$ 的双射，故 $|\{1\}|=1$，符号为 $(-1{)}^2=1$。右边就是 $|A_1|$。

设等式对某个 $n$ 与任意 $n$ 个有限集成立。现设 $A_1,\dots ,A_{n+1}$ 为有限集。记 $U_n={\bigcup }_{i=1}^n{A}_i$。归纳假设给出 $U_n$ 有限，且

$$|U_n|=\sum _{\varnothing \ne S\subseteq [n]}(-1{)}^{|S|+1}\left|\bigcap _{i\in S}{A}_i\right|.$$

对每个 $i\in [n]$，$A_i\cap A_{n+1}\subseteq A_i$，由引理有限。$x\in U_n\cap A_{n+1}$ 当且仅当 $x\in A_{n+1}$ 且有某个 $i\in [n]$ 使 $x\in A_i$，当且仅当有某个 $i\in [n]$ 使 $x\in A_i\cap A_{n+1}$。因此

$$U_n\cap A_{n+1}=\bigcup _{i=1}^n(A_i\cap A_{n+1}).$$

对这 $n$ 个有限集用归纳假设：

$$|U_n\cap A_{n+1}|=\sum _{\varnothing \ne T\subseteq [n]}(-1{)}^{|T|+1}\left|\bigcap _{i\in T}(A_i\cap A_{n+1})\right|.$$

对非空的 $T\subseteq [n]$，

$$\bigcap _{i\in T}(A_i\cap A_{n+1})=\bigcap _{i\in T\cup \{n+1\}}{A}_i.$$

$U_n$ 与 $A_{n+1}$ 有限。由两集合的命题，

$$|U_n\cup A_{n+1}|=|U_n|+|A_{n+1}|-|U_n\cap A_{n+1}|.$$

$n+1$ 个集合时，右边是

$$\sum _{\varnothing \ne S\subseteq [n+1]}(-1{)}^{|S|+1}\left|\bigcap _{i\in S}{A}_i\right|.$$

$[n+1]$ 的非空子集分成三类：不含 $n+1$ 的、等于 $\{n+1\}$ 的、以及形如 $T\cup \{n+1\}$ 的，其中 $T\subseteq [n]$ 且 $T\ne \varnothing$。

$T\subseteq [n]$ 时 $n+1\notin T$。$|[n]|=n$，由引理 $T$ 有限。映射 $n+1\mapsto 1$ 是 $\{n+1\}$ 到 $[1]$ 的双射，故 $|\{n+1\}|=1$。这两项不交，加法原理给出 $|T\cup \{n+1\}|=|T|+1$。因此第三类中 $S=T\cup \{n+1\}$ 的符号满足 $(-1{)}^{|S|+1}=(-1{)}^{|T|+2}$。$|T|+2$ 与 $|T|$ 同奇偶，故 $(-1{)}^{|T|+2}=(-1{)}^{|T|}$。$|T|+1$ 与 $|T|$ 奇偶相反，故 $(-1{)}^{|T|}=-(-1{)}^{|T|+1}$。第三类的和等于

$$\sum _{\varnothing \ne T\subseteq [n]}(-(-1{)}^{|T|+1})\left|\bigcap _{i\in T\cup \{n+1\}}{A}_i\right|=-|U_n\cap A_{n+1}|.$$

$\{n+1\}$ 的项是 $|A_{n+1}|$。不含 $n+1$ 的那些子集就是 $[n]$ 的非空子集，其和为 $|U_n|$。三类相加，右边的和等于 $|U_n|+|A_{n+1}|-|U_n\cap A_{n+1}|$，也就是 $|U_n\cup A_{n+1}|$。由归纳，等式对一切 $n\ge 1$ 成立。

$n=3$ 时，把 $[3]$ 的非空子集按基数展开。三个有限集 $A,B,C$ 满足

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

排列数

设 $n,k$ 为非负整数。

从 $[k]$ 到 $[n]$ 的单射全体为

$$P(n,k)=\{f:[k]\to [n]\mid f\text{ 是单射}\}.\text{\hspace{1em}(1)}$$

排列数是这个集合的基数 $A_n^k=|P(n,k)|$。

从 $[n]$ 中有序选取 $k$ 个不同元素的全体是

$$P(n,k)=\{(a_1,\dots ,a_k)\in [n{]}^k\mid i\ne j\Rightarrow a_i\ne a_j\}.\text{\hspace{1em}(2)}$$

$f\mapsto (f(1),\dots ,f(k))$ 是 (1) 与 (2) 之间的双射。$k=0$ 时空函数对应空元组。因此两个集合基数相同。

组合数

$[n]$ 的 $k$ 元子集全体为

$$C(n,k)=\{S\subseteq [n]:|S|=k\},\text{\hspace{1em}(3)}$$

组合数是 $C_n^k=|C(n,k)|$。

$0!=1$，并且 $n\ge 1$ 时 $n!=n(n-1)!$。$k>n$ 时 $[n]$ 没有 $k$ 元子集，故 $C_n^k=0$。

阶乘作为非负整数。$a\mid b$ 且 $a\ne 0$ 时，存在整数 $q$ 使 $b=qa$。整数无零因子，消去律给出 $q$ 唯一，记作 $b/a$。$c\ne 0$ 时 $(bc)/(ac)=b/a$。若两商的分母相同，则相加是分子相加后的商。下面的分式都是这个整数商。

命题. 设 $n,k$ 为非负整数且 $k\le n$。则 $k!(n-k)!\mid n!$，且

$$C_n^k=\frac{n!}{k!(n-k)!}.$$

proof

对 $n$ 用数学归纳法：对每个非负整数 $n$，凡 $0\le k\le n$，都有 $k!(n-k)!\mid n!$，且 $C_n^k=n!/(k!(n-k)!)$。

$n=0$ 时只有 $k=0$。$C_0^0=1$，而 $0!/(0!0!)=1$。

设等式对某个 $n$ 与一切 $0\le j\le n$ 已成立。现在证它对 $n+1$ 与一切 $0\le k\le n+1$ 成立。

$k=0$ 时，$[n+1]$ 只有一个空子集，故 $C_{n+1}^0=1=(n+1)!/(0!(n+1)!)$。$k=n+1$ 时，$C_{n+1}^{n+1}=1=(n+1)!/((n+1)!0!)$。

设 $1\le k\le n$。$C(n+1,k)$ 分成含 $n+1$ 与不含 $n+1$ 的两类。含 $n+1$ 的子集形如 $T\cup \{n+1\}$，$T\in C(n,k-1)$，故这类与 $C(n,k-1)$ 等势。不含 $n+1$ 的子集就是 $C(n,k)$。两类不交，并且并起来是 $C(n+1,k)$。由加法原理，

$$C_{n+1}^k=C_n^{k-1}+C_n^k.$$

归纳假设给出

$$C_n^{k-1}=\frac{n!}{(k-1)!(n-k+1)!},C_n^k=\frac{n!}{k!(n-k)!}.$$

$(n-k+1)!=(n+1-k)!$，$k(k-1)!=k!$。分子分母同乘 $k$ 或 $n+1-k$，商不变。两商分母相同，相加等于分子之和的商。因此

$$\begin{array}{rl}{C}_{n+1}^k& =\frac{n!k}{k!(n+1-k)!}+\frac{n!(n+1-k)}{k!(n+1-k)!}\\ & =\frac{n!(n+1)}{k!(n+1-k)!}=\frac{(n+1)!}{k!(n+1-k)!}.\end{array}$$

最后一步用定义 $(n+1)!=(n+1)n!$。由归纳，等式对一切 $n$ 与 $0\le k\le n$ 成立。