排列組合問題PPT課件

1、第1頁/共59頁排列組合應(yīng)用題的主要類型和常用方法排列組合應(yīng)用題的主要類型和常用方法排列組合應(yīng)用題大致可分為三大類：不帶限制條排列組合應(yīng)用題大致可分為三大類：不帶限制條件的排列或組合題，帶有約束條件的排列或組合件的排列或組合題，帶有約束條件的排列或組合題；排列與組合的綜合題解此類問題常用的方題；排列與組合的綜合題解此類問題常用的方法有：法有：(1)相鄰元素的排列，可以采用相鄰元素的排列，可以采用“整體到局整體到局部部”的排法，就是將相鄰的元素當(dāng)成的排法，就是將相鄰的元素當(dāng)成“一個一個”元元素進(jìn)行排列，然后再局部排列，分作兩步素進(jìn)行排列，然后再局部排列，分作兩步(2)元元素間隔排列應(yīng)用題，一般采

2、用素間隔排列應(yīng)用題，一般采用“插空法插空法”第2頁/共59頁(3)含有特殊元素和特殊位置的排列，組合應(yīng)用題，常采用“特殊元素法”，從元素為主出發(fā)，先安排特殊元素；從位置為主出發(fā)，先安排好特殊位置上的元素，結(jié)合排除法解決此類問題(4)指標(biāo)問題采用“隔板法”(5)有關(guān)“分堆”與“到位”應(yīng)用問題常采用“分組法”與“分配法”若只分堆，不指定到具體位置，則需注意平均分的情況(6)相鄰類排列應(yīng)用題常采用“捆綁法”解決，就是將幾個相鄰元素先抽出進(jìn)行排列再將它們視為一個元素參與下一步的排列，此法是法(1)的逆向思維應(yīng)用第3頁/共59頁排列與組合應(yīng)用題，主要考查有附加條件的應(yīng)用問題，解決此類問題通常有三種途徑：

3、以元素為主，應(yīng)先滿足特殊元素的要求，再考慮其他元素；以位置為主考慮，即先滿足特殊位置的要求，再考慮其他位置；先不考慮附加條件，計算出排列或組合數(shù)，再減去不符合要求的排列數(shù)或組合數(shù)前兩種方法叫直接解法，后一種方法叫間接解法，求解時應(yīng)注意先把具體問題轉(zhuǎn)化或歸結(jié)為排列或組合問題；再通過分析確定運用分類計數(shù)原理還是分步計數(shù)原理：然后分析題目條件，避免“選取”時重復(fù)和遺漏；最后列出式子計算作答第4頁/共59頁典型問題的典型解法典型問題的典型解法相鄰問題相鄰問題捆綁法捆綁法不相鄰問題不相鄰問題插空法插空法間隔問題間隔問題分析法分析法定序問題定序問題空位法空位法相同名額的分配的問題相同名額的分配的問題插板法

4、插板法不同元素的平均分組的問題不同元素的平均分組的問題 平均分成幾組就除以幾的階乘平均分成幾組就除以幾的階乘第5頁/共59頁 4個男同學(xué)，3個女同學(xué)站成一排 (1)3個女同學(xué)必須排在一起，有多少種不同的排法？ (2)任何兩個女同學(xué)彼此不相鄰，有多少種不同的排法？ (3)甲、乙兩人相鄰，但都不與丙相鄰，有多少種不同的排法？第6頁/共59頁【嘗試解答】(1)3個女同學(xué)是特殊元素，共有A種排法；由于3個女同學(xué)必須排在一起，視排好的女同學(xué)為一整體，再與4個男同學(xué)排隊，應(yīng)有A種排法第7頁/共59頁第8頁/共59頁1對于有限制條件的排列問題，分析問題時有位置分析法、元素分析法，在實際進(jìn)行排列時一般采用特殊

5、元素優(yōu)先原則，即先安排有限制條件的元素或有限制條件的位置，對于分類過多的問題可以采用間接法2對相鄰問題采用捆綁法、不相鄰問題采用插空法、定序問題采用倍縮法是解決有限制條件的排列問題的常用方法第9頁/共59頁 在本例中，條件不變，把第(1)、(2)小題改為下面兩問題：(1)甲不站排頭，乙不站排尾，有多少種不同的排法？(2)若甲乙兩同學(xué)之間必須有3人，有多少種不同的排法？第10頁/共59頁第11頁/共59頁 (2013汕頭質(zhì)檢)若一個三位數(shù)的十位數(shù)字比個位數(shù)字和百位數(shù)字都大，稱這個數(shù)為“傘數(shù)”現(xiàn)從1，2，3，4，5，6這六個數(shù)字中取3個數(shù)，組成無重復(fù)數(shù)字的三位數(shù)，其中“傘數(shù)”有() A120個 B

6、80個 C40個 D20個【答案】C第12頁/共59頁 男運動員6名，女運動員4名，其中男女隊長各1名，選派5人外出比賽，在下列情形中各有多少種選派方法？ (1)至少有1名女運動員； (2)既要有隊長，又要有女運動員 【思路點撥】第(1)問可以用直接法或間接法求解第(2)問根據(jù)有無女隊長分類求解第13頁/共59頁第14頁/共59頁第15頁/共59頁1本題中第(1)小題，含“至少”條件，正面求解情況較多時，可考慮用間接法第(2)小題恰當(dāng)分類是關(guān)鍵2組合問題常有以下兩類題型變化(1)“含有”或“不含有”某些元素的組合題型：“含”，則先將這些元素取出，再由另外元素補(bǔ)足；“不含”，則先將這些元素剔除，

7、再從剩下的元素中去選取(2)“至少”或“最多”含有幾個元素的題型：若直接法分類復(fù)雜時，逆向思維，間接求解第16頁/共59頁熱點分類突破本講欄目開關(guān)主干知識梳理熱點分類突破押 題 精 練第17頁/共59頁熱點分類突破本講欄目開關(guān)主干知識梳理熱點分類突破押 題 精 練第18頁/共59頁熱點分類突破本講欄目開關(guān)主干知識梳理熱點分類突破押 題 精 練第19頁/共59頁熱點分類突破本講欄目開關(guān)主干知識梳理熱點分類突破押 題 精 練第20頁/共59頁熱點分類突破本講欄目開關(guān)主干知識梳理熱點分類突破押 題 精 練第21頁/共59頁第22頁/共59頁思路導(dǎo)引思路導(dǎo)引(1)取出的取出的4張卡片所標(biāo)的數(shù)字之張卡片

8、所標(biāo)的數(shù)字之和等于和等于10，注意到：，注意到：12341144223310，據(jù)此進(jìn)行分類，又取出，據(jù)此進(jìn)行分類，又取出卡片還要排序，因此這是排列與組合的綜合問卡片還要排序，因此這是排列與組合的綜合問題題(2)一般地，解答排列與組合的綜合問題，是一般地，解答排列與組合的綜合問題，是先選元素先選元素(組合組合)再排元素再排元素(排列排列)，本題的求解，本題的求解有兩處難點，一是如何分類，分成幾類，這里有兩處難點，一是如何分類，分成幾類，這里“數(shù)字之和為數(shù)字之和為10”即為問題的突破點；二是選即為問題的突破點；二是選出滿足條件的卡片后還需排列，這是易錯點出滿足條件的卡片后還需排列，這是易錯點第23

9、頁/共59頁答案：432第24頁/共59頁解決排列、組合綜合問題要遵循的原則：(1)按事情發(fā)生的過程進(jìn)行分步：(2)按元素的性質(zhì)進(jìn)行分類特殊元素優(yōu)先法特殊位置優(yōu)先法先不考慮附加條件，計算出排列或組合數(shù)，再減去不合要求的排列或組合數(shù)第25頁/共59頁1有五張卡片，它們正、反面上分別寫0與1,2與3,4與5,6與7,8與9，將其中任意三張并排放在一起，組成三位數(shù)，共可組成多少個不同的三位數(shù)？第26頁/共59頁第27頁/共59頁第28頁/共59頁思路導(dǎo)引思路導(dǎo)引(1)是平均分組問題，與順序無關(guān)，是平均分組問題，與順序無關(guān)，相當(dāng)于相當(dāng)于6本不同的書平均分給甲、乙、丙三人，本不同的書平均分給甲、乙、丙三

10、人，可以理解為一個人一個人地來取，可以理解為一個人一個人地來取，(2)是是“均均勻分組問題勻分組問題”，(3)是不均勻分組問題，分三是不均勻分組問題，分三步進(jìn)行，步進(jìn)行，(4)分組后再分配，分組后再分配，(5)明確明確“至少一至少一本本”包括包括“2、2、2型型”、“1、2、3型型”、“1、1、4型型”，(6)實質(zhì)為全排列實質(zhì)為全排列第29頁/共59頁第30頁/共59頁第31頁/共59頁(1)解決此類問題要分清是分組問題還是分配問題(2)分組問題屬于“組合”問題，常見的分組問題有三種：完全均勻分組，每組的元素個數(shù)均相同；第32頁/共59頁2將4名大學(xué)生分配到3個鄉(xiāng)鎮(zhèn)去當(dāng)村官，每個鄉(xiāng)鎮(zhèn)至少一名，

11、則不同的分配方案有多少種？第33頁/共59頁思路導(dǎo)引以多面手入選的人數(shù)為分類標(biāo)準(zhǔn)分類求解第34頁/共59頁第35頁/共59頁第36頁/共59頁第37頁/共59頁第38頁/共59頁對于多個限制條件的組合問題，要以其中的某個條件為主去進(jìn)行分類，然后再考慮其余的限制條件，分類要不重不漏第39頁/共59頁3賽艇運動員10人，3人會劃右舷，2人會劃左舷，其余5人兩舷都能劃，現(xiàn)要從中選6人上艇，平均分配在兩舷上劃漿，有多少種不同的選法？第40頁/共59頁 2A、B、C、D、E五人并排站成一排，如果B必須站在A的右邊(A、B可以不相鄰)，那么不同的排法共有 ()A24種 B60種 C90種 D120種【答案

12、】B第41頁/共59頁 n個 相同小球放入m(mn)個盒子里,要求每個盒子里至少有一個小球的放法等價于n個相同小球串成一串從間隙里選m-1個結(jié)點剪截成m段.例4. 某校準(zhǔn)備參加今年高中數(shù)學(xué)聯(lián)賽,把16個選手名額分配到高三年級的1-4 個教學(xué)班,每班至少一個名額,則不同的分配方案共有_種.題型四、指標(biāo)問題采用“剪截法（檔板法）”：解： 問題等價于把16個相同小球放入4個盒子里,每個盒子至少有一個小球的放法種數(shù)問題. 將16個小球串成一串，截為4段有 315455C種截斷法，對應(yīng)放到4個盒子里.因此，不同的分配方案共有455種 .第42頁/共59頁 n個 相同小球放入m(mn)個盒子里,要求每個盒

13、子里至少有一個小球的放法等價于n個相同小球串成一串從間隙里選m-1個結(jié)點剪截成m段.變式： 某校準(zhǔn)備參加今年高中數(shù)學(xué)聯(lián)賽,把16個選手名額分配到高三年級的1-4 個教學(xué)班,每班的名額不少于該班的序號數(shù),則不同的分配方案共有_種.解： 問題等價于先給2班1個，3班2個，4班3個，再把余下的10個相同小球放入4個盒子里,每個盒子至少有一個小球的放法種數(shù)問題. 將10個小球串成一串，截為4段有 3984C 種截斷法，對應(yīng)放到4個盒子里.因此，不同的分配方案共有84種 .第43頁/共59頁【練習(xí)練習(xí)】 把把9 9個相同的小球放入編號為個相同的小球放入編號為1 1、2 2、3 3的三個箱子里，要求每個箱

14、子放入球的三個箱子里，要求每個箱子放入球的個數(shù)不小于其編號數(shù)，則不同的方的個數(shù)不小于其編號數(shù)，則不同的方法種數(shù)有法種數(shù)有 種。種?；瘹w成典型問題化歸成典型問題第44頁/共59頁編號為1至n的n個小球放入編號為1到 n的n個盒子里,每個盒子放一個小球.要求小球與盒子的編號都不同,這種排列稱為錯位排列.錯位法：特別當(dāng)n=2,3,4,5時的錯位數(shù)各為1,2,9,44.例5. 編號為1至6的6個小球放入編號為1至6的6個盒子里,每個盒子放一個小球,其中恰有2個小球與盒子的編號相同的放法有_種.解： 選取編號相同的兩組球和盒子的方法有 2615C 種,其余4組球與盒子需錯位排列有9種放法.故所求方法有1

15、59135種.第45頁/共59頁【思考題思考題】 7 7個人坐成一排，要調(diào)換其中三人的個人坐成一排，要調(diào)換其中三人的位置而其余四人不動，有位置而其余四人不動，有 種不同種不同的調(diào)換方法的調(diào)換方法 ？第46頁/共59頁【例例1 1】如圖，在某城市中，如圖，在某城市中，MM、N N兩地之間有整齊的道路網(wǎng)兩地之間有整齊的道路網(wǎng)（圖中正方形的每一條邊都表示一條（圖中正方形的每一條邊都表示一條街道）。則從街道）。則從MM到到N N的最短路徑有的最短路徑有 條。條。捷徑問題第47頁/共59頁【例例1 1】（0808，重慶卷，重慶卷) )某人有某人有4 4種顏色的燈泡（每種顏色的燈泡（每種顏色的燈泡足夠多）

16、，要在如圖所示的種顏色的燈泡足夠多），要在如圖所示的6 6個點個點A A、B B、C C、A A1 1、B B1 1、C C1 1上各裝一個上各裝一個燈燈泡，要求同一條線段兩端的燈泡不同色，泡，要求同一條線段兩端的燈泡不同色，則則每種顏色的燈泡都至少用一個的安裝方法每種顏色的燈泡都至少用一個的安裝方法共共有有 種。種。 染色問題染色問題第48頁/共59頁題型七、染色問題解：按照A1，B1，C1，A，B，C的順序安裝燈泡A1處有4種方法，B1處有3種方法，C1處有2種方法(1)當(dāng)A處與B1處不同與C1處相同時，A處有1種方法，由于裝完B，C后每種顏色的燈泡至少用一個，因此共有4321(12)72

17、種(2)當(dāng)A處與B1處相同與C1處不同時，A處有1種方法B處有3種方法，C處有1種方法，共有43213172種(3)當(dāng)A處與B1，C1均不相同時，A處有1種方法。B，C處共有213種方法，因此，共有4321(21)72種因此，由分類計數(shù)原理可得共有727272216(種)方法第49頁/共59頁熱點分類突破本講欄目開關(guān)主干知識梳理熱點分類突破押 題 精 練第50頁/共59頁熱點分類突破本講欄目開關(guān)主干知識梳理熱點分類突破押 題 精 練第51頁/共59頁易錯辨析實際意義理解不清導(dǎo)致計數(shù)錯誤 (2012山東高考改編)現(xiàn)有16張不同的卡片，其中紅色、黃色、藍(lán)色、綠色卡片各4張，從中任取3張，要求這3張卡片不能是同一種顏色，且紅色卡片至多1張，不同取法的種數(shù)為 () A232 B256 C472 D484第52頁/共59頁 【答案】B第53