解排列組合題的若干技巧

王承超　向清耀

排列組合問(wèn)題的解題方法既有一般的規(guī)律，又有很多特別的技巧. 它要求我們認(rèn)真地審題，對(duì)題目中的信息進(jìn)行科學(xué)地加工處理，下面通過(guò)一些例題來(lái)說(shuō)明幾種常見(jiàn)的解法.

運(yùn)用兩個(gè)基本原理

加法原理和乘法原理是解排列組合應(yīng)用題最基本的出發(fā)點(diǎn)，可以說(shuō)對(duì)每道應(yīng)用題我們都要考慮在計(jì)數(shù)的時(shí)候進(jìn)行分類或分步處理.

例1 如右圖，一個(gè)地區(qū)分為5個(gè)行政區(qū)域，現(xiàn)給地圖著色，要求相鄰區(qū)域不得使用同一顏色，現(xiàn)有4種顏色可供選擇，則不同著色方法共有 種.（以數(shù)字作答）.

分析 本題只要用兩個(gè)基本原理即可解決.

解 根據(jù)題意，可分類求解：第一類，用三種顏色著色，由乘法原理[C14C41C12=24]種方法；第二類，用四種顏色著色，由乘法原理有[2C14C41C12C11=48]種方法. 再由加法原理得，24+48=72種方法.

答案 72

特殊元素（位置）優(yōu)先

特殊元素優(yōu)先考慮，特殊位置優(yōu)先考慮.

例2 從[a，b，c，d，e]這5個(gè)元素中，取出4個(gè)放在四個(gè)不同的格子中，且元素[b]不能放在第二個(gè)格子中，問(wèn)共有多少種不同的放法？

分析 若從特殊元素考慮可以先排[b]，若從特殊位置考慮先排第二格.

解 法一：（元素分析法，[b]為特殊元素）先排[b]，但考慮到取出的4個(gè)元素可以有[b]，也可以沒(méi)有[b]，所以分兩類. 第一類，取出的4個(gè)元素中有[b]，則排[b]有[A13]種方法；再?gòu)腫a，c，d，e]中取出3個(gè)排另外三個(gè)格子有[A34]種，所以此類共有[A13?A34]種. 第二類，取出的4個(gè)元素中沒(méi)有[b]，則有[A44]種方法. 所以共有[A13?A34+A44=96]種放法.

法二：（位置分析法，第二格為特殊位置）先排第二格，有[A14]種（從[a，c，d，e]中取一個(gè)）；再排另外三格有[A34]種，所以共有[A14?A34=96]種放法.

捆綁法

對(duì)于相同類別不可分開的，要先進(jìn)行捆綁.

例3 計(jì)劃在一畫廊展出10幅不同的畫，其中1幅水彩畫，4幅油畫，5幅國(guó)畫，排成一行陳列. 要求同一品種的畫必須排一起，并且水彩畫不放在兩端，那么不同的陳列方式有（ ）

A. [A44?A55] B. [A33?A44?A55]

C. [C13?A44?A55] D. [A22?A44?A55]

分析 先捆綁，然后再看其他限制條件.

解 油畫整體、國(guó)畫整體、水彩畫按“元素”先排，考慮到水彩畫不能排兩端，所以有[A22]種方法. 又4幅油畫的不同陳列方式有[A44]種，5幅國(guó)畫陳列方式有[A55]種. 因而，畫展的不同陳列方式有[A22?A44?A55]種.

答案 D

插空法

解決某幾個(gè)元素要求不相鄰的問(wèn)題時(shí)，先將其他元素排好，再將指定的不相鄰的元素插入已排好元素的間隙和兩端位置，從而將問(wèn)題解決.

例4 道路邊上有編號(hào)為1，2，3，4，5，6，7，8，9，10的10盞路燈，現(xiàn)要關(guān)掉其中的3盞，但不能關(guān)掉相鄰的2盞或3盞，也不能關(guān)兩端的路燈，則滿足要求的關(guān)燈方法有幾種？

分析 在[n]個(gè)元素間的[n-1]個(gè)空中插入若干個(gè)板，共有[Cbn-1]種方法.

解 由于問(wèn)題中有7盞亮3盞暗，又兩端不能暗，問(wèn)題等價(jià)于：在7盞開著的路燈的6個(gè)間隔中，選出3個(gè)間隔各插入3只關(guān)掉的路燈，所以關(guān)燈的方法共有[C36=20]種.

排除法

在直接法考慮比較難或分類不清或多種時(shí)，可考慮用排除法.

例5 從正方體的6個(gè)面中選取3個(gè)面，其中有2個(gè)面不相鄰的選法共有（ ）

A. 8種 B. 12種 C. 16種 D. 20種

分析 解決幾何問(wèn)題必須注意幾何圖形本身對(duì)其構(gòu)成元素的限制.

解 六個(gè)面中任取三個(gè)共有[C36=20]種，排除掉3個(gè)面都相鄰的種數(shù)，即8個(gè)角上3個(gè)平面相鄰的特殊情形共8種，故符合條件的共有[C36-8=12]種.

答案 B

多元分類法

對(duì)于元素多、選取情況多的，可按要求進(jìn)行分類討論，最后總計(jì).

例6 有甲、乙、丙三項(xiàng)任務(wù)，甲需2人承擔(dān)，乙、丙各需1人承擔(dān)，從10人中選派4人承擔(dān)這三項(xiàng)任務(wù)，不同的選法共有（ ）

A. 1260種 B. 2025種

C. 2520種 D. 5040種

分析 先依次選出甲、乙、丙承擔(dān)的人數(shù)，再根據(jù)根據(jù)乘法原理計(jì)算總?cè)藬?shù).

解 先從10人中選出2人承擔(dān)甲項(xiàng)任務(wù)，有[C210]種選法，再?gòu)挠嘞碌?人中選1人承擔(dān)乙項(xiàng)任務(wù)，有8種；最后從7人中選1人承擔(dān)丙項(xiàng)任務(wù)，有7種. 所以根據(jù)乘法原理知共有[C210×8×7=2520]種.

答案 C

先取后排法

從幾類元素中取出符合題意的幾個(gè)元素，再安排到一定位置上，可用先取后排法.

例7 有5個(gè)男生和3個(gè)女生，從中選5個(gè)擔(dān)任5門學(xué)科代表，求符合下列條件的選法數(shù). （1）有女生但人數(shù)少于男生. （2）某女生一定要擔(dān)任語(yǔ)文科代表. （3）某男生必須在內(nèi)，但不擔(dān)任數(shù)學(xué)科代表. （4）某女生一定要擔(dān)任語(yǔ)文科代表，某男生必須擔(dān)任科代表，但不是數(shù)學(xué)科代表.

分析 比較復(fù)雜的排列組合混合問(wèn)題，一般要遵循先取后排的原則.

解 （1）可分為1女4男和2女3男，共計(jì)不同的選法種數(shù)為[C13?C45+C23?C35=45]，任科代表種數(shù)為[（C13?C45][+C23?C35）A55]=5400.

（2）某女生一定要擔(dān)任語(yǔ)文科代表，余4門科代表從余下的7人中任選有[A47=840]種.

（3）某男生從除數(shù)學(xué)外四科中任選一科代表有[C14]，余4科從余下的7人中任選有[A47，]共有不同種數(shù)為[C14?A47=3360].

（4）某女生任語(yǔ)文科代表，某男生從余下3種（數(shù)學(xué)除外）中任選一科有[C13]種，余3科代表由余下6人中選任，共計(jì)不同安排總數(shù)為[C13?A36=360]種.

隔板法

排列組合中對(duì)于不可分辨的球裝入到可以分辨的盒子中而求裝入的方法數(shù)的問(wèn)題，通常用隔板法.

例8 將20個(gè)相同的球分放在三個(gè)盒中，不允許有盒不放球，有多少種分法？

分析 由兩個(gè)隔板將20個(gè)球分成三個(gè)部分.

解 將20個(gè)球排成一排，一共有19個(gè)空隙，將兩個(gè)隔板插入這些空隙中，規(guī)定由隔板分成的左、中、右三部分球分別放在三個(gè)盒中，則每一種隔法對(duì)應(yīng)了一種分法，于是分法的總數(shù)為[C219=171]種方法.

轉(zhuǎn)化法

將陌生、復(fù)雜的問(wèn)題轉(zhuǎn)化為熟悉、簡(jiǎn)單的問(wèn)題也是解決排列組合較難問(wèn)題的重要策略.

例9 將組成籃球隊(duì)的12個(gè)名額分給7所學(xué)校，每校至少1個(gè)名額，問(wèn)名額分配的方法共有多少種？

分析 名額分配問(wèn)題通常轉(zhuǎn)化為平時(shí)熟悉的隔板法.

解 問(wèn)題等價(jià)于將排成一行的12個(gè)相同元素分成7份的方法數(shù)，相當(dāng)于用6塊隔板插在11個(gè)間隔中，共有[C611=462]種不同的方法.

例10 10級(jí)樓梯，要求7步跨完，且每步最多跨2級(jí)，問(wèn)有幾種不同跨法？

分析 問(wèn)題轉(zhuǎn)化為先捆后排.

解 由題意知要有4步單級(jí)、3步雙級(jí)，因此，這是兩類不同元素的排列，問(wèn)題等價(jià)于只要在7步中任意選3步雙級(jí)即可. 故[C37=35]種.