例析求解排列組合問(wèn)題的四個(gè)途徑

袁社軍

解答排列組合問(wèn)題，需重點(diǎn)研究給定的元素在排列的過(guò)程中可能出現(xiàn)的情況的數(shù)量，需要考慮的情況比較多，很多同學(xué)在解題時(shí)得不到正確的答案.熟悉一些常用的解題途徑，有利于提高解答排列組合問(wèn)題的效率.

一、利用插空法求解

對(duì)于要求元素不相鄰的排列組合問(wèn)題，我們一般優(yōu)先考慮插空法，即先排列沒(méi)有要求的元素然后把要求不相鄰的元素插入其他元素的間隔中或者首尾的位置.若m個(gè)元素中有n個(gè)不相鄰的元素，需首先排列其他沒(méi)有要求的m-n個(gè)元素，再把這n個(gè)元素隨機(jī)插入m-n+1個(gè)間隔中，即可求得問(wèn)題的答案.

例1.將2個(gè)男生和4個(gè)女生排成一排，要求男生既不相鄰，也不站在隊(duì)伍的兩端，則共有____種排法.

解析：首先將沒(méi)有要求的4個(gè)女生排成一排，共有

種排法，

然后把2個(gè)男生插入4個(gè)女生中間的3個(gè)空中，共有

種排法，

根據(jù)分步計(jì)數(shù)原理可得，滿足要求的排法有

= 144種，

運(yùn)用插空法解題主要分三步，首先對(duì)沒(méi)有特殊要求的元素進(jìn)行排列，再把不相鄰的元素插入其他元素的空隔中，最后運(yùn)用乘法原理得出結(jié)果.

二、利用隔板法求解

有些問(wèn)題中的元素是相同的，沒(méi)有任何區(qū)別，對(duì)于這樣的問(wèn)題，我們一般采用隔板法來(lái)求解.若把n個(gè)相同元素分成m份（m、n均為正整數(shù)），要求每份至少含有1個(gè)元素，就可以把m-1塊隔板插進(jìn)n-l個(gè)空隙巾，這樣就有

種分法.

例2.已知有7個(gè)相同的小球，現(xiàn)將它們?nèi)我夥湃?個(gè)不同的盒子中，則每一個(gè)盒子都至少有1個(gè)小球的放法有____種.

解析：每2個(gè)球之間都有1個(gè)空，則7個(gè)小球中有6個(gè)空.

把7個(gè)小球分成4份，只需在6個(gè)空中任選3個(gè)插入隔板，共有

=20種插法.

運(yùn)用隔板法解題的關(guān)鍵是確定隔板和空隙的個(gè)數(shù).

三、利用間接法求解

有些問(wèn)題如果從正面分析，要討論的情況較多或者較為復(fù)雜，此時(shí)我們可以運(yùn)用間接法來(lái)求解，從問(wèn)題的對(duì)立面來(lái)進(jìn)行分析，著重分析其對(duì)立事件，這樣可以簡(jiǎn)化解題的過(guò)程，優(yōu)化解題的方案.

例3.某班級(jí)為晚會(huì)準(zhǔn)備了6個(gè)不同類(lèi)型的節(jié)目，為節(jié)目效果考慮，要求小品節(jié)目不排在第一個(gè)和最后一個(gè)，跳舞節(jié)目和唱歌節(jié)目必須排在一起，則該晚會(huì)節(jié)目的表演順序有____種.

解：若跳舞節(jié)目和唱歌節(jié)目必須排在一起，則共有

=240種排法，

若小品節(jié)目排在第一個(gè)和最后一個(gè)，則有

= 96種排法，

所以該晚會(huì)的節(jié)目表演順序共有240 - 96= 144種排法.

該問(wèn)題若從正面進(jìn)行考慮，要分析的情況較多，采用間接法解答較為簡(jiǎn)便.將總的節(jié)目表演順序數(shù)目減去不滿足要求的數(shù)目，便得到了滿足要求的節(jié)目表演順序數(shù)目.這樣避免了分情況難以討論清楚的問(wèn)題，有效地提升了解題的效率.

四、利用優(yōu)先法求解

優(yōu)先法常用于求解有特殊要求的排列組合問(wèn)題.在解題時(shí)，要首先對(duì)特殊的元素、位置進(jìn)行分析，求出所有滿足條件的可能，然后在滿足特殊要求的情況下求出排列組合的可能個(gè)數(shù)，進(jìn)而求出問(wèn)題的答案.

例4.已知生產(chǎn)過(guò)程含有4道工序，每道工序都需要安排1人進(jìn)行質(zhì)檢，現(xiàn)從6人中選取4人對(duì)每道工序進(jìn)行檢驗(yàn)，若第1道工序只能由甲或乙負(fù)責(zé)，第4道工序只能由甲或丙執(zhí)行，則不同安排的方案共有____種.

解：分兩種情況進(jìn)行討論：

①若甲在第1道工序或第4道工序中，則第1道工序或第4道工序有

種方案，再?gòu)氖Ｓ嗟膫€(gè)4人中任意選取2個(gè)人安排到剩余的2道工序中，有

種方案.因此共有

= 24種方案，

②若甲不在第1道工序也不在第4道工序中，則第1道工序只能安排乙、第4道工序只能安排丙，再?gòu)氖Ｓ嗟?個(gè)人中任意選取2個(gè)人安排到剩余的2道工序中，有

種方案.所以共有方案

=12種;

綜上，滿足要求的方案有

+

= 36種.

本題較為復(fù)雜，有特殊要求的元素、位置較多，需首先利用分類(lèi)討論思想，對(duì)甲的位置進(jìn)行討論，然后逐步安排第1道工序、第4道工序以及第2、3道工序上的檢驗(yàn)員，最后根據(jù)分類(lèi)計(jì)數(shù)原理求得結(jié)果.

通過(guò)上述分析，同學(xué)們對(duì)解答排列組合問(wèn)題的這四個(gè)途徑有了基本的了解.可以看出，這四個(gè)途徑適用的條件各不相同.插空法適用于解答相鄰問(wèn)題，隔板法適用于解答元素相同的問(wèn)題，間接法適用于解答反面情況較少的問(wèn)題，特殊優(yōu)先法適用于求解有特殊要求的問(wèn)題.因此，在解題時(shí)，同學(xué)們要注意分辨問(wèn)題的模型，然后選擇合適的途徑來(lái)解題.

（作者單位：安徽省無(wú)為市第二中學(xué)）