Principle of inclusion and exclusion（排容原理）
假設 \(U\) 為與集合，其中 \(|U| = N\)，令 \(a_1, a_2, ..., a_n\) 為 n 個性質，其中這些性質直接定義在 \(U\) 上且 \(N(a_i)\) 表示 \(U\) 中滿足性質 \(a_i\) 的元素個數。
- 定義
- \(N(\bar{a_i})\) 表示 \(U\) 中不滿族性質 \(a_i\) 的元素個數。
- \(N(a_ia_j)\) 表示 \(U\) 中同時滿足性質 \(a_i\) 與 \(a_j\) 的元素個數。
- \(N(\bar{a_i}\bar{a_j})\) 表示 \(U\) 中同時滿足性質 \(a_i\) 與 \(a_j\) 的元素個數。
Lemma 1
若有一數 \(n\) 有正因數解，該組解必有一正因數「小於等於」\(\sqrt{n}\)。
Proof
若兩正因數都大於 \(\sqrt{n}\) ，相乘後不可能為 \(n\)
Ex ( 97 清大 )
1 ~ 100 中質數有幾個？
Sol
\[ \because \sqrt{100} = 10 \therefore Consider: 2, 3, 5, 7\\ \begin{matrix} 令 & \; U \; 表示 2 到 100 的所有數所成集合，則 \; N = |U| = 99 \\ & a_1 表示 U 中大於 2 且為 2 的倍數的性質 \\ & a_2 表示 U 中大於 3 且為 3 的倍數的性質 \\ & a_3 表示 U 中大於 5 且為 5 的倍數的性質 \\ & a_4 表示 U 中大於 7 且為 7 的倍數的性質 \end{matrix} \\ 欲求: N(\bar{a_1}\bar{a_2}\bar{a_3}\bar{a_4})\\ \Rightarrow 100 - (\lfloor\frac{100}{2}\rfloor + \lfloor\frac{100}{3}\rfloor+ \lfloor\frac{100}{5}\rfloor+ \lfloor\frac{100}{7}\rfloor) + \\ (\lfloor\frac{100}{6}\rfloor + \lfloor\frac{100}{15}\rfloor+ \lfloor\frac{100}{35}\rfloor+ \lfloor\frac{100}{10}\rfloor + \lfloor\frac{100}{14}\rfloor + \lfloor\frac{100}{21}\rfloor) - \\ (\lfloor\frac{100}{30}\rfloor + \lfloor\frac{100}{70}\rfloor+\lfloor\frac{100}{105}\rfloor + \lfloor\frac{100}{42}\rfloor) + \lfloor\frac{100}{350}\rfloor\\ = 22 -1 + 4 = 25 \]
Ex ( 97 台大 ) 尤拉公式說明
\(n = P_1^{e_1}\times P_2^{e_2}\times P_3^{e_3}, P_i \;is \;prime , e_i > 0\quad Prove: \Phi(n) = n\times(1 - \frac1{P_1}) \times (1 - \frac1{P_2}) \times (1 - \frac1{P_3})\)
Proof
\[ U = ｛1, ..., n｝, a_1 = ｛1 < x < n \;\vert\; P_1|x ｝, a_2 = ｛1 < x < n \;\vert\; P_2|x ｝, a_3 = ｛1 < x < n \;\vert\; P_3|x ｝\\ 求 \; N(\bar{a_1}\bar{a_2}\bar{a_3}) \\ \Rightarrow n - (\frac{n}{P_1}+\frac{n}{P_2}+\frac{n}{P_3}) + (\frac{n}{P_1P_2} + \frac{n}{P_2P_3} + \frac{n}{P_1P_3}) - \frac{n}{P_1P_2P_3} \\ = n \times (1-(\frac{1}{P_1}+\frac{1}{P_2}+\frac{1}{P_3}) + (\frac{1}{P_1P_2} + \frac{1}{P_2P_3} + \frac{1}{P_1P_3}) - \frac{1}{P_1P_2P_3}) \\ = n\times(1 - \frac1{P_1}) \times (1 - \frac1{P_2}) \times (1 - \frac1{P_3}) \]
Theorem
m 個相異物放置 n 個相異箱子「不允許」空箱的方法數。
\(|A| = m, |B| = n, m\geq n \Rightarrow onto(m, n) = \sum_{i = 0}^n(-1)^i\binom{n}{i}(n-i)^m\) ( 由 A 集合至 B 集合的映成函數個數 )
箱子不得為「空」，採用排容原理。
Proof
\[ onto(m, n) = n^m - \binom{n}{1}(n-1)^m + \binom{n}{2}(n-2)^m - ... + (-1)^{n-1}\binom{n}{n-1}(1)^m + (-1)^{n}\binom{n}{n}(0)^m\\ = \sum_{i = 0}^n(-1)^i\binom{n}{i}(n-i)^m \]
Stirling number of the second kind
＜Note＞ 分堆
m 個相異物放置於 n 個相同箱子「不允許空箱」的方法數，也就是將「映成函數個數」扣除重複計算到相同箱子的個數
- 假設 \(m, n\) 為兩個整數，其中 \(m \geq n \geq 1\)，定義
\[ S(m, n) = \frac{onto(m, n)}{n!} = \frac{\sum_{i = 0}^n(-1)^i\binom{n}{i}(n-i)^m}{n!} \]
稱為第二種 Stirling 數，有時記作 \(\begin{Bmatrix} m \\ n \end{Bmatrix}\) ，另外為了方便起見，當 \(m < n\) 時，定義 \(S(m, n) = 0\)
＜Note＞
m 個相異物放置於 n 個相同箱子「允許空箱」的方法數 \[ = S(m, n) + S(m, n-1)+S(m, n-2)+\ldots+S(m, 2)+S(m, 1) \]
Theorem - 第二種 Stirling 數的遞迴結構
可用在演算法的使用上，通常以「Dynamic programming」的方式撰寫。
\[ S(m+1, n) = S(m, n-1)+S(m, n) \]
- Dynamic programming ( 直向軸為 m，橫向軸為 n )
1 2 3 4 5 6 7 1 S(1, 1) = 1 - - - - - - 2 S(2, 1) = 1 S(2, 2) = 1 - - - - 3 S(3, 1) = 1 S(3, 2) = 3 S(3, 3) = 1 - - - - 4 S(4, 1) = 1 S(4, 2) = 7 S(4, 3) = 6 S(4, 4) = 1 - - - 5 S(5, 1) = 1 S(5, 2) = 15 S(5, 3) = 25 S(5, 4) = 10 S(5, 5) = 1 - - 6 S(6, 1) = 1 S(6, 2) = 31 S(6, 3) = 90 S(6, 4) = 65 S(6, 5) = 15 S(6, 6) = 1 -
- 使用方法
- 欲求 \(onto(6, 3) + onto(6, 4)\)
- 查表加上轉換後：\(90\times 3! +65\times 4!\)
Proof ( 組合證法 )
- S(m+1, n)：m+1 個相異物分成 n 堆，固定一物 A
- A 為邊緣人\(\Rightarrow S(m, n-1)\)
- A 有孤單病，所以在 n 堆中挑一堆進入 \(\Rightarrow S(m, n)\times n\)