3-4. 排容原理

Principle of Inclusion and Exclusion (PIE)

$U$: universal set, $a_1$, $a_2$, ..., $a_n$: 性質, $A_i$ = { $x \in U$ | $x$ 滿足 $a_i$ }, $N$($a_i$) = $|A_i|$, $N$($\bar{a_i}$) = $|\bar{A_i}|$
$\Rightarrow N$($\bar{a_i} \bar{a_j}$) = $|\bar{A_i} \cap \bar{A_j}|$ = $|U|$ - [$N$($a_i$) + $N$($a_j$)] + $N$($a_i \cap a_j$)
$\Rightarrow N$($\bar{a_i} \bar{a_j} \bar{a_k}$) = $|\bar{A_i} \cap \bar{A_j} \cap \bar{A_k}|$ = $|U|$ - [$N$($a_i$) + $N$($a_j$) + $N$($a_k$)] + [$N$($a_i \cap a_j$) + $N$($a_i \cap a_k$) + $N$($a_j \cap a_k$)] - $N$($a_i a_j a_k$)
$\Rightarrow \quad \vdots$
$\Rightarrow N$($\bar{a_1} \bar{a_2}$ ... $\bar{a_k}$) = $\color{red}{|U|}$ - $\color{orange}{\displaystyle\sum_{i=1}^n N(a_i)}$ + $\color{green}{\displaystyle\sum_{1 \le i < j \le n} N(a_i a_j)}$ - $\color{blue}{\displaystyle\sum_{1 \le i < j < k \le n} N(a_i a_j a_k)}$ + ... + $\color{purple}{(-1)^n N(a_1 a_2 ... a_n)}$
= $\color{red}{S_0}$ - $\color{orange}{S_1}$ + $\color{green}{S_2}$ - $\color{blue}{S_3}$ + ... + $\color{purple}{(-1)^n S_n}$, 其中 $S_r$ 含 $\dbinom{n}{r}$ 項之和

排容原理即文氏圖，只看 $U$ 與當下性質

Euler's Totient Function

$n \in Z^+$, $n$ = $P^{e_1}_1 P^{e_2}_2 ... P^{e_k}_k$ 為 $n$ 的質因數分解，則 $\phi$($n$) = $n$($1$ - $\dfrac{1}{P_1}$)($1$ - $\dfrac{1}{P_2}$)...($1$ - $\dfrac{1}{P_k}$)

proof: $k$ = $3$

$U$ = { $1$, $2$, ..., $n$ }, 令 $a_i$ 表 $P_i$ 之倍數, $i$ = $1$, $2$, $3$, $\phi$($n$) = $N$($\bar{a_1} \bar{a_2} \bar{a_3}$) = $S_0$ - $S_1$ + $S_2$ - $S_3$
= $n$ - [$\dfrac{n}{P_1}$ + $\dfrac{n}{P_2}$ + $\dfrac{n}{P_3}$] + [$\dfrac{n}{P_1 P_2}$ + $\dfrac{n}{P_1 P_3}$ + $\dfrac{n}{P_2 P_3}$] - $\dfrac{n}{P_1 P_2 P_3}$
= $n$[$1$ - ($\dfrac{1}{P_1}$ + $\dfrac{1}{P_2}$ + $\dfrac{1}{P_3}$) + ($\dfrac{1}{P_1 P_2}$ + $\dfrac{1}{P_1 P_3}$ + $\dfrac{1}{P_2 P_3}$) - $\dfrac{1}{P_1 P_2 P_3}$]
= $\dfrac{n}{P_1 P_2 P_3}$[$P_1 P_2 P_3$ - ($P_1 P_2$ + $P_1 P_3$ + $P_2 P_3$) + ($P_1$ + $P_2$ + $P_3$) - $1$]
= $\dfrac{n}{P_1 P_2 P_3}$($P_1$ - $1$)($P_2$ - $1$)($P_3$ - $1$) = $n$($\dfrac{P_1 - 1}{P_1}$)($\dfrac{P_2 - 1}{P_2}$)($\dfrac{P_3 - 1}{P_3}$) = $n$($1$ - $\dfrac{1}{P_1}$)($1$ - $\dfrac{1}{P_2}$)($1$ - $\dfrac{1}{P_3}$)

Theorem of Onto Function Amount

$A$, $B$: sets, $|A|$ = m, $|B|$ = n, $m \ge n$, 則 $f$: $A \rightarrow B$ onto 個數: $onto$($m$, $n$) = $\displaystyle\sum_{i=0}^n$($-1$)$^i \dbinom{n}{i}$($n$ - $i$)$^m$

$m$ 個相異球放入 $n$ 個相異箱子，不允許空箱之方法數

proof:

$U$ = { $f$ | $f$: $A \rightarrow B$ } $\Rightarrow |U|$ = $n^m$, 令 $a_i$ 表示 $U$ 中函數滿足值域不含 $b_i$ 之條件(第 $i$ 個箱子為空), $i$ = $1$, ..., $n$
$\Rightarrow onto$($m$, $n$) = $N$($\bar{a_1} \bar{a_2}$ ... $\bar{a_n}$) = $S_0$ - $S_1$ + $S_2$ - $S_3$ + ... + ($-1$)$^n S_n$
= ${\color{red}{\dbinom{n}{0}}} n^m$ - $\dbinom{n}{1}$($n$ - $1$)$^m$ + $\dbinom{n}{2}$($n$ - $2$)$^m$ - $\dbinom{n}{3}$($n$ - $3$)$^m$ + ... + ($-1$)$^n \dbinom{n}{n}$($n$ - $n$)$^m$
= $\displaystyle\sum_{i=0}^n$($-1$)$^i \dbinom{n}{i}$($n$ - $i$)$^m$

($-1$)$^n \dbinom{n}{n}$($n$ - $n$)$^m$ = $0$

Stirling Number of The Second Kind

$m$, $n \in Z$, $m \gt n \gt 1$
$S$($m$, $n$) = $\dfrac{onto(m, n)}{n!}$ = $\dfrac{\displaystyle\sum_{i=0}^n (-1)^i \dbinom{n}{i} (n - i)^m}{n!}$
稱為第二種 Stirling 數(Stirling number of the second kind)

• 當 $m$ < $n$ 時，$S$($m$, $n$) = $0$

$m$ 個相異球放入 $n$ 個相同箱子，不允許空箱之方法數

$\rightarrow m$ 個相異球放入 $n$ 個相同箱子，允許空箱之方法數?

$S$($m$, $n$) + $S$($m$, $n$ - $1$) + ... + $S$($m$, $1$)

• $S$($m$, $n$): $0$ 個空箱
• $S$($m$, $n$ - $1$): $1$ 個空箱
  ...
• $S$($m$, $1$): $n$ - $1$ 個空箱

Theorem of S(m, n)

$m$, $n \in N$, $m \gt n \gt 2$, $S$($m$ + $1$, $n$) = $S$($m$, $n$ - $1$) + $n S$($m$, $n$)

proof:

$S$($m$ + $1$, $n$): $m$ + $1$ 相異物分成恰 $n$ 箱，固定一物 $A$

1. $A$ 所在的箱子只有 $A$: $S$($m$, $n$ - $1$)
2. $A$ 所在的箱子不只有 $A$: $n S$($m$, $n$) $\rightarrow$ 先放除 $A$ 之外的 $m$ 個相異物入 $n$ 箱，再從其中任一箱放入 $A$

Table of S(m, n)

$Example$:
$\quad$ $onto$($6$, $3$) + $onto$($6$, $3$) = ?
$solution$:
$\quad$ $90$($3!$) + $65$($4!$)