王承超　向清耀

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

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

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

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

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

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

答案 72

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

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

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

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

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

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

捆綁法

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

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

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

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

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

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

答案 D

插空法

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

例4 道路邊上有編號為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]個元素間的[n-1]個空中插入若干個板，共有[Cbn-1]種方法.

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

排除法

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

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

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

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

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

答案 B

多元分類法

對于元素多、選取情況多的，可按要求進(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]種選法，再從余下的8人中選1人承擔(dān)乙項(xiàng)任務(wù)，有8種；最后從7人中選1人承擔(dān)丙項(xiàng)任務(wù)，有7種. 所以根據(jù)乘法原理知共有[C210×8×7=2520]種.

答案 C

先取后排法

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

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

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

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

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

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

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

隔板法

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

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

分析 由兩個隔板將20個球分成三個部分.

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

轉(zhuǎn)化法

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

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

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

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

例10 10級樓梯，要求7步跨完，且每步最多跨2級，問有幾種不同跨法？

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

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