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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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