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

1、計(jì)數(shù)專題學(xué)習(xí)目標(biāo)1 .正確理解“標(biāo)數(shù)”法計(jì)算路徑數(shù)目；2 .正確理解“加法原理”、“乘法原理”的意義和運(yùn)用場景；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ù)加 法原理，到D點(diǎn)就

2、有（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ū)別。乘法原理是把一件事 分幾步完成，這幾步缺一不可 ，所以完成任務(wù)的不

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

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

5、不完全相同，它們是不同的組合；(3)如果兩個(gè)組合中的元素完全相同，那么不管元素的順序如何，都是相同的組合.計(jì)算：除法原理：從n個(gè)不同元素中取出m個(gè)元素(m n)的所有組合的個(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ù)乘法原理，得到PmCmP；,因此，組合數(shù)CmPmn (n 1(n2) L(nm 1Pmm (m 1) (m 2) L 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）（種）。（ 2）只需排其余6 個(gè)人站剩下的6 個(gè)位置（種）.（3）先確定中間的位置站誰，冉排剩下的6個(gè)位置.2X=1440（種）.（ 4）先排

7、兩邊，再排剩下的5 個(gè)位置，其中兩邊的小新和阿呆還可以互換位置（ 種 ） （ 5）先排兩邊，從除小新、阿呆之外的5 個(gè)人中選2 人，再排剩下的5 個(gè)人，（種）.（ 6）七個(gè)人排成一排時(shí)，7 個(gè)位置就是各不相同的現(xiàn)在排成兩排，不管前后排各有幾個(gè)人，7 個(gè)位置還是各不相同的，所以本題實(shí)質(zhì)就是7 個(gè)元素的全排列（種）.（ 7）可以分為兩類情況：“小新在前，阿呆在后”和“小新在前，阿呆在后”，兩種情況是對等的，所以只要求出其中一種的排法數(shù)，再乘以2即可.4X 3XX 2=2880（種）.排隊(duì)問題，一般先考慮特殊情況再去全排列?！眷柟獭楷F(xiàn)有男同學(xué)3人，女同學(xué)4人 （女同學(xué)中有一人叫王紅），從中選出男女同

8、學(xué)各2 人，分別參加數(shù)學(xué)、英語、音樂、美術(shù)四個(gè)興趣小組：（1） 共有多少種選法?（2） 其中參加美術(shù)小組的是女同學(xué)的選法有多少種?（3） 參加數(shù)學(xué)小組的不是女同學(xué)王紅的選法有多少種?（4） 參加數(shù)學(xué)小組的不是女同學(xué)王紅，且參加美術(shù)小組的是女同學(xué)的選法有多少種?. ,32 * .,43. ，一(1)從3個(gè)男同學(xué)中選出2人，有3/=3種選法。從4個(gè)女同學(xué)中選出2人，有=6種選法。在四 個(gè)人確定的情況下，參加四個(gè)不同的小組有4X3X2X1=24種選法。3X 6X24=432,共有432種選法。(2)在四個(gè)人確定的情況下，參加美術(shù)小組的是女同學(xué)時(shí)有2X3X2X 1=12種選法。3X6X12=216,所

9、以其中參加美術(shù)小組的是女同學(xué)的選法有216種。(3)考慮參加數(shù)學(xué)小組的是王紅時(shí)的選法，此時(shí)的問題相當(dāng)于從3個(gè)男同學(xué)中選出2人，從3個(gè)女同學(xué)中選出1人，3個(gè)人參加3個(gè)小組時(shí)的選法。3X3X3X2X1=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í)的選法。 3X2X3=18, 所以參加數(shù)學(xué)小組的是王紅且參加美術(shù)小組的是女同學(xué)時(shí)的選法有18種，216-18=198,

10、所以參加數(shù)學(xué)小組的不是女同學(xué)王紅，且參加美術(shù)小組的是女同學(xué)的選法有198種。四.優(yōu)選法優(yōu)選法：對于問題中的特殊元素、特殊位置要優(yōu)先安排確定。在操作時(shí)，針對實(shí)際問題，有時(shí) “元素優(yōu)先”，有時(shí)“位置優(yōu)先”。注意：看特殊，分步、分類，限制完，自由排，注意“0”。難點(diǎn)：不管是位置優(yōu)先還是元素優(yōu)先，都要看清是分類還是分步來解決問題；注意“0”，題目中往往對于“ 0”有暗含的限制條件。例題.由數(shù)字1、2、3、4、5組成沒有重復(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種選法；第三步，對于剩下的三個(gè)位置沒有限制，則可以隨意選擇剩下的三 個(gè)數(shù)字排上去，則有 A33種選法。根據(jù)乘法計(jì)數(shù)原則，共有： C12X C13 XA33=36。解析二：利用元素優(yōu)先方法。第一步，從數(shù)字2、4中選一個(gè)放在個(gè)位上，有 C12種選法；第二步，從個(gè)數(shù)上已選數(shù)字和5之外的數(shù)字選一個(gè)放在首位上，則有C13種選法；第三步，對于剩下的三個(gè)數(shù)字沒有限制，則可以隨意安排到剩下的三個(gè)數(shù)位上去，則有A33種選法。根據(jù)乘法計(jì)數(shù)原則，共有：C12X C13 XA44=36。五 . ”捆綁法”捆綁法：用于解決"相鄰問題"，即在

12、解決對于某幾個(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è)人 " 捆綁" ，視其為"一個(gè)人 &q

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

14、uot; 。例題：若有A、B、C D E五個(gè)人排隊(duì)，要求 A和B兩個(gè)人必須不站在一起，則有多少排隊(duì)方法？【解析】：題目要求 A和B兩個(gè)人必須隔開。首先將 C、Dk 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)了（

15、n-1）個(gè)空檔，現(xiàn)在我們用（m-1）個(gè) “檔板”插入（n-1 ）個(gè)空檔中，就把n個(gè)元素隔成有序的 m份，每個(gè)組依次按組序號(hào)分到對應(yīng)位置的幾個(gè)元素（可能是 1個(gè)、2個(gè)、3個(gè)、4個(gè)、.），這樣不同的插入辦法就對應(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è)班，每

16、個(gè)班分2 個(gè)球；第二步，從剩下的4 個(gè)班中選4 個(gè)班，每班分1 球。其分法種數(shù)為： C（ 7， 3） *C（ 4， 4） =35注明：由于排版的關(guān)系，我用 C （n, m）和A （n, mm代替原來的組合與排列公式。第二類：有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（種）。解析

17、二：從上面的解題過程可以看出，用常規(guī)方法解這類題，需要分類計(jì)算，計(jì)算過程繁瑣。并且如果元素個(gè)數(shù)較多的話處理起來就變得十分的困難了。因此我們需要尋求一種新的方法解決問題，也就是插板法。我們可以將10 個(gè)相同的球排成一行，10 個(gè)球之間出現(xiàn)了9 個(gè)空隙，現(xiàn)在我們用6 個(gè)檔板”插入這 9 個(gè)空隙中，就“把 10 個(gè)球隔成有序的7 份，每個(gè)班級依次按班級序號(hào)分到對應(yīng)位置的幾個(gè)球（可能是1 個(gè)、 2 個(gè)、 3 個(gè)、 4 個(gè)），這樣，借助于虛擬“檔板”就可以把 10 個(gè)球分到了 7 個(gè)班中。由上述分析可知，原問題就可以轉(zhuǎn)化成：在9 個(gè)空檔之中插入6 個(gè)“檔板”（ 6 個(gè)檔板可把球分為 7 組）的問題，這是

18、一個(gè)很簡單的組合問題，其方法種數(shù)為： C（ 9， 6） =84【總結(jié)】：對于這種要求每組元素至少要分到一個(gè)的情況，則只需在n 個(gè)元素的n-1 個(gè)間隙中放置m-1塊隔板把它隔成 m份即可，共有C （n-1 , m-1）種不同方法?！咀⒁狻浚哼@種插板法解決相同元素分到不同組的問題非常簡單，但同時(shí)也提醒各位考友，這類3 個(gè)條件：（ 1）所有要分的元素須完全相同；（ 2）所要分的元素必須分完，決不允許有剩余；（ 3）參與分元素的每組至少分到1 個(gè)，決不允許出現(xiàn)分不到元素的組。這樣對于很多的問題，是不能直接利用插板法解題的。但，可以通過一定的轉(zhuǎn)變，將其變成符合上面3 個(gè)條件的問題，這樣就可以利用插板法解

19、決，并且常常會(huì)產(chǎn)生意想不到的效果?！净绢}型的變形（一）】題型：有n個(gè)相同的元素，要求分到 m組中，問有多少種不同的分法？解題思路：這種問題是允許有些組中分到的元素為“0”，也就是組中可以為空的。對于這樣的題，我們就首先將每組都填上1個(gè)，這樣所要元素總數(shù)就 m個(gè)，問題也就是轉(zhuǎn)變成將（n+n）個(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è)相同的球放到3 個(gè)不同盒子