發刊日期 |
2009年9月
|
|||||||||||||||||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
標題 | 排容原理 |
|||||||||||||||||||||||||||||||||||||||||||
作者 | ||||||||||||||||||||||||||||||||||||||||||||
關鍵字 | ||||||||||||||||||||||||||||||||||||||||||||
檔案下載 | ||||||||||||||||||||||||||||||||||||||||||||
全文 |
1. 前言在組合數學中, 常需討論有關集合元素個數的問題, 而重複計數卻是造成結果錯誤的一大主因, 故需再進一步討論所有可能重複的情況, 此時「排容原理」是一個能夠解決關於多個具有某些性質的非互斥集合其交集與聯集計數問題的有效方法, 能輕易的將重複計數的困擾排除。 排容原理是一個很容易使用的計數方法, 而它最早被使用的歷史可追溯到早期的一些手稿中, 以篩選方法( Sieve Method) 或交叉分類法則 ( Principle of Cross Classification) 等不同的名稱出現, 而其所考慮到集合的交集與聯集的觀點, 可在 18 世紀著名數學家 DeMoivre (1667-1754) 的著作 Doctrine of Chances (1718) 中找到相關的論述。 但在更早之前, 法國數學家de Montmort (1678-1719) 在 1708 年時便已使用了這個想法解決撲克牌的配對問題。 而現今所闡述與使用的排容原理是由英國數學家Sylvester (1814-1897) 所建立。 但在早期排容原理這一種計數技巧並未獲得重視, 一直到由 Whitworth 所撰寫的"選擇與機會 (Choice and Chance)"這本大眾書籍問世後, 才使得數學家開始注意到排容原理的用途。也因為排容原理簡單明瞭, 所以在其他領域更是被廣泛的應用, 例如著名的 Möbius 反轉公式。 Balakrishnan (1994) 由計數的基本原理開始, 利用方法、定義及概念的歸納與推廣, 對排容原理作全面的論述。 Ross (2006) 利用基本概念的推廣, 來介紹在機率中的排容原理。 單壿、 葛軍 (1991) 介紹了在數學奧林匹克如何運用排容原理來解決相關題目。 Gelca and Andreescu (2007) 收錄北美著名的 Putnam 數學競賽考題。 中國數學奧林匹克委員會和開南大學數學系 (2002) 收錄了各國奧林匹克的訓練題或比賽題目。 讀者若想對排容原理有深入的瞭解, 可參考以上書目。 本文主要的目的是對於排容原理做全面性的介紹, 首先透過一些淺顯易懂的例子來熟悉排容原理的基本定義及定理, 接下來再舉出數個條件個數由少 $(n=1)$ 到多 $(n\ge 4)$ 的例子, 針對不同的情況適當的使用排容原理來求解。 一旦學會了排容原理的技巧及其使用的時機, 在處理各種計數問題時, 重複計數便可輕鬆解決。 而在第二節先介紹排容原理兩種基本的型式及其應用, 第三節介紹如何透過排容原理證明出尤拉公式及映成函數的對應問題, 第四節介紹排容原理在機率問題上的應用, 第五節則舉出一些在數學競賽中出現有關排容原理的題目。 2. 排容原理在開始介紹排容原理的內容前, 我們先給出一些符號介紹: 若三個集合 $A$, $B$, $C$ 滿足:
若三個集合 $A$, $B$, $C$ 滿足:
取集合 $A$ 是宇集合 $S$ 的一個子集合, 以記號 $\overline{A}$ 表示其元素屬於 $S$ 而不屬於 $A$ 的集合, 則稱 $\overline{A}$ 為 $A$ 的補集合。 而用記號 $|A|$ 來表示 $A$ 的元素個數, 則集合 $A$ 的元素個數, 等於 $S$ 的所有元素個數減去屬於 $S$ 但不屬於集合 $A$ 的元素個數, 故可以用 下列形式來表示 \begin{equation} \label{eqn:2755875} %(1) |\overline{A}| = |S| - |A| \end{equation} 以下舉出幾個例子, 利用式子$(\ref{eqn:2755875})$來計算答案。
解: 假設 $S$ 為從 54 位專家中選取 3 位的所有取法形成的集合, 故 $|S|={54\choose 3}$。 而令 $A$ 表示沒有任何一位心理學家被選取, 故題意所求即為 $|\overline{A}|$。 $A$ 表示被選取的 $3$ 位專家中, 沒有心理學家, 故選法共有 $|A|={30\choose 3}$。 因此根據題意, 此 3 位主持人的選法有 \begin{eqnarray*} ~\hskip 3cm|\overline{A}| &=& |S| - |A| \\ &=& {54 \choose 3} - {30 \choose 3} = 24804 - 4060 = 20744\hskip 3.5cm\Box \end{eqnarray*}
解: 假設 $S$ 為 $1, 2, \ldots, 100$ 的數所形成的集合, 所以 $|S|={100 \choose 2}$。 而令 $A$ 表示從 $1, 2, \ldots, 100$ 中選出的兩個數和為奇數, 則題意即為求 $|\overline{A}|$。 因為取出兩數和需為奇數, 則此兩數必為一奇一偶, 所以其選取方式有 $|A|={50 \choose 1}{50 \choose 1}$ 種, 因此取出兩數和為偶數的取法 \begin{eqnarray*} ~\hskip 4cm|\overline{A}| &=& |S| - |A| \nonumber\\ &=& {100 \choose 2} - {50 \choose 1}{50 \choose 1} = 2450\hskip 4cm\Box \end{eqnarray*} 以下為求兩補集合交集元素個數的問題, 並提供了三種不同的計算方法。
解: 設 $S$ 表示所有壁報紙所形成的集合, $A_1$ 表示長度達到 150 公分的壁報紙所形成的集合, $A_2$ 表示寬度達到 100 公分的壁報紙所形成的集合, 則題意即為求 $|\overline{A_1}\,\overline{A_2}|$。 由題意知 $|S|=50$, $|A_1|=35$, $|A_2|=40$, $|A_1A_2|=30$。
前面三個例子已經引出排容原理的基本雛形, 如 (\ref{eqn:8406815}) 式, 接下來的定理將給出排容原理完整的敘述及其證明。完整的敘述及其證明。
證明:
接下來舉一些簡易的例子, 說明當滿足多個條件時, 如何適當的使用兩種排容原理來幫助我們計算。
解: 假設 $S$ 為這 $8$ 個元素做直線排列所有可能形成的集合, 所以 $|S|=8!$。 而令 $A_1$ 表示在 $S$ 中出現 $abc$ 的直線排列, $A_2$ 表示在 $S$ 中出現 $efgh$ 的直線排列, 故題意即為求 $|\overline{A_1}\,\overline{A_2}|$。 $A_1$ 表示出現 $abc$ 的排列方式, 相當於集合 $\{abc, d, e, f, g, h\}$ 中元素的直線排列, 所以其排列數為 $|A_1|=6!$。 而 $A_2$ 表示出現 $efgh$ 的排列方式, 相當於集合 $\{a, b, c, d, efgh\}$ 中元素的直線排列, 所以其排列數為 $|A_2|=5!$。 又 $A_1\cap A_2$ 表示出現 $abc$ 及 $efgh$ 的排列方式, 相當於集合 $\{abc, d, efgh\}$ 中元素的直線排列, 所以其排列數為 $|A_1A_2|=3!$。 由排容原理 \begin{eqnarray*} ~|\overline{A_1}\,\overline{A_2}| &=& |S| - (|A_1|+|A_2|) + |A_1A_2| \\ &=& 8! - (6!+5!) + 3! = 39486\Box \end{eqnarray*}
解: 去除 0, 4, 則 $n$ 位數中的所有數字皆由 1, 2, 3, 5, 6, 7, 8, 9 這 8 個數字所組成。 令 $S$ 表示由這 $8$ 個數字組成的所有 $n$ 位數的集合, 其個數 $|S|=8^n$。 而 $A_1$ 表示一個 $n$ 位數中不包含 3, $A_2$ 表示一個 $n$ 位數中不包含 8, $A_3$ 表示一個 $n$ 位數中不包含 9, 則題意即為求 $|\overline{A_1}\,\overline{A_2}\,\overline{A_3}|$。 在 8 個可選取的數字中不允許選取數字 3, 則這 $n$ 位數可能的個數為 $|A_1|=7^n$, 同理 $|A_2|=|A_3|=7^n$。 而不允許選取 3 與 8, 則這 $n$ 位數可能的個數為 $|A_1A_2|=6^n$, 同理 $|A_1A_3|=|A_2A_3|=6^n$。 當不允許選取 3, 8, 9 這 3 個數字時, 這 $n$ 位數可能的個數為 $|A_1A_2A_3|=5^n$。 由排容原理 \begin{eqnarray*} ~|\overline{A_1}\,\overline{A_2}\,\overline{A_3}| &=& |S| - \sum_{i=1}^3|A_i| + \sum_{1\le i\lt j\le 3}|A_iA_j| - |A_1A_2A_3| \\ &=& 8^n - 3 \cdot 7^n + 3 \cdot 6^n - 5^n\Box \end{eqnarray*}
解: 假設 $S$ 為學校所有學生, $A$ 為男學生的集合, $B$ 為三年級學生的集合, $C$ 為學生會員的集合。由題意知 \begin{eqnarray*} |S| &=& 900, ~|A| = 528, ~|B| = 312, ~|C| = 670 \\ |AB| &=& 192, ~|AC| = 336, ~|BC| = 247, ~|ABC| = 175 \end{eqnarray*} 故由以上訊息, 求不是男生亦不是三年級學生也不是學生會員的人數應為 $|\overline{A}\,\overline{B}\,\overline{C}|$。 由排容原理 \begin{eqnarray*} |\overline{A}\,\overline{B}\,\overline{C}| &=& |S| - (|A|+|B|+|C|-|AB|-|AC|-|BC|+|ABC|) \\ &=& 900 - (528+312+670) + (192+336+247) - 175 = -10 \lt 0 \end{eqnarray*} 但因為 $|\overline{A}\,\overline{B}\,\overline{C}|\ge 0$, 不可能為負數, 表示所統計的數據有錯誤。$\Box$
解: 假設 $S$ 為 $\{1, 2, \ldots, 200\}$ 的集合, 令 $A_1$, $A_2$, $A_3$ 為在 $S$ 中分別為 2, 3, 5 的倍數所形成的集合, 故題意即為求 $\overline{A_1}\,\overline{A_2}\,\overline{A_3}$ 的和, 取 $\sum(\overline{A_1}\,\overline{A_2}\,\overline{A_3})$表示。 由排容原理 \begin{eqnarray*} \sum(\overline{A_1}\,\overline{A_2}\,\overline{A_3}) &=& \sum S - \sum (A_1\cup A_2\cup A_3) \\ &=& \sum S - \sum_{i=1}^3 A_i + \sum_{i\lt j} A_iA_j - \sum A_1A_2A_3 \\ &=& \frac{200\times 201}{2} - \bigg (\sum_{a=1}^{100} 2a + \sum_{b=1}^{66} 3b + \sum_{c=1}^{40} 5c\bigg ) \\ && + \bigg (\sum_{d=1}^{33} 6d + \sum_{e=1}^{20} 10e + \sum_{f=1}^{13} 15f\bigg ) - \sum_{g=1}^6 30g \\ &=& 20100 \!-\! (10100\!+\!6633\!+\!4100) \!+\! (3366\!+\!2100\!+\!1365) \!-\! 630 \!=\! 5468\Box \end{eqnarray*}
解: 因為 $30=2\times 3\times 5$, 且 $(n+4, 30)\ne 1$, 可知 $n+4$ 為 2 或 3 或 5 的倍數, 所以假設 $A_1$ 表示 $n+4$ 為 2 的倍數, $A_2$ 表示 $n+4$ 為 3 的倍數, $A_3$ 表示 $n+4$ 為 5 的倍數, 故題意即為求 $|A_1\cup A_2\cup A_3|$。 因為 $1\le n\le 2006$, 所以 $5\le n+4\le 2010$, 由排容原理 \begin{eqnarray*} ~\hskip .7cm|A_1\cup A_2\cup A_3| &=& \sum_{i=1}^3 |A_i| - \sum_{i\lt j}|A_iA_j| + |A_1A_2A_3| \\ &=& \bigg (\Big [\frac{2010}{2}\Big ] - 2\bigg ) + \bigg (\Big [\frac{2010}{3}\Big ] - 1\bigg ) + \bigg (\Big [\frac{2010}{5}\Big ]\bigg ) \\ && - \bigg (\Big [\frac{2010}{6}\Big ] + \Big [\frac{2010}{10}\Big ] + \Big [\frac{2010}{15}\Big ]\bigg ) + \bigg (\Big [\frac{2010}{30}\Big ]\bigg ) \\ &=& (1003+669+402) - (335+201+134) + 67 = 1471\Box \end{eqnarray*}
解: 首先將此三數因式分解 $$ 10^{10} = 2^{10} \cdot 5^{10}, \quad 15^7 = 3^7 \cdot 5^7, \quad 18^{11} = 2^{11} \cdot 3^{22} $$ 則 $10^{10}$ 共有 121 個正因數, 而表示這些正因數可將 $10^{10}$ 除盡, 同理 $15^7$ 有 64 個正因數, $18^{11}$ 有 276 個正因數。 而令 $A_1$ 為 $10^{10}$ 所有正因數所形成的集合, $A_2$ 為 $15^7$ 所有正因數所形成的集合, $A_3$ 為 $18^{11}$ 所有正因數所形成的集合, 因此題意即為求 $|A_1\cup A_2\cup A_3|$。 由求正因數個數公式可得 $|A_1|=11\times 11=121$, $|A_2|=64$, $|A_3|=276$。 而 $A_1\cap A_2$ 表示為 $10^{10}$, $15^7$ 共同的正因數, 所以 $|A_1A_2|=8 (5^0, 5^1, \ldots, 5^7)$, 同理可推得 $|A_1A_3|=11$, $|A_2A_3|=8$, $|A_1A_2A_3|=1$。 所以由排容原理 \begin{eqnarray*} ~|A_1 \cup A_2 \cup A_3| &=& \sum_{i=1}^3 |A_i| - \sum_{i\lt j} |A_iA_j| + |A_1A_2A_3| \\ &=& (121+64+276) - (8+11+8) + 1 = 435\Box \end{eqnarray*}
解: 令 S 為宿舍中所有的學生人數, 且 $A_1$ 表示上美術課的學生, $A_2$ 表示上生物課的學生, $A_3$ 表示上化學課的學生, 及 $A_4$ 表示上戲劇課的學生。假設 $|S|=N$, 而由題意知 \begin{eqnarray*} && |A_1| = 12, ~|A_2| = 20, ~|A_3| = 20, ~|A_4| = 8 \\ && |A_1A_2| = 5, ~|A_1A_3| = 7, ~|A_1A_4| = 4, ~|A_2A_3| = 16, ~|A_2A_4| = 4, ~|A_3A_4| = 3 \\ && |A_1A_2A_3| = 3, ~|A_1A_2A_4| = 2, ~|A_1A_3A_4| = 3, ~|A_2A_3A_4| = 2 \\ && |A_1A_2A_3A_4| = 2 \end{eqnarray*} 因此由排容原理 \begin{eqnarray*} 71 &=& |S| - \sum_{i=1}^4 |A_i| + \sum_{i\lt j} |A_iA_j| - \sum_{i\lt j\lt k} |A_iA_jA_k| + |A_1A_2A_3A_4| \\ &=& N - 60 + 39 - 10 + 2 \end{eqnarray*} 所以可推得 $N=100$, 表示宿舍中共有 100 位學生。
解: $S$ 表示 26 個字母所有排列所形成的集合, $A_1$, $A_2$, $A_3$ 及 $A_4$ 分別表示這些排列中出現 car, dog, pun及byte, 故題意即為求 $|\overline{A_1}\,\overline{A_2}\,\overline{A_3}\,\overline{A_4}|$。 因為 $A_1$ 表示排列中出現 car 的情形, 故將 car 視為一個體, 再與剩下的 23 個字母一起排列, 所以其排列數為 $|A_1|=24!$。同理 $|A_2|=|A_3|=24!$, $|A_4|=23!$。 而 $A_1\cap A_2$ 表示同時出現 car, dog 兩種情形, 故亦將此兩種情形視為兩個體, 再與剩下的 20 個字母一起排列, 所以其排列數為 $|A_1A_2|=22!$, 同理可得 $|A_1A_3|=|A_2A_3|=22!$, $|A_1A_4|=|A_2A_4|=|A_3A_4|=21!$。 採用相同的討論方法, 可得下列方法數 $|A_1A_2A_3|=20!$, $|A_1A_2A_4|=|A_1A_3A_4|=|A_2A_3A_4|=19!$, $|A_1A_2A_3A_4|=17!$。 根據排容原理 \begin{eqnarray*} |\overline{A_1}\,\overline{A_2}\,\overline{A_3}\,\overline{A_4}| &=& |S| - \sum_{i=1}^4 |A_i| + \sum_{i\lt j} |A_iA_j| - \sum_{i\lt j\lt k} |A_iA_jA_k| + |A_1A_2A_3A_4| \\ &=& 26! - [3 \times (24!) + 23!] + [3 \times (22!) + 3 \times (21!)] \\ && - [20! + 3 \times (19!)] + 17! \end{eqnarray*}
解: 將可能的走法以下列圖形敘述
此題可利用排容原理來計算 \begin{eqnarray*} ~\hskip .9cm&& \hskip -25pt |\text{由點}(0, 0)\text{到點}(m, n)\text{但不經過點}(p, q)\text{和點}(r, s)| \\ &=& |\text{由點}(0, 0)\text{到點}(m, n)\text{的走法}| - |\text{經過點}(p, q)\text{或經過點}(r, s)| \\ &=& |\text{由點}(0, 0)\text{到點}(m, n)\text{的走法}| - |\text{經過點}(p, q)| - |\text{經過點}(r, s)| \\ && + |\text{經過點}(p, q)\text{且經過點}(r, s)| \\ &=& \frac{(m+n)!}{m!n!} - \frac{(p+q)!}{p!q!} \frac{(m+n-p-q)!}{(m-p)!(n-q)!} + \frac{(r+s)!}{r!s!} \frac{(m+n-r-s)!}{(m-r)!(n-s)!} \\ && - \frac{(p+q)!}{p!q!} \frac{(r+s-p-q)!}{(r-p)!(s-q)!} \frac{(m+n-r-s)!}{(m-r)!(n-s)!} \\ &=& {m+n \choose n} - {p+q \choose q}{m+n-p-q \choose n-q} - {r+s \choose s}{m+n-r-s \choose n-s} \\ && + {p+q \choose q}{r+s-p-q \choose s-q}{m+n-r-s \choose n-s}\Box \end{eqnarray*} 接下來為兩個有關於排容原理在幾何問題上的應用。
解: 定義一頂點 $x$, 令 $A_x$ 為與頂點 $x$ 間以一條邊連接的頂點所形成的集合, 假設 $|A_x|\ge\lfloor\frac{n}{2}\rfloor+1$, 對於所有的頂點 $x$。 取兩個頂點 $x$ 及 $y$, 其中 $y\in A_x$。而由排容原理可知 $$ |A_x\cup A_y| = |A_x| + |A_y| - |A_xA_y| $$ 亦可寫為 $$ |A_xA_y| = |A_x| + |A_y| - |A_x\cup A_y| $$ 而由題目知 $|A_x\cup A_y|\le n$, 因此可推論出 $$ |A_xA_y| = |A_x| + |A_y| - |A_x\cup A_y| \ge 2 \Big (\Big \lfloor\frac{n}{2}\Big \rfloor + 1\Big ) - n \ge 1 $$ 故可知 $A_x\cap A_y$ 存在某一頂點 $z$, 使得 $x$, $y$, $z$ 為一三角形的三個頂點。$\Box$
解: 如果 $m$ 邊形的銳角為 $\angle A_kA_1A_{k+r}$, 則此角為銳角的條件轉換為 $r\le n$。 因為 $m-2\le r$, 所以 $m$ 邊形介於點 $A_k$ 及 $A_{k+r}$ 間的其他頂點, 共有 ${r-1 \choose m-3}$ 種選法, 其中 $1\le k\le 2n-r$。因此有一個銳角 $A_1$ 的 $m$ 邊形個數為 \begin{eqnarray*} \sum_{r=m-2}^n \sum_{k=1}^{2n-r} {r-1 \choose m-3} &=& 2n \sum_{r=m-2}^n {r-1 \choose m-3}-\sum_{r=m-2}^nr{r-1\choose m-3} \\ &=& 2n {n \choose m-2} - (m-2){n+1 \choose m-1} \end{eqnarray*} 上述結果將會有許多有一銳角在 $A_1, A_2, \ldots, A_{2n+1}$ 的多邊形。 接下來計算此 $m$ 邊形有兩個銳角的情況, 假設此兩銳角為 $\angle A_sA_1A_k$, $\angle A_1A_kA_r$, 而其他兩個頂點介於點 $A_s$ 與 $A_r$ 間。故有下列限制 $$ \begin{cases} 2 \le k \le 2n - m \text{ 及 } n + 2 \le r \lt s \le k + n, & \quad k \le n \\ \text{無限制}, & \quad k \gt n \end{cases} $$ 則此種情形下的 $m$ 邊形共有 \begin{eqnarray*} \sum_{k=1}^n {k-1 \choose m-2} + \sum_{k=n+1}^{2n+1-(m-2)} {2n+1-k \choose m-2} &=& \sum_{k=m-1}^n {k-1 \choose m-2} + \sum_{s=m-2}^n {s \choose m-2} \\ &=& {n+1 \choose m-1} + {n \choose m-1} \end{eqnarray*} 但因為再選取起始的第一個銳角 $(A_1, A_2, \ldots, A_{2n+1})$ 共有 $2n+1$ 種選法, 故上式結果需乘以 $2n+1$。 由排容原理知, 至少有一銳角的 $m$ 邊形共有 \begin{eqnarray*} && \hskip -25pt (2n+1) \bigg [2n{n \choose m-2} - (m-2){n+1 \choose m-1}\bigg ] - (2n+1) \bigg [{n+1 \choose m-1} + {n \choose m-1}\bigg ] \\ &=& (2n+1) \bigg [2n{n \choose m-2} - (m-1){n+1 \choose m-1} - {n \choose m-1}\bigg ] \end{eqnarray*} 3. 尤拉公式、映成函數當一個數的因數只有 1和自己本身外, 並沒有任何其他的因數時, 則稱此數為質數。 而當兩數之間共同的公因數只有 1時, 則稱此兩數為互質。 若要判斷兩數間是否為互質時, 則需比較兩數間的公因數是否為 1。 但若要同時比較多個數與某一指定的數是否為互質時, 那所需要的計算將會很費時, 因此以下提供一個特殊的例題來說明與某特定的數互質的數有多少個。
解: 1到 $n$ 之自然數中, 它是 $p$ 倍數者為 $p\cdot 1, p\cdot 2, \ldots, p\cdot\lfloor\frac{n}{p}\rfloor$ 共有 $\lfloor\frac{n}{p}\rfloor=\lfloor\frac{pqr}{p}\rfloor=qr=n\times\frac{1}{p}$ 個。 令 $A_1$, $A_2$, $A_3$ 分別為 1到 $n$ 之自然數中, 它是 $p$, $q$, $r$ 倍數之集合。
上述例題說明了, 若正整數 $n$ 可分解為 3個質因數 $p$, $q$, $r$ 相乘時, 則在小於 $n$ 的正整數中與正整數 $n$ 互質的數共有 $n(1-\frac{1}{p})(1-\frac{1}{q})(1-\frac{1}{r})$ 個。 將此結果做一般化的延伸: 小於等於 $n$ 且與 $n$ 互質的正整數個數稱之為尤拉函數, 以 $\phi(n)$ 表示, 以下對尤拉函數作詳細的介紹。
證明: 考慮 $S=\{1, 2, \ldots, n\}$, 所以 $|S|=n$。 令 $A_i$ 表 $S$ 中滿足被 $p_i$ 整除的性質, $i=1, 2, \ldots, k$, 則 $\phi(n)=|\overline{A_1}\,\overline{A_2}\cdots\overline{A_k}|$。 因為 $S$ 中被 $p_{i_1}$ 整除的元素個數有 $\frac{n}{p_{i_1}}$ 個, 所以 $|A_{i_1}|=\frac{n}{p_{i_1}}$, ${i_1}=1, 2, \ldots, k$。 而 $S$ 中被 $p_{i_1}$ 及 $p_{i_2}$ 整除的元素個數有 $\frac{n}{p_{i_1}p_{i_2}}$個, 所以 $|A_{i_1}A_{i_2}|=\frac{n}{p_{i_1}p_{i_2}}$, $1\le i_1\lt i_2\le k$。 同理 $|A_{i_1}A_{i_2}A_{i_3}|=\frac{n}{p_{i_1}p_{i_2}p_{i_3}}$, $1\le {i_1}\lt {i_2}\lt {i_3}\le k$, 以此類推可得 $|A_1A_2\cdots A_k|=\frac{n}{p_1p_2\cdots p_k}$。 所以由排容原理 \begin{eqnarray*} ~\phi(n) &=& |\overline{A_1}\,\overline{A_2}\cdots\overline{A_k}| = |S| - \sum_{i=1}^k |A_i| + \sum_{i\lt j} |A_iA_j| - \cdots + (-1)^k |A_1A_2\cdots A_k| \\ &=& n - \Big (\frac{n}{p_1} + \cdots + \frac{n}{p_k}\Big ) + \Big (\frac{n}{p_1p_2} + \frac{n}{p_1p_3} + \cdots + \frac{n}{p_{k-1}p_k}\Big ) \\ && - \Big (\frac{n}{p_1p_2p_3} + \frac{n}{p_1p_2p_4} + \cdots + \frac{n}{p_{k-2}p_{k-1}p_k}\Big ) + \cdots + (-1)^n \Big (\frac{n}{p_1p_2\cdots p_k}\Big ) \\ &=& n \bigg [1 - \Big (\frac{1}{p_1} + \cdots + \frac{1}{p_k}\Big ) + \Big (\frac{1}{p_1p_2} + \frac{1}{p_1p_3} + \cdots + \frac{1}{p_{k-1}p_k}\Big ) \\ && - \Big (\frac{1}{p_1p_2p_3} + \frac{1}{p_1p_2p_4} + \cdots + \frac{1}{p_{k-2}p_{k-1}p_k}\Big ) + \cdots + (-1)^n \Big (\frac{1}{p_1p_2\cdots p_k}\Big )\bigg ] \\ &=& n \Big (1-\frac{1}{p_1}\Big ) \Big (1-\frac{1}{p_2}\Big ) \cdots \Big (1-\frac{1}{p_k}\Big )\Box \end{eqnarray*} 不難發現, 在證明的過程中, 排容原理扮演一個不可或缺的角色, 以下舉一簡單應用尤拉函數的例子。
解: 因為 $3528=(2^3)(3^2)(7^2)$, 題意即求與 3528 互質的數有幾個。 利用尤拉 $\phi$ 函數可得 \begin{eqnarray*} ~\phi(3528) &=& 3528 \Big (1 - \frac{1}{2}\Big ) \Big (1 - \frac{1}{3}\Big ) \Big (1 - \frac{1}{7}\Big ) \\ &=& 3528 \cdot \frac{1}{2} \cdot \frac{2}{3} \cdot \frac{6}{7} = 1008\hbox{。}\Box \end{eqnarray*} 在上述的例子中, 利用排容原理幫助我們推導出尤拉 $\phi$ 函數的算式, 提供我們在求互質個數時有更為快速的方法。 在介紹完尤拉函數後, 以下的幾個例題進一步對此函數來討論它的特殊性質。
解: 亦可將總和改寫為 $\sum\phi(n/d_i)$。其中 $d_i$ 為 $n$ 的遞增的正因數, 而 $n/d_i$ 為 $n$ 的遞減的正因數。 令 $X=\{1, 2, \ldots, n\}$, 且 $X_i=\{m\in X: m$ 和 $n$ 的最大公因數為 $d_i$, $i=1, 2, \ldots, r\}$。 因為任意兩個正整數有唯一的最大公因數。對於每一個 $i$ 使得 $d_i\in X_i$, 所以可以得到 $\{X_1, X_2, \ldots, X_r\}$ 是 $X$ 的一個分割。 而且 $m$ 是落在 $X_i$ 中若且唯若 $m/d_i$ 與 $n/d_i$ 是互質的。 因此在 $X_i$ 中的元素個數就是不超過 $n/d_i$ 且與他互質的正整數個數, 即為 $\phi(n/d_i)$。$\Box$
解: 12 的正因數為 1, 2, 3, 4, 6 和 12。 \begin{eqnarray*} &&\hskip -20pt X_1 = \{1, 5, 7, 11\} \hskip 3pt \quad \mbox{且} \quad |X_1| = \phi(12/1) = 4 \\[-2pt] &&\hskip -20pt X_2 = \{2, 10\} \hskip 25pt \quad \mbox{且} \quad |X_2| = \phi(12/2) = 2 \\[-2pt] &&\hskip -20pt X_3 = \{3, 9\} \hskip 30pt \quad \mbox{且} \quad |X_3| = \phi(12/3) = 2 \\[-2pt] &&\hskip -20pt X_4 = \{4, 8\} \hskip 30pt \quad \mbox{且} \quad |X_4| = \phi(12/4) = 2 \\[-2pt] &&\hskip -20pt X_6 = \{6\} \hskip 40pt \quad \mbox{且} \quad |X_6| = \phi(12/6) = 1 \\[-2pt] &&\hskip -20pt X_{12} = \{12\} \hskip 30pt \quad \mbox{且} \quad |X_{12}| = \phi(12/12) = 1 \end{eqnarray*} 所求為 $4+2+2+2+1+1=12$。$\Box$
證明: Step 1. 證明: 若 $p$ 為一質數則 $\phi(p)=p-1$。 如果 $p$ 為一質數, 則 $$ \phi(p) = p \Big (1 - \frac{1}{p}\Big ) = p - 1 $$ 故得證。 Step 2. 證明: 若 $\phi(p)=p-1$ 則 $p$ 為一質數。(利用反證法) 相反地, 假如 $p$ 不為質數, 則會存在一個正整數 $d$ $(1\lt d\lt p)$ 可以除盡 $p$, 因此 $p=kd$, 由尤拉 $\phi$ 函數的定義可知 $\phi(p)\le p-2\ne p-1$, 故得證。$\Box$ 自古質數的問題就是數學界非常有興趣的問題, 研究各種有關於質數的性質與判別方法。 而在西元 2006年 9月 4日美國密蘇里州立大學的 Curtis Cooper 教授和 Steven Boone 教授所帶領的團隊發現到目前為止最大的質數為 $2^{32, 582, 657}-1$, 這是一個有 9,808,358 位的質數。 那麼在這些新的演算法被建立使用前, 我們是如何去計算在給定的範圍內, 共有多少個質數? 以下給出一個利用排容原理所推得的厄拉多塞氏之篩選法 (Sieve of Eratosthenes), 進一步討論質數其他相關的問題。 而厄拉多塞的方法是根據所觀察的數 $n(n\ge 2)$, 將小於等於 $n^{1/2}$ 的所有質數的倍數刪除, 即將非質數的數去除, 則剩下的數即為質數。將此想法列舉成下列四個步驟:
利用上述的想法, 可證明出下列的定理。
證明: 取 $X=\{2, 3, \ldots, n\}$, 且 $2=p_1\lt p_2\lt \cdots\lt p_r\le n^{1/2}\lt p_{r+1}$。 假設 $A_i$ $(i=1, 2, \ldots, r)$ 表示由 $p_i$ 的倍數所組成的 $X$ 的子集合, 而 $A_1\cup A_2\cup\cdots\cup A_r$ 將會是由在 $X$ 中的合成數及前 $r$ 個質數所構成。 因此可以求得 $$ S_1 = \Big \lfloor \frac{n}{p_1}\Big \rfloor + \Big \lfloor \frac{n}{p_2}\Big \rfloor + \cdots + \Big \lfloor \frac{n}{p_r}\Big \rfloor = \sum_{i=1}^r \Big \lfloor \frac{n}{p_i}\Big \rfloor $$ 且其他一般項 $$ S_j = \sum_{1\le i_1\lt i_2\lt \cdots\lt i_j\le r} \Big \lfloor \frac{n}{p_{i_1}p_{i_2}\cdots p_{i_j}}\Big \rfloor, \quad j = 1, 2, \ldots, r $$ 所以 $|A_1\cup A_2\cup\cdots\cup A_r|=S_1-S_2+\cdots+(-1)^{r-1}S_r$, 故可推得 $$ \pi(n) = (n-1) + r - S_1 + S_2 - \cdots + (-1)^rS_r $$ 如果 $\pi$ 函數被拓展成任意實變量時, $r$ 可以用 $\pi(n^{1/2})$ 來表示。$\Box$
解: 因為 98, 99 和 100 均為合成數, 所以只需要證明 $\pi(100)=25$ 即可。 由厄拉多塞氏的方法中可知 $r=4$ (因為 $p_r\le (100)^{1/2}=10$, 所以 $p_1=2$, $p_2=3$, $p_3=5$, $p_4=7)$ \begin{eqnarray*} S_1 &=& \Big \lfloor \frac{100}{2}\Big \rfloor + \Big \lfloor \frac{100}{3}\Big \rfloor + \Big \lfloor\frac{100}{5}\Big \rfloor + \Big \lfloor \frac{100}{7}\Big \rfloor = 117 \\ S_2 &=& \Big \lfloor \frac{100}{2\cdot 3}\Big \rfloor + \Big \lfloor \frac{100}{2\cdot 5}\Big \rfloor + \Big \lfloor \frac{100}{2\cdot 7}\Big \rfloor + \Big \lfloor \frac{100}{3\cdot 5}\Big \rfloor + \Big \lfloor \frac{100}{3\cdot 7}\Big \rfloor + \Big \lfloor \frac{100}{5\cdot 7}\Big \rfloor = 45 \\ S_3 &=& \Big \lfloor \frac{100}{2\cdot 3\cdot 5}\Big \rfloor + \Big \lfloor \frac{100}{2\cdot 3\cdot 7}\Big \rfloor + \Big \lfloor \frac{100}{2\cdot 5\cdot 7}\Big \rfloor + \Big \lfloor \frac{100}{3\cdot 5\cdot 7}\Big \rfloor = 6 \\ S_ 4 &=& \Big \lfloor \frac{100}{2\cdot 3\cdot 5\cdot 7}\Big \rfloor = 0 \end{eqnarray*} 因此 $\pi(100)=(100-1)+4-117+45-6+0=25$。$\Box$
解: 假設 $x$ 是一個正整數, 用函數 $g(x)$ 表示小於或等於 $x$ 的質數個數。 所以題意即為求 $g(N)-g(\sqrt{N})$。 假設 $a_1, a_2, \ldots, a_r$ 為 $\le\sqrt{N}$ 的全部質數, 由定理知 \begin{eqnarray*} g(N) - g(\sqrt{N}) &=& N - \sum_{i=1}^r \Big \lfloor \frac{N}{a_i}\Big \rfloor + \sum_{1\le i\lt j\le r} \Big \lfloor \frac{N}{a_ia_j}\Big \rfloor - \sum_{1\le i\lt j\lt k\le r} \Big \lfloor \frac{N}{a_ia_ja_k}\Big \rfloor \\ && + \cdots + (-1)^r \Big \lfloor \frac{N}{a_ia_ja_k \cdots a_r}\Big \rfloor - (1) \\ &=& (N-1) - \sum_{i=1}^r \Big \lfloor \frac{N}{a_i}\Big \rfloor + \sum_{1\le i\lt j\le r} \Big \lfloor \frac{N}{a_ia_j}\Big \rfloor - \sum_{1\le i\lt j\lt k\le r} \Big \lfloor \frac{N}{a_ia_ja_k}\Big \rfloor \\ && + \cdots + (-1)^r \Big \lfloor \frac{N}{a_ia_ja_k \cdots a_r}\Big \rfloor \end{eqnarray*} 其中 1為非質數, 所以將其去除。$\Box$ 前面的諸多問題皆為討論數論中質數問題的應用, 而接下來將利用排容原理來解決關於函數的一些問題。 在開始使用函數時, 其定義域與值域為對此函數的先決條件, 在確認這些區域後, 我們才能討論有關反函數的對應問題, 如以下將介紹的映成(Onto)函數。
解: 假設 $S$ 表示所有 $f: E\rightarrow F$ 的映成函數, 所以 $|S|=p^n$。 令 $A_i$ 表示值域 $F$ 中的第 $i$ 個元素沒有被對應到的映成函數, 其中 $i=1, 2, \ldots, p$, 故題意即為求 $|\overline{A_1}\,\overline{A_2}\cdots\overline{A_p}|$。 $A_1$ 表示 $F$ 中第 1個元素未被對應到, 故此時 $|A_1|=(p-1)^n$。 以此類推, $|A_i|=(p-1)^n$, $i=1, 2, \ldots, p$。 而$A_1\cap A_2$ 表示 $F$ 中第 1與第 2個元素未被對應到, 故 $|A_1A_2|=(p-2)^n$, 亦可推得$|A_iA_j|=(p-2)^n$, $1\le i\lt j\le p$。 由前述兩種情況可推論出 $|A_1A_2\cdots A_k|=(p-k)^n$, $1\le i\lt j\lt \cdots\lt k\le p$。故由排容原理 \begin{eqnarray*} ~|\overline{A_1}\,\overline{A_2}\cdots\overline{A_p}| &=& |S| - \sum_{i=1}^n |A_i| + \sum_{i\lt j} |A_iA_j| - \cdots + (-1)^p |A_1A_2 \cdots A_p| \\ &=& p^n - {n \choose1}(p-1)^n + {n \choose2}(p-2)^n - \cdots + (-1)^{p-1} {n \choose p-1} \\ &=& \sum_{k=0}^{p-1} (-1)^{k} {n \choose k}(p-k)^n\hskip 6.8cm\Box \end{eqnarray*} 以下給出映成函數利用排容原理所歸納出來的一般式。
證明: 假設 $B=\{b_1, b_2, \ldots, b_n\}$, 令 $S$ 為所有由 $A$ 到 $B$ 的函數所成的集合, 即 $S=\{f|f: A\rightarrow B$ 為一個函數$\}$。 令 $A_i$ 表示 $S$ 中函數滿足值域不含$b_i$的條件, $1\le i\le n$, 則由 $A$ 到 $B$ 的映成函數個數相當於 $|\overline{A_1}\,\overline{A_2}\cdots\overline{A_n}|$。 若 $S$ 中函數需滿足值域不含 $b_i$, 則相當於 $m$ 個元素對應到 $n-1$ 個元素的函數個數有 $(n-1)^m$, 即 $|A_i|=(n-1)^m$, $1\le i\le n$。 若 $S$ 中函數需滿足值域不含 $b_i$ 及 $b_j$, 則相當於 $m$ 個元素對應到 $n-2$ 個元素的函數個數有 $(n-2)^m$, 即 $|A_iA_j|=(n-2)^m$, $1\le i\lt j\le n$。 同理 $|A_iA_jA_k|=(n-3)^m$, $1\le i\lt j\lt k\le n, \ldots$, $|A_1A_2\cdots A_n|=(n-n)^m$。由排容原理 \begin{eqnarray*} |\overline{A_1}\,\overline{A_2}\cdots\overline{A_n}| &=& |S| - \sum_{i=1}^n |A_i| + \sum_{i\lt j} |A_iA_j| - \cdots + (-1)^n |A_1A_2 \cdots A_n| \\ &=& n^m - {n \choose1}(n-1)^m + {n \choose2}(n-2)^m - \cdots + (-1)^n (n-n)^m \\ &=& \sum_{i=0}^n (-1)^n {n \choose i}(n-i)^m \end{eqnarray*} 註: 為了方便起見, 我們記作 $Onto(m, n)=\sum_{i=0}^n(-1)^n{n\choose i}(n-i)^m$, 即 $Onto(m, n)$ 表示 $m$ 個元素到 $n$ 個元素的映成函數個數。$\Box$
證明: 令 $A$ 為 $m$ 個物品所形成之集合, $B$ 為 $n$ 個箱子所形成之集合。 將 $m$ 個物品放入 $n$ 個箱子的一種方法相當於一個 $A$ 到 $B$ 的函數。 另外, 不允許有空箱子相當於函數是映成函數, 故其方法數有 $Onto(m, n)$種。$\Box$
解: 此題可視為, 5個元素對應到 4個元素的 $onto$ 函數有多少種。故 \begin{eqnarray*} ~Onto(5, 4) &=& \sum_{i=0}^4 (-1)^i {4 \choose i}(4-i)^5 \\ &=& {4 \choose 0} 4^5 - {4 \choose 1} 3^5 + {4 \choose 2} 2^5 - {4 \choose 3} 1^5 + {4 \choose 4} 0^5 = 240\hbox{。}\hskip 1.8cm\Box \end{eqnarray*} 4. 機率上述將幾種排容原理在計數問題中重要的應用作詳細的介紹, 可知透過排容原理做有效的轉換, 可將問題從簡易卻明確的角度切入, 而能得到相同的結果, 故排容原理將會是我們在考慮問題時, 一個不可或缺的技巧。 但排容原理並不僅只有在計數上的應用, 更可以將其與其他數學中的主題做有效的連結, 一個明顯的推廣即為在機率上的應用, 因此以下將對於排容原理在機率上的應用有詳細介紹。 首先在進入到機率的領域中, 必須先對機率的定義有所瞭解, 在滿足所有架構下, 才將排容原理做應用及轉換, 因此以下給出機率的基本定義。
有了機率的基本定義, 我們將排容原理引進, 透過以下的定理, 給出排容原理在機率 上明確的形式。
證明:
有了機率中的排容原理, 以下給出幾個機率問題, 從中去感受排容原理是如何在機率問題中做計算。
解: 假設 $A$ 表示 4次中沒有出現一次 6所形成的集合, 故題意所求機率即為 $1-P(A)$。 而 $A$ 表示 4次中沒有出現點數 6, 則這 4次投擲出來的可能點數為 1, 2, 3, 4, 5, 故共有 $5^4$ 種可能的點數組合。因此題意所求之機率為 \begin{eqnarray*} ~1 - P(A) &=& 1 - \Big (\frac{5}{6}\Big )^4 \\ &\approx& 1 - 0.4823 = 0.5177\hskip 4.7cm\Box \end{eqnarray*}
解: 假設 $A$ 為參加數學競賽的學生所形成的集合, $B$ 為參加作文競賽的學生所形成的集合, 故題意即為求 $P(A\cup B)$。 由排容原理知 \begin{eqnarray*} ~P(A\cup B) &=& P(A) + P(B) - P(AB) \\ &=& \frac{15}{50} + \frac{10}{50} - \frac{5}{50} = \frac{2}{5}\hskip 5.3cm\Box \end{eqnarray*}
解: 令 $A_1$ 表示被 7整除, $A_2$ 表示被 11整除, 則題意即為求 $P(A_1\cup A_2)-P(A_1A_2)$。 因為 $P(A_1)=\frac{142}{1000}$, $P(A_2)=\frac{90}{1000}$, $P(A_1A_2)=\frac{12}{1000}$, 由排容原理可得機率為 \begin{eqnarray*} ~P(A_1\cup A_2) - P(A_1A_2) &=& [P(A_1) + P(A_2) - P(A_1A_2)] - P(A_1A_2) \\ &=& \frac{142}{1000} + \frac{90}{1000} - 2 \times \frac{12}{1000} = \frac{208}{1000} = \frac{26}{125}\hskip 1.7cm\Box \end{eqnarray*}
解: 假設 $A_1$ 表示取出的 5顆球中, 沒有取到紅色球; $A_2$ 表示取出的 5顆球中, 沒有取到白色球; $A_3$ 表示取出的 5顆球中, 沒有取到藍色球。 故題意即為求 $1-P(\cup_{i=1}^3A_i)$。 由排容原理得 \begin{eqnarray*} P\Big(\bigcup_{i=1}^3A_i\Big) &=& \sum_{i=1}^3 P(A_i) - \sum_{i\lt j} P(A_iA_j) + P(A_1A_2A_3) \\ &=& \left (\frac{{13 \choose 5}}{{18 \choose 5}} + \frac{{12 \choose 5}}{{18 \choose 5}} + \frac{{11 \choose 5}}{{18 \choose 5}}\right ) - \left (\frac{{7 \choose 5}}{{18 \choose 5}} + \frac{{6 \choose 5}}{{18 \choose 5}} + \frac{{5 \choose 5}}{{18 \choose 5}}\right ) + 0 \\ &\approx& 0.2933 \end{eqnarray*} 因此所求機率為 $$ 1 - P\Big(\bigcup_{i=1}^3A_i\Big) = 1 - 0.2933 = 0.7067{\Box} $$
解: 假設 $A_1$ 表底圓直徑不合格的產品形成的集合, $A_2$ 表高度不合格的產品形成的集合, $A_3$ 表表層色澤不合格的產品形成的集合, 故題意所求機率即為 $P(A_1\cup A_2\cup A_3)$。 由題目得, $P(A_1)=\frac{15}{1000}$, $P(A_2)=\frac{10}{1000}$, $P(A_3)=\frac{20}{1000}$, $P(A_1A_2)=\frac{4}{1000}$, $P(A_1A_3)$ $=\frac{6}{1000}$, $P(A_2A_3)=\frac{8}{1000}$, $P(A_1A_2A_3)=\frac{2}{1000}$, 故由排容原理 \begin{eqnarray*} P(A_1\cup A_2\cup A_3) &=& \sum_{i=1}^3 P(A_i) - \!\!\sum_{i\lt j} P(A_iA_j) + P(A_1A_2A_3) \\ &=& \bigg (\frac{15}{1000} \!+\! \frac{10}{1000} \!+\! \frac{20}{1000}\bigg ) \!-\! \bigg (\frac{4}{1000} \!+\! \frac{6}{1000} \!+\! \frac{8}{1000}\bigg ) \!+\! \frac{2}{1000} \!=\! \frac{29}{1000}\ \Box \end{eqnarray*}
解:
假設 $A_i$ 表示第 $i$ 節車廂沒有乘客的事件, 其中 $i=1, 2, 3, 4$, 則題意即為求 因為 $A_1$ 表示第 1節車廂沒有乘客, 所以 $P(A_1)=\frac{3^{10}}{4^{10}}=(\frac{3}{4})^{10}$, 同理 $P(A_i)=(\frac{3}{4})^{10}$, $i=1, 2, 3, 4$。 而 $A_i\cap A_j$ 表示第 $i$, $j$ 節 ($1\le i\lt j\le 4$) 車廂沒有乘客的事件, 所以 $P(A_iA_j)=(\frac{2}{4})^{10}$, $1\le i\lt j\le 4$。 而 $A_i\cap A_j\cap A_k$ 表示第 $i$, $j$, $k$ 節 ($1\le i\lt j\lt k\le 4$) 車廂沒有乘客的事件, 所以 $P(A_iA_jA_k)=(\frac{1}{4})^{10}$, $1\le i\lt j\lt k\le 4$。 由排容原理 \begin{eqnarray*} ~&& \hskip -25pt P(\overline{A_1}\,\overline{A_2}\,\overline{A_3}\,\overline{A_4}) = 1 - P(A_1\cup A_2\cup A_3\cup A_4) \\ &=& 1 - \bigg (\!\sum_{i=1}^4\! P(A_i) - \!\!\sum_{i\lt j}\! P(A_iA_j) + \!\!\sum_{i\lt j\lt k}\! P(A_iA_jA_k) - P(A_1A_2A_3A_4)\!\bigg ) \\ &=& 1 - {4 \choose 1} \bigg (\frac{3}{4}\bigg )^{10} + {4 \choose 2} \bigg (\frac{2}{4}\bigg )^{10} - {4 \choose 1} \bigg (\frac{1}{4}\bigg )^{10} \\ &=& 1 - \frac{3^{10} - 3 \cdot2^9 + 1}{4^9}\Box \end{eqnarray*} 5. 競賽題本節探討一些數學競賽中有關排容原理的考題, 這些問題一般而言是比較艱澀的。
解: 因為 $20000=2^5\times 5^4$, $20=2^2\times 5$, 假設 $$ a = 2^{a_1} 5^{a_2}, ~b = 2^{b_1} 5^{b_2},~c = 2^{c_1}5^{c_2}, \quad 2 \le a_1, b_1, c_1 \le 5, ~1 \le a_2, b_2, c_2 \le 4 $$ 因此 $(a_1, a_2)$, $(b_1, b_2)$, $(c_1, c_2)$ 的取值可能如下 \begin{eqnarray*} S &=& \{(2, 1), (2, 2), (2, 3), (2, 4), (3, 1), (3, 2), (3, 3), (3, 4), (4, 1), (4, 2), (4, 3), (4, 4), \\ && (5, 1), (5, 2), (5, 3), (5, 4)\} \end{eqnarray*} 綜合上述情形, 以下列四個條件表示 \begin{eqnarray*} \min\{a_1, b_1, c_1\} &=& 2, \quad \max\{a_1, b_1, c_1\} = 5 \\ \min\{a_2, b_2, c_2\} &=& 1, \quad \max\{a_2, b_2, c_2\} = 4 \end{eqnarray*} 故 $(a_1, a_2)$, $(b_1, b_2)$, $(c_1, c_2)$ 可能的取值為從集合 $S$ 中可重複選取的所有情形, 共有 $H_3^{16}={18\choose 3}$ 種。
解: 我們先將這個題目推廣至一般情形來進行討論。假設有一 $w\times l\times h$ 的長方體, 內部由足夠多個 $1\times 1\times 1$ 的立方體所填滿。接下來將此長方體座標化, 令其中一頂點座標為 $O(0, 0, 0)$, 其相對的頂點座標為 $A(w, l, h)$, 所以 $\overline{OA}$ 即為長方體之對角線, 故欲求此對角線穿過立方體的個數。 因為對角線不是通過立方體的某一面, 就是通過某一個邊或是某一頂點, 所以求在對角線上點座標的三個分量 $(x, y, z)$ 中有一為正整數的點個數, 即為通過多少個立方體。 假設 $A_x$ 表示對角線上 $x$ 座標為正整數的點, $A_y$ 表示對角線上 $y$ 座標為正整數的點, $N_z$ 表示對角線上 $z$ 座標為正整數的點, 故題意即為求 $|A_x\cup A_y\cup A_z|$。 假設在對角線上的點 $P(kw, kl, kh)$, $0\lt k\le 1$。而 $x$ 座標需為正整數時, $k=\frac{1}{w}, \frac{2}{w}$, $\ldots, \frac{w}{w}$ 共 $w$ 種可能, 即 $|A_x|=w$。以此類推, $|A_y|=l$, $|A_z|=h$。 而 $A_x\cap A_y$ 表示對角線上的點 $x$ 與 $y$ 座標皆為正整數, 所以 $t=\frac{m}{\gcd(w, l)}$, $1\le m\le\gcd(w, l)$, 因此 $|A_xA_y|=\gcd(w, l)$。 以此類推, $|A_xA_z|=\gcd(w, h)$, $|A_yA_z|=\gcd(l, h)$, $|A_xA_yA_z|=\gcd(w, l, h)$。 由排容原理可推得 \begin{eqnarray*} |A_x\cup A_y\cup A_z| &=& |A_x| + |A_y| + |A_z| - |A_xA_y| - |A_xA_z| - |A_yA_z| + |A_xA_yA_z| \\ &=& w + l + h - \gcd(w, l) - \gcd(w, h) - \gcd(l, h) + \gcd(w, l, h) \end{eqnarray*} 今題目為 $w=150$, $l=324$, $h=375$, 所以穿過的立方體個數為 $$ 150 + 324 + 375 - 6 - 75 - 3 + 3 = 768{\Box} $$
解: 因為 $0.abcabcabcabc\ldots=0.\overline{abc}=\frac{abc}{999}$, 又 $999=3^3\times 37$, 所以分成下列兩種情形討論:
由 (1)、 (2) 可得, 共有 $648+12=660$ 種不同的分子。$\Box$
解: 出現紅色的 $2\times 2$ 正方形會有下列四種情況
假設 $A_1$ 表示出現情況 1, $A_2$ 表示出現情況 2, $A_3$ 表示出現情況 3, $A_4$ 表示出現情況 4, 故題意即為求 $P(\overline{A_1}\,\overline{A_2}\,\overline{A_3}\,\overline{A_4})$。 由排容原理 \begin{eqnarray*} P(\overline{A_1}\,\overline{A_2}\,\overline{A_3}\,\overline{A_4}) &=& 1 - \sum_{i=1}^4 P(A_i) + \sum_{i\lt j} P(A_iA_j) - \sum_{i\lt j\lt k} P(A_iA_jA_k) + P(A_1A_2A_3A_4) \\ &=& 1 - 4 \times \bigg (\frac{1}{2}\bigg )^4 + \bigg (4 \times \Big (\frac{1}{2}\Big )^6 + 2 \times \Big (\frac{1}{2}\Big )^7\bigg ) - 4 \times \bigg (\frac{1}{2}\bigg )^8 + \bigg (\frac{1}{2}\bigg )^9 \\ &=& \frac{417}{512}\hskip 10.7cm\Box \end{eqnarray*}
解: 定義 $U_n$ 為使得 $f^n(z)=z$ 且為集合 $S^1$ 的複數 $z$ 所形成的集合, 所以 $f^n(z)=z^{m^n}$, 因此 $U_n$ 由長度為 1之複數的 $m^n-1$ 方根所形成的集合。 已知題意欲求週期 $n=1989$, 但在 $U_{1989}$ 中的週期點其週期不可小於 1989, 又 $1989=3^2\times 13\times17$, 故需將週期分別為 $1989/3=663$, $1989/13=153$, $1989/17=117$ 的週期點去除, 即為 $U_{1989}-(U_{663}\cup U_{153}\cup U_{117})$, 所以週期點個數為 $|U_{1989}|-|U_{663}\cup U_{153}\cup U_{117}|$。 利用排容原理可求得週期為 1989的週期點個數為 \begin{eqnarray*} ~&& \hskip -25pt |U_{1989}| - |(U_{663} \cup U_{153} \cup U_{117}| \\ &=& |U_{1989}| - (|U_{663}| + |U_{153}| + |U_{117}| - |U_{663}U_{153}| - |U_{663}U_{117}| \\ && - |U_{153}U_{117}| + |U_{663}U_{153}U_{117}|) \\ &=& |U_{1989}| - (|U_{663}| + |U_{153}| + |U_{117}| - |U_{51}| - |U_{39}| - |U_9| + |U_3|) \\ &=& (m^{1989}-1) - [(m^{663}-1) + (m^{153}-1) + (m^{117}-1) \\ && - (m^{51}-1) - (m^{39}-1) - (m^9-1) + (m^3-1)] \\ &=& m^{1989} - m^{663} - m^{153} - m^{117} + m^{51} + m^{39} + m^9 - m^3\Box \end{eqnarray*}
解: 因選出的 $n$ 個數的乘積需被 10整除, 故在 $n$ 次選取中需至少選擇一次 5, 並且至少有一次選擇偶數。 假設 $A$ 表示在 $n$ 次選擇中沒有一次選到 5, $B$ 表示在 $n$ 次選擇中沒有一次選到偶數, 故所求機率即為 $P(\overline{A}\overline{B})$。 由排容原理 \begin{eqnarray*} P(\overline{A}\,\overline{B}) &=& 1 - P(A\cup B) = 1 - [P(A) + P(B) - P(AB)] \\ &=& 1 - \Big (\frac{8}{9}\Big )^n - \Big (\frac{5}{9}\Big )^n + \Big (\frac{4}{9}\Big )^n = 1 - \frac{8^n+5^n-4^n}{9^n} \end{eqnarray*} 故選出的 $n$ 個數的乘積能被 10整除的機率為 $1-\frac{8^n+5^n-4^n}{9^n}$。$\Box$
解: 由題意知, 只需證明具有性質 $P$ 的排列數大於全部排列數的一半即可。 假設具有性質 $P$ 的排列數為 $m$, $A_k$ 表示 $(x_1, x_2, \ldots, x_{2n})$ 中 $k$, $n+k$ 相鄰的所有排列的集合, 其中 $k=1, 2, \ldots, n$。 $A_1$ 表示 1, $n+1$ 兩個數在排列中為相鄰, 所以 $|A_1|=(2n-1)!\times 2!$, 故 $|A_k|=2(2n-1)!$, $k=1, 2, \ldots, n$。而 $A_1\cap A_2$ 表示 1, $n+1$ 與 2, $n+2$分別相鄰, 所以 $|A_1A_2|=2^2(2n-2)!$, 亦可推得 $|A_kA_l|=2^2(2n-2)!$, $1\le k\lt l\le n$。 又 $2n$ 個正整數的排列數為 $(2n)!$ 種。 由排容原理知 \begin{eqnarray*} m &\ge& \sum_{k=1}^n |A_k| - \sum_{1\le k\lt l\le n} |A_kA_l| = {n \choose 1}2(2n-1)! - {n \choose2} 4(2n-2)! \\ &=& (2n)! - 2n(n-1)(2n-2)! = 2n(n)(2n-2)! \end{eqnarray*} 因為 $n\gt n-\frac{1}{2}$, 所以 $m\ge 2n(n)(2n-2)!\gt \frac{1}{2}(2n)!$, 故得證。$\Box$ 參考文獻---本文作者任教國立中山大學應用數學系--- |