C33N34.dvi

Transcription

1 數學傳播 卷 期, pp 排容原理 張福春 洪偉誠 1. 前言 在組合數學中, 常需討論有關集合元素個數的問題, 而重複計數卻是造成結果錯誤的一大主因, 故需再進一步討論所有可能重複的情況, 此時 排容原理 是一個能夠解決關於多個具有某些性質的非互斥集合其交集與聯集計數問題的有效方法, 能輕易的將重複計數的困擾排除 排容原理是一個很容易使用的計數方法, 而它最早被使用的歷史可追溯到早期的一些手稿中, 以篩選方法 (Sieve Method 或交叉分類法則 (Priciple of Cross Classificatio 等不同的名稱出現, 而其所考慮到集合的交集與聯集的觀點, 可在 18 世紀著名數學家 DeMoivre ( 的著作 Doctrie of Chaces (1718 中找到相關的論述 但在更早之前, 法國數學家 de Motmort ( 在 1708 年時便已使用了這個想法解決撲克牌的配對問題 而現今所闡述與使用的排容原理是由英國數學家 Sylvester ( 所建立 但在早期排容原理這一種計數技巧並未獲得重視, 一直到由 Whitworth 所撰寫的 選擇與機會 (Choice ad Chace 這本大眾書籍問世後, 才使得數學家開始注意到排容原理的用途 也因為排容原理簡單明瞭, 所以在其他領域更是被廣泛的應用, 例如著名的 Möbius 反轉公式 Balakrisha (1994 由計數的基本原理開始, 利用方法 定義及概念的歸納與推廣, 對排容原理作全面的論述 Ross (2006 利用基本概念的推廣, 來介紹在機率中的排容原理 單壿 葛軍 (1991 介紹了在數學奧林匹克如何運用排容原理來解決相關題目 Gelca ad Adreescu (2007 收錄北美著名的 Putam 數學競賽考題 中國數學奧林匹克委員會和開南大學數學系 (2002 收錄了各國奧林匹克的訓練題或比賽題目 讀者若想對排容原理有深入的瞭解, 可參考以上書目 本文主要的目的是對於排容原理做全面性的介紹, 首先透過一些淺顯易懂的例子來熟悉排容原理的基本定義及定理, 接下來再舉出數個條件個數由少 ( = 1 到多 ( 4 的例子, 針對不同的情況適當的使用排容原理來求解 一旦學會了排容原理的技巧及其使用的時機, 在處 44

2 排容原理 45 理各種計數問題時, 重複計數便可輕鬆解決 而在第二節先介紹排容原理兩種基本的型式及其應用, 第三節介紹如何透過排容原理證明出尤拉公式及映成函數的對應問題, 第四節介紹排容原理在機率問題上的應用, 第五節則舉出一些在數學競賽中出現有關排容原理的題目 2. 排容原理 在開始介紹排容原理的內容前, 我們先給出一些符號介紹 : 若三個集合 A, B, C 滿足 : A 中的任一元素 x 都屬於 B 中或者屬於 C 中 又集合 B 或者 C 中的元素也都包含在集合 A 中則稱集合 A 為集合 B 與 C 的聯集合或簡稱為聯集, 以 A = B C 表示 若三個集合 A, B, C 滿足 : 集合 A 中的任一元素 x, 屬於集合 B 中, 也一定屬於集合 C 中 又集合 B 和 C 共同含有的元素也屬於集合 A 中則稱 A 是集合 B 與 C 之交集合或簡稱交集, 以 A = B C 表示, 亦可簡寫為 A = BC 取集合 A 是宇集合 S 的一個子集合, 以記號 A 表示其元素屬於 S 而不屬於 A 的集合, 則稱 A 為 A 的補集合 而用記號 A 來表示 A 的元素個數, 則集合 A 的元素個數, 等於 S 的所有元素個數減去屬於 S 但不屬於集合 A 的元素個數, 故可以用下列形式來表示 A = S A (1 以下舉出幾個例子, 利用式子 (1 來計算答案 例 1: 0 名精神疾病專家與 24 位心理學家一同出席醫學會議, 而現在要從這 54 個人中隨機選取 名專家主持會議, 請問其中至少會有 1 位心理學家的選取方法有多少種? 解 : 假設 S 為從 54 位專家中選取 位的所有取法形成的集合, 故 S = ( 54 而令 A 表示沒有任何一位心理學家被選取, 故題意所求即為 A A 表示被選取的 位專家中, 沒有心理學家, 故選法共有 A = ( 0 因此根據題意, 此 位主持人的選法有 A = S A ( ( 54 0 = = = 20744

3 46 數學傳播 卷 期民 98 年 9 月 例 2: 從正整數 1, 2,..., 100 中選取出兩個不同的數, 使得此兩數的和為偶數, 試問有多 少種取法? 解 : 假設 S 為 1, 2,..., 100 的數所形成的集合, 所以 S = ( 而令 A 表示從 1, 2,..., 100 中選出的兩個數和為奇數, 則題意即為求 A 因為取出兩數和需為奇數, 則此兩數必為一奇一偶, 所以其選取方式有 A = ( ( 因此取出兩數和為偶數的取法 A = S A ( 100 = 2 ( 50 1 ( 50 1 種, = 2450 以下為求兩補集合交集元素個數的問題, 並提供了三種不同的計算方法 例 : 某校進行班際教室布置比賽, 某班的學藝股長買了 50 張的矩形壁報紙, 其中長達到 150 公分的有 5 張, 而寬達到 100 公分的有 40 張, 長達到 150 公分且寬達到 100 公分的共有 0 張, 請問在這些壁報紙中長度沒有達到 150 公分且寬度沒有達到 100 公分的有幾張? 解 : 設 S 表示所有壁報紙所形成的集合, A 1 表示長度達到 150 公分的壁報紙所形成的集合, A 2 表示寬度達到 100 公分的壁報紙所形成的集合, 則題意即為求 A 1 A 2 由題意知 S = 50, A 1 = 5, A 2 = 40, A 1 A 2 = 0 ( 方法 1 利用式子 (1 可求得下列個數 : A 1 = S A 1 = 50 5 = 15, A 1 A 2 = A 2 A 1 A 2 = 40 0 = 10 又因為 A 1 = A 1 A 2 + A 1 A 2, 所以可推得 A 1 A 2 = A 1 A 1 A 2 = = 5 ( 方法 2 由集合原理可知 A 1 A 2 = A 1 A 1 A 2 = ( S A 1 ( A 2 A 1 A 2 = S A 1 A 2 + A 1 A 2

4 排容原理 47 = S ( A 1 + A 2 + A 1 A 2 = 50 ( = 5 (2 與上式所得之結果相同 ( 方法 可透過文氏圖 ( 如下圖 從圖中可組合出 A 1 A 2 = S A 1 A 2 = S ( A 1 + A 2 + A 1 A 2 = 50 ( = 5 因此我們在求集合的個數時亦可透過文氏圖的方式, 簡單的表達集合的狀況, 再根據 所要求的條件來計算 前面三個例子已經引出排容原理的基本雛形, 如 (2 式, 接下來的定理將給出排容原理完 整的敘述及其證明 完整的敘述及其證明 定理 2.1 ( 排容原理 (The Priciple of Iclusio ad Exclusio 假設 S 為宇集合, 其中 S = N (S 中的元素個數 令 A 1, A 2,...,A 為 個定義在 S 上的性質, 而以 A i 表示在 S 中不滿足 A i 性質的元素個數 (i = 1, 2,...,, 則 (a 這 個性質皆不滿足的集合個數 ( A 1 A 2 A = N + ( 1 k k=1 (b 至少具有其中之一性質 A i 的集合個數 ( A 1 A 2 A = ( 1 k+1 k=1 1 i 1 <i 2 < <i k 1 i 1 <i 2 < <i k A i1 A i2 A ik 以上兩種對於排容原理的敘述是等價的, 因此這兩種形式皆為排容原理 A i1 A i2 A ik

5 48 數學傳播 卷 期民 98 年 9 月 證明 : (a 假設 A 1, A 2,...,A 為 個定義在 S 上的性質, 欲證 A 1 A 2 A = S A i + i=1 1 i<j A i A j + ( 1 A 1 A 2 A 其中 x S, 並分別討論 x 在 A 1, A 2,...,A 這 個條件下滿足的個數 (1 若 x 在這 個條件皆不滿足 : 則 x 在 A 1 A 2 A 中算了一次, 所以等號左式的值為 1 而在等號的右式中, x 在 S 中算了一次且在 A i, i=1 1 i<j A i A j,...,( 1 A 1 A 2 A 中皆沒有列入計算, 所以等號右式的值為 1, 此時等號左式與右式相等 (2 若 x 在這 個條件中恰好滿足 r 個 : 則 x 在 A 1 A 2 A 中算了 0 次, 所以等號左式的值為 0 而在等號的右式中 x 在 S 中算了 1 次 x 在 A i 中算了 x 在. x 在 i=1 1 i<j 1 i 1 <i 2 < <i r ( r 次 1 A i A j 中算了 ( r 次 2 A i1 A i2 A ir 中算了 ( r 次 r 所以等號右式的值為 1 ( ( r 1 + r ( 2 + ( 1 r r = (1 + ( 1 r = 0, 故等號左式與右式相等 由 (1 (2 中的討論可得, 等號的左式與右式相等 (b A 1 A 2 A 表示在 S 中至少具有其中之一性質的集合 所以由餘集合的想法知 又因為由 DeMorga s 定理知 A 1 A 2 A = S A 1 A 2 A A 1 A 2 A = A 1 A 2 A

6 排容原理 49 故我們可以得到 A 1 A 2 A = S A 1 A 2 A = S A 1 A 2 A = A i A i A j + + ( 1 +1 A 1 A 2 A i=1 1 i<j 故得證 接下來舉一些簡易的例子, 說明當滿足多個條件時, 如何適當的使用兩種排容原理來幫助我們計算 例 4: 將集合 A = {a, b, c, d, e, f, g, h} 中所有元素做直線排列, 試求 abc 與 efgh 均不出現的所有排列數 解 : 假設 S 為這 8 個元素做直線排列所有可能形成的集合, 所以 S = 8! 而令 A 1 表示在 S 中出現 abc 的直線排列, A 2 表示在 S 中出現 efgh 的直線排列, 故題意即為求 A 1 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 A 2 表示出現 abc 及 efgh 的排列方式, 相當於集合 {abc, d, efgh} 中元素的直線排列, 所以其排列數為 A 1 A 2 =! 由排容原理 A 1 A 2 = S ( A 1 + A 2 + A 1 A 2 = 8! (6! + 5! +! = 9486 例 5: 在所有 位數中, 包含數字, 8, 9 但不包含 0, 4 的數有多少個? 解 : 去除 0, 4, 則 位數中的所有數字皆由 1, 2,, 5, 6, 7, 8, 9 這 8 個數字所組成 令 S 表示由這 8 個數字組成的所有 位數的集合, 其個數 S = 8 而 A 1 表示一個 位數中不包含, A 2 表示一個 位數中不包含 8, A 表示一個 位數中不包含 9, 則題意即為求 A 1 A 2 A 在 8 個可選取的數字中不允許選取數字, 則這 位數可能的個數為 A 1 = 7, 同理 A 2 = A = 7

7 50 數學傳播 卷 期民 98 年 9 月而不允許選取 與 8, 則這 位數可能的個數為 A 1 A 2 = 6, 同理 A 1 A = A 2 A = 6 當不允許選取, 8, 9 這 個數字時, 這 位數可能的個數為 A 1 A 2 A = 5 由排容原理 A 1 A 2 A = S A i + A i A j A 1 A 2 A i=1 1 i<j = 例 6: 有一位老師對於自己所任教學校的學生進行調查, 全校共 900 個人, 其中男生有 528 人, 三年級學生有 12 人, 學生會員有 670 人, 三年級的男生有 192 人, 男學生會員有 6 人, 三年級學生會員有 247 人, 三年級男學生會員有 175 人, 請問這些數據是否有統計錯誤? 解 : 假設 S 為學校所有學生, A 為男學生的集合, B 為三年級學生的集合, C 為學生會員的集合 由題意知 S = 900, A = 528, B = 12, C = 670 AB = 192, AC = 6, BC = 247, ABC = 175 故由以上訊息, 求不是男生亦不是三年級學生也不是學生會員的人數應為 AB C 由排容原理 AB C = S ( A + B + C AB AC BC + ABC = 900 ( ( = 10 < 0 但因為 A B C 0, 不可能為負數, 表示所統計的數據有錯誤 例 7: 求從 1 到 200 中, 同時不能被 2,, 5 整除的數的和 解 : 假設 S 為 {1, 2,..., 200} 的集合, 令 A 1, A 2, A 為在 S 中分別為 2,, 5 的倍數 所形成的集合, 故題意即為求 A 1 A 2 A 的和, 取 (A1 A 2 A 表示 由排容原理 (A1 A 2 A = S (A 1 A 2 A = S i=1 A i + i<j A i A j A 1 A 2 A

8 = 2 + ( d=1 6d + ( 100 2a + a=1 20 e=1 66 b=1 1 10e + 15f f=1 40 b + c=1 5c 6 0g g=1 排容原理 51 = ( ( = 5468 例 8: 已知 A = { N 且 ( + 4, 0 1}, 求 A 解 : 因為 0 = 2 5, 且 ( + 4, 0 1, 可知 + 4 為 2 或 或 5 的倍數, 所以 假設 A 1 表示 + 4 為 2 的倍數, A 2 表示 + 4 為 的倍數, A 表示 + 4 為 5 的倍數, 故題意即為求 A 1 A 2 A 因為 , 所以 , 由排容原理 A 1 A 2 A = A i A i A j + A 1 A 2 A i=1 i<j ( [2010 ] ( [2010 ] ( [2010 ] = ( [2010 ] [ 2010 ] [ 2010 ] ( [2010 ] = ( ( = 1471 例 9: 試求能夠除盡 10 10, 15 7, 三數中至少一個數的正整數有多少個? 解 : 首先將此三數因式分解 = , 15 7 = 7 5 7, = 則 共有 121 個正因數, 而表示這些正因數可將 除盡, 同理 15 7 有 64 個正因數, 有 276 個正因數 而令 A 1 為 所有正因數所形成的集合, A 2 為 15 7 所有正因數所形成的集合, A 為 所有正因數所形成的集合, 因此題意即為求 A 1 A 2 A 由求正因數個數公式可得 A 1 = = 121, A 2 = 64, A = 276 而 A 1 A 2 表示為 10 10, 15 7 共同的正因數, 所以 A 1 A 2 = 8(5 0, 5 1,...,5 7, 同理可推得 A 1 A = 11, A 2 A = 8, A 1 A 2 A = 1

9 52 數學傳播 卷 期民 98 年 9 月所以由排容原理 A 1 A 2 A = A i A i A j + A 1 A 2 A i=1 i<j = ( ( = 45 例 10: 在一間學生宿舍中, 經過課程調查後, 發現有 12 位學生有上美術課, 20 位學生有上生物課, 20 位學生有上化學課, 及 8 位學生有上戲劇課 而且其中有 5 位學生同時上了美術與生物課, 7 位學生同時上了美術及化學課,4 位學生同時上了美術課及戲劇課, 16 位學生同時上了生物課及化學課, 4 位學生同時上了生物課及戲劇課, 位學生同時上了化學課及戲劇課 另外也發現有 位學生同時上了美術 生物及化學課, 2 位學生同時上了美術 生物及戲劇課, 2 位學生同時上了生物 化學及戲劇課, 位同學同時上了美術 化學及戲劇課 且有 2 位同學同時上了這四種課程 而且得知在宿舍中有 71 位學生並沒有上四種課程中的任何一種, 請問在宿舍中共有多少學生? 解 : 令 S 為宿舍中所有的學生人數, 且 A 1 表示上美術課的學生, A 2 表示上生物課的學生, A 表示上化學課的學生, 及 A 4 表示上戲劇課的學生 假設 S = N, 而由題意知 A 1 = 12, A 2 = 20, A = 20, A 4 = 8 A 1 A 2 = 5, A 1 A = 7, A 1 A 4 = 4, A 2 A = 16, A 2 A 4 = 4, A A 4 = A 1 A 2 A =, A 1 A 2 A 4 = 2, A 1 A A 4 =, A 2 A A 4 = 2 A 1 A 2 A A 4 = 2 因此由排容原理 4 71 = S A i + A i A j A i A j A k + A 1 A 2 A A 4 i=1 i<j i<j<k = N 所以可推得 N = 100, 表示宿舍中共有 100 位學生 例 11: 在 26 個字母排列中, 不出現 car, dog, pu 或 byte 這些樣式有幾個? 解 : S 表示 26 個字母所有排列所形成的集合, A 1, A 2, A 及 A 4 分別表示這些排列中 出現 car, dog, pu 及 byte, 故題意即為求 A 1 A 2 A A 4

10 排容原理 5 因為 A 1 表示排列中出現 car 的情形, 故將 car 視為一個體, 再與剩下的 2 個字母一起排列, 所以其排列數為 A 1 = 24! 同理 A 2 = A = 24!, A 4 = 2! 而 A 1 A 2 表示同時出現 car, dog 兩種情形, 故亦將此兩種情形視為兩個體, 再與剩下的 20 個字母一起排列, 所以其排列數為 A 1 A 2 = 22!, 同理可得 A 1 A = A 2 A = 22!, A 1 A 4 = A 2 A 4 = A A 4 = 21! 採用相同的討論方法, 可得下列方法數 A 1 A 2 A = 20!, A 1 A 2 A 4 = A 1 A A 4 = A 2 A A 4 = 19!, A 1 A 2 A A 4 = 17! 根據排容原理 4 A 1 A 2 A A 4 = S A i + A i A j A i A j A k + A 1 A 2 A A 4 i=1 i<j i<j<k = 26! [ (24! + 2!] + [ (22! + (21!] [20! + (19!] + 17! 例 12: 令 m,, p, q, r, s 為正整數且滿足 p < r < m, q < s < 試問從點 (0, 0 走 捷徑 ( 只能向上或向右 到點 (m,, 每次走一個單位, 但不經過點 (p, q 和 (r, s, 有 多少種走法? 解 : 將可能的走法以下列圖形敘述 (a 經過 (p, q (b 經過 (r, s (c 經過 (p, q 且經過 (r, s 圖 1. 由 (0, 0 到 (m, 三類的走法 此題可利用排容原理來計算 由點 (0, 0 到點 (m, 但不經過點 (p, q 和點 (r, s = 由點 (0, 0 到點 (m, 的走法 經過點 (p, q 或經過點 (r, s

11 54 數學傳播 卷 期民 98 年 9 月 = 由點 (0, 0 到點 (m, 的走法 經過點 (p, q 經過點 (r, s + 經過點 (p, q 且經過點 (r, s (m +! (p + q! (m + p q! (r + s! (m + r s! = + m!! p!q! (m p!( q! r!s! (m r!( s! (p + q! (r + s p q! (m + r s! p!q! (r p!(s q! (m r!( s! ( ( ( ( ( m + p + q m + p q r + s m + r s = q q s s ( ( ( p + q r + s p q m + r s + q s q s 接下來為兩個有關於排容原理在幾何問題上的應用 例 1: 給定一個有 個點的圖形, 試證明此圖形不是包含一個三角形, 就是存在一個頂 點為至多 2 個邊的終點, 其中 x 表示不大於 x 的最大整數 解 : 定義一頂點 x, 令 A x 為與頂點 x 間以一條邊連接的頂點所形成的集合, 假設 A x 2 + 1, 對於所有的頂點 x 亦可寫為 取兩個頂點 x 及 y, 其中 y A x 而由排容原理可知 A x A y = A x + A y A x A y A x A y = A x + A y A x A y 而由題目知 A x A y, 因此可推論出 ( A x A y = A x + A y A x A y 故可知 A x A y 存在某一頂點 z, 使得 x, y, z 為一三角形的三個頂點 例 14: 令 m, 為給定的正整數, 且 m 5 假設 A 為一個正 邊形, 試求有至少 一個銳角且有頂點屬於圖形 A 的凸 m 邊形有多少個 解 : 如果 m 邊形的銳角為 A k A 1 A k+r, 則此角為銳角的條件轉換為 r 因為 m 2 r, 所以 m 邊形介於點 A k 及 A k+r 間的其他頂點, 共有種選法, 其中 1 k 2 r 因此有一個銳角 A 1 的 m 邊形個數為 2 r ( r 1 = 2 m r=m 2 k=1 r=m 2 ( r 1 m ( r 1 m r=m 2 ( r 1 r m

12 ( ( + 1 = 2 (m 2 m 2 m 1 排容原理 55 上述結果將會有許多有一銳角在 A 1, A 2,...,A 2+1 的多邊形 接下來計算此 m 邊形有兩個銳角的情況, 假設此兩銳角為 A s A 1 A k, A 1 A k A r, 而其 他兩個頂點介於點 A s 與 A r 間 故有下列限制 2 k 2 m 及 + 2 r < s k +, k 無限制, 則此種情形下的 m 邊形共有 k=1 ( k 1 + m (m 2 k=+1 ( k = m 2 = k=m 1 ( + 1 m 1 ( k 1 + m 2 + k > ( m 1 s=m 2 ( s m 2 但因為再選取起始的第一個銳角 (A 1, A 2,...,A 2+1 共有 種選法, 故上式結果需乘 以 由排容原理知, 至少有一銳角的 m 邊形共有 [ ( ( ] [( ( (m 2 ( m 2 m 1 m 1 [ ( ( ( ] + 1 = ( (m 1 m 2 m 1 m 1. 尤拉公式 映成函數 ( ] m 1 當一個數的因數只有 1 和自己本身外, 並沒有任何其他的因數時, 則稱此數為質數 而當 兩數之間共同的公因數只有 1 時, 則稱此兩數為互質 若要判斷兩數間是否為互質時, 則需比較兩數間的公因數是否為 1 但若要同時比較多個 數與某一指定的數是否為互質時, 那所需要的計算將會很費時, 因此以下提供一個特殊的例題 來說明與某特定的數互質的數有多少個 例 15: 設 = pqr, p, q, r 為正質數, 求證 (a 1 到 之自然數中, 它是 p 之倍數, 但不為 q, r 之倍數者, 共有 1 p (1 1 q (1 1 r 個 (b 1 到 之自然數中, 它與 互質, 共有 (1 1 p (1 1 q (1 1 r 個

13 56 數學傳播 卷 期民 98 年 9 月 解 : 1 到 之自然數中, 它是 p 倍數者為 p 1, p 2,...,p p 共有 p = pqr p = qr = 1 p 個 令 A 1, A 2, A 分別為 1 到 之自然數中, 它是 p, q, r 倍數之集合 (a 由題意, 即為求 A 1 A 2 A A 1 A 2 A = A 1 A 1 A 2 A 1 A + A 1 A 2 A = + p pq pr pqr = pqr p pqr pq pqr pr + pqr pqr = pqr ( 1 1 p q 1 r + 1 = 1 ( 1 1 ( 1 1. qr p q r (b 由題意, 即為求 A 1 A 2 A A 1 A 2 A = S A i + A i A j A 1 A 2 A i=1 i<j [ ( = p + q + ( r pq + pr qr + ( = 1 1 ( 1 1 ( 1 1 p q r + ] pqr 上述例題說明了, 若正整數 可分解為 個質因數 p, q, r 相乘時, 則在小於 的正整數中與正整數 互質的數共有 (1 1(1 1(1 1 個 p q r 將此結果做一般化的延伸 : 小於等於 且與 互質的正整數個數稱之為尤拉函數, 以 φ( 表示, 以下對尤拉函數作詳細的介紹 定理.1 ( 尤拉 φ- 函數 (Euler s φ-fuctio 假設 = p e 1 1 pe 2 2 pe k k 數個數, 則 為 的質因數分解, φ( 為小於正整數 且與 互質的正整 φ( = k (1 1 p j j=1 證明 : 考慮 S = {1, 2,..., }, 所以 S = 令 A i 表 S 中滿足被 p i 整除的性質, i = 1, 2,..., k, 則 φ( = A 1 A 2 A k 因為 S 中被 p i1 整除的元素個數有 p i1 個, 所以 A i1 = p i1, i 1 = 1, 2,..., k 而 S 中 被 p i1 及 p i2 整除的元素個數有 p i1 p i2 個, 所以 A i1 A i2 = p i1 p i2, 1 i 1 < i 2 k 同理 A i1 A i2 A i = p i1 p i2 p i, 1 i 1 < i 2 < i k, 以此類推可得 A 1 A 2 A k = p 1 p 2 p k

14 排容原理 57 所以由排容原理 k φ( = A 1 A 2 A k = S A i + A i A j + ( 1 k A 1 A 2 A k i=1 i<j ( = + + ( p 1 p k p 1 p 2 p 1 p p k 1 p ( k + ( ( 1 p 1 p 2 p p 1 p 2 p 4 p k 2 p k 1 p k p 1 p 2 p [ k ( 1 = ( p 1 p k p 1 p 2 p 1 p p k 1 p k ( ( ( 1 1 ] p 1 p 2 p p 1 p 2 p 4 p k 2 p k 1 p k p 1 p 2 p k = (1 1 (1 1 (1 1 p 1 p 2 p k 不難發現, 在證明的過程中, 排容原理扮演一個不可或缺的角色, 以下舉一簡單應用尤拉 函數的例子 例 16: 計算 φ(528 得 解 : 因為 528 = (2 ( 2 (7 2, 題意即求與 528 互質的數有幾個 利用尤拉 φ 函數可 ( φ(528 = ( 1 1 ( = = 1008 在上述的例子中, 利用排容原理幫助我們推導出尤拉 φ 函數的算式, 提供我們在求互質個 數時有更為快速的方法 在介紹完尤拉函數後, 以下的幾個例題進一步對此函數來討論它的特 殊性質 例 17: 假設 d 1 = 1, d 2,...,d r = 是正整數 的 r 個相異正因數, 證明 φ(di = 解 : 亦可將總和改寫為 φ(/di 其中 d i 為 的遞增的正因數, 而 /d i 為 的遞減的正因數 令 X = {1, 2,..., }, 且 X i = {m X : m 和 的最大公因數為 d i, i = 1, 2,..., r} 因為任意兩個正整數有唯一的最大公因數 對於每一個 i 使得 d i X i, 所以可以得到 {X 1, X 2,...,X r } 是 X 的一個分割

15 58 數學傳播 卷 期民 98 年 9 月而且 m 是落在 X i 中若且唯若 m/d i 與 /d i 是互質的 因此在 X i 中的元素個數就是不超過 /d i 且與他互質的正整數個數, 即為 φ(/d i 例 18: 利用上述的公式計算 = 12 解 : 12 的正因數為 1, 2,, 4, 6 和 12 X 1 = {1, 5, 7, 11} 且 X 1 = φ(12/1 = 4 X 2 = {2, 10} 且 X 2 = φ(12/2 = 2 X = {, 9} 且 X = φ(12/ = 2 X 4 = {4, 8} 且 X 4 = φ(12/4 = 2 X 6 = {6} 且 X 6 = φ(12/6 = 1 X 12 = {12} 且 X 12 = φ(12/12 = 1 所求為 = 12 例 19: 證明 φ(p = p 1 若且唯若 p 為一質數 故得證 證明 : Step 1. 證明 : 若 p 為一質數則 φ(p = p 1 如果 p 為一質數, 則 ( φ(p = p 1 1 = p 1 p Step 2. 證明 : 若 φ(p = p 1 則 p 為一質數 ( 利用反證法 相反地, 假如 p 不為質數, 則會存在一個正整數 d (1 < d < p 可以除盡 p, 因此 p = kd, 由尤拉 φ 函數的定義可知 φ(p p 2 p 1, 故得證 自古質數的問題就是數學界非常有興趣的問題, 研究各種有關於質數的性質與判別方法 而在西元 2006 年 9 月 4 日美國密蘇里州立大學的 Curtis Cooper 教授和 Steve Booe 教 授所帶領的團隊發現到目前為止最大的質數為 2 2,582,657 1, 這是一個有 9,808,58 位的質 數 那麼在這些新的演算法被建立使用前, 我們是如何去計算在給定的範圍內, 共有多少個質 數? 以下給出一個利用排容原理所推得的厄拉多塞氏之篩選法 (Sieve of Eratosthees, 進 一步討論質數其他相關的問題 而厄拉多塞的方法是根據所觀察的數 ( 2, 將小於等於 1/2 的所有質數的倍數刪 除, 即將非質數的數去除, 則剩下的數即為質數 將此想法列舉成下列四個步驟 :

16 排容原理 59 (1 取集合 X = {2,,..., } (2 求出小於等於 1/2 的所有質數 2 = p 1 < p 2 < < p r 1/2 < p r+1 其中 p 表質數, r 為不超過 1/2 的質數個數 ( 由 2 到 的數中, 分別將 p 1, p 2,..., p r 的倍數刪除, 則剩下的數皆為質數 (4 計算剩下質數的個數 利用上述的想法, 可證明出下列的定理 定理.2: ( 厄拉多塞氏之篩選法 令 π( 表示不超過正整數 的質數個數, S 1 = r i=1 p i 且 S j = 1 i 1 <i 2 < <i j r p i1 p i2 p ij, 且 j = 1, 2,..., r, 其中 p 表示小於等於 1/2 的 質數且 x 表示不大於 x 的最大整數, 則 π( = ( 1 + r S 1 + S 2 + ( 1 r S r 證明 : 取 X = {2,,..., }, 且 2 = p 1 < p 2 < < p r 1/2 < p r+1 假設 A i (i = 1, 2,..., r 表示由 p i 的倍數所組成的 X 的子集合, 而 A 1 A 2 A r 將會是由 在 X 中的合成數及前 r 個質數所構成 因此可以求得 且其他一般項 S j = S 1 = = p 1 p 2 p r 1 i 1 <i 2 < <i j r r p i i=1, j = 1, 2,..., r p i1 p i2 p ij 所以 A 1 A 2 A r = S 1 S ( 1 r 1 S r, 故可推得 π( = ( 1 + r S 1 + S 2 + ( 1 r S r 如果 π 函數被拓展成任意實變量時, r 可以用 π( 1/2 來表示 例 20: 證明 97 是第 25 個質數

17 60 數學傳播 卷 期民 98 年 9 月 解 : 因為 98, 99 和 100 均為合成數, 所以只需要證明 π(100 = 25 即可 由厄拉多塞氏 的方法中可知 r = 4 ( 因為 p r (100 1/2 = 10, 所以 p 1 = 2, p 2 =, p = 5, p 4 = S 1 = = S 2 = = S = = S 4 = = 因此 π(100 = ( = 25 例 21: 厄拉多塞氏篩選法 : 先將正整數數列 2,,..., N 中, 先將 2,, 5,..., p (p 為 N 的最大質數 的倍數全部去除, 最後剩下來的則為小於等於 N 的質數 試問, 用 厄拉多塞氏篩選法可以找到多少個質數會大於 N 及小於等於 N? 解 : 假設 x 是一個正整數, 用函數 g(x 表示小於或等於 x 的質數個數 所以題意即為求 g(n g( N 假設 a 1, a 2,...,a r 為 N 的全部質數, 由定理知 g(n g( N = N r N + a i i=1 1 i<j r N a i a j 1 i<j<k r + + ( 1 r N (1 a i a j a k a r r N = (N 1 + N a i a i a j i=1 1 i<j r + + ( 1 r N a i a j a k a r N a i a j a k 1 i<j<k r N a i a j a k 其中 1 為非質數, 所以將其去除 前面的諸多問題皆為討論數論中質數問題的應用, 而接下來將利用排容原理來解決關於函數的一些問題 在開始使用函數時, 其定義域與值域為對此函數的先決條件, 在確認這些區域後, 我們才能討論有關反函數的對應問題, 如以下將介紹的映成 (Oto 函數

18 排容原理 61 例 22: 令 E, F 分別為 個及 p 個元素的集合, 其中 p 試問有多少個映成函數 f : E F? 解 : 假設 S 表示所有 f : E F 的映成函數, 所以 S = p 令 A i 表示值域 F 中的 第 i 個元素沒有被對應到的映成函數, 其中 i = 1, 2,..., p, 故題意即為求 A 1 A 2 A p A 1 表示 F 中第 1 個元素未被對應到, 故此時 A 1 = (p 1 以此類推, A i = (p 1, i = 1, 2,..., p 而 A 1 A 2 表示 F 中第 1 與第 2 個元素未被對應到, 故 A 1 A 2 = (p 2, 亦可推得 A i A j = (p 2, 1 i < j p 排容原理 由前述兩種情況可推論出 A 1 A 2 A k = (p k, 1 i < j < < k p 故由 A 1 A 2 A p = S = p A i + A i A j + ( 1 p A 1 A 2 A p i<j (p 1 + i=1 ( 1 p 1 ( = ( 1 k k k=0 以下給出映成函數利用排容原理所歸納出來的一般式 ( ( (p 2 + ( 1 p 1 2 p 1 (p k 定理.: 假設 A, B 為二有限集合, 其中 A = m, B = 且 m, 則由 A 到 B 的映成函數個數有 i=0 ( 1( i ( i m 種 證明 : 假設 B = {b 1, b 2,...,b }, 令 S 為所有由 A 到 B 的函數所成的集合, 即 S = {f f : A B 為一個函數 } 令 A i 表示 S 中函數滿足值域不含 b i 的條件, 1 i, 則由 A 到 B 的映成函數個數相當於 A 1 A 2 A 若 S 中函數需滿足值域不含 b i, 則相當於 m 個元素對應到 1 個元素的函數個數有 ( 1 m, 即 A i = ( 1 m, 1 i 若 S 中函數需滿足值域不含 b i 及 b j, 則相當於 m 個元素對應到 2 個元素的函數個數有 ( 2 m, 即 A i A j = ( 2 m, 1 i < j 同理 A i A j A k = ( m, 1 i < j < k,..., A 1 A 2 A = ( m 由排容 原理 A 1 A 2 A = S A i + A i A j + ( 1 A 1 A 2 A i<j i=1

19 62 數學傳播 卷 期民 98 年 9 月 = m = ( ( 1 m + 1 ( ( 1 i i=0 ( i m ( ( 2 m + ( 1 ( m 2 註 : 為了方便起見, 我們記作 Oto(m, = i=0 ( 1( i ( i m, 即 Oto(m, 表示 m 個元素到 個元素的映成函數個數 性質.1: m 個相異物放入 個相異箱子不允許有空箱的方法數有 Oto(m, 種 證明 : 令 A 為 m 個物品所形成之集合, B 為 個箱子所形成之集合 將 m 個物品放入 個箱子的一種方法相當於一個 A 到 B 的函數 另外, 不允許有空箱子相當於函數是映成函數, 故其方法數有 Oto(m, 種 例 2: 指定 5 種不同的工作給 4 位不同的雇員, 如果每一位雇員至少被指定一個工作, 則 有多少種指定的方法? 解 : 此題可視為, 5 個元素對應到 4 個元素的 oto 函數有多少種 故 Oto(5, 4 = = 4 ( 4 ( 1 i i 4 5 i=0 ( 4 0 (4 i 5 ( ( ( ( = 機率 上述將幾種排容原理在計數問題中重要的應用作詳細的介紹, 可知透過排容原理做有效的轉換, 可將問題從簡易卻明確的角度切入, 而能得到相同的結果, 故排容原理將會是我們在考慮問題時, 一個不可或缺的技巧 但排容原理並不僅只有在計數上的應用, 更可以將其與其他數學中的主題做有效的連結, 一個明顯的推廣即為在機率上的應用, 因此以下將對於排容原理在機率上的應用有詳細介紹 首先在進入到機率的領域中, 必須先對機率的定義有所瞭解, 在滿足所有架構下, 才將排容原理做應用及轉換, 因此以下給出機率的基本定義

20 排容原理 6 定義 4.1: ( 機率 假設 A 在一個試驗中所發生事件, 而 A 為在 次試驗中, 事件 A 發生的次數, 則事件 A 發生的機率, 以 P(A 表示, 以下給出其定義 P(A = lim 即為事件 A 發生的次數與重複試驗次數之比的極限 A 確的形式 有了機率的基本定義, 我們將排容原理引進, 透過以下的定理, 給出排容原理在機率上明 定義 4.1: ( 機率的排容原理 假設 S 為樣本空間, 其中 P(S = 1 令 A 1, A 2,..., A 為 個定義在 S 上的事件, 而以 P(A i 表示在 S 中 A i 餘事件的機率 (i = 1, 2,...,, 則 (a 屬於這 個餘事件交集的機率為 P(A 1 A 2 A = 1 + k=1 (b 屬於至少一個事件 A i 的機率為 P(A 1 A 2 A = k=1 以上兩種對於機率的排容原理敘述是等價的 證明 : ( ( 1 k 1 i 1 <i 2 < <i k P(A i 1 A i2 A ik ( ( 1 k+1 1 i 1 <i 2 < <i k P(A i 1 A i2 A ik (a 假設 A 1, A 2,...,A 為 個定義在 S 上的事件, 欲證 P(A 1 A 2 A = 1 P(A i + P(A i A j + ( 1 P(A 1 A 2 A i=1 1 i<j 其中 x S, 並分別討論 x 在 A 1, A 2,...,A 這 個事件下滿足的機率 (1 若元素 x 屬於這 個餘事件的交集 : 則元素 x 在餘事件交集 A 1 A 2 A 中算了一次 而在等號的右式中, 元素 x 在 N 中算了一次且在事件的聯集 A i, i = 1, 2,...,, (A i A j, 1 i < j,..., 以 及 A 1 A 2 A 中皆沒有列入計算 所以由前述的狀況, 在左式與右式 x 發生的機率相 等 (2 若元素 x 在 個事件中恰好滿足 r 個事件 : 元素 x 在左式事件交集 A 1 A 2 A 中算了 0 次, 而在等號的右式中 x 在 S 中算了 1 次

21 64 數學傳播 卷 期民 98 年 9 月 ( r x 在 A i 中算了次, 1 ( r x 在 (A i A j 中算了 2. 次, x 在 (A i1 A i2 A ir 中算了 i = 1, 2,..., 1 i < j ( r 次, r 1 i 1 < i 2 < < i r 所以等號右式的值為 1 ( ( r 1 + r ( 2 + ( 1 r r = (1 + ( 1 r = 0 故等號左式與右式相等 故亦可推得, 在滿足 r 個事件下, x 發生的機率左式與右式相等, 且機 率值為 0 由 (1, (2 中的討論可得, 等號的左式與右式相等, 即 P(A 1 A 2 A = 1 + k=1 ( ( 1 k 1 i 1 <i 2 < <i k P(A i1 A i2 A ik (b A 1 A 2 A 表示在 S 中至少落於其中一個事件的樣本點集合 所以由餘事件的想 法知 P(A 1 A 2 A = P(S P(A 1 A 2 A 又因為由 DeMorga s 定理知 故我們可以得到 A 1 A 2 A = A 1 A 2 A P(A 1 A 2 A = P(S P(A 1 A 2 A ( = 1 P(A 1 A 2 A = ( 1 k+1 P(A i1 A i2 A ik k=1 1 i 1 <i 2 < <i k 故得證 中做計算 有了機率中的排容原理, 以下給出幾個機率問題, 從中去感受排容原理是如何在機率問題 例 24: 投擲一顆公正的骰子 4 次, 至少出現一次 6 的機率? 解 : 假設 A 表示 4 次中沒有出現一次 6 所形成的集合, 故題意所求機率即為 1 P(A

22 排容原理 65 而 A 表示 4 次中沒有出現點數 6, 則這 4 次投擲出來的可能點數為 1, 2,, 4, 5, 故共有 5 4 種可能的點數組合 因此題意所求之機率為 ( P(A = = 例 25: 某間高中舉辦數學及作文競賽, 某班 50 名學生中有 15 名參加數學競賽, 10 名參加作文競賽, 其中有 5 名同時參加這兩項競賽 試問從該班級中任意挑選一名學生, 而該名學生是有參加競賽的機率是多少? 解 : 假設 A 為參加數學競賽的學生所形成的集合, B 為參加作文競賽的學生所形成的集 合, 故題意即為求 P(A B 由排容原理知 P(A B = P(A + P(B P(AB = = 2 5 例 26: 從集合 {1, 2,..., 1000} 中隨機選取一個整數, 求此整數可以被 7 或是 11 整除但 不可同時被整除的機率為何? 解 : 令 A 1 表示被 7 整除, A 2 表示被 11 整除, 則題意即為求 P(A 1 A 2 P(A 1 A 2 因為 P(A 1 = , P(A 2 = , P(A 1A 2 = , 由排容原理可得機率為 P(A 1 A 2 P(A 1 A 2 = [P(A 1 + P(A 2 P(A 1 A 2 ] P(A 1 A 2 = = = 例 27: 一個籃子裡裝有 5 個紅球, 6 個白球和 7 個藍球, 從中選取 5 顆球, 取後不放回, 請 問 種顏色都取到的機率為多少? 解 : 假設 A 1 表示取出的 5 顆球中, 沒有取到紅色球 ; A 2 表示取出的 5 顆球中, 沒有取到白色球 ; A 表示取出的 5 顆球中, 沒有取到藍色球 故題意即為求 1 P( i=1a i 由排容原理得 ( P A i = P(A i P(A i A j + P(A 1 A 2 A i=1 i=1 i<j

23 66 數學傳播 卷 期民 98 年 9 月 (( 1 ( 12 ( 11 ( ( 7 ( 6 ( = ( 18 + ( 18 + ( 18 ( 18 + ( ( 因此所求機率為 ( 1 P A i = = i=1 例 28: 某家公司出產圓形喜餅盒, 若禮盒的底圓直徑 圓盒高度及盒表層的色澤其中之一不合格即為瑕疵品 假設在 1000 個圓形喜餅盒中, 底圓直徑不合格的有 15 件, 高度不合格的有 10 件, 表層色澤不合格的有 20 件, 而底圓直徑與高度皆不合格的有 4 件, 高度與表層色澤皆不合格者有 8 件, 表層色澤與底圓直徑皆不合格者有 6 件, 三者皆不合格者有 2 件 從這批產品中任取一件, 求拿到瑕疵品的機率為多少? 解 : 假設 A 1 表底圓直徑不合格的產品形成的集合, A 2 表高度不合格的產品形成的集合, A 表表層色澤不合格的產品形成的集合, 故題意所求機率即為 P(A 1 A 2 A 由題目得, P(A 1 = 15, P(A = 10, P(A 1000 = 20, P(A A 2 = 4, P(A A = 6, P(A A = 8, P(A A 2 A = 2, 故由排容原理 1000 P(A 1 A 2 A = = P(A i A j + P(A 1 A 2 A P(A i i=1 i<j ( ( = 例 29: 一台火車有四節車廂, 現有 10 人上車, 試問每節車廂均有乘客的機率為多少? 解 : 假設 A i 表示第 i 節車廂沒有乘客的事件, 其中 i = 1, 2,, 4, 則題意即為求 P(A 1 A 2 A A 4 因為 A 1 表示第 1 節車廂沒有乘客, 所以 P(A 1 = = ( 4 10, 同理 P(A i = ( 4 10, i = 1, 2,, 4 而 A i A j 表示第 i, j 節 (1 i < j 4 車廂沒有乘客的事件, 所以 P(A i A j = ( , 1 i < j 4 而 A i A j A k 表示第 i, j, k 節 (1 i < j < k 4 車廂沒有乘客的事件, 所以 P(A i A j A k = ( , 1 i < j < k 4

24 排容原理 67 由排容原理 P(A 1 A 2 A A 4 = 1 P(A 1 A 2 A A 4 ( 4 = 1 i i=1p(a P(A i A j + P(A i A j A k P(A 1 A 2 A A 4 i<j i<j<k ( ( 10 ( ( 10 ( ( = = 競賽題 本節探討一些數學競賽中有關排容原理的考題, 這些問題一般而言是比較艱澀的 例 0: ( 中國天津市代表隊測驗題 1992 求滿足 [a, b, c] = 20000, (a, b, c = 20 的所有 正整數 a, b, c 形成的數對 (a, b, c 有多少組? 解 : 因為 = , 20 = 2 2 5, 假設 a = 2 a 1 5 a 2, b = 2 b 1 5 b 2, c = 2 c 1 5 c 2, 2 a 1, b 1, c 1 5, 1 a 2, b 2, c 2 4 因此 (a 1, a 2, (b 1, b 2, (c 1, c 2 的取值可能如下 S = {(2, 1, (2, 2, (2,, (2, 4, (, 1, (, 2,(,, (,4, (4,1, (4, 2, (4,,(4, 4, (5, 1, (5, 2, (5,, (5, 4} 綜合上述情形, 以下列四個條件表示 mi{a 1, b 1, c 1 } = 2, max{a 1, b 1, c 1 } = 5 mi{a 2, b 2, c 2 } = 1, max{a 2, b 2, c 2 } = 4 故 (a 1, a 2, (b 1, b 2, (c 1, c 2 可能的取值為從集合 S 中可重複選取的所有情形, 共有 H 16 = ( 18 種 不滿足四個其中一個限制條件, 則有 H 12 = ( 14 種情形 不滿足其中兩個條件, 當兩個限制條件為同列時, 則有 H 8 = ( 10 種情形 ; 當兩個限制條 件為不同列時, 則有 H 9 = ( 11 種情形 不滿足其中三個條件, 則共有 H 6 = ( 8 種情形

25 68 數學傳播 卷 期民 98 年 9 月 此四個條件皆不滿足時, 共有 H 4 = ( 6 種情形 由排容原理知數對共有 ( 18 [ (4 ( 14 1 ( 2 ( ( 11 + ( 4 ( 8 ( 4 4 ( ] 6 = = 56 例 1: (AIME 1996 一個 的長方體是被許多個 的立方體 所組成 試問在這個長方體內部的一對角線穿過多少個 的立方體? 解 : 我們先將這個題目推廣至一般情形來進行討論 假設有一 w l h 的長方體, 內 部由足夠多個 的立方體所填滿 接下來將此長方體座標化, 令其中一頂點座標為 O(0, 0, 0, 其相對的頂點座標為 A(w, l, h, 所以 OA 即為長方體之對角線, 故欲求此對角線 穿過立方體的個數 因為對角線不是通過立方體的某一面, 就是通過某一個邊或是某一頂點, 所以求在對角線 上點座標的三個分量 (x, y, z 中有一為正整數的點個數, 即為通過多少個立方體 假設 A x 表 示對角線上 x 座標為正整數的點, A y 表示對角線上 y 座標為正整數的點, N z 表示對角線上 z 座標為正整數的點, 故題意即為求 A x A y A z 假設在對角線上的點 P(kw, kl, kh, 0 < k 1 而 x 座標需為正整數時, k = 1 w, 2 w,..., w w 共 w 種可能, 即 A x = w 以此類推, A y = l, A z = h 而 A x A y 表示對角線上的點 x 與 y 座標皆為正整數, 所以 t = m, 1 m gcd(w,l gcd(w, l, 因此 A x A y = gcd(w, l 以此類推, A x A z = gcd(w, h, A y A z = gcd(l, h, A x A y A z = gcd(w, l, h 由排容原理可推得 A x A y A z = A x + A y + A z A x A y A x A z A y A z + A x A y A z = w + l + h gcd(w, l gcd(w, h gcd(l, h + gcd(w, l, h 今題目為 w = 150, l = 24, h = 75, 所以穿過的立方體個數為 = 768 例 2: (AIME 1992 令 S 為所有可以寫為 0.abcabcabcabc... 形式的有理數形成的集 合, 其中 a, b, c 不一定相異 如果將 S 中所有的元素寫為最簡分數 r/s 時, 請問共有多 少個不同的分子?

26 排容原理 69 解 : 因為 0.abcabcabcabc... = 0.abc = abc 999, 又 999 = 7, 所以分成下列兩種情形討論 : (1 abc 不為 且不為 7 的倍數, 則 abc 999 即為最簡分數 假設 S 為 1 到 999 之所有可能分子形成的集合, A 表示 1 到 999 中 的倍數形成的集合, A 7 表示 1 到 999 中 7 的倍數形成的集合, 故即為求 A A 7 由排容原理 (2 最簡分數之分子 r 為 或為 7 的倍數 : A A 7 = S A A 7 [ ] [ ] [ ] = = = 648 (i 假設 abc = 81k, k = 1, 2,..., 12, 經過化簡可得最簡分數為 k, k = 1, 2,..., 12 7 故此時最簡分數之分子 r 為 的倍數有 12 種可能 (ii 假設 abc = 7 2 m, 經過化簡可得最簡分數為 以最簡分數之分子不可能為 7 的倍數 7m 27, 則此時最簡分數值會恆大於 1, 所 由 (1 (2 可得, 共有 = 660 種不同的分子 例 : (AIME 隨機將一個 正方形中的方格塗上紅色或是藍色 ( 塗色機率 各為 1/2, 試求沒有出現紅色的 2 2 正方形的機率為多少? 解 : 出現紅色的 2 2 正方形會有下列四種情況 假設 A 1 表示出現情況 1, A 2 表示出現情況 2, A 表示出現情況, A 4 表示出現情況 4, 故題意即為求 P(A 1 A 2 A A 4

27 70 數學傳播 卷 期民 98 年 9 月 由排容原理 4 P(A 1 A 2 A A 4 = 1 P(A i + P(A i A j P(A i A j A k + P(A 1 A 2 A A 4 i=1 i<j i<j<k ( 4 ( 1 ( 1 6 ( ( ( = = 例 4: (ChiaMO 1989 令 S 1 = {z C z = 1}, 對於所有函數 f : S 1 S 1, 且 假設 f 1 = f, f +1 = f f, 1 若 f i (w w, i = 1, 2,..., 1, 但 f (w = w, 則稱 w S 1 為函數 f 且週期為 的一個週期點 如果 f(z = z m, 其中 m 為 正整數, 試求週期為 1989 的函數 f 的週期點個數 解 : 定義 U 為使得 f (z = z 且為集合 S 1 的複數 z 所形成的集合, 所以 f (z = z m, 因此 U 由長度為 1 之複數的 m 1 方根所形成的集合 已知題意欲求週期 = 1989, 但在 U 1989 中的週期點其週期不可小於 1989, 又 1989 = , 故需將週期分別為 1989/ = 66, 1989/1 = 15, 1989/17 = 117 的週期點去除, 即為 U 1989 (U 66 U 15 U 117, 所以週期點個數為 U 1989 U 66 U 15 U 117 利用排容原理可求得週期為 1989 的週期點個數為 U 1989 (U 66 U 15 U 117 = U 1989 ( U 66 + U 15 + U 117 U 66 U 15 U 66 U 117 U 15 U U 66 U 15 U 117 = U 1989 ( U 66 + U 15 + U 117 U 51 U 9 U 9 + U = (m [(m (m (m (m 51 1 (m 9 1 (m (m 1] = m 1989 m 66 m 15 m m 51 + m 9 + m 9 m 例 5: (USAMO 1972 假設一個隨機選擇器只能從 1, 2,..., 9 中以等機率的選取出一個數, 試定在 次選擇後 ( > 1, 選出的 個數的乘積能被 10 整除的機率 解 : 因選出的 個數的乘積需被 10 整除, 故在 次選取中需至少選擇一次 5, 並且至少 有一次選擇偶數

28 排容原理 71 假設 A 表示在 次選擇中沒有一次選到 5, B 表示在 次選擇中沒有一次選到偶數, 故 所求機率即為 P(AB 由排容原理 P(AB = 1 P(A B = 1 [P(A + P(B P(AB] ( 8 ( 5 ( 4 8 = 1 + = 故選出的 個數的乘積能被 10 整除的機率為 例 6: (IMO 1989 假設 為正整數, 則稱集合 {1, 2,..., 2} 的一個直線排列 (x 1, x 2,...,x 2 具有性質 P, 是指在 {1, 2,..., 2 1} 中至少有一個 i, 使得 x i x i+1 = 試證明對於任意, 具有性質 P 的排列數比不具有性質 P 的排列數多 解 : 由題意知, 只需證明具有性質 P 的排列數大於全部排列數的一半即可 假設具有性質 P 的排列數為 m, A k 表示 (x 1, x 2,...,x 2 中 k, + k 相鄰的所有排 列的集合, 其中 k = 1, 2,..., A 1 表示 1, + 1 兩個數在排列中為相鄰, 所以 A 1 = (2 1! 2!, 故 A k = 2(2 1!, k = 1, 2,..., 而 A 1 A 2 表示 1, + 1 與 2, + 2 分別相鄰, 所以 A 1 A 2 = 2 2 (2 2!, 亦可推得 A k A l = 2 2 (2 2!, 1 k < l 又 2 個正整數的 排列數為 (2! 種 由排容原理知 m A k k=1 1 k<l A k A l = ( 2(2 1! 1 = (2! 2( 1(2 2! = 2((2 2! ( 4(2 2! 2 因為 > 1 2, 所以 m 2((2 2! > 1 2 (2!, 故得證 參考文獻 1. Balakrisha, V. K. (1994. Combiatorics, 1st editio. McGraw-Hill, New York. 2. Gelca, R. ad Adreescu, T. (2007. Putam ad Beyod. Spriger, New York.. Ross, S. (2006. A First Course i Probability, 7th editio. Pretice Hall, New York. 4. 單壿 葛軍, 國際數學奧林匹克大陸隊訓練教材, 九章出版社, 台北, 中國數學奧林匹克委員會 開南大學數學系, 世界數學 奧林匹克 解題大辭典 組合卷, 河北少年兒童出版社, 河北, 本文作者任教國立中山大學應用數學系