Min-Hwei College of Health Care Management 排列與組合 Mathematics 3, Autumn 2010, C. J. Chang
加法原理 加法原理若完成某件事有 k 種做法可供選擇 其中 1, 2,, k 種做法分別有 m 1, m 2,, m k 個方法, 則完成此件事共有 m 1 +m 2 + +m k 種方法 Ex. 假設今天我們至簡餐店用餐, 該餐廳餐點分為排餐 義大利麵與火鍋三種, 其中排餐有三種選擇, 義大利麵有五種選擇, 火鍋有三餐點選擇種選擇, 則我們在該店用餐共用幾種選擇? 3 5 4 12 加法原理用於找出單一次決策時, 可供選擇的項目 排餐義大利麵火鍋 2
Ex. 加法原理 小明想去看電影, 有國片與洋片, 其中國片有 5 片, 洋片有 3 片, 試問他有多少種選擇看電影方法? 5 3 8 國片 洋片 小華想到餐廳吃飯, 其中西式的有 5 家, 港式的有 3 家, 中餐有 2 家, 則小華吃飯有餐廳選擇多少家餐廳可供選擇? 5 3 2 10 西式港式中餐 3
乘法原理 乘法原理假設完成某件事必須經過 k 個步驟, 而步驟一至步驟 k 分別由有 m 1, m 2,, m k 種方法, 則完成這件事共有 m 1 m 2 m k 種方法 乘法原理用於流程式的決策, 且不同步驟間的選項必須相互獨立 假設我們今天至飲料店購買茶飲料, 我們必須決定茶的種類 加冰的情況與甜度 ; 若共有四種茶 三種加冰情況與五種甜度可供選擇, 則我們可以選擇的飲料搭配有幾種? 4 3 5 60 茶的種類冰的狀況甜度 4
Ex. 乘法原理 從甲地到乙地有 2 條路可走, 乙到丙地有 3 條路可走, 試問某人從甲地到丙地, 共有多少種不同的走法? 6 從甲地到乙地, 乙地到丙地, 丙地到丁地分別有 3 4 5 條路可走, 試問甲地到丁地, 共有多少種不同的走法? 60 5
Ex. 乘法原理 某人上衣有 3 件, 領帶 4 條, 褲子 5 件, 鞋子 6 雙, 外出時要穿著整齊, 問有多少種配穿法? 3 4 5 6 360 護理科甲 乙 丙班分別有 50 49 48 位同學, 若美班任選一位同學出來擔任交通隊服務人員, 問共有多少種選法? 50 49 48 117600 6
Ex. 乘法原理 現有 1000 元紙鈔 1 張,500 元紙鈔 4 張,100 元紙鈔 4 張, 可配出多少種不同款項的付款方式? 1張 1000元可換成 2張 500元紙鈔, 因此 1000元紙鈔 1 張, 500元 紙鈔 3張, 相當於 500元紙鈔 5張 因此 500元紙鈔有付一張 二張 三張 四張 五張與不付, 6種方法 同理 100元紙鈔有 5種付法 所以付款方法有 6 5 1 29 種 ( 均不支付的方式要扣除 ) 因為 500 元鈔票有兩張以上, 因此我們必須把 1000 元鈔票視為 500 元鈔票 ; 同理若 100 元有五張以上, 我們也必須把 500 元鈔票視為 100 鈔票 7
排列 (1) 將一些人或事物有前後順序地排成一列, 稱為排列 通常排列指的都是 直線排列 Ex. 現在將甲 乙 丙三人排成一列, 有多少種排法? 甲乙丙甲丙乙乙甲丙 乙丙甲丙甲乙丙乙甲 很明顯的共有 6 種方法 因為上述的問題並沒有太多變化, 所以我們可以將所有排法全部列出, 但如果要同時將 10 個人排列呢? 要將全部的情況列出很難, 因此我們需要一個規則去計算 8
排列 (2) 我們把三人的排列問題視為有三個固定位置, 我們要決定每個位置的人 在位置一的時候, 我們有三個人可以選 ; 在位置二的時候, 則有兩個人可以選 ( 因為位置一已選定了一個人 ); 而位置三則僅剩一個人可選 因此由乘法定理可知, 排成一列的方法有 3 2 1=6 種 6 甲 乙 丙 乙丙甲丙甲乙 丙乙丙甲乙甲 9
Ex. 排列 甲 乙 丙 等 10 人排成一列, 方法有幾種? 10! 3628800 n (n 1) (n 2) 3 2 1 這個式子就是所謂的階乘, 我們一般用 n! 表示, 其中 n 必須為非負的整數 0! 1, 1! 1, 2! 1 2 2, 3! 3 2 1,, n! 1 2 ( n 1) n 10
Ex. 排列 有 5 位實力相當的選手參加接力賽, 試問他們比賽時棒次的安排方式有幾種方法? 5! 120 11
Ex. 排列 12 甲 乙 丙 丁 戊 5 人中任選 3 位排成一列, 試問有多少種方法? 60
Ex. 排列 13 1, 2, 3, 4, 5, 6, 7, 8, 9 九個數字中, 任取三個數字排成一個 3 位數, 試問可以組成多少個 3 位數? 504
排列的公式 n 個相異物品, 排成一列的方法有 n ( n 1) ( n 2) 3 2 1 n!( n階乘 ) n 個相異物品, 取 r 個排成一列的方法有 n ( n 1) ( n 2) ( n r 1) n ( n 1) ( n 2) ( n r 1) ( n r) 3 2 1 n! ( n r) 3 2 1 ( n r)! 我們一般將上式簡寫成 n P r n P n( n 1) ( n r 1) r n! ( n r)! 14
Ex. 排列 0, 2, 4, 6, 8 五個數字中, 任取三個數字排成一個三位數, 試問方法有幾種? 48 因為百位數若放 0, 將無法構成十位數, 因此僅有 4 種選法 另用一種想法為我們先將 5個數字取 3個任意排列, 再減去 0排在百位數的情況 P 5 4 3 P2 5 4 3 4 3 60 12 48 15
Ex. 排列 甲 乙 丙 丁 戊 5 人排成一列, 則 1. 2. 1. 甲必在首位有幾種排法 2. 甲 乙 丙三人必相鄰有幾種方法 24 6 所以方法為 6 6 36種 6 16
Ex. 排列 甲 乙 丙 丁 戊 5 人排成一列, 則 17 3. 甲 乙 丙三人必須分離方法有幾種 3. 2 所以方法為 2 6 12種 6
相同物的排列 在一個 n 件物件的排列當中, 若出現有相同物的情況, 稱為有相同物的排列 Ex. 二個紅球, 一個綠球, 一個白球排成一列的方法有幾種 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 若我們將兩個紅球看作不一樣的球, 則有 4!=24 種排法 但實際上紅球是一樣的東西, 因此我們必須將重覆計算的部份 ( 紅球的排列方式 ) 除回來 18
Ex. 相同物的排列 將 banana 一字的各字母任意排成一列, 可有幾種排法? 我們先計算視為六個相異字母的排法, 再將重覆 (a與 n) 的部份除回來 6! 6 5 4 3 2 1 60 3!2! 3 2 1 2 1 古詞 庭院深深深幾許 將其中文字任意排成一列, 可有幾種不同排法? 我們先計算視為七個相異字的排法, 再將重覆 ( 深 ) 的部份除回來 7! 7 6 5 4 3 2 1 840 3! 3 2 1 19
相同物的排列 在一個有 n 件事件的排列中, 若出現有相同物件的排列 情形, 則其排列數為 m, 其中 m 1, m 2,, m 1! m2! mk! k 分別為第 1 種, 第 2 種,, 第 k 種相同物件的個數 n! 20
Ex. 相同物排列 棋盤街道如圖, 某人由甲走截徑 ( 只能向右或向上 ) 到乙, 試問有幾種走法? 由甲走到乙, 我們必須經過 5條橫的與 4條直的路徑, 是一個相同物排列 的問題 (9個物件的排列, 其中橫的有 5個相同物件, 直的有 4 個相同物件 ) 9! 因此總共的走法為 5!4! 21
Ex. 相同物排列 棋盤街道如圖, 某人由甲走截徑 ( 只能向右或向上 ) 到乙, 但陰影部份不能經過, 試問有幾種走法 因不能經過陰影, 我們可能的方式有三種類型, 其各別的走法為 5! 4! 甲 1 乙有 1 5! 4! 5! 4! 甲 2 乙有 20 4!1! 3!1! 5! 4! 甲 3 乙有 5 4!1! 4! 因此總共的走法為 1 20 5 26 甲 乙 22
重複排列的公式 23 從 n 個不同的事物中, 選取 r 個排成一列, 每個可重複選取時, 稱為重複排列 ( 可重複選取的直線排列 ) 其排列方法有 n r 種 n r
Ex. 重複排列 從 1, 2, 3, 4, 5 五個數字中, 選取三個數字 ( 可重複 ) 排成一個三位數, 可有多少個不同的三位數? 3 5 125 24
Ex. 重複排列 25 數學期中考試有 10 題選擇題, 每題皆是 4 選 1 的單選題, 某生用猜的作答, 試問他有多少種不同的猜測答案 10 4 1048576
Ex. 重複排列 26 某人上班途中會經過 8 個僅設有紅燈與綠燈的十字路口, 試問他可能遇到多少種不同的紅綠燈情形? 2 8 256
組合 從 n 個相異取 r 個排成一列 ( 有順序關係 ) 的方法有 P rn 那麼, 從 n 個相異取 r 個當成一組 ( 沒有順序關係 ), 其方法有多少種? 這種沒有順序關係的選取方式, 稱作組合問題 組合與排列的最大差異在於沒有順序關係, 我們以三個人排成一列的例子來看, 可能的排列方式會有 6 種, 但它們實際上都是同一種選取方式 甲乙丙甲丙乙乙甲丙 乙丙甲丙甲乙丙乙甲 甲乙丙 因此組合的計算, 可先計算排列的數量, 再將因順序關係 ( 排列 ) 所產生的部份除回來 27
組合的公式 從 n 個相異物, 取 r 個為一組的方法, 我們以 C r n 表示 C n r n Pr n! r! r!( n r)! C C n n n r n 0 1 n! n! r!( n r)! ( n r)! r! n n P C r! r C r C n n r 28
Ex. 排列與組合 P C C P C 7 3 7 3 7 7 4 3 12 3 7 6 5 210 7 6 5 35 1 2 3 7 6 5 C 35 1 2 3 12 11 10 1320 12 11 10 9 C 1 2 3 4 12 12 8 4 495 29
Ex. 組合 某班有 24 位男生,16 位女生, 若選出 2 男 3 女組成啦啦隊, 問有幾種不同的選法? C 24 23 16 15 14 C 154560 1 2 1 2 3 24 16 2 3 男生的選法 女生的選法 30
Ex. 組合 某次考試共有 10 個題目, 規定前 4 題中任選 2 題, 後 6 題中任選 3 題作答, 則有幾種選題方法? C 4 3 6 5 4 C 120 1 2 1 2 3 4 6 2 3 前題 後題 前 4 題 後 6 題 31
Ex. 組合 樂透彩券, 由 1 到 42 個號碼中, 不可重覆地開出 6 個號碼為一組,6 個號碼全部簽中即得頭獎 請問 1 到 42 個號碼, 可開出幾組號碼? C 42 6 42 41 40 39 38 37 1 2 3 4 5 6 5245786 32
Ex. 組合 12 本不同的書依照下列分法, 各有幾種分法 1. 平分給甲, 乙, 丙三人 2. 平分成三堆 12 C 4 8 C 4 4 C 4 12 11 10 9 8 7 6 5 4 3 2 1 34650 1 2 3 4 1 2 3 4 1 2 3 4 12 8 4 C4 C4 C4 34650 3! 3! 5775 33
Ex. 組合 12 本不同的書依照下列分法, 各有幾種分法 3. 6 本給甲,3 本給乙,3 本給丙 4. 按 6,3,3 分成三堆 5. 按 6,3,3 任意給 3 人 12 C 6 6 C 3 3 C 3 12 11 10 9 8 7 6 5 4 3 2 1 18480 1 2 3 4 5 6 1 2 3 1 2 3 12 6 3 C6 C3 C3 18480 2! 2! 9240 12 6 6 C6 C3 C3 3! 9240 6 55440 2! 34
重複組合 (1) 設有 n 類不同物品 ( 每類至少有 m 個 ), 若從其中每次選取 m 個為一組 ( 選取的物品可以重複 ), 此種組合方式稱為從 n 類中取 m 個的 重複組合, 記為 H n m 假設將 3 個相同的球, 任意分給甲, 乙兩個人 ( 每人可兼得 ), 它的分法有幾種呢 我們可以將這個問題想像成多插入一個間隔, 並用它來區分給甲或乙, 也就是這個問題變成四個物件的排列, 其求解方式也就是 4! 3!1! 35
重複組合 (2) 我們再進一步思考, 剛才間隔物是為了區分兩個人而產生 那如果我們要區隔三個人呢? 同樣可以利用間隔物, 但此時我們需要兩個間隔物 間隔物的數量為待區隔類別減 1 由上述討論可知,m 個相同物品分給 n 個人 ( 亦可說成 n 類不同物品選出 m 個 ), 其計算的通式為 類別 H n m ( m ( n 1))! ( m n 1)! C m!( n 1)! m!( n 1)! m n 1 m 數量 36
Ex. 重複組合 袋中有編號 1~6 的號碼球各 20 個, 小明從袋中取 4 球, 問所取出球的號碼有多少種可能組合 1到 6個號碼就是 6個類別 由 6類物品取出 4個是重複組合的問題 6 6 4 1 9 9 8 7 6 H4 C4 C4 126 1 2 3 4 37
Ex. 重複組合 6 本相同的書, 全部分給甲 乙 丙三人, 則 : 每人可兼得 ( 全部拿 ) 方法有幾種? 每人至少一本, 方法有幾種? 6本相同的書分給 3個人是重複組合的問題 3 3 6 1 8 8 8 7 (1) H6 C6 C6 C2 28 1 2 (2) 先發給每人 1本書, 再將剩下的書任意分給 3個人 3 3 3 1 5 5 5 4 H3 C3 C3 C2 10 1 2 38
排列與組合的類型 39 不能重複可以重複 排列 ( 順序有意義 ) 組合 ( 順序無意義 ) P C n n r r r n n m n H C m m 1
二項式乘法運算的展開式 ( ) 1 x y x y ( x y) x 2xy y 2 2 2 ( x y) x 3x y 3xy y 3 3 2 2 3 ( x y) x 4x y 6x y 4xy y 4 4 3 2 2 3 4 ( x y) x 5xy 10xy 10xy 5xy y ( x y) n 5 5 4 3 2 2 3 4 5 上面已列出二項展開後部份項的係數, 各項係數的確認是很重要的問題, 如何才能透過有系統的方式找出係數? 40
二項式定理 5 ( x y) ( x y)( x y)( x y)( x y)( x y) x 5個 x相乘 C C 1(5 個乘項都選 x) x y 4 x 1 y C C 5(4 個乘項選 x) x y 3 x 2 y C C 10(3 個乘項選 x) x y 2 x 3 y C C 10(2 個乘項選 x) xy 1 x 4 y C C 5(1 個乘項選 x) y 5 y C C 1( 沒有乘項選 x) 5 5 5 5 0 4 5 5 個與個相乘 4 1 3 2 5 5 個與個相乘 3 2 2 3 5 5 個與個相乘 2 3 4 5 5 個與個相乘 1 4 5 5 5 個相乘 0 5 只要 x 的位置決定了,y 的位置就決定, 反之亦然 二項式定理 ( x y) n C n x n C n x n y C n x n y C n y n 1 2 2 0 1 2 n 41
Ex. 二項式定理 利用二項式定理展開 (x y) 5 ( x y) ( x ( y)) 5 5 Cx Cx( y) Cx( y) Cx( y) Cx( y) C( y) 5 5 5 4 5 3 2 5 2 3 5 4 5 5 0 1 2 3 4 5 5 5 4 5 4 5 1 x x ( y) x ( y) x ( y) x( y) 1 ( y) 1 1 2 1 2 1 5 4 3 2 2 3 4 5 x 5 x ( y) 10 x ( y) 10 x ( y) 5 x( y) ( y) 5 4 3 2 2 3 4 5 5 10 10 5 4 3 2 2 3 4 5 x x y x y x y 5xy y 42
Ex. 二項式定理 利用二項式展開式, 求 (1.01) 10 的小數點後第三位數字? (1.01) (1 0.01) 10 10 10 10 10 9 10 8 2 10 7 3 C0 1 C1 1 (0.01) C2 1 (0.01) C3 1 (0.01) 1 1 10 1 0.01 45 1 0.0001 120 1 0.000001 1 0.1 0.0045 0.000120 1.104620 因此小數點後第三位數字為 4 43
Ex. 二項式定理 試求 C C C C C 10 10 10 10 10 0 1 2 3 10 之值 ( x y) C x C x y C x y C x y C y 10 10 10 10 9 10 8 2 10 7 3 10 10 0 1 2 3 10 令 x 1, y 1代入 (1 1) C C C C C 10 10 10 10 10 10 0 1 2 3 10 C C C C C 2 1024 10 10 10 10 10 10 0 1 2 3 10 44
Min-Hwei College of Health Care Management The end of this chapter. Thank You!