基本計數原理 在殷商時代, 透過爻 ( 因ㄧㄠ ˊ, 即卦上的橫線 ) 與卦的排列和變化來解釋 各種自然現象, 經後人整理成為中國最古老的典籍之一 - 周易 若每次取 個爻, 有 4種不同的排列, 稱為 四象 ; 若每次取 個爻可得 8種相異的排 列, 稱為 八卦, 在周易裡還把每次取 個卦形成的 8 64 種排列稱為 八 卦, 宋代科學家沈括也討論過圍棋棋局總數的問題 : 因棋盤上共有 99 6 6 格點, 因此共有 種棋局 而西元前 600 年左右, 印度人也討論過這樣的問題 : 酸 甜 苦 辣 鹹 澀 6 種味道可調配出多少種不同的味道? 答案是 : 單味 6 種 雙味 5 種 三味 0 種 四味 5 種 五味 6 種 六味 種, 共 6 種味道 計數原理常見的有窮舉法 樹狀圖 一一對應原理 加法原理 乘法原理 排容原理以及遞迴關係式 一 窮舉法 : 在有限的集合裡, 一一列舉出所有可能的解 ( 即可行解 ), 並從中尋找最適合 的解, 也是解決計數問題的一種方法 例 : 在邊長 的正三角形 ABC 中, 在每一邊的兩個三等分點中, 各選取一點而 連成一個三角形, 問共可連成幾個三角形? 這些三角形中共有幾個銳三角形? 幾個直角三角形? 幾個鈍三角形? 解 : 設 AB BC CA 邊上的等分點依次為 D E F G H I 如下圖 : 所連成的三角形有 DFH DFI DGH DGI EFH EFI EGH EGI 共 8 個三角形 而其中 DFH 及 EGI 是邊長 的正三角形, 其餘 6 個是 的直角三角形
隨堂練習 : 一個房間的地面是由 個正方形所組成, 如下圖 今想要用長方形磁磚鋪滿地面, 已知每一塊長方形磁磚可以覆蓋兩個相鄰的正方 形, 即 或 試問用 6 塊磁磚鋪滿房間地面的方法共有多少個? 例 : 周長為 0 而三邊長度均為整數的三角形共有多少個? 解 : 設三角形邊長為 abc 且滿足 ab c 0 ab c 因三角形兩短邊長的合大於最長邊的長即 b c a, 所以 0 a b c a a a 0 a b c a a a a 即 0 a 5 列舉所有有的理解如下 : a 0 4 4 4 4 4 4
b 0 0 0 9 0 9 4 0 9 8 c 0 8 9 6 7 8 9 4 5 6 7 8 4 5 6 7 8 隨堂練習 : 三邊長均為正整數且最長的邊長為 的正三角形共有多少個? 二 樹狀圖 : 例 的 8 個三角形也可用樹狀圖表示 樹狀圖在不具規則的問題中比較能表現出它的效力 例 有一長方體如右圖, 由頂點 A 沿著稜線走到對角線 ( AG ) 的另一頂點 G, 每一個頂點最多只能經過一次, 問共有多少種走法? 解 : 由 A 經 B 到 G 的所有走法, 以樹狀圖表示如下 : 同理由 A 經 C ( 或 D ) 到 G 也有相同的走法, 因此共有 6 8 種走法 隨堂練習 : 有一四面體 ABCD 如右圖 由頂點 A 沿著稜線走到頂點 B 每個頂點最多只能經過一次, 問共有多少種走法 三 一一對應原理 設 A B 是兩個集合, 且函數 f 從 A 映到 B, 計為 f : A B, 若對於集合 A 中的任兩個元素 ( 當然不相等 ), 恆有 f f 的一對函數 如 f x x, gx x 中的任一元素 b, 在 A 中有一元素 a, 使得, 則稱 f 是從 A 映到 B 都是從 R 應到 R 的一對一函數 若對於 B f a 成函數 ( 或稱蓋射 ), 如 h x x 是從 R 映到 0 0, b, 則稱 f 是從 A 映到 B 的映 x x 的映成函數, 但不 是從 R 映到 R 的映成函數, 而 x log x 是從 0 0, x x 映到?? 的一對一
x log 且映成的函數 一對一且映成的函數會有 R 函數 如 是 gx x, 又如 px x 的反函數就是 g x x 例 4: 已知 是自然對數的底數, 它是個無理數, 且.788..., 設 f x x x x x 試證 : f 是從 R 映到 (,) X X 數 x 的反映函數就 的一對一且映成的函數, 並求其反函 解 : f x 設, R x x x x, 將 f 且 f f x x 的分子 分母同乘以, 得 f x x x, ( )( ) ( )( ) ( ) ( ) 因 f f 同義於 f = f = 所以 f 數 再設 y f x, 即 x x y y x y y y, x 因 0, 所以 y 0 ( y )( y ) 0 y, y x 是一個一對一函 y 的範圍即為函數值 f x 的範圍, 將它寫成集合就成為值域 y y =(-,) y 底下, 證明 f : R (,) 是個映成函數 設 y (,), 可找到 x log ( ) 使 y y y log ( ) x y y y 得 f x y x y log ( ) y y y
而反函數 y x f x log ( ) log ( ), x(,) y x 函數 f x x x 的略圖描繪如下, 其中 y, y 是兩條漸近線 由例 4, 可知 f : A B 是個映成函數的充要條件是 : 值域等於對應域, 即 f A B 隨堂練習 : 設 f x x x, 試證 f 是從 R 映到 R 的一對一函數, 並作函數 y f x 的圖形 隨堂練習中的 f x x x, 其實也是從 R 映到 R 的映成函數, 介紹卡丹 (Cardao) 公式的解法如下 設 y x x, 令 x u v, 兩邊立方得 x u v uv( u v) x uvx u v 0 因此 uv u, v 為 t ( ) u v y u v y uv 7 4 y y yt 0 的兩根, 而 7 y y t 7 4 7 4 4 y y y y 因 x x y 0, 洽有一實根, 所以 x u v 4 7 4 7 檢驗一下 4 4 4 4 y y y y y y y y x x ( )+( ) ( )( ) x x 4 7 4 7 4 7 4 7
4 y y y x x 4 7 y 設 y R 存在 y y y y 4 7 4 7 4 4 x 使得 f x y, f 確是 從 R 映到 R 的映成函數且 f x x x x ( x) 4 7 4 7 4 4 設 A B 是兩個有線集合, 且函數 f : A B ( 一 ) 若 f 是一個一對一函數, 設 A a a a, 因,,... f a f a f a 是集 ( ),..., 合 B 中兩兩相異的元素, 因此 A B, 其中 A 表示集合 A 的元素個數 ( 二 ) 若 f 是個一對一且應成的函數, 因 B f A f a a a B A 例 5: 設集合 S a a a,,..., 因此 ( ),,..., 試求 S 的所有子集合的個數 解 : 設 S 的所有子集合所成集合為 S X X S, i,= 而 T x, x..., x x 或 0, i,,..., 函數 f : s T 當 A S 時, 令 f A x x x ( ),,..., 當 xi () 設 AB, S 且 A B A時, x, 否則 x 0, 其中 i,,..., 存在某個元素 ai i i S 但不同時屬於 A 與 B, 此 f( A ) 與 f( B ) 的第 i 個分量必不相等, 即 f ( A) f ( B), 故 f 是個一對一函數 x x x T, 當 xi 時, a i S, 當 xi 0 () 設,,..., 因此存在 A S, 使得 f ( A) x, x,..., x 時, a i S, i,,...,, 故 f 為映成函數 因 ( x, x,..., x ) 中每一個 x i 不是 就是 0, 所以集合 T 共有 個元素 又 f : s T 是個一對一
s 且映成的函數, 因此 T 隨堂練習 : 東山里舉辦桌球單打比賽, 每場比賽一定要分出勝負, 採單敗淘汰制 ( 即輸一場就淘汰 ), 現有 0 人參賽, 問總共要比賽幾場才能產生冠軍? 四 加法原理 ( 分類 ) 若完成某件事情有 類方法, 而每一類方法中分別有 m, m,..., m 種方法, 不論採用這些方法中的任何一種, 均能單獨完成這件事情, 那麼要完成這件事情 共有 m m... m 種方法, 若使用集合的語法, 加法原理也可敘述如下 設 A 是一個有限集合, 而 A, A,... A K 是 A 的一些兩兩互斥 ( 及 Ai Aj, 其中 i j, 且 i, j,,... ) 的子集合, 且 A A A... A, 那麼就有 A A A... A, 我們稱 A, A,... A K 為集合 A 的一個分割 運用加法原 理來計數的關鍵是如何適當的找到集合 A 的一個分割 A, A,... A K 例題 6: 設向量 a 的始點與終點均為正方體的頂點, 且 a 0, 問共有多少個相異 的 a 向量? 解 : 正方體 ABCDEFGH 如右圖 設正方體的一稜長為, 那麼向量 a 的長度有 三類 : (): a, 有 AB AD AE 及相反向量, 共 6 個 (): a, 有 AC BD AF BE AH ED 及相反向量, 共 個 (): a, 有 AG EC BH DF 及相反向量, 共 8 個 這三類兩兩互斥, 由加法原理, 向量 a 共有 6++8=6( 個 ) 隨堂練習下圖是正五邊形與共對角線所構成的圖形, 問所有的三角形共有多少
個? 五 乘法原理 ( 分段 ) 若完成某件事情必須經過 個步驟, 而每一步驟分有 m, m,... m 種方法, 那麼 完成這件事情共有 m m... m 種方法 例 7: 關於正整數 540 正因數的問題 : () 540 有多少個正因數? () 540 正因數的總合為何? () 540 正因數的成績為合? 解 : 先做 540 的標準分解式 540 5 a b c () 540 的正因數是 5 的形式, 其中 a 0,or, b 0,, or, c 0or, 因此 abc,, 依次有,4, 種選擇, 即將求 540 正因數的個數這件事分成 個步驟, 每一步驟分別有,4, 種方法, 所以完成這件事的方法為 4 4 ( 種 ), 即 540 的正因數有 4 個 () 將 () 中的正因數相加 : 5 5 5 5 5 7 406 680 () 將 () 中的 改為, 可得
5 5 4 4 5 540 a b c 隨堂練習 : 設正整數 p q r, 其中 pqr,, 為正質數, 而 abc,, 都是正整數, 試求 解下列問題 () 有多少個正因數? () 的正因數總和等於多少? () 的正因數乘積等於多少? 關於函數惡樹的問題也可運用乘法原理來處理 例 8 設 AB, 為兩個有限集合, 且 A, B, 函數 f : A B () 函數 f 共有多少個? () 若, 且 f 是一對一函數, 問函數 f 共有多少個? () 若, 且 f 是一對一又映成的函數, 問函數 f 共有多少個? 解 : () 集合 A 中的任一元素 a,( i,,..., ) 都可以唯一對應到 B 中的任一元素, 因 B i 有 個元素, 由乘法原理, 共可定義... 個函數 () 集合 B 的 個元素中洽有一個是 a 的函數值, 集合 B 中剩下的 個元素洽 有一個是 a 的函數值, 依此類推, 集合 B 中剩下的 個元素中洽有一個 是 a 的函數值, 由乘法原理可定義... 個一對一函數, 將此數 計為 P, 稱為 中取 的排列數 () 由 () 得一對一且映成的函數共有 P =...! ( 個 ), 又
............ P!!! 當 時, P 又 P!, 所以規定 0! 0! 運用函數的特性 ( 定義域 A 中的任一元素唯一的對應 B 中的某一元素 ), 可以處理下列問題隨堂練習 : 將三本不同的書全部分給甲 乙 丙 丁 戊五人 求下列個小題的分法 () 任意分 () 每人至少一本 () 甲至少一本 一筆畫 的問題, 也可以利用乘法原理處理 例 9 誠慧社區巷道如下, 垃圾車從 A 進入, 由 B 離去, 須走過每一條巷道, 但 走過的巷道不再走, 問共有多少種走法?( 上述走法的一筆畫 ) 解 : 圖 ( 一 ) 圖 ( 二 ) 圖 ( 三 )
() 關於圖 ( 一 ) 的解, 繪出精密圖如右 : 由 A 到 P 有 條路 徑, 如走甲路線到 Q, 又有 條路徑, 如走乙路線到 P, 最 後走丙路線到 Q, 然後離去, 由乘法原理, 共有! 種走法 () 關於圖 ( 二 ) 的解, 再利用 () 重複兩次, 可得 (!) 6 種走法 () 關於圖 ( 三 ) 的解, 分成 先走上一圈, 再走下一圈 及 先走上半圈 下半圈, 再走完 兩類, 每一類都各有 (!) 種走法, 由加法原理共 有 (!) 7種走法 隨堂練習 : ( 一 ) 下列圖形, 由 A 走到 B, 一筆畫的走法有多少種? () () ( 二 ) 試作一個無法以一筆畫走完的圖形 如 六 排容原理 在加法原理中, 必須先找到集合 A 的一個分割 A, A,..., A K 才會有 A Ai 的漂亮結果, 假若找不到 A 的一個分割, 只好使用排容原理來計數 排容原理就是計算 A A... A 的方法 在 及 時, 都可以使用文氏圖, 得到 : i
A A A + A A A A A A A + A A A A A A A A A A A 但 4 時即, 文氏圖不容易處理, 使用 及分配律 A B C ( A B) A C 可推出, 再使用數學歸納法可以推出 的 一般情形 A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A 而 的排容原理是 A A... A A A A A A A... A A... A 其中 i j i j i i j i j i i j i j Ai Aj 是指兩兩交集的個數和共有 C 個, 同理 Ai Aj A 是參參交集的個數和, 共有 C 個, 組合! 是 中取 ( 只取不排 ) 的方法數, 即 C! P, 亦即 C C 54 C 0! 5 5 P!, 如!!( )! 例 0: 設 A B 均為有限集合, 且 A, B, 函數 f : A B, 若, 且函數 f 是映成函數, 問函數 f 共有多少個? 解 : 設 A a, a,..., a, B b, b,..., b C 令在集合 B 中, b 不是函數值的函數, 所成的集合為 B b 不是函數值的函數, 所成的集合為 B
b 不是函數值的函數, 所成的集合為 B 那麼由 A 映到 B 的映成個數為 B B... B C C C...... C C C 將五件不同的玩具分給三位小朋友, 每人至少一件的分法數即是 5 對 的映成函數 ( 蓋射 ) 個數, 也就是 : C C 4 96 5 5 5 50 隨堂練習 : 從 到 9876 的正整數中, 數字中有 0 的數 ( 即個位數字 0 十位數字 0 或百位數字 0) 共有多少個?,,...,, 函數 f : A A, 而且是個一對一函數, 若 a 的函數值 設集合 A a a a 不是 a, 若 a 的函數值不是 a,, 若 a 的函數值不是 a, 則稱 f 是個錯列函數, 這種錯列函數共有多少個? 設 w 表示 A A的錯列函數個數, 顯然 w 0, w, w, 但 w 4 就不顯然了, 運用排容原理是求解的方法之一, 先求 w, w 4 就成為特例了 在集合 A 中設 a a的函數所成的集合為 A, a a 的函數所成的集合為 A,, a a 的函數所成的集合為 A, 那麼
w! A A... A! C! C!... C! C0!!! C!... C C!... ( ) ( )!! ( )! ( )! w 9, w 44, w 65, w 854 計算一下 4 5 6 7 若取 7, A A的一對一函數中, 任取一函數其為錯列的機率為 w 7 854 0.68, 當 7! 5040 很大時 w!, 若取.78, 0.68 十 遞迴關係式有些計數問題可使用數列的遞迴關係式處理, 具有簡潔俐落的特性 例 : 將 元和 元的兩種郵票貼成一排, 若郵資是 元, 問共有多少種貼法? 解 : ( 一 ) 窮舉法 : 設 元郵票 元郵票分別貼 xy, 張, 共貼 元, 則有 xy, 其中 xy, 為非負整數 其解為 : x 9 6 y 0 4 共有 5 種情況, 如 x6, y ( 及 元郵票 6 張, 元郵票 張 ), 8! 8 8,,,,,,,, 排列法共有 C6 C 8種, 所以共有 6!! 0 8 6 4 C0 C C C C4 0 8 0 60 ( 種貼法 ) ( 二 ) 遞迴關係式法 : 設使用 元和 元郵票貼成一排, 共貼成 源的方法有 a 種, 顯然 a, a, a, 又貼成 元 ( 4, N ) 的方法可分成互斥兩類
() 第一張貼 元, 剩下 (-) 元, 其貼法有 a 種 () 第一張貼 元, 剩下 (-) 元, 其貼法有 a 種 由加法原理, 可得遞迴關係式 : a ( 4) a a, 由 a, a, a 迭 代可得 a a a, a a a 4, a a a 6, a a a 9 4 5 4 6 5 7 6 4 a a a, a a a 9, a a a 8, a a a 4 8 7 5 9 8 6 0 9 7 0 8 a a a 60 9 所以郵資 元的貼法共有 60 種 當 很大時, 迭代十分複雜, 但借助電腦耐煩 耐操的特性, 可以很快速求 得 a 的值 隨堂練習 : 阿毅登樓 每步可走 階, 也可走 階 若樓梯共有 階, 那麼他 有多少種上樓的方法 再回到錯列函數的問題, A a a a,,...,, w 表示 A A的錯列函數的個 數, 已知 w 0, w, w, 接著尋求 < w > 的遞迴關係 首先, a 的函數值不是 a 時共有 ( ) 種方法, 而 a, a,..., a 錯列的情況 可分成互斥的兩類 : () a 的函數值是 ai ( i ), 但是 ai ( i ) 的函數值不是 a, 剩下來的 a, a,..., a 錯列的方法數為 w () a 的函數值是 ai ( i ), 但是 ai ( i ) 的函數值是 a, 剩下的 w a, a,..., ai, ai,..., a 錯列的方法數為 由加法 乘法原理得 w ( )( w w ), 又已知 w 0, w, w, 可得知
w 9, w 44, w 65, w 854, 的確快速 俐落! 4 5 6 7 最後, 看一個運用遞迴關係式處理機率問題的例子 例 ( 全盤獲勝問題 ) 甲持有 m 元, 乙持有 元, 兩人擲一公正硬幣, 若出現正面, 乙給甲 元, 若出現反面, 甲給乙 元, 求甲將乙的 元全部贏過來的機率 解 : 設 P 為持有 K 元的一方全贏的機率, 則 P0 0, Pm 若持有 K 元的一方擲硬幣 () 獲正面得 元, 共有 (K+) 元, 以後全贏的機率為 P () 獲反面輸 元, 共有 (K-) 元, 以後全贏的機率為 P 所以, P P P 即 P P P P 所以,< P > 為一等差數列, 0,,... m P P ( m ) 公差, 且 P0 0 又 m 0 因此, 公差 m 所以, P 0 ( ) 公差 m m 故甲全贏的機率為 Pm m 隨堂練習 : 在例 中, 將公正硬幣改為出現正面機率為 a(0 a, a ) 的不公 正硬幣, 求甲全贏的機率 習題 :. 將正三角形 ABC 的各邊六等分, 過各分點在 ABC 內作各邊的平行線如下圖 () 試問共有多少個三角形? () 試問共有多少個平行四邊形?
.NBA 總冠軍是由東 西區的冠軍隊採七戰四勝制比賽後的獲勝隊獲得的 若現在已賽畢三場, 湖人隊以 : 領先, 試問往後有多少種結果來決定總冠軍?. 某鐵路沿線設有 0 個站, 試問鐵路局需準備幾種車票? 這票上的票款有多少種? 4. 試使用例 5, 求本章引起動機中印度 6 種味道 ( 酸 甜 苦 辣 鹹 澀 ) 共可調配出多少種不同的味道? 5. 試使用數學歸納法證明排容原理 6.( 尤拉中函數 ) 設函數中 ( m ) 表示不大於正整數 m 且與 m 互質的正整數個數, 如 ( i), (), (), (4), (5) 4 () 設 p 為正質數, 為正整數, 求 ( P ) () 設 m ( P P... P ) 其中 P, P... P 為正質數,,,... 為正整數, 試證 : ( m) m( )( )...( ) p p p 7. 從 到 000 的正整數中 () 不含有 7 的數字共有多少個? () 不能被 5,6,8 任一數整除的數有多少個? 8. 有紅 黃 藍 白四種色球各 0 個, 現在從中取 5 個排成一列, 試問同色球不相鄰的排法有多少種? 9. 在下圖中, 由 A 到 B 一筆畫的走法有多少種?
0. 考慮正整數 m 寫成 個正整數和的寫法, 其中 m= 如 5=++=++=++=++=++=++, 將 5 寫成 個正整數和只有 6 種寫法, 在和式中, 項的位置次序不同, 就視為不同的寫法 試問共有多少種不同的寫法? 參考答案 : ( 一 ) 隨堂練習 :. 種.6 個.5 種 5.9 場 6.5 個 7.()a b c () a b c p q r p q r () ( ) a b c 8.() 5 5 種 () P 5 60種 () 5 4 6種 9.( 一 )()! 5! 70 種 ()! 5! 60 種 ( 二 ) 如圖 0.590 個. 種 a a a P P P P, P a a a. m m m ( 二 ) 習題.()78 個 ()0 個, 將平行四邊形的邊分成部平行 AB BC 與 CA 三類.0 種.()90 種 ()45 種票款 4. 6 6種 6.() P ( P )
() 考慮排容原理 7.()79 個 8. ()600 個 4 4 4 種 9. 0.!! 864 種 C m ( m )! ( )!( m )! 參考資料 : ( 一 ) 高中數學實驗教材第五冊 ( 二 ) 高中數學第四冊南一書局 ( 三 ) 高中數學第四冊教師手冊龍騰文化 ( 四 ) 路線的探針 - 賴敦生 ( 五 ) 高中數學競賽教程九章出版社