排列與組合.ppt

1、第一章 排列與組合,1-1乘法原理 1-2排列 1-3組合 1-4二項式定理,總目錄,1-1乘法原理,加法原理 乘法原理,目錄,加法原理,節目錄,下一頁,上一頁,如果完成一件事僅有n類辦法，每一類辦法與其他類皆無關連性，且每一類辦法皆可獨立完成此一件事，而第一類有m1種不同的辦法，第二類有m2種不同的辦法，第n類有mn種不同的辦法，則完成這件事的方法有 N m1 m2 mn種,在甲市與乙市之間有8座橋樑，4個渡船航線，2條捷運線，試問從甲市到乙市有多少種方法？ 解：從甲市到乙市有3類方法： 第一類方法：經由橋樑，有8種方法 第二類方法：經由渡船，有4種方法 第三類方法：經由捷運，有2種方法 本

2、題的目的只是要從甲市到乙市，所以以上3類方法互相不影響，故從甲市到乙市的方法有 84214種方法。,節目錄,下一頁,上一頁,例題：,乘法原理,如果做一件事必須要n個步驟進行，每一步驟與其它步驟皆有關連性，而第一個步驟有m1種不同的方法，第二個步驟有m2種不同的方法，第n個步驟有mn種不同的方法，則完成這件事的方法有 N m1 m2 mn種,節目錄,下一頁,上一頁,某天中午，學校的營養午餐供應3種主菜，3種副食。小倩到餐廳吃飯，主菜、副食必須各選一種，問她有多少種不同的選法？ 解：我們把一種主菜與一種副食的搭配看成一種選法，要完成這件事可分兩步驟進行： 第一步驟選主菜，有3種方法 第二步驟選副食

3、，有3種方法 根據乘法原理，小倩有339種不同的選法,節目錄,下一頁,上一頁,例題：,1-2排列,n的階乘(n!) 完全相異物的直線排列 不盡相異物的直線排列 重複排列 環狀排列,目錄,n的階乘(n!),n(n1) (n2) 21 n! n(n1) (n2) 21 規定0! 1,節目錄,下一頁,上一頁,完全相異物的直線排列,由n個不同的事物中取出r個排成一列，其方法數為 其中,節目錄,下一頁,上一頁,甲、乙、丙等共10人排成一列，則 (1)共有多少種排法？ (2)若甲、乙、丙必須排前面三位，有多少種排法？ 解：(1) 10人全取作直線排列有10!排法。 (2)甲、乙、丙先排前三位，有3!排法，

4、 其餘7人排後七位，有7!排法， 甲、乙、丙必須排前面三位有3! 7!排法,節目錄,下一頁,上一頁,例題：,不盡相異物的直線排列,若n個事物中，共可分成r類，每一類中相同的事物個數，分別以m1、m2、 mr表示，即n m1 m2 mr排成一列，則其不同的排法有,節目錄,下一頁,上一頁,3枝相同的原子筆，4枝相同的鉛筆，分給兒童，每人最多1枝，分給7人有幾種分法？ 解： 7位兒童成一列坐定後，將7枝鉛筆分給7位兒童，因此可視為將7枝筆排在每一位兒童面前，共有 35種分法,節目錄,下一頁,上一頁,例題：,重複排列,從n個相異事物中，每次選取一個，可放回重複選取排列，則選取 r 次其排列總數為nr,

5、節目錄,下一頁,上一頁,某人將五種酒，倒入4個不同的酒杯，每杯只倒一種酒，試問共有幾種倒法？ 解： 第1個酒杯，可自5種酒中選一種倒入，共5種方法 同理，其它的酒杯亦各有5種倒法 此為5中取4的重複排列 故共有555554種倒法。,節目錄,下一頁,上一頁,例題：,環狀排列,1. n個相異物全取排列之環狀排列數為： 自n個相異物中，每次取r個（ ）作環狀排列，其排列數為：,節目錄,下一頁,上一頁,甲、乙、丙、丁四人坐一圓桌，問有幾種坐法？ 解：,節目錄,下一頁,上一頁,例題：,1-3組合,相異物的組合 重複組合,目錄,相異物的組合,自n個不同的事物中，每次不重複地取r個為一組，則其組合數為：,節

6、目錄,下一頁,上一頁,一平面上共有12個點，其中有6點共線，其餘其餘無三點共線，求可連成 (1)多少條直線？ (2)多少個三角形？ 解： (1) (2),節目錄,下一頁,上一頁,例題：,重複組合,從n 類相異物中，任取 r 個為一組，其中每一類的事物個數均不小於 r，且每一類的事物可以重複選取2次，3次，或 r 次，則稱此種組合為 n 中取 r 的重複組合，則重複組合總數為,節目錄,下一頁,上一頁,設有相同的鉛筆6枝，原子筆6枝，彩色筆8枝，從中任意取出5枝，共有幾種取法？ 解： 每一種筆的數目都大於5，所以此為重複組合 因此假設鉛筆取出x 枝，原子筆取出y 枝，彩色筆取出z 枝，則原題即為求方程式xyz5的非負整數解的問題，故有,節目錄,下一頁,上一頁,例題：,1-4二項式定理,二項式定理 二項式定理的應用 巴斯卡三角形,目錄,二項式定理