排列、組合中常見的解題思路與方法

解決與排列、組合有關(guān)的問題，首先，必須認真審題，明確這個問題是排列問題，還是組合問題？其次，抓住問題的本質(zhì)特征，靈活運用基本計數(shù)原理和排列數(shù)、組合數(shù)公式進行分析、解答.實踐證明，備考的有效方法是題型和解法歸類，識別模式，熟練運用.下面例談排列、組合問題中常見的解題思路和方法.

一、分組（堆）問題

分組（堆）問題的6個模型：①無序不等分;②無序等分;③無序局部等分;④有序不等分;⑤有序等分;⑥有序局部等分.

處理問題的原則：

（1）若干個不同的元素“等分”為n堆，要將選取出每一個堆的組合數(shù)的乘積除以n！;

（2）若干個不同的元素局部“等分”有k個均等堆，要將選取出每一個堆的組合數(shù)的乘積除以k！;

（3）非均分堆問題，只要按比例取出分完再用乘法原理作積;

（4）要明確堆的順序時，必須先分堆后，再把堆數(shù)當作元素個數(shù)進行全排列.

例1 有4項不同的工程，要分包給3個工程隊，要求每個工程隊至少分到一項工程，共有多少種不同的分包方式？

解：要完成分包這件事，可以分為兩個步驟：

①先將4項工程分為3“堆”，有C24C12C11A22=6種分法;

②再將分好的3“堆”依次分給3個工程隊，有3！=6種分法.所以，共有6×6=36種不同的分包方式.

二、不相鄰元素“插空法”

解決一些不相鄰問題時，可以先排“一般”元素，然后插入“特殊”元素，使問題得以解決.

例2 7人排成一排，甲、乙兩人不相鄰，有多少種不同的排法？

解：分兩步進行：

①把除甲乙以外的其他5人排列，有A55=120種排法;

②將甲乙分別插入到不同的間隙或兩端中（插空），有A26=30種插入法.

所以，共有120×30=3600種排法.

注意：幾個元素不能相鄰時，先排一般元素，再讓特殊元素插空.

三、相鄰元素“捆綁法”

相鄰元素的排列，可以采用“局部到整體”的排法，即將相鄰的元素局部排列當成“一個”元素，然后再進行整體排列.

例3 6人排成一排，甲、乙兩人必須相鄰，有多少種不同的排法？

解：可分兩步進行：

①把甲乙排列（捆綁），有A22=2種捆法;

②把甲乙兩人的捆看作一個人與其他的4人排隊，有A55=120種排法.

所以，共有2×120=240種排法.

注意：幾個元素必須相鄰時，先捆綁成一個元素，再與其它的進行排列.

四、消序法（留空法）

幾個元素順序一定的排列問題，一般是先排列，再消去這幾個元素的順序，或者先讓其它元素選取位置排列，留下來的空位置自然就是順序一定的了.

例4 5個人站成一排，甲總是站在乙的右側(cè)有多少種站法？

解法1：將5個人依次站成一排，有A55種站法，然后再消去甲乙之間的順序數(shù)A22，所以甲總站在乙的右側(cè)站法總數(shù)為A55A22=A35=60.

解法2：先讓甲乙之外的3人從5個位置選出3個站好，有A35種站法，留下的兩個位置自然給甲乙，有1種站法.所以，甲總站在乙右側(cè)的站法總數(shù)為A35×1=A35.

五、隔板法

n個相同小球放入m（m≤n）個盒子里，要求每個盒子里至少有一個小球的放法等價于n個相同的小球穿成一串，從間隙里選m-1個結(jié)點剪截成m段.

例5 某校準備參加今年高中數(shù)學聯(lián)賽，把16名選手名額分配到高三年級的1～4個教學班，每班至少一個名額，則不同的分配方案共有 " "種.

解：問題等價于把16個相同的小球放入4個盒子里，每個盒子里至少有一個小球的放法種數(shù)問題.將16個小球穿成一串，截為4段有C315=455種截斷法，對應放到4個盒子里.因此，不同的分配方案共有455種.

變式：某校準備參加今年高中數(shù)學聯(lián)賽，把16個選手名額分配到高三年級的1～4個數(shù)學班，每班的名額不少于該班序號數(shù)，則不同的分配方案共有多少種？

解：問題等價于先給2班1個，3班2個，4班3個，再把剩余的10個相同小球放入4個盒子里，每個盒子至少有一個小球的方法種數(shù)問題.將10個小球穿成一串，截為4段，有C39種截法，對應放到4個盒子里.因此，不同的分配方案共C39=84種.

六、錯位法

編號為1至n的n個小球放入編號為1到n的n個盒子里，每個盒子里放一個小球，要求小球與盒子的編號都不同，這種排列稱為錯位排列.

例6 編號為1至6的6個小球放入編號為1至6的6個盒子里，每個盒子放一個小球，其中恰有2個小球與盒子的編號相同的放法有多少種？

解：選取編號相同的兩組球和盒子的方法有C26=15種，其余4組球與盒子需錯位排列有9種方法.故所求方法有：15×9=135種.

七、剔除法

從總體中排除不符合條件的方法數(shù)，這是一種間接解題的方法.排列組合應用題往往和代數(shù)、三角、立體幾何、平面解析幾何的某些知識聯(lián)系，從而增加了問題的綜合性.

例7 以正方體的頂點為頂點的四面體有多少個？

解：正方體8個頂點從中每次取4個，理論上可構(gòu)成C48種四面體，但6個表面和6個對角面的4個頂點共面就不能構(gòu)成四面體.所以四面體實際有C48-12=58個.

變式：某校開設A類選修課3門，B類選修課4門，一位同學從中共選3門，若要求兩類課程中各至少選一門，則不同的選法共有 " "種.

解法1：分兩類：①A類選修課2門，B類選修課1門，有C23×C14種;②A類選修課1門，B類選修課2門，有C13×C24種.故共有C23×C14+C13×C24=30種.

解法2：從7門中任意選修3門，有C37種，減去3門同時在A類選修課（C33）或B類選修課（C34）中，故共有C37-C33-C34=30種.

八、圓排問題線排法

n個元素圓排列數(shù)有n！n種.

例8 5對姐妹站成一圈，要求每對姐妹相鄰，有多少種不同的站法？

解：根據(jù)乘法原理，分兩步：第一步是把5對姐妹看作5個整體，進行排列有5！種不同的排法，但是因為是圍成一個首尾相接的圓圈，就會產(chǎn)生5個重復，因此實際排法只有5！5=24種.第二步每一對姐妹之間又可以相互交換位置，也就是說每一對姐妹均有2種排法，共有25=32種.所以應有24×32=768種站法.

九、可重復的排列求冪法

重復排列問題要區(qū)分兩類元素：一類可以重復，另一類不能重復.把不能重復的元素看作“客”，能重復的元素看作“店”，則通過“住店法”可順利解題，在這類問題使用住店處理的策略中，關(guān)鍵是正確判斷哪個是底數(shù)，哪個是指數(shù).

例9 8名同學爭奪3項冠軍，獲得冠軍的可能性有 " "種.

解：冠軍不能重復，但同一個學生可獲得多項冠軍，把8名學生看作8家“店”，3項冠軍看作3個“客”，他們都可能住進任意一家“店”，每個“客”有8種可能.因此共有83種不同的結(jié)果.

（作者：丁稱興，江蘇省溧水高級中學）