排列組合常用幾種基本方法ppt課件
《排列組合常用幾種基本方法ppt課件》由會員分享,可在線閱讀,更多相關(guān)《排列組合常用幾種基本方法ppt課件(14頁珍藏版)》請在裝配圖網(wǎng)上搜索。
第十章排列、組合和二項定理,解排列組合問題的幾種基本方法,,1,④要明確堆的順序時,必須先分堆后再把堆數(shù)當(dāng)作元素個數(shù)作全排列.,②若干個不同的元素局部“等分”有 m個均等堆,要將選取出每一個堆的組合數(shù)的乘積除以m!,①若干個不同的元素“等分”為 m個堆,要將選取出每一個堆的組合數(shù)的乘積除以m!,③非均分堆問題,只要按比例取出分完再用乘法原理作積.,分組(堆)問題的六個模型:①無序不等分;②無序等分;③無序局部等分;(④有序不等分;⑤有序等分;⑥有序局部等分.),處理問題的原則:,1. 分組(堆)問題,,2,例1.有四項不同的工程,要發(fā)包給三個工程隊,要求每個工程隊至少要得到一項工程. 共有多少種不同的發(fā)包方式?,解:要完成發(fā)包這件事,可以分為兩個步驟:,⑴先將四項工程分為三“堆”,有,種分法;,⑵再將分好的三“堆”依次給三個工程隊, 有3!=6種給法.,∴共有6×6=36種不同的發(fā)包方式.,1. 分組(堆)問題,,3,例2 . 7人排成一排.甲、乙兩人不相鄰,有多少種不同的排法?,♀ ♀ ♀ ♀ ♀,解:分兩步進行:,♀ ♀,幾個元素不能相鄰時,先排一般元素,再讓特殊元素插孔.,第1步,把除甲乙外的一般人排列:,第2步,將甲乙分別插入到不同的間隙或兩端中(插孔):,↑ ↑ ↑ ↑ ↑ ↑,解決一些不相鄰問題時,可以先排“一般”元素然后插入“特殊”元素,使問題得以解決.,2.插空法:,,,,4,相鄰元素的排列,可以采用“局部到整體”的排法,即將相鄰的元素局部排列當(dāng)成“一個”元素,然后再進行整體排列.,3.捆綁法,,例3 . 6人排成一排.甲、乙兩人必須相鄰,有多少種不的排法?,♀ ♀ ♀ ♀ ♀ ♀,解:(1)分兩步進行:,甲 乙,第一步,把甲乙排列(捆綁):,第二步,甲乙兩個人的梱看作一個元素與其它的排隊:,♀ ♀,幾個元素必須相鄰時,先捆綁成一個元素,再與其它的進行排列.,,5,例4. 5個人站成一排,甲總站在乙的右側(cè)的有多少種站法?,幾個元素順序一定的排列問題,一般是先排列,再消去這幾個元素的順序.或者,先讓其它元素選取位置排列,留下來的空位置自然就是順序一定的了.,4.消序法(留空法),解法1:將5個人依次站成一排,有,解法2:先讓甲乙之外的三人從5個位置選出3個站好,有,種站法,,然后再消去甲乙之間的順序數(shù),∴甲總站在乙的右側(cè)的有站法總數(shù)為,種站法,留下的兩個位置自然給甲乙有1種站法,∴甲總站在乙的右側(cè)的有站法總數(shù)為,,6,變式:如下圖所示,有5橫8豎構(gòu)成的方格圖,從A到B只能上行或右行共有多少條不同的路線?,解: 如圖所示,將一條路經(jīng)抽象為如下的一個排法(5-1)+(8-1)=11格:,其中必有四個↑和七個→組成!,所以, 四個↑和七個→一個排序就對應(yīng)一條路經(jīng),,所以從A到B共有,,條不同的路徑.,4.消序法(留空法),也可以看作是1,2,3,4,5,6,7,①,②,③,④順序一定的排列,有 種排法.,,7,n個 相同小球放入m(m≤n)個盒子里,要求每個盒子里至少有一個小球的放法等價于n個相同小球串成一串從間隙里選m-1個結(jié)點剪截成m段.,例5. 某校準(zhǔn)備參加今年高中數(shù)學(xué)聯(lián)賽,把16個選手名額分配到高三年級的1-4 個教學(xué)班,每班至少一個名額,則不同的分配方案共有___種.,5.剪截法(隔板法):,解: 問題等價于把16個相同小球放入4個盒子里,每個盒子至少有一個小球的放法種數(shù)問題.,將16個小球串成一串,截為4段有,種截斷法,對應(yīng)放到4個盒子里.,因此,不同的分配方案共有455種 .,,8,n個 相同小球放入m(m≤n)個盒子里,要求每個盒子里至少有一個小球的放法等價于n個相同小球串成一串從間隙里選m-1個結(jié)點剪截成m段.,變式: 某校準(zhǔn)備參加今年高中數(shù)學(xué)聯(lián)賽,把16個選手名額分配到高三年級的1-4 個教學(xué)班,每班的名額不少于該班的序號數(shù),則不同的分配方案共有___種.,5.剪截法:,解: 問題等價于先給2班1個,3班2個,4班3個,再把余下的10個相同小球放入4個盒子里,每個盒子至少有一個小球的放法種數(shù)問題.,將10個小球串成一串,截為4段有,種截斷法,對應(yīng)放到4個盒子里.,因此,不同的分配方案共有84種 .,,9,編號為1至n的n個小球放入編號為1到 n的n個盒子里,每個盒子放一個小球.要求小球與盒子的編號都不同,這種排列稱為錯位排列.,6.錯位法:,特別當(dāng)n=2,3,4,5時的錯位數(shù)各為1,2,9,44.,例6. 編號為1至6的6個小球放入編號為1至6的6個盒子里,每個盒子放一個小球,其中恰有2個小球與盒子的編號相同的放法有____種.,解: 選取編號相同的兩組球和盒子的方法有,,種,其余4組球與盒子需錯位排列有9種放法.,故所求方法有15×9=135種.,,10,7.剔除法,從總體中排除不符合條件的方法數(shù),這是一種間接解題的方法.,例7. 從集合{0,1,2,3,5,7,11}中任取3個元素分別作為直線方程Ax+By+C=0中的A、B、C,所得的經(jīng)過坐標(biāo)原點的直線有_________條.,解:所有這樣的直線共有 條,,其中不過原點的直線有 條,,∴所得的經(jīng)過坐標(biāo)原點的直線有210-180=30條.,排列組合應(yīng)用題往往和代數(shù)、三角、立體幾何、平面解析幾何的某些知識聯(lián)系,從而增加了問題的綜合性,解答這類應(yīng)用題時,要注意使用相關(guān)知識對答案進行取舍.,,11,B,B,鞏固練習(xí),,12,A,4. 5個人排成一排,其中甲、乙不相鄰的排法種數(shù)是( ) A.6 B.12 C.72 D.144,C,鞏固練習(xí),,13,①分堆問題; ②解決排列、組合問題的一些常用方法:錯位法、剪截法(隔板法)、捆綁法、剔除法、插孔法、消序法(留空法).,小結(jié),,14,- 1.請仔細閱讀文檔,確保文檔完整性,對于不預(yù)覽、不比對內(nèi)容而直接下載帶來的問題本站不予受理。
- 2.下載的文檔,不會出現(xiàn)我們的網(wǎng)址水印。
- 3、該文檔所得收入(下載+內(nèi)容+預(yù)覽)歸上傳者、原創(chuàng)作者;如果您是本文檔原作者,請點此認領(lǐng)!既往收益都歸您。
下載文檔到電腦,查找使用更方便
20 積分
下載 |
- 配套講稿:
如PPT文件的首頁顯示word圖標(biāo),表示該PPT已包含配套word講稿。雙擊word圖標(biāo)可打開word文檔。
- 特殊限制:
部分文檔作品中含有的國旗、國徽等圖片,僅作為作品整體效果示例展示,禁止商用。設(shè)計者僅對作品中獨創(chuàng)性部分享有著作權(quán)。
- 關(guān) 鍵 詞:
- 排列組合 常用 基本 方法 ppt 課件
鏈接地址:http://m.zhongcaozhi.com.cn/p-1563452.html