再谈「组合计数的方法」.PDF

再談 「 合計數的方法」 張鎮華 一. 前言 李政豐 [1] 和陳世傑 [2] 在數學傳播談論這樣的題 目: 「白球 2 個, 黑球 2 個, 黃球 2 個, 紅 球 2 個全部放在一個袋子中, 每次從中取一球, 問紅球先取完的機率是多少?」 李文採用排容原 理 , 從兩種球, 各 自有一不一定是 2 的球數去算機率; 再擴張到三種、 四種、 五種球, 並猜測出一 般的公式, 真可謂匠心獨具。 陳文則堅持在有 m 種球 但每種還是 2球, 並從 m 是 2 開始, 算到 3 和 4, 並從而猜測一般 m 的答案是 1 , 整體清楚明白, 學生很容易懂。 在這個小文裡, 我們要 m 來說明他們的一般公式都是對的。 二. m 種顏色的球每種 k 球 我們先來談李文原來的題 目, 用到的方法對於一般有 m 種球每種 k 球的證明和 m = 4 及 k = 2 的原來題 目並沒有什麼不同, 所以乾脆就證明這一般的結果。 我們用的方法是一對一對應法, 一般來說要說明兩個集合元素個數一樣多, 最直接的方法 是在這兩個集合的元素間建立出一對一的對應, 這方法很直觀, 卻能解決許多問題。 最著名的例 子是 Caley 定理的證明, 這個定理是說: 「n 個點的完全圖共有 nn−2 個生成樹」, 最早的證明 是比較複雜的, 後來, 有人將這些生成樹和 「長度 n − 2 佈於 {1, 2, . . . , n} 的有序字列」 做出 一對一的對應, 因此這兩類物件的個數一樣多, 而後者很容易知道是 nn−2 , 所以前者的數目就 是 nn−2。 現在讓我們回到原來的問題, 首先, 令 S 表示每次從袋中取一球, 但不放回, 並且將這 km 球全部取完的樣本空間, 而 Si 是 S 中第 i 種球最先取完的事件 (1 ≤ i ≤ m)。 我們並不需要 真正去算 S 的元素個數, 雖然我們知道它是 (km)!/(k!)m。 我們真正需要說明的只是 |S | = |S | = = |S |. 1 2 m 1 如果這是對的, 則對於任一個 i, 第 i 種球最先被取完的機率就是 。 m 14 再談 「 合計數的方法」 15 要看出 i = j 時 |S | = |S | 並不難, 我們考慮下面的對應: 對於 S 中的任一取球法 i j i ′ ′ ′ (a , a , . . . , a ) 對應到 (a , a , . . . , a ), 其中 1 2 km 1 2 km   j, 當 a = i;  t  a′ = i, 當 at = j ; t