例析求解排列组合问题的四个途径

袁社军

解答排列组合问题，需重点研究给定的元素在排列的过程中可能出现的情况的数量，需要考虑的情况比较多，很多同学在解题时得不到正确的答案.熟悉一些常用的解题途径，有利于提高解答排列组合问题的效率.

一、利用插空法求解

对于要求元素不相邻的排列组合问题，我们一般优先考虑插空法，即先排列没有要求的元素然后把要求不相邻的元素插入其他元素的间隔中或者首尾的位置.若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道工序上的检验员，最后根据分类计数原理求得结果.

通过上述分析，同学们对解答排列组合问题的这四个途径有了基本的了解.可以看出，这四个途径适用的条件各不相同.插空法适用于解答相邻问题，隔板法适用于解答元素相同的问题，间接法适用于解答反面情况较少的问题，特殊优先法适用于求解有特殊要求的问题.因此，在解题时，同学们要注意分辨问题的模型，然后选择合适的途径来解题.

（作者单位：安徽省无为市第二中学）