例析求解排列組合問題的四個途徑

袁社軍

解答排列組合問題，需重點研究給定的元素在排列的過程中可能出現的情況的數量，需要考慮的情況比較多，很多同學在解題時得不到正確的答案.熟悉一些常用的解題途徑，有利于提高解答排列組合問題的效率.

一、利用插空法求解

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

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

解析：首先將沒有要求的4個女生排成一排，共有

種排法，

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

種排法，

根據分步計數原理可得，滿足要求的排法有

= 144種，

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

二、利用隔板法求解

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

種分法.

例2.已知有7個相同的小球，現將它們任意放入4個不同的盒子中，則每一個盒子都至少有1個小球的放法有____種.

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

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

=20種插法.

運用隔板法解題的關鍵是確定隔板和空隙的個數.

三、利用間接法求解

有些問題如果從正面分析，要討論的情況較多或者較為復雜，此時我們可以運用間接法來求解，從問題的對立面來進行分析，著重分析其對立事件，這樣可以簡化解題的過程，優化解題的方案.

例3.某班級為晚會準備了6個不同類型的節目，為節目效果考慮，要求小品節目不排在第一個和最后一個，跳舞節目和唱歌節目必須排在一起，則該晚會節目的表演順序有____種.

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

=240種排法，

若小品節目排在第一個和最后一個，則有

= 96種排法，

所以該晚會的節目表演順序共有240 - 96= 144種排法.

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

四、利用優先法求解

優先法常用于求解有特殊要求的排列組合問題.在解題時，要首先對特殊的元素、位置進行分析，求出所有滿足條件的可能，然后在滿足特殊要求的情況下求出排列組合的可能個數，進而求出問題的答案.

例4.已知生產過程含有4道工序，每道工序都需要安排1人進行質檢，現從6人中選取4人對每道工序進行檢驗，若第1道工序只能由甲或乙負責，第4道工序只能由甲或丙執行，則不同安排的方案共有____種.

解：分兩種情況進行討論：

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

種方案，再從剩余的個4人中任意選取2個人安排到剩余的2道工序中，有

種方案.因此共有

= 24種方案，

②若甲不在第1道工序也不在第4道工序中，則第1道工序只能安排乙、第4道工序只能安排丙，再從剩余的4個人中任意選取2個人安排到剩余的2道工序中，有

種方案.所以共有方案

=12種;

綜上，滿足要求的方案有

+

= 36種.

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

通過上述分析，同學們對解答排列組合問題的這四個途徑有了基本的了解.可以看出，這四個途徑適用的條件各不相同.插空法適用于解答相鄰問題，隔板法適用于解答元素相同的問題，間接法適用于解答反面情況較少的問題，特殊優先法適用于求解有特殊要求的問題.因此，在解題時，同學們要注意分辨問題的模型，然后選擇合適的途徑來解題.

（作者單位：安徽省無為市第二中學）