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

1、計(jì)數(shù)專題學(xué)習(xí)目標(biāo)1 .正確理解“標(biāo)數(shù)”法計(jì)算路徑數(shù)目；2 .正確理解“加法原理”、“乘法原理”的意義和運(yùn)用場(chǎng)景；3 .正確理解“排列”、“組合”的意義、區(qū)別和計(jì)算公式；4 .正確掌握“優(yōu)選法” “捆綁法”、“插空法”、“隔板法”這些排列組合解題技巧, 理解各種排列組合解題技巧的原理，所解決的問題類型及其解題方法；一.標(biāo)數(shù)法例題：在左下圖中，從 A點(diǎn)沿實(shí)線走最短路徑到 B點(diǎn)，共有多少條不同路線?分析與解：題目要求從左下向右上走，所以走到任一點(diǎn)，例如右上圖中的D點(diǎn)，不是經(jīng)過左邊的 E點(diǎn)，就是經(jīng)過下邊的 F點(diǎn)。如果到E點(diǎn)有a種走法（此處a = 6）,到F點(diǎn)有b種走法（此處b=4）,根 據(jù)加法原理，到

2、 D點(diǎn)就有（a+b）種走法（此處為6 + 4=10）。我們可以從左下角 A點(diǎn)開始，按加法原 理，依次向上、向右填上到各點(diǎn)的走法數(shù)（見右上圖），最后得到共有35條不同路線。二.加乘原理加法原理：分情況、分類計(jì)數(shù)；乘法原理：分步驟完成，各步驟單獨(dú)計(jì)數(shù)，再連乘；加乘混合：加法、乘法混合使用；（1） 一個(gè)步驟內(nèi)有多種情況時(shí)，在計(jì)算本步驟時(shí)用加法，再總體用乘法計(jì)算出所有情況；（2）總體分幾種情況，分別計(jì)算各種情況時(shí)分步驟用乘法，再將各種情況匯總用加法加法原理與乘法原理的區(qū)別：乘法原理和加法原理是兩個(gè)重要而常用的計(jì)數(shù)法則，在應(yīng)用時(shí)一定要注意 它們的區(qū)別。乘法原理是把一件事 分幾步完成，這幾步缺一不可，所以

3、完成任務(wù)的不同方法數(shù)等于各步 方法數(shù)的乘積；加法原理是把完成一件事的方法分成幾類，每一類中的任何一種方法都能完成任務(wù)（一步完成任務(wù)），所以完成任務(wù)的不同方法數(shù)等于各類方法數(shù)之和。例題：由A村去B村有2條路可走，由B村去C村有4條路可走，問從 A村經(jīng)B村去C村，共有多少種不同的走法?三.排列組合排列：有順序要求(交換順序，就產(chǎn)生新的計(jì)數(shù))乘法原理；A52=5%從n個(gè)不同的元素中取出 m (mEn)個(gè)元素，按照一定的順序排成一列，叫做從n個(gè)不同元素中取出m個(gè)元素的一個(gè)排列.(1)兩個(gè)排列相同，指的是兩個(gè)排列的元素完全相同，并且元素的排列順序也相同.(2)如果兩個(gè)排列中，元素不完全相同，它們是不同的

4、排列；(3)如果兩個(gè)排列中，雖然元素完全相同，但元素的排列順序不同，它們也是不同的排列.計(jì)算：乘法原理：從n個(gè)不同元素中取出 m個(gè)元素的排列數(shù)是n(n1) (n-2) i|(n-m+1),即Pm =n(n 1)(n2)| Knm+1),這里，mEn,且等號(hào)右邊從n開始，共有m個(gè)因數(shù)相乘。組合：無順序要求(交換順序，不產(chǎn)生新的計(jì)數(shù))除法原理；C52= (5M) + (2X)從n個(gè)不同元素中取出mj(mWn)元素組成一組不計(jì)較組內(nèi)各元素的次序，叫做從n個(gè)不同元素中取出m個(gè)元素的一個(gè)組合.(1)從排列和組合的定義可以知道，排列與元素的順序有關(guān)，而組合與順序無關(guān).(2)如果兩個(gè)組合中，元素不完全相同，

5、它們是不同的組合；(3)如果兩個(gè)組合中的元素完全相同，那么不管元素的順序如何，都是相同的組合.計(jì)算：除法原理：從n個(gè)不同元素中取出 m個(gè)元素(mWn)的所有組合的個(gè)數(shù)，叫做從 n個(gè)不同元素中 取出m個(gè)不同元素的組合數(shù).記作onmo一般地，求從n個(gè)不同元素中取出的 m個(gè)元素的排列數(shù)Pmn可分成以下兩步：第一步：從n個(gè)不同元素中取出m個(gè)元素組成一組，共有 Cnm種方法；第二步：將每一個(gè)組合中的 m個(gè)元素進(jìn)行全排列，共有 Pm種排法.根據(jù)乘法原理，得到pm=cm p二.因此，組合數(shù)cnm4=n(n-1 :n：2) "I(n-m+1pmmm，( m 1) .(m-2)川 3 2 1(運(yùn)用除法

6、，將元素完全相同，元素順序不同的多種排列合并成一種組合).【例1】 小新、阿呆等七個(gè)同學(xué)照像，分別求出在下列條件下有多少種站法？(1)七個(gè)人排成一排；(2)七個(gè)人排成一排，小新必須站在中間.(3)七個(gè)人排成一排，小新、阿呆必須有一人站在中間.(4)七個(gè)人排成一排，小新、阿呆必須都站在兩邊.(5)七個(gè)人排成一排，小新、阿呆都沒有站在邊上.(6)七個(gè)人戰(zhàn)成兩排，前排三人，后排四人.(7)七個(gè)人戰(zhàn)成兩排，前排三人，后排四人.小新、阿呆不在同一排。(1) P77 =5040 (種)。(2)只需排其余6個(gè)人站剩下的6個(gè)位置.P66 =720 (種).(3)先確定中間的位置站誰，冉排剩下的6個(gè)位置.2 X

7、P66 =1440(種).(4)先排兩邊，再排剩下的 5個(gè)位置，其中兩邊的小新和阿呆還可以互換位置.2父傍=240 (種).(5)先排兩邊，從除小新、阿呆之外的5個(gè)人中選2人，再排剩下的5個(gè)人，P52Mp5 =2400 (種).(6)七個(gè)人排成一排時(shí)，7個(gè)位置就是各不相同的.現(xiàn)在排成兩排，不管前后排各有幾個(gè)人，7個(gè)位置還是各不相同的，所以本題實(shí)質(zhì)就是 7個(gè)元素的全排列.P7 =5040 (種).(7)可以分為兩類情況：“小新在前，阿呆在后”和“小新在前，阿呆在后”，兩種情況是對(duì)等的，所以只要 求出其中一種的排法數(shù)，再乘以 2即可.4X3xp5 x2=2880(種).排隊(duì)問題，一般先考慮特殊情況

8、再去全排 列?！眷柟獭楷F(xiàn)有男同學(xué)3人，女同學(xué)4人(女同學(xué)中有一人叫王紅)，從中選出男女同學(xué)各 2人，分別參加數(shù) 學(xué)、英語、音樂、美術(shù)四個(gè)興趣小組：(1)共有多少種選法？ (2)其中參加美術(shù)小組的是女同學(xué)的選法有多少種(3)參加數(shù)學(xué)小組的不是女同學(xué)王紅的選法有多少種？(4)參加數(shù)學(xué)小組的不是女同學(xué)王紅，且參加美術(shù)小組的是女同學(xué)的選法有多少種？3 24 3(1)從3個(gè)男同學(xué)中選出2人，有3-2 =3種選法。從4個(gè)女同學(xué)中選出2人，有43 =6種選法。在四個(gè)人確定的情況下，參加四個(gè)不同的小組有4>><2X1=24種選法。3X6X24=432,共有432種選法。(2)在四個(gè)人確定的情

9、況下，參加美術(shù)小組的是女同學(xué)時(shí)有2>X2X=12種選法。3X6X12=216 ,所以其中參加美術(shù)小組的是女同學(xué)的選法有216種。(3)考慮參加數(shù)學(xué)小組的是王紅時(shí)的選法，此時(shí)的問題相當(dāng)于從3個(gè)男同學(xué)中選出2人，從3個(gè)女同學(xué)中選出1人，3個(gè)人參加3個(gè)小組時(shí)的選法。3X3 4X2X1=54,所以參加數(shù)學(xué)小組的是王紅時(shí)的選法 有54種，432-54=378 ,所以參加數(shù)學(xué)小組的不是女同學(xué)王紅的選法有378種。(4)考慮參加數(shù)學(xué)小組的是王紅且參加美術(shù)小組的是女同學(xué)時(shí)的選法，此時(shí)的問題相當(dāng)于從3個(gè)男同學(xué)中選出2人參加兩個(gè)不同的小組，從 3個(gè)女同學(xué)中選出1人參加美術(shù)小組時(shí)的選法。3X24=18,所以參

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

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

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

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

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

15、“檔板”插入n-1)個(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組的一種分法，這種借助于這樣的虛擬“檔板”分配元素的方 法稱之為插板法?！净绢}型】【例1】共有10完全相同的球分到7個(gè)班里，要求每個(gè)班至少要分到一個(gè)球，問有幾種不同分法？解析一：我們首先用常規(guī)方法。若想將 10個(gè)球分到7個(gè)班里，球的分法共三類：第一類：有3個(gè)班每個(gè)班分到2個(gè)球，其余4個(gè)班每班分到1個(gè)球。這樣，第一步，我們從 7個(gè) 班中選出3個(gè)班，每個(gè)班分2個(gè)球；第二步，從剩下的 4個(gè)班中選4個(gè)班，每班分1球

16、。 其分法種數(shù)為：C (7, 3) *C (4, 4) =35注明：由于排版的關(guān)系，我用 C (n, m)和A (n, m)代替原來的組合與排列公式。第二類：有1個(gè)班分到3個(gè)球，1個(gè)班分到2個(gè)球，其余5個(gè)班每班分到1個(gè)球。其分法種數(shù)： C (7, 1) *C (6, 1) *C (5, 5) =42第三類：有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ī)方法解這類題，需要分類計(jì)算，計(jì)算過程繁瑣。并且如 果元素個(gè)數(shù)較多

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è)班中。由上述分析可知，原問題就可以轉(zhuǎn)化成：在 9個(gè)空檔之中插入6個(gè)“檔板” 6個(gè)檔板可把球分為 7組)的問題，這是一個(gè)很簡(jiǎn)單的組合問題，其方法種數(shù)為：C (9, 6) =84【總結(jié)】：對(duì)于這種要求每組元素至少要分到一個(gè)的情況，則只需在 n個(gè)元素的n

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

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