排列組合(加乘、排列、組合、捆綁、插空、隔板)

1、計(jì)數(shù)專(zhuān)題學(xué)習(xí)目標(biāo)1.正確理解“標(biāo)數(shù)”法計(jì)算路徑數(shù)目；2.正確理解“加法原理”、“乘法原理”的意義和運(yùn)用場(chǎng)景；2.正確理解“排列”、“組合”的意義、區(qū)別和計(jì)算公式；3.正確掌握“優(yōu)選法”“捆綁法”、“插空法”、“隔板法”這些排列組合解題技巧，理解各種排列組合解題技巧的原理，所解決的問(wèn)題類(lèi)型及其解題方法；一.標(biāo)數(shù)法例題：在左下圖中，從A點(diǎn)沿實(shí)線(xiàn)走最短路徑到B點(diǎn)，共有多少條不同路線(xiàn)？                   分

2、析與解：題目要求從左下向右上走，所以走到任一點(diǎn)，例如右上圖中的D點(diǎn)，不是經(jīng)過(guò)左邊的E點(diǎn)，就是經(jīng)過(guò)下邊的F點(diǎn)。如果到E點(diǎn)有a種走法（此處a6），到F點(diǎn)有b種走法（此處b4），根據(jù)加法原理，到D點(diǎn)就有（ab）種走法（此處為64=10）。我們可以從左下角A點(diǎn)開(kāi)始，按加法原理，依次向上、向右填上到各點(diǎn)的走法數(shù)（見(jiàn)右上圖），最后得到共有35條不同路線(xiàn)。二. 加乘原理加法原理： 分情況、分類(lèi)計(jì)數(shù)；乘法原理：分步驟完成，各步驟單獨(dú)計(jì)數(shù)，再連乘；加乘混合：加法、乘法混合使用； （1）一個(gè)步驟內(nèi)有多種情況時(shí)，在計(jì)算本步驟時(shí)用加法，再總體用乘法計(jì)算出所有情況； （2）總體分幾種情況，分別計(jì)算各種情況時(shí)分步驟用乘法

3、，再將各種情況匯總用加法 加法原理與乘法原理的區(qū)別：乘法原理和加法原理是兩個(gè)重要而常用的計(jì)數(shù)法則，在應(yīng)用時(shí)一定要注意它們的區(qū)別。乘法原理是把一件事分幾步完成，這幾步缺一不可，所以完成任務(wù)的不同方法數(shù)等于各步方法數(shù)的乘積；加法原理是把完成一件事的方法分成幾類(lèi)，每一類(lèi)中的任何一種方法都能完成任務(wù)（一步完成任務(wù)），所以完成任務(wù)的不同方法數(shù)等于各類(lèi)方法數(shù)之和。ABC例題：由A村去B村有2條路可走，由B村去C村有4條路可走，問(wèn)從A村經(jīng)B村去C村，共有多少種不同的走法？ 三.排列組合排列：有順序要求（交換順序，就產(chǎn)生新的計(jì)數(shù)）à乘法原理；A52=5×4 從個(gè)不同的元素中取出()個(gè)元素，

4、按照一定的順序排成一列，叫做從個(gè)不同元素中取出個(gè)元素的一個(gè)排列（1）兩個(gè)排列相同，指的是兩個(gè)排列的元素完全相同，并且元素的排列順序也相同（2）如果兩個(gè)排列中，元素不完全相同，它們是不同的排列；（3）如果兩個(gè)排列中，雖然元素完全相同，但元素的排列順序不同，它們也是不同的排列計(jì)算：乘法原理：從個(gè)不同元素中取出個(gè)元素的排列數(shù)是，即，這里，且等號(hào)右邊從開(kāi)始，共有個(gè)因數(shù)相乘。組合：無(wú)順序要求（交換順序，不產(chǎn)生新的計(jì)數(shù)）à除法原理；C52=（5×4）÷（2×1） 從個(gè)不同元素中取出個(gè)()元素組成一組不計(jì)較組內(nèi)各元素的次序，叫做從個(gè)不同元素中取出個(gè)元素的一個(gè)組合 （1

5、）從排列和組合的定義可以知道，排列與元素的順序有關(guān)，而組合與順序無(wú)關(guān)（2）如果兩個(gè)組合中，元素不完全相同，它們是不同的組合；（3）如果兩個(gè)組合中的元素完全相同，那么不管元素的順序如何，都是相同的組合計(jì)算：除法原理：從個(gè)不同元素中取出個(gè)元素()的所有組合的個(gè)數(shù)，叫做從個(gè)不同元素中取出個(gè)不同元素的組合數(shù)記作。一般地，求從個(gè)不同元素中取出的個(gè)元素的排列數(shù)可分成以下兩步：第一步：從個(gè)不同元素中取出個(gè)元素組成一組，共有種方法； 第二步：將每一個(gè)組合中的個(gè)元素進(jìn)行全排列，共有種排法根據(jù)乘法原理，得到因此，組合數(shù)（運(yùn)用除法，將元素完全相同，元素順序不同的多種排列合并成一種組合）【例 1】 小新、阿呆等七個(gè)同

6、學(xué)照像，分別求出在下列條件下有多少種站法？（1）七個(gè)人排成一排； （2）七個(gè)人排成一排，小新必須站在中間.（3）七個(gè)人排成一排，小新、阿呆必須有一人站在中間.（4）七個(gè)人排成一排，小新、阿呆必須都站在兩邊.（5）七個(gè)人排成一排，小新、阿呆都沒(méi)有站在邊上.（6）七個(gè)人戰(zhàn)成兩排，前排三人，后排四人.（7）七個(gè)人戰(zhàn)成兩排，前排三人，后排四人. 小新、阿呆不在同一排。（1）（種）。（2）只需排其余6個(gè)人站剩下的6個(gè)位置（種）.（3）先確定中間的位置站誰(shuí)，冉排剩下的6個(gè)位置2×=1440(種)（4）先排兩邊，再排剩下的5個(gè)位置，其中兩邊的小新和阿呆還可以互換位置 (種)（5）先排兩邊，從除小新

7、、阿呆之外的5個(gè)人中選2人，再排剩下的5個(gè)人，（種）.（6）七個(gè)人排成一排時(shí)，7個(gè)位置就是各不相同的現(xiàn)在排成兩排，不管前后排各有幾個(gè)人，7個(gè)位置還是各不相同的，所以本題實(shí)質(zhì)就是7個(gè)元素的全排列（種）.（7）可以分為兩類(lèi)情況：“小新在前，阿呆在后”和“小新在前，阿呆在后”，兩種情況是對(duì)等的，所以只要求出其中一種的排法數(shù)，再乘以2即可4×3××2=2880(種)排隊(duì)問(wèn)題，一般先考慮特殊情況再去全排列?！眷柟獭?現(xiàn)有男同學(xué)3人，女同學(xué)4人(女同學(xué)中有一人叫王紅)，從中選出男女同學(xué)各2人，分別參加數(shù)學(xué)、英語(yǔ)、音樂(lè)、美術(shù)四個(gè)興趣小組：(1)共有多少種選法?(2)其中參加美術(shù)

8、小組的是女同學(xué)的選法有多少種?(3)參加數(shù)學(xué)小組的不是女同學(xué)王紅的選法有多少種?(4)參加數(shù)學(xué)小組的不是女同學(xué)王紅，且參加美術(shù)小組的是女同學(xué)的選法有多少種?（1）從3個(gè)男同學(xué)中選出2人，有=3種選法。從4個(gè)女同學(xué)中選出2人，有=6種選法。在四個(gè)人確定的情況下，參加四個(gè)不同的小組有4×3×2×1=24種選法。3×6×24=432，共有432種選法。（2）在四個(gè)人確定的情況下，參加美術(shù)小組的是女同學(xué)時(shí)有2×3×2×1=12種選法。3×6×12=216，所以其中參加美術(shù)小組的是女同學(xué)的選法有216種。

9、（3）考慮參加數(shù)學(xué)小組的是王紅時(shí)的選法，此時(shí)的問(wèn)題相當(dāng)于從3個(gè)男同學(xué)中選出2人，從3個(gè)女同學(xué)中選出1人，3個(gè)人參加3個(gè)小組時(shí)的選法。3×3×3×2×1=54，所以參加數(shù)學(xué)小組的是王紅時(shí)的選法有54種，432-54=378，所以參加數(shù)學(xué)小組的不是女同學(xué)王紅的選法有378種。（4）考慮參加數(shù)學(xué)小組的是王紅且參加美術(shù)小組的是女同學(xué)時(shí)的選法，此時(shí)的問(wèn)題相當(dāng)于從3個(gè)男同學(xué)中選出2人參加兩個(gè)不同的小組，從3個(gè)女同學(xué)中選出1人參加美術(shù)小組時(shí)的選法。3×2×3=18，所以參加數(shù)學(xué)小組的是王紅且參加美術(shù)小組的是女同學(xué)時(shí)的選法有18種，216-18=19

10、8，所以參加數(shù)學(xué)小組的不是女同學(xué)王紅，且參加美術(shù)小組的是女同學(xué)的選法有198種。四.優(yōu)選法優(yōu)選法：對(duì)于問(wèn)題中的特殊元素、特殊位置要優(yōu)先安排確定。在操作時(shí)，針對(duì)實(shí)際問(wèn)題，有時(shí)“元素優(yōu)先”，有時(shí)“位置優(yōu)先”。注意：看特殊，分步、分類(lèi)，限制完，自由排，注意“0”。難點(diǎn)：不管是位置優(yōu)先還是元素優(yōu)先，都要看清是分類(lèi)還是分步來(lái)解決問(wèn)題；注意“0”，題目中往往對(duì)于“0”有暗含的限制條件。例題.由數(shù)字1、2、3、4、5組成沒(méi)有重復(fù)數(shù)字的五位數(shù)，其中小于50000的偶數(shù)共有多少個(gè)？解析一：利用位置優(yōu)先方法。偶數(shù)則要求個(gè)位為偶數(shù)，小于50000則首位要小于5。:第一步，首先看個(gè)位，從2個(gè)偶數(shù)中選擇有C12種選法；

11、第二步，看首位，從個(gè)數(shù)上已選數(shù)字和5之外的數(shù)字選，則有 C13種選法；第三步，對(duì)于剩下的三個(gè)位置沒(méi)有限制，則可以隨意選擇剩下的三個(gè)數(shù)字排上去，則有A33 種選法。根據(jù)乘法計(jì)數(shù)原則，共有：C12×C13 ×A33=36。解析二：利用元素優(yōu)先方法。第一步，從數(shù)字2、4中選一個(gè)放在個(gè)位上，有C12種選法；第二步，從個(gè)數(shù)上已選數(shù)字和5之外的數(shù)字選一個(gè)放在首位上，則有 C13種選法；第三步，對(duì)于剩下的三個(gè)數(shù)字沒(méi)有限制，則可以隨意安排到剩下的三個(gè)數(shù)位上去，則有A33 種選法。根據(jù)乘法計(jì)數(shù)原則，共有：C12×C13 ×A44=36。五.”捆綁法” 捆綁法：用于解決&q

12、uot;相鄰問(wèn)題"，即在解決對(duì)于某幾個(gè)元素要求相鄰的問(wèn)題時(shí)，先將其"捆綁"后整體考慮，也就是將相鄰元素視作"一個(gè)"大元素進(jìn)行排序，然后再考慮大元素內(nèi)部各元素間排列順序的解題策略。 注意：運(yùn)用捆綁法解決排列組合問(wèn)題時(shí)，一定要注意"捆綁"起來(lái)的大元素內(nèi)部的順序問(wèn)題。解題過(guò)程是"先捆綁，再排列"。例題：若有A、B、C、D、E五個(gè)人排隊(duì)，要求A和B兩個(gè)人必須站在相鄰位置，則有多少排隊(duì)方法？ 【解析】：題目要求A和B兩個(gè)人必須排在一起，首先將A和B兩個(gè)人"捆綁"，視其為"一個(gè)人&quo

13、t;，也即 對(duì)"A，B"、C、D、E"四個(gè)人"進(jìn)行排列，有 種排法。又因?yàn)槔壴谝黄鸬腁、B兩人也要排序，有 種排法。根據(jù)分步乘法原理，總的排法有 種。 六.“插空法” 插空法：用于解決"不鄰問(wèn)題"，即在解決對(duì)于某幾個(gè)元素要求不相鄰的問(wèn)題時(shí)，先將其它元素排好，再將指定的不相鄰的元素插入已排好元素的間隙或兩端位置，從而將問(wèn)題解決的策略。注意：運(yùn)用插空法解決排列組合問(wèn)題時(shí)，一定要注意插空位置包括先排好元素"中間空位"和"兩端空位"。解題過(guò)程是"先排列，再插空"。例題：若有A、B、

14、C、D、E五個(gè)人排隊(duì)，要求A和B兩個(gè)人必須不站在一起，則有多少排隊(duì)方法？【解析】：題目要求A和B兩個(gè)人必須隔開(kāi)。首先將C、D、E三個(gè)人排列，有 種排法；若排成D C E，則D、C、E"中間"和"兩端"共有四個(gè)空位置，也即是： D C E ，此時(shí)可將A、B兩人插到四個(gè)空位置中的任意兩個(gè)位置，有 種插法。由乘法原理，共有排隊(duì)方法： 。 七.“隔板法”（插板法） 隔板法：有n個(gè)相同的元素，要求分到m組中，并且要求每組中至少有一個(gè)元素問(wèn)有多少種分法？基本思路：將n個(gè)相同的元素排成一行，n個(gè)元素之間出現(xiàn)了（n-1）個(gè)空檔，現(xiàn)在我們用（m-1）個(gè)“檔板”插入（n-1

15、）個(gè)空檔中，就把n個(gè)元素隔成有序的m份，每個(gè)組依次按組序號(hào)分到對(duì)應(yīng)位置的幾個(gè)元素（可能是1個(gè)、2個(gè)、3個(gè)、4個(gè)、.），這樣不同的插入辦法就對(duì)應(yīng)著n個(gè)相同的元素分到m組的一種分法，這種借助于這樣的虛擬“檔板”分配元素的方法稱(chēng)之為插板法?！净绢}型】【例1】 共有10完全相同的球分到7個(gè)班里，要求每個(gè)班至少要分到一個(gè)球，問(wèn)有幾種不同分法？解析一：我們首先用常規(guī)方法。若想將10個(gè)球分到7個(gè)班里，球的分法共三類(lèi)：第一類(lèi)：有3個(gè)班每個(gè)班分到2個(gè)球，其余4個(gè)班每班分到1個(gè)球。這樣，第一步，我們從7個(gè)班中選出3個(gè)班，每個(gè)班分2個(gè)球；第二步，從剩下的4個(gè)班中選4個(gè)班，每班分1球。其分法種數(shù)為 ：C（7，3）*

16、C（4，4）=35注明：由于排版的關(guān)系，我用C（n，m）和A（n，m）代替原來(lái)的組合與排列公式。第二類(lèi)：有1個(gè)班分到3個(gè)球，1個(gè)班分到2個(gè)球，其余5個(gè)班每班分到1個(gè)球。其分法種數(shù) ：C（7，1）* C（6，1）* C（5，5）=42第三類(lèi)：有1個(gè)班分到4個(gè)球，其余的6個(gè)班每班分到1個(gè)球。其分法種數(shù) ：C（7，1）* C（6，6）=7所以，10個(gè)球分給7個(gè)班，每班至少一個(gè)球的分法種數(shù)為： 35+42+7=87（種）。解析二：從上面的解題過(guò)程可以看出，用常規(guī)方法解這類(lèi)題，需要分類(lèi)計(jì)算，計(jì)算過(guò)程繁瑣。并且如果元素個(gè)數(shù)較多的話(huà)處理起來(lái)就變得十分的困難了。因此我們需要尋求一種新的方法解決問(wèn)題，也就是插板

17、法。我們可以將10個(gè)相同的球排成一行，10個(gè)球之間出現(xiàn)了9個(gè)空隙，現(xiàn)在我們用6個(gè)檔板”插入這9個(gè)空隙中，就“把10個(gè)球隔成有序的7份，每個(gè)班級(jí)依次按班級(jí)序號(hào)分到對(duì)應(yīng)位置的幾個(gè)球（可能是1個(gè)、2個(gè)、3個(gè)、4個(gè)），這樣，借助于虛擬“檔板”就可以把10個(gè)球分到了7個(gè)班中。由上述分析可知，原問(wèn)題就可以轉(zhuǎn)化成：在9個(gè)空檔之中插入6個(gè)“檔板”（6個(gè)檔板可把球分為7組）的問(wèn)題，這是一個(gè)很簡(jiǎn)單的組合問(wèn)題，其方法種數(shù)為 ：C（9，6）=84【總結(jié)】：對(duì)于這種要求每組元素至少要分到一個(gè)的情況，則只需在n個(gè)元素的n-1個(gè)間隙中放置m-1塊隔板把它隔成m份即可,共有C（n-1，m-1）種不同方法?！咀⒁狻浚?#160

18、; 這種插板法解決相同元素分到不同組的問(wèn)題非常簡(jiǎn)單，但同時(shí)也提醒各位考友，這類(lèi)問(wèn)題模型適用前提相當(dāng)嚴(yán)格，必須同時(shí)滿(mǎn)足以下3個(gè)條件：（1）所有要分的元素須完全相同； （2）所要分的元素必須分完，決不允許有剩余； （3）參與分元素的每組至少分到1個(gè)，決不允許出現(xiàn)分不到元素的組。     這樣對(duì)于很多的問(wèn)題，是不能直接利用插板法解題的。但，可以通過(guò)一定的轉(zhuǎn)變，將其變成符合上面3個(gè)條件的問(wèn)題，這樣就可以利用插板法解決，并且常常會(huì)產(chǎn)生意想不到的效果。【基本題型的變形（一）】題型：有n個(gè)相同的元素，要求分到m組中，問(wèn)有多少種不同的分法？解題思路：

19、這種問(wèn)題是允許有些組中分到的元素為“0”，也就是組中可以為空的。對(duì)于這樣的題，我們就首先將每組都填上1個(gè)，這樣所要元素總數(shù)就m個(gè)，問(wèn)題也就是轉(zhuǎn)變成將（n+m）個(gè)元素分到m組，并且每組至少分到一個(gè)的問(wèn)題，也就可以用插板法來(lái)解決。  【例2】有8個(gè)相同的球放到三個(gè)不同的盒子里，共有（ ）種不同方法.解析：這道題很多同學(xué)錯(cuò)選C，錯(cuò)誤的原因是直接套用 “插板法”，而忽略了題中并沒(méi)有說(shuō)每個(gè)盒子至少要分到一個(gè)球，也就是可以出現(xiàn)空盒子。原題并不符合“插板法”的條件不過(guò)，此題只要我們多一個(gè)小變化，就可以將其轉(zhuǎn)化為用“插板法”解題的類(lèi)型了。我們可以人為地在每個(gè)盒子增加一個(gè)球，原有8個(gè)相同的球放到三個(gè)不同的盒子里這樣這個(gè)