解排列組合題的若干技巧

王承超　向清耀

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

運用兩個基本原理

加法原理和乘法原理是解排列組合應用題最基本的出發點，可以說對每道應用題我們都要考慮在計數的時候進行分類或分步處理.

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

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

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

答案 72

特殊元素（位置）優先

特殊元素優先考慮，特殊位置優先考慮.

例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]種放法.

捆綁法

對于相同類別不可分開的，要先進行捆綁.

例3 計劃在一畫廊展出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

插空法

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

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

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

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

排除法

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

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

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

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

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

答案 B

多元分類法

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

例6 有甲、乙、丙三項任務，甲需2人承擔，乙、丙各需1人承擔，從10人中選派4人承擔這三項任務，不同的選法共有（ ）

A. 1260種 B. 2025種

C. 2520種 D. 5040種

分析 先依次選出甲、乙、丙承擔的人數，再根據根據乘法原理計算總人數.

解 先從10人中選出2人承擔甲項任務，有[C210]種選法，再從余下的8人中選1人承擔乙項任務，有8種；最后從7人中選1人承擔丙項任務，有7種. 所以根據乘法原理知共有[C210×8×7=2520]種.

答案 C

先取后排法

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

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

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

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

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

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

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

隔板法

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

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

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

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

轉化法

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

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

分析 名額分配問題通常轉化為平時熟悉的隔板法.

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

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

分析 問題轉化為先捆后排.

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