怎樣求解排列組合問題

卞伶雅

排列組合問題常以填空題或選擇題的形式出現(xiàn)在各類試題中，通常要求一些元素的排列數(shù)．這類問題的難度不大，卻是出錯(cuò)率較高的一類題目．本文重點(diǎn)談一談求解排列組合問題的幾種常用方法，

一、插空法

例2.一條長(zhǎng)街上原有6個(gè)路燈，假設(shè)保持這幾個(gè)路燈的相對(duì)順序不變，再多安裝3個(gè)路燈，則一共有多少種不同的安裝方法？

分析：要保持原來的6個(gè)路燈的相對(duì)順序不變，就需采用插空法求解．原來6個(gè)路燈的中間空隙和兩端共有7個(gè)空位，先將一個(gè)路燈插入，那么此時(shí)7個(gè)路燈的中間空隙和兩端共有8個(gè)空位，再插入第二個(gè)路燈，那么此時(shí)8個(gè)路燈的中間空隙和兩端共有9個(gè)空位，將最后一個(gè)路燈插入，最后利用乘法計(jì)數(shù)原理求解即可，

解：原來6個(gè)路燈的中間空隙和兩端共有7個(gè)空位，將其中一個(gè)路燈插入這些空位中，則A; =7種方法；7個(gè)路燈的中間空隙和兩端共有8個(gè)空位，再插入第二個(gè)路燈，有A1=8種方法；8個(gè)路燈的中間空隙和兩端共有9個(gè)空位，將最后一個(gè)路燈插入，有A 1=8種方法，由乘法計(jì)數(shù)原理可得，共有A7．A8．A9=504種不同的安裝方法．

二、隔板法

隔板法適用于求解一些相同元素的分組問題，若要將n個(gè)相同的元素分成m組．需將m-1個(gè)板插入n個(gè)元素之間的n-l空隙中，使其分為m組，則共有C- 1種分法．

例3．將7個(gè)相同的小球放人4個(gè)不同的盒子中，則每一個(gè)盒子至少有1個(gè)小球的放法有____種，

分析：7個(gè)小球相同，要將其放入4個(gè)不同的盒子中，只需采用隔板法，在7個(gè)小球之間的6個(gè)空位中隨意插入3塊隔板，將小球分成4組，再將其放入4個(gè)盒子中即可．

解：7個(gè)小球之間有6個(gè)空位，將3個(gè)隔板插入，便把7個(gè)小球分成4份，有C6= 20種分法，故使每個(gè)盒子至少有1個(gè)小球的不同分法共有20種，

例4．體育老師將10個(gè)完全相同的籃球分給7個(gè)小組，要使每個(gè)小組至少有1個(gè)籃球，則一共有多少種分配方案？

分析：10個(gè)籃球完全相同，要將其分給7個(gè)小組，需采用隔板法，將10個(gè)籃球排成一排，在籃球之間的空隙中插入6塊隔板，就能將籃球分為7份，且使每一份中至少有一個(gè)籃球．

解：將10個(gè)籃球排成一排，那么在籃球之間形成9個(gè)空隙中，插入6塊隔板，就將籃球分為7份，有C6=84種分法，所以一共有84種分配方案．

三、優(yōu)先法

優(yōu)先法適用于求解某個(gè)或某些元素有特殊要求的排列組合問題，優(yōu)先法有兩種：特殊位置優(yōu)先法和特殊元素優(yōu)先法，采用優(yōu)先法解題，要先明確哪些元素或位置有特殊要求，然后優(yōu)先對(duì)特殊元素、位置進(jìn)行排列，最后再安排沒有特殊要求的元素的排列順序，

例5．從6人中選取4人對(duì)每道生產(chǎn)程序進(jìn)行檢驗(yàn)，若第1道生產(chǎn)程序只能由甲、乙兩人完成，第4道生產(chǎn)程序只能由甲、丙兩人完成，則共有____種不同安排的方案，

分析：?jiǎn)栴}對(duì)甲、乙、丙都有特殊要求，其中甲的情況較為復(fù)雜，需分三種情況：（1）檢驗(yàn)第1道生產(chǎn)程序；（2）檢驗(yàn)第4道生產(chǎn)程序；（3）既不檢驗(yàn)第1道生產(chǎn)程序，也不檢驗(yàn)第4道生產(chǎn)程序．分別求得各種情況下的安排方法數(shù)，再根據(jù)分類計(jì)數(shù)原理和分布計(jì)數(shù)原理進(jìn)行求解。

解：分三種情況：

①甲檢驗(yàn)第1道生產(chǎn)程序，那么丙必須檢驗(yàn)第4道生產(chǎn)程序，從剩余的4人中任意挑選2人檢驗(yàn)第二、三道生產(chǎn)程序，有A4種安排方案；

②甲檢驗(yàn)第4道生產(chǎn)程序，那么乙必須檢驗(yàn)第1道生產(chǎn)程序，從剩余的4人中任意挑選2人檢驗(yàn)第二、三道生產(chǎn)程序，有A4種安排方案；

③甲既不檢驗(yàn)第1道生產(chǎn)程序，也不檢驗(yàn)第4道生產(chǎn)程序，則乙檢驗(yàn)第1道生產(chǎn)程序，丙檢驗(yàn)第4道生產(chǎn)程序，從其余的4人中任意挑選2人檢驗(yàn)第二、三道生產(chǎn)程序，有A2種安排方案；

綜上所述，共有A4+A4+A4=36種安排方案，

例6．將紅色、橙色、黃色、綠色、藍(lán)色、紫色6個(gè)小球排成一列，要求紅色的小球不能放在兩端，一共有多少種不同的排法？

分析：本題中紅色小球的位置有特殊，需采用優(yōu)先法求解，有兩種思路：（1）可優(yōu)先考慮特殊元素；（2）可優(yōu)先考慮特殊位置．

解法1：特殊位置優(yōu)先法，

因?yàn)榧t色的小球不能放在兩端，所以從剩下的5個(gè)小球中任意挑選2個(gè)放在兩端，有A；種排法；再將剩下的4個(gè)小球安排在中間的4個(gè)位置上，有A4種排法，所以一共有A5．A4= 480種排法，

解法2：特殊元素優(yōu)先法．

因?yàn)榧t色的小球不能放在兩端，所以先將紅色的小球安排在中間的4個(gè)位置上，有A：種排法；剩下的5個(gè)小球就可以隨意安排，有Ai種排法，所以一共有A IA5_480種排法．

例7．某單位安排甲、乙、丙、丁4名工作人員從周一到周五值班，每天有且只有1人值班，每人至少安排一天且甲連續(xù)兩天值班，則不同的安排方法種數(shù)為（ ）．

A.18

B.24

C.48

D.96

解：甲連續(xù)兩天值班，共有（周一，周二），（周二，周三），（周三，周四），（周四，周五）四種情況，剩下三個(gè)人進(jìn)行全排列，有A；=6種排法，因此共有4x6=24種排法，故選B．

本題中，甲為特殊元素，需采用優(yōu)先法，先安排甲的值班時(shí)間，然后再考慮其他沒有要求的人的值班時(shí)間．用優(yōu)先法解答排列組合問題，往往要靈活運(yùn)用分步計(jì)數(shù)原理．

四、倍縮法

對(duì)于要求某些元素必須保持一定順序的問題，即元素定序問題，可以利用倍縮法求解，運(yùn)用倍縮法解題，需先求出所有元素的全排列數(shù)，然后求出必須保持一定順序的元素的排列數(shù)，再將二者相除即可．做除法的目的是為了消序．

例8．將7顆棋子排成一列，要求甲、乙、丙3顆棋子的順序保持不變，則一共有多少種不同的排法？

分析：本題中甲、乙、丙3顆棋子的順序固定不變，屬于元素定序問題，需采用倍縮法求解．分別求得所有元素的排列數(shù)和甲、乙、丙3顆棋子的排列數(shù)，然后做除法即可．

解：7顆棋子的全排列，有A7種排法；

甲、乙、丙3顆棋子全排列，有A3種排法，

因此，一共有 = 840種排法，

例9.10個(gè)小朋友一起拍照，要求小紅、小藍(lán)和小剛3人的排列順序不變，則一共有多少種站法？

分析：小紅、小藍(lán)和小剛的排列順序固定，需采用倍縮法，分別求出10個(gè)小朋友全排列數(shù)以及小紅、小藍(lán)、小剛3人的全排列數(shù)，再做除法．

解：10個(gè)小朋友排列，有A10種站法；

小紅、小藍(lán)和小剛3人一起排列，有A3種站法；

則共有A10= 604800種站法，

通過上述分析，同學(xué)們應(yīng)對(duì)排列組合問題及其四種解題方法有了更深入的了解．插空法、隔板法、優(yōu)先法、倍縮法都是解答排列組合問題的有效方法，但每種方法的適用情形不同．同學(xué)們?cè)诮忸}時(shí)，要注意審題，尤其要關(guān)注一些關(guān)鍵字眼，如相鄰、不相鄰、相同元素、不同元素、順序固定，以及對(duì)某些的元素、位置的特殊要求，再選擇與之相應(yīng)的方法進(jìn)行求解．

（作者單位：江蘇省溧陽市溧陽中學(xué)）