<4D F736F F D D DB1C6AE65ADECB27AA4CEC0B3A5CEC17CA8D228A4EBA55A4F4B29>

Size: px

Start display at page:

Download "<4D F736F F D D DB1C6AE65ADECB27AA4CEC0B3A5CEC17CA8D228A4EBA55A4F4B29>"

作昙盛
7 years ago
Views:

1 許介彥私立大葉大學電機工程學系小於的正整數總共有九個, 其中與互質的有,, 7, 9 等四個 ; 小於 5 的正整數中與 5 互質的整數則有,, 4, 7, 8,,, 4 等八個你能很便捷地答出所有小於的正整數中與互質的數有幾個嗎? 這個問題由集合的觀點不難解決本文假設所討論的集合都是元素個數有限的集合即 fte set, 並且用來表示集合的元素個數, 因此如果 {,, 5, 7}, 那麼 4, 因為含有四個元素壹排容原理數學上經常碰到的一種情況是需要計算兩個集合的聯集總共有多少個元素, 也就是對任意兩個集合和, 我們想要計算的值 ; 我們不能只是單純地將和相加, 因為這樣一來有些元素會被算到兩次, 修正的方法顯然是將兩個集合的共同元素的個數減掉使得和中的每個元素都被算到正好一次, 因此以下關係成立 : 上式的等號右邊雖然有三項, 但是對許多問題來說, 計算這三項會比直接算左邊的來得容易一般而言, 計算交集的元素個數會比計算聯集的元素個數容易對任意三個集合,,, 我們是否也能透過計算集合間的交集的元素個數來算出的值呢? 由於我們可以將看成是和這兩個集合的聯集, 因此可以應用剛才的式子得其中的我們已經知道如何展開了, 而由恆等式可得因此這就是我們要的式子 ; 將等號右邊各項的位置稍作調整可得請注意上式的等號右邊是先將個別集合的元素個數相加, 但是因為有些元素 - 9 -

2 科學教育月刊第 65 期中華民國年月被重覆計算了, 因此接著將任兩個集合的交集的元素個數減掉, 但是這樣一來又減過頭了, 因此又需將三個集合的交集的元素個數加回來觀察以上當集合數為兩個及三個時的情形, 有一個模式已經慢慢顯現出來了一般而言, 對任意個集合,,,, 下式恆成立 : 上面的式子是有名的排容原理 the cle of cluso ad excluso, 簡稱為 PIE, 也稱作 seve cle 當我們要根據上式算出個集合的聯集的元素個數時, 我們先將個別集合的元素個數相加總共有個數相加, 再減去每兩個集合的交集的元素個數總共減去了 C, 個數, 再加上每三個集合的交集的元素個數總共加上了 C, 個數, 再減去, 直到最後加上或減去所有個集合的交集的元素個數為止, 這一系列包容與排除的運算就是排容原理名稱的由來, 中文也稱做容斥原理或取捨原理如果我們令,,, 等, 那麼排容原理可以更簡潔地表為或附帶一提, 集合的聯集關係是對應到邏輯上的或, 而交集則對應到邏輯上的且, 因此是由屬於或屬於或屬於的元素所成的集合, 而則是由屬於且屬於且屬於的元素所成的集合貳另一個形式如果集合和都是某個宇集 U 的部分集合, 那麼集合 U 中既不屬於也不屬於的元素有幾個呢? 如果 U N, 答案顯然是 N, 也就是的補集的元素個數下圖的陰影部分同理, 對任意個集合,,,, 如果它們全都是某個宇集 U 的部分集合而且 U N, 那麼 U 中不屬於任何的元素所成的集合就是, 也就是的補集, 其元素個數為 N N - -

3 這個式子可算是排容原理的另一個形式, 可用來算出不屬於且不屬於且且不屬於的元素個數, 在解決許多問題時也很有用排容原理要如何推導呢? 仿照我們前面由推導出的作法, 讀者不難由個集合的情形推導出個集合的情形, 因此排容原理不難用數學歸納法來推導雖不難但是頗煩, 讀者可自行一試本文稍後還將介紹另一種推導方式, 不過接下來讓我們先看排容原理的幾個應用參圓桌上的夫妻 B C D E 等五個男生的太太分別是 a b c d e 五個女生, 他們人即將圍著一張圓桌而坐, 入座的方式是由五個男生先隨機就座, 不過每兩人之間都空出一個座位, 然後五個女生再隨機坐在剩下的五個座位中請問 : 全部個人都就座後, 沒有任何一對夫婦比鄰而坐的機率是多少? 為了簡單起見, 如果某種坐法可以經由另一種坐法旋轉而得, 我們將這兩種坐法視為相同的坐法 ; 因此我們不妨將看成是固定坐在這個座位中的某個位子上例如最靠近門的位子, 如此一來不難看出五對夫婦圍著圓桌而坐且男女相間的坐法總共有 4!5! 88 種, 因為 BCDE 有 4! 種坐法而 abcde 有 5! 種坐法我們只要知道這 88 種坐法中有至少一對夫婦相鄰的坐法有幾種, 用 88 減去此數即為沒有任何一對夫婦相鄰的坐法數, 再將結果除以 88 即為沒有任何一對夫婦相鄰而坐的機率請注意有至少一對夫婦相鄰也就是 a 相鄰或 Bb 相鄰或 Cc 相鄰或 Dd 相鄰或 Ee 相鄰, 引號裡我們用了好多次的或, 這顯然是集合的聯集關係, 因此可以用排容原理來解決假設為與 a 相鄰的所有坐法所成的集合, 為 B 與 b 相鄰的所有坐法所成的集合,, 5 為 E 與 e 相鄰的所有坐法所成的集合, 如此一來 4 5 就是有至少一對夫婦相鄰的坐法數首先考慮是多少如果我們先忽略和 a, 讓其他八人隨機且男女相間地坐在八個座位上, 坐法總共有!4! 44 種仿照前面的作法, 可先將 B 看成是固定坐在最靠近門的位子, 接著和 a 可以一起被安插到已經坐好的八人的任意兩個人之間, 這總共有八種可能的選擇, 因此同理, 接著考慮是多少同樣地, 我們先讓 CDE 與 cde 就座, 坐法有!! 種, 接著讓與 a 一起坐在已就座的六人的任意兩人之間, 總共有六種選擇 ; 接著讓 B 與 b 一起坐在已就座的八人的任意兩人之間與 a 之間除外, 總共有七種選擇 ; 因此同理可知,,, 4, 5 個集合的交集的元素個數都是 54 的任意兩 - -

4 科學教育月刊第 65 期中華民國年月接著考慮的值我們先讓 DE 與 de 就座, 坐法有!! 種 ; 接著讓與 a 一起坐在已就座的四人的任意兩人之間, 總共有四種選擇 ; 接著讓 B 與 b 一起坐在已就座的六人的任意兩人之間與 a 之間除外, 總共有五種選擇 ; 接著讓 C 與 c 一起坐在已就座的八人的任意兩人之間與 a 之間及 B 與 b 之間除外, 總共有六種選擇 ; 因此同理可知,,, 4, 5 的任意三個集合的交集的元素個數都是 4 透過類似的推導可知,,, 4, 5 的任意四個集合的交集的元素個數都是!! 4 5 接著考慮 4 5 的值我們先讓所有五個男生就座, 坐法有 4! 4 種 ; 接著讓五個女生入座, 此時坐法只有兩種每個女生都坐在配偶的左邊或都坐在配偶的右邊, 因此最後, 我們由排容原理得因此沒有任何一對夫婦相鄰的坐法總共有種, 發生的機率為.8 88 探討對夫婦圍著圓桌男女相間而坐且夫婦皆不相鄰的坐法數的問題在數學上稱為 Méage oblem 肆旅客與捷運列車一輛包含了節空車廂的捷運列車進站後有名旅客上了車與皆為正整數, 每名旅客選擇車廂的方式是隨機的請問 :a 每節車廂裡都有旅客的機率是多少?b 所有個車廂中有正好個車廂裡有旅客的機率是多少? 由於名旅客進入個車廂的方法總共有種每個人都有個選擇, 我們只要知道其中有至少一個車廂是空車廂的乘坐方法有幾種, 再用減去此數即為每節車廂裡都有旅客的方法數, 再將結果除以即為每節車廂裡都有旅客的機率有至少一個車廂是空車廂也就是第一個車廂是空車廂或第二個車廂是空車廂或或第個車廂是空車廂, 又用了好多次的或, 因此又是集合的聯集, 排容原理又可以派上用場假設為第一個車廂是空車廂的所有乘坐方法所成的集合, 為第二個車廂是空車廂的乘坐方法所成的集合,, 為第個車廂是空車廂的乘坐方法所成的集合, 如此一來就是這個車廂中有至少一個車廂是空車廂的乘坐方法數我們立即可知, 因為每名旅客都可以選擇進入個車廂中的任何一個同理, 對任意 - -

5 - - 兩個不同的集合與而言,, 因為每名旅客都可以選擇進入個車廂中的任何一個 ; 同理可得等 ; 因此每節車廂裡都有旅客的乘坐方法數因此等於這可以更簡潔地表為而每節車廂裡都有旅客的機率就是接著我們考慮 b 小題, 也就是個車廂中有正好個車廂裡有旅客的機率由於從個車廂中選出個車廂的方法有, C 種, 而由 a 小題可知名旅客進入個車廂而且這個車廂裡都有旅客的乘坐方法有種, 因此個車廂中有正好個車廂裡有旅客的乘坐方法有種, 發生的機率為本題的 a 小題其實是 b 小題在時的特例由於當時顯然不可能每節車廂裡都有旅客, 因此我們由 a 小題可得恆等式的一個組合解說 ; 另一方面, 當時, 每節車廂裡都有旅客的乘坐方法顯然有! 種, 因此下式也一定成立 :!. 伍字串的個數由字母和 B 各兩個總共可以排列出 BB, BB, BB, BB, BB, BB 等六個不同的字串, 其中相同的字母不相鄰的字串只有 BB 與 BB 兩個假設 a a a,,, 是個相異的字母, 請問 : 利用每個字母各兩個總共個字母總共可以排列出多少個沒有任何相同的字母相鄰的字串?

6 科學教育月刊第 65 期中華民國年月由全部個字母總共可以排列出!!! 個不同的字串, 我們只要知道其中有至少一對相同的字母相鄰的字串有幾個, 再用!/ 減去此數即為沒有任何相同的字母相鄰的字串數有至少一對相同的字母相鄰也就是兩個 a 相鄰或兩個 a 相鄰或或兩個 a 相鄰, 同樣是集合的聯集關係, 可以用排容原理來解決假設是兩個 a 相鄰的所有字串所成的集合, 是兩個 a 相鄰的所有字串所成的集合,, 是兩個 a 相鄰的所有字串所成的集合, 如此一來就是有至少一對相同的字母相鄰的字串數要利用排容原理, 我們必須知道,, 等集合的任意個, 集合的交集的元素個數是多少 ; 請考慮當個集合為,,, 時的情形, 此時的為字串中的兩個 a 相鄰且兩個 a 相鄰且且兩個 a 相鄰的字串數, 這種字串可以由下面的方法製造出來 : 先取 a, a,, a 等字母各一個來和其他種字母各兩個組成長度為的字串, 然後再讓所得字串中的 a, a,, a 等字母分別連續出現兩次即可, 因此! 此式對任意個集合都適用, 因此所求為!! 看了上面的幾個例子, 讀者應該可以體認到排容原理確實是處理許多計數問題時相當有力的工具以下我們繼續介紹排容原理除了數學歸納法以外的另一種推導方式, 所推導的是前述排容原理的第一種形式陸排容原理的推導假設某個元素同時屬於,,, 等個集合中的 t 個集合, 此元素在排容原理的 Σ 中被算了 t 次, 在 Σ 中被算了 C t, 次, 在 Σ 中被算了 C t, 次等, 因此該元素在排容原理中總共被算了 t t t 次 ; 由二項式定理我們知道 t t t t t t t t t t t t t 即 t t t t t t t 因此該元素在排容原理中被算了不多不少正好一次, 這正是我們想要的結果柒尤拉函數接下來我們考慮本文一開始所提出的問題 : 對任意正整數假設大於, - 4 -

7 所有小於的正整數中與互質的數有幾個? 不大於的正整數總共有個, 我們只要先求出其中與不互質的數有幾個, 再用減去此數即為所求如果總共有,,, t 等 t 個質因數, 那麼與不互質的數就是的倍數或的倍數或或 t 的倍數, 顯然又是集合的聯集, 可用排容原理來解決假設為不大於的正整數中所有的倍數所成的集合 t, 我們可以用排容原理求出 t, 也就是不大於的正整數中與不互質的數的個數的值很容易求得, 因為就是的倍數中不大於的數的個數, 因此 / 同理得, 等, 因此所求為 t t 4 t t, t 最後一個式子是成立的, 讀者將各括號乘開即知數學上常將小於的所有正整數中與互質的數的個數記作, 稱此函數為尤拉函數 Eule fucto 或 Eule s totet fucto 舉例來說, 由於 6 5, 因此所有小於 6 的正整數中與 6 互質的數總共有個 5 捌一般化的排容原理對任意個集合,,,, 我們前面曾經將排容原理簡潔地表為以下我們介紹幾個更具一般性的性質僅作描述而不予証明性質一 : 對任意個集合,,,, 同時屬於其中的至少個集合的元素的個數為排容原理是此性質當時的特例當且時, 上式是說 : 同時屬於,, 中的至少兩個集合的元素下圖的陰影部分的個數為 - 5 -

8 科學教育月刊第 65 期中華民國年月對照下圖不難看出此關係為真性質二 : 對任意個集合,,,, 同時屬於其中的正好個集合的元素的個數為同樣以且為例, 上式是說 : 同時屬於,, 中的正好兩個集合的元素下圖的陰影部分的個數為由圖中不難看出此關係為真性質三 : 要利用排容原理算出,,, 的聯集的元素個數時, 如果我們在計算的過程中提早結束而沒有算到最後, 所得雖然可能不是正確值, 不過卻可以肯定所算出來的值與正確值相比是太大還是太小即誤差是正數或負數一般而言, 正確值正確值正確值 4 正確值也就是當為偶數時, 而當為奇數時, 這些不等式通稱為 Bofeo equaltes, 因義大利數學家 C. E. Bofeo8996 而得名玖結語式本文的捷運列車問題所提及的恆等除了文中的推導外亦不難利用生成函數導出 ; 以恆等式 x x x x 做為起點, 將等號兩邊同時對 x 微分然後再同時乘以 x, 並將上述步驟重複次, 然後將 x 以代入即得對一個已知正整數而言, 是否能快速求得的值在某些場合相當重要 ; 當不太大時, 我們當然不難將做質因數分解, 然後用本文的方法順利求出的值, 但是當很大時例如是一個 - 6 -

9 包含了位數的十進位數, 要將做質因數分解的工作有可能變得相當困難, 困難到即使借助電腦都很難在短時間內達成事實上, 如何快速地將整數做質因數分解的問題一般稱作 me factozato 是數學上有名的難題, 現代密碼學中有些加密法的安全性正是建立在這個問題的困難度上 ; 如果有朝一日有人找到了能快速地將大整數質因數分解的方法, 或是發明了不需做質因數分解就能快速求得的方法, 某些目前廣受信賴的加密法將頓時變得不堪一擊排容原理雖然簡單卻很有用, 與鴿同一個櫃子裡宴會中他們全都喝醉了, 離開時都醉醺醺地從櫃子裡隨機拿了一頂帽子就走了請問 : 他們當中有至少一人拿走的帽子是自己的帽子的機率是多少?. 將五件不同的工作分配給四個人, 每個人至少須被分配到一件工作, 總共有多少種分法? 答案 :4 種. 滿足方程式 x x x 且 x, x 4, x 6 的非負整數解有幾組? 4. 持續投擲一顆骰子, 不超過 5 次就能擲出點數,,, 4, 5 至少各一次的機率是多少? 答案約為.698 籠原理可並列為組合數學中的兩個最基本的定理, 都是處理組合問題時應隨身攜帶的工具拾練習題以下是幾個與本文相關的問題, 提供讀者參考參考資料許介彥 : 幾個恆等式的組合証明科學教育月刊, 第 54 期 Rose, K. H. 7.Dscete Mathematcs ad Its lcatos 6th edto.new Yo: McGaw-Hll. Tomescu, I Poblems Combatocs ad Gah Theoy. Joh Wley & os.. 有個人各戴著一頂帽子去參加宴會, 在到達會場後他們都將帽子放到 - 7 -

0 0 = 1 0 = 0 1 = = 1 1 = 0 0 = 1

0 0 = 1 0 = 0 1 = = 1 1 = 0 0 = 1 0 0 = 1 0 = 0 1 = 0 1 1 = 1 1 = 0 0 = 1 : = {0, 1} : 3 (,, ) = + (,, ) = + + (, ) = + (,,, ) = ( + )( + ) + ( + )( + ) + = + = = + + = + = ( + ) + = + ( + ) () = () ( + ) = + + = ( + )( + ) + = = + 0