用“十字法”解排列組合類應(yīng)用題

排列與組合是中學(xué)數(shù)學(xué)中較為特殊的部分，特殊性在于它研究的對(duì)象以及研究的方法都和學(xué)生已掌握的數(shù)學(xué)知識(shí)很不相同，內(nèi)容比較抽象，方法比較靈活.但因它與舊知識(shí)聯(lián)系相對(duì)較少，初學(xué)者不易深刻理解和掌握，容易出現(xiàn)重復(fù)、遺漏和方法選擇不當(dāng)?shù)儒e(cuò)誤.最近筆者在教學(xué)之余，苦心研習(xí)，深入思考，連點(diǎn)成線，總結(jié)出解排列組合類應(yīng)用題的“十字法”，即用“加，減，乘，除，捆，插，隔，化，列，遞”十字可解決常見(jiàn)的排列組合類應(yīng)用題.下面作簡(jiǎn)要闡述.

一、加，乘

分類、分步計(jì)數(shù)原理，用途很廣泛，因主要用加法、乘法，也分別被稱為加法原理、乘法原理.

【例1】 給圖1中的區(qū)域涂色，要求相鄰區(qū)域不同色，現(xiàn)有4種可選顏色，則不同的涂色方法有多少種？

解：當(dāng)①、⑤同色時(shí)，先涂①⑤，然后按②、③、④的順序進(jìn)行涂色，據(jù)分步計(jì)數(shù)原理得涂法有4×3×2×2=48種；

當(dāng)①、⑤不同色時(shí)，先涂①，然后按涂⑤、②、③、④的順序進(jìn)行涂色，據(jù)分步計(jì)數(shù)原理得涂法有4×3×2×1×1=24種；

最后再據(jù)分類計(jì)數(shù)原理，得共有48+24=72種不同的涂法.

【例2】 已知A={-1，0，1}，B={2，3，5}，且f是從A到B的映射，若x+xf（x）+f（x）為奇數(shù)，則不同的映射最多有多少個(gè)？

解：分三步考慮.

第一步，當(dāng)x=-1時(shí)，由于x+xf（x）+f（x）=-1總為奇數(shù)，所以f（-1）可以為B中的2或3或5，這樣A中的元素-1與B中的元素就有3種對(duì)應(yīng)方法.

第二步，當(dāng)x=0時(shí)，由于x+xf（x）+f（x）=f（0）要為奇數(shù)，所以f（0）只能為B中的3或5，這樣A中的元素0與B中的元素就有2種對(duì)應(yīng)方法.

第三步，當(dāng)x=1時(shí)，由于x+xf（x）+f（x）=1+2f（1）總為奇數(shù)，所以f（1）可以為B中的2或3或5，這樣A中的元素1與B中的元素就有3種對(duì)應(yīng)方法.

根據(jù)分步計(jì)數(shù)原理，共有3×2×3=18個(gè)映射.

二、減

題設(shè)中出現(xiàn)不確定詞“至多”、“至少”，以及否定詞“不”時(shí)，為了避免過(guò)多分類，往往會(huì)從反面來(lái)考慮，這樣就出現(xiàn)了減法，對(duì)應(yīng)的方法叫去雜法.

【例3】 從正六棱柱的12個(gè)頂點(diǎn)中任取四點(diǎn)，其中不共面的四點(diǎn)有多少組？

解：從12個(gè)點(diǎn)中任取4個(gè)點(diǎn)，有C412種不同取法，從中再除去四點(diǎn)共面的組數(shù)即得所求的四點(diǎn)不共面的組數(shù).那么在正六棱柱的12個(gè)頂點(diǎn)中，有多少組四點(diǎn)共面呢？

（1）四點(diǎn)所共的面是水平的，有2C46=30組；

（2）四點(diǎn)所共的面是豎直的，有C26=15組；

（3）四點(diǎn)所共的面是傾斜的，有6×2+6×1+3×2=24組.

所以，不共面的四點(diǎn)有C412-30-15-24=426組.

三、除

排列問(wèn)題中，有些元素之間的排列順序“已經(jīng)固定”，這時(shí)候可以先將這些元素與其他元素進(jìn)行排列，再除以這些元素的全排列數(shù).另外平均分組的問(wèn)題，也要用到除法.

【例4】 一張節(jié)目表上原有6個(gè)節(jié)目，如果保持這6個(gè)節(jié)目的相對(duì)順序不變，再添3個(gè)新節(jié)目，有多少種安排方法？

解：A99÷A66=504種.也有人稱此法為“縮倍法”.

【例5】 （1）將13個(gè)球隊(duì)分成3組，一組5個(gè)隊(duì)，其他兩組4個(gè)隊(duì)，有多少種分法？

（2）6本不同的書(shū)全部送給4人，每人至少1本，共有多少種不同的送書(shū)方法？

分析：平均分成的組，不管它們的順序如何，都屬于同一種情況，所以分組后一定要除以Ann（n為均分的組數(shù)），避免重復(fù)計(jì)數(shù).

解：（1）雖不全是平均分組，但里面有平均分組，故分法為C513×C48C44A22=45045種.

（2）分兩步進(jìn)行.第一步，先將這6本書(shū)分成4堆，每堆數(shù)目為3，1，1，1和2，2，1，1.第二步，再將分得的4堆分給4個(gè)人，每人一堆，所以共有（C36C13C12C11A33+C26C24C12C11A22A22）×A44=1560種送書(shū)方法.

四、捆，插

要求某幾個(gè)元素排在一起可以用捆綁法來(lái)解決；要求某幾個(gè)元素兩兩不排在一起可以用插空法來(lái)解決.

【例6】 已知9人站成一排，求其中甲與乙、丙都不相鄰的排法有多少種？

解：分兩種情況.（1）當(dāng)乙與丙不相鄰時(shí)，此時(shí)甲、乙、丙兩兩不相鄰，有A66A37種排法.（2）當(dāng)乙與丙相鄰時(shí)，有A66A27A22種排法.于是共有A66A37+A66A27A22=211680種排法.

【例7】 （1）某城市一條馬路上有12盞路燈，為了節(jié)約用電，須關(guān)掉其中3盞，但兩端路燈不能熄滅，也不能熄滅相鄰兩盞燈，則共有熄燈方法多少種？

（2）某人射擊8槍，命中4槍，這4槍中恰有3槍連在一起的有多少種不同的情況？

略解：（1）由插空法可得有C38=56種方法.

（2）由捆綁法和插空法可得有A25=20種不同的情況.

五、隔

將n個(gè)相同的元素分成m份，每份至少有一個(gè)元素，可以用m-1塊板插入n個(gè)元素排成一排的n-1個(gè)空隙中，不同分法總數(shù)為Cm-1n-1種（其中n，m均為正整數(shù)，且m≤n），這種方法叫隔板法.

【例8】 方程x1+x2+x3+…+x7=10有多少組正整數(shù)解？

解：把10分解成10個(gè)1，讓這10個(gè)1排成一排，然后取6塊板，插在10個(gè)1形成的9個(gè)空隙中的某6個(gè)空隙中（一個(gè)空隙內(nèi)只插入一塊板），這樣6塊板就把10個(gè)1分成了7個(gè)部分，每部分至少有一個(gè)1，從而每部分中1的個(gè)數(shù)依次序?qū)?duì)應(yīng)于原方程的一組正整數(shù)解.顯然一種插板方法對(duì)應(yīng)于原方程的一組正整數(shù)解，而插板方法有C69=84種，所以原方程就有84組正整數(shù)解.

評(píng)注：若求方程x1+x2+x3+…+x7=10有多少組自然數(shù)解，可先令yi=xi+1（i=1，2，3，4，5，6，7），然后對(duì)關(guān)于yi的方程用隔板法.

【例9】 （1）有10個(gè)運(yùn)動(dòng)員名額，分給5個(gè)班，每班至少一個(gè)，則有多少種分配方案？

（2）從6個(gè)學(xué)校中選出30名學(xué)生參加數(shù)學(xué)競(jìng)賽，每校至少有3人，這樣有幾種選法？

（3）某民航站共有1～4四個(gè)入口，每個(gè)入口處只能按次序一個(gè)人一個(gè)人地進(jìn)入，現(xiàn)在一個(gè)小組有4個(gè)人，那么進(jìn)站的方案數(shù)是多少種？

解：（1）不妨設(shè)這5個(gè)班為1～5班，各班分得的運(yùn)動(dòng)員的名額依次為xi（i=1，2，3，4，5且xi≥1），則有x1+x2+x3+x4+x5=10，利用隔板法得所求的分配方案有126種.

（2）每校先各選出2人，然后只需從6個(gè)學(xué)校中再選出18人且每校至少選1人.采用“隔板法”得答案為C517=6188.

（3）設(shè)四個(gè)入口為甲、乙、丙、丁，從這四個(gè)入口分別進(jìn)入的人數(shù)為xi（i=1，2，3，4且xi∈N），則有x1+x2+x3+x4=4，易知其有C37=35組自然數(shù)解，然后將四個(gè)人全排列有A44=24種方法，所以共有35×24=840種方案.

評(píng)注：對(duì)于相同元素的分配問(wèn)題，可考慮建立不定方程，再用隔板法求解.

六、化

在排列組合問(wèn)題中，會(huì)遇到許多背景新穎的問(wèn)題，若能善用“轉(zhuǎn)化”會(huì)有“神奇”效果.

【例10】 如圖3所示，某地有南北街道5條，東西街道6條，一郵遞員從該地東北角的郵局A出發(fā)，送信到西南角的B地，且途經(jīng)C地，要求所走路程最短，共有多少種不同的走法？

略解：從A到C走2條橫街、3條縱街的方法數(shù)，可轉(zhuǎn)化為從5條橫街中選3條橫街變成縱街的方法數(shù)，故有C35=10種；從C到B走2條橫街、2條縱街，類似地有C24=6種.故從A經(jīng)C到B一共有10×6=60種不同的走法.

【例11】 已知圓上有n個(gè)不同的點(diǎn)，過(guò)每?jī)蓚€(gè)點(diǎn)作一條直線，那么所有這些直線在圓內(nèi)的交點(diǎn)個(gè)數(shù)最多有多少個(gè)？

解：因?yàn)榭紤]最多交點(diǎn)個(gè)數(shù)，所以不妨設(shè)圓內(nèi)所有交點(diǎn)均不重合.由于任取不同4點(diǎn)可以連成一個(gè)四邊形，其對(duì)角線的交點(diǎn)就是符合題意的圓內(nèi)的一個(gè)交點(diǎn)；反之，符合題意的圓內(nèi)任意一個(gè)交點(diǎn)，必來(lái)自兩條直線的交點(diǎn)，或說(shuō)來(lái)自圓周上的4個(gè)點(diǎn).這樣“圓內(nèi)的一個(gè)交點(diǎn)”和“圓周上的4點(diǎn)組”是一一對(duì)應(yīng)的，故圓內(nèi)的交點(diǎn)個(gè)數(shù)就是圓周上的4點(diǎn)組的組數(shù).而圓周上的4點(diǎn)組的組數(shù)為C4n，所以圓內(nèi)的交點(diǎn)個(gè)數(shù)為C4n，即所求最多為C4n個(gè).

七、列

對(duì)于一些不易用公式求解，而且數(shù)據(jù)還比較小的排列組合問(wèn)題，用列舉法往往會(huì)收到意想不到的效果.

【例12】 已知A={a，b，c}，B={-1，0，1}，且f是從A到B的映射，若f（a）+f（b）=f（c），則不同的映射f最多有多少個(gè)？

略解：采用列舉法，有7種情況，故最多有7個(gè)不同的映射.

八、遞

排列組合中會(huì)碰到一類特殊的計(jì)數(shù)問(wèn)題，其復(fù)雜的情形常令人無(wú)從下手.此時(shí)跳出原有的范圍去思考一個(gè)比它更為一般的問(wèn)題，且一般的問(wèn)題比特殊的問(wèn)題更容易解決，這就是“特殊問(wèn)題一般化”的數(shù)學(xué)思想.利用“特殊問(wèn)題一般化”的數(shù)學(xué)思想，通過(guò)構(gòu)造數(shù)列將問(wèn)題一般化并建立遞推關(guān)系式，然后對(duì)遞推數(shù)列求解，就能達(dá)到對(duì)原問(wèn)題的求解的目的.

【例13】 用數(shù)字1或2排成10位數(shù)，要求數(shù)字1、1不相鄰，問(wèn)有多少種不同的排法？

解：設(shè)用數(shù)字1或2排成n位數(shù)，其中數(shù)字1、1不相鄰時(shí)有an種不同的排法，則a1=2，a2=3，且an=an-1+an-2（n≥3）.由此進(jìn)一步可得到{an}的前10項(xiàng)依次為：2，3，5，8，13，21，34，55，89，144，所以所求不同的排法有144種.

【例14】 在一個(gè)正六邊形（把過(guò)中心的三條對(duì)角線連起來(lái)）的六個(gè)區(qū)域內(nèi)栽種觀賞植物，要求同一區(qū)域中種同一種植物，相鄰的兩個(gè)區(qū)域種不同的植物，現(xiàn)有4種不同的植物可供選擇，則有多少種栽培方案？

解：設(shè)對(duì)正n邊形的n個(gè)區(qū)域栽種觀賞植物，符合題設(shè)要求的栽種方案共有an種，于是有an=4×3n-1-an-1（n≥3），∴an-3n=-（an-1-3n-1）.

易知a3=4×3×2=24，a3-33=-3≠0，所以數(shù)列{an-3n}是以-1為公比的等比數(shù)列，從而an-3n=-3×（-1）n-3，故an=3n+3×（-1）n（n≥3）.

令n=6，得a6=36+3×（-1）6=732.

九、較復(fù)雜的排列組合應(yīng)用題的例解與點(diǎn)評(píng)

以下選的是近年來(lái)的高中數(shù)學(xué)競(jìng)賽題，可以說(shuō)難度偏大，但解決它們所用的方法還是前面所討論的“十字法”.

【例15】 8個(gè)女孩和25個(gè)男孩圍成一圈，任意兩個(gè)女孩之間至少站兩個(gè)男孩，共有 種不同的排列方法.（旋轉(zhuǎn)一下就重合的排法認(rèn)為是相同的）

解：給8個(gè)女生編號(hào)為1，2，3，4，5，6，7，8，且不妨設(shè)1號(hào)女生的位置是固定的.下面分三步來(lái)排人.

第一步：先把除1號(hào)以外的7個(gè)女孩排好，共有7！種排法.

第二步：在1號(hào)女生的兩旁各排1個(gè)男生，有A225種排法，在2號(hào)女生的兩旁各排1個(gè)男生，有A223種排法，依號(hào)如此繼續(xù)，……，在8號(hào)女生的兩旁各排1個(gè)男生，有A211種排法.（此時(shí)已排好16個(gè)男生，還有9個(gè)男生沒(méi)排好）

第三步：把第二步中排好的1個(gè)女生及其兩旁的各1個(gè)男生共3人，利用捆綁法把他們捆成一個(gè)“大人”，這樣就有8個(gè)“大人”，下面將余下沒(méi)有排好的9個(gè)男生依次插進(jìn)8個(gè)“大人”留下的空隙中，有8×9×10×…×16種方法.

綜上所述，根據(jù)分步計(jì)數(shù)原理，所求的排法數(shù)為7！×A225×A223×A221×…×A211×8×9×10×…×16=16！×25！9！.

評(píng)注：本題中圍成的圈，最終把它分解成三步來(lái)排，這是解答本題的關(guān)鍵.解答中用到“乘”“捆”“插”等法.

【例16】 在世界杯足球賽前，F(xiàn)國(guó)教練為了考察A1，A2，A3，A4，A5，A6，A7這七名隊(duì)員，準(zhǔn)備讓他們?cè)谌龍?chǎng)訓(xùn)練比賽（每場(chǎng)90分鐘）中都上場(chǎng)，假設(shè)在比賽的任何時(shí)刻，這些隊(duì)員中有且僅有一人在場(chǎng)上，并且A1，A2，A3，A4每人上場(chǎng)的總時(shí)間（以分鐘為單位）均被7整除，A5，A6，A7每人上場(chǎng)的總時(shí)間（以分鐘為單位）均被13整除，如果每場(chǎng)換人次數(shù)不限，那么按每名隊(duì)員上場(chǎng)的總時(shí)間計(jì)算，共有多少種不同的情況？

解：設(shè)A1，A2，A3，A4，A5，A6，A7上場(chǎng)的時(shí)間分別為7x1，7x2，7x3，7x4，13x5，13x6，13x7（其中x1，x2，x3，x4，x5，x6，x7都為正整數(shù)）分鐘.

由于他們?cè)谌龍?chǎng)訓(xùn)練比賽（每場(chǎng)90分鐘）中都上場(chǎng)，且在比賽的任何時(shí)刻，這些隊(duì)員中有且僅有一人在場(chǎng)上，所以有7x1+7x2+7x3+7x4+13x5+13x6+13x7=270.

設(shè)x1+x2+x3+x4=m，x5+x6+x7=n，其中m，n∈N*，則有7m+13n=270，易得此方程只有三組正整數(shù)解：n=7，

n=17；m=20，

n=10；m=33，

n=3.

再利用隔板法知道，共有C36C216+C319C29+C332C22=42244種不同的情況.

評(píng)注：通過(guò)轉(zhuǎn)“化”法的運(yùn)用，將原問(wèn)題轉(zhuǎn)化成求一個(gè)不定方程所有的正整數(shù)解的問(wèn)題，進(jìn)而再轉(zhuǎn)“化”為三個(gè)不定方程組各自有多少組正整數(shù)解，這時(shí)利用“隔”板法可輕松獲得解決，最后再用一下分類計(jì)數(shù)原理“加”一下即可.

【例17】 在一次實(shí)戰(zhàn)軍事演習(xí)中，紅方的一條直線防線上設(shè)有20個(gè)崗位.為了試驗(yàn)5種不同新式武器，打算安排5個(gè)崗位配備這些新式武器，要求第一個(gè)和最后一個(gè)崗位不配備新式武器，且每相鄰5個(gè)崗位至少有一個(gè)崗位配備新式武器，相鄰兩個(gè)崗位不同時(shí)配備新式武器，問(wèn)共有多少種配備新式武器的方案？

解：設(shè)想20個(gè)崗位上一字形地排列著5種不同的新式武器和15個(gè)相同的空崗位，按照要求，圖4是符合題意的排法之一（其中▲表示相同的空崗位，☆表示不同的新式武器）.

▲▲☆▲▲ ▲☆▲▲▲ ☆▲▲▲☆ ▲▲▲☆▲

下面把☆換成隔板，這就相當(dāng)于用5塊隔板把15個(gè)空崗位分成6段的問(wèn)題.

設(shè)每段的空崗位數(shù)依次為xi（i=1，2，3，4，5，6），則x1+x2+x3+x4+x5+x6=15（其中1≤xi≤4，xi∈N），于是在15個(gè)空崗位形成的14個(gè)空隙中選取符合題意的5個(gè)空隙插入5塊隔板的方法數(shù)，就轉(zhuǎn)化為求方程x1+x2+x3+x4+x5+x6=15（其中1≤xi≤4，xi∈N）有多少組不同的解.因?yàn)楦郊訔l件1≤xi≤4，xi∈N的限制，需考察（x+x2+x3+x4）6展開(kāi)式中x15的系數(shù).利用二項(xiàng)式定理的知識(shí)容易求得（x+x2+x3+x4）6展開(kāi)式中x15的系數(shù)為580.又因?yàn)?種新式武器各不相同，互換位置得到不同的排列數(shù)，所以配備新式武器的方案數(shù)等于580×5！=69600種.

評(píng)注：通過(guò)“隔”板法的探路，結(jié)合轉(zhuǎn)“化”法的運(yùn)用，最后再用分步計(jì)數(shù)原理“乘”一下，便成功解出此題.當(dāng)然能否轉(zhuǎn)“化”到構(gòu)造多項(xiàng)式后利用二項(xiàng)式定理解題，這是問(wèn)題的另一個(gè)難點(diǎn).

（責(zé)任編輯 金 鈴）