如何有效解决排列组合问题

如何有效解决排列组合问题

徐海峰

关键词：观察；本质；排列组合

作者简介：徐海峰，任教于湖北省云梦县第一中学。

解决排列组合问题，首先要认真审题，弄清楚要完成的是一件什么事，属于排列还是组合，还是排列与组合混合问题。其次，要抓住问题的本质特征，正确合理地利用两个计数原理，进行分类或分步。分类计数原理的特征是分类解决问题，分类必须满足两个条件：（1）类与类必须互斥（保证不重复）（2）总类必须完备（保证不漏）。分步计数原理的特征是分步解决问题，分步也必须满足两个条件：（1）步与步互相独立互不干扰；（2）总步确保连续性。分类与分步是解决排列组合问题最基本的思想策略，在实际操作中，往往是“步”“类”交叉，有机结合。

一、合理分类，准确分步

解含有约束条件的排列组合问题，应按元素性质进行分类，按事情发生的连续过程分步，作到分类标准明确，分步层次清楚，不重不漏。

例1：五个人排成一排，其中甲不在排头，乙不在排尾，不同的排法有多少种？

分析：由题意可先安排甲，并按其分类讨论：（1）若甲在末尾，剩下四人可自由排，有种排法；（2）若甲在第二，三，四位上，则有种排法；第二步安排乙也有种排法；第三步安排其余三人共有种排法，由分步计数原理可得共有种排法。由分类计数原理，共有种排法。

二、注意转化，化难为易

对于一些生疏问题或直接求解较为复杂、困难的问题，从正面入手情况复杂，不易解决，这时可以从反面入手，将其转化为一个简单问题来处理。

例2马路上有8盏路灯，为节约用电又不影响正常的照明，可把其中的三盏灯关掉，但不能同时关掉相邻的两盏或三盏，也不能关掉两端的灯，那么满足条件的关灯方法共有多少种？

分析：关掉第一盏灯的方法有6种，关第二盏，第三盏时需分类讨论，十分复杂。若从反面入手考虑，每一种关灯的方法对应着一种满足题设条件的亮灯与关灯的排列，于是问题转化为“在5盏亮灯的4个空中插入3盏暗灯”的问题，故关灯的方法种数为=4种。

三、“优先”对待，灵活掌握

对于问题中的特殊元素或特殊位置要优先安排，在操作时针对实际问题，有时元素优先，有时位置优先，需灵活掌握，简便为主。

例3从6名运动员中选4名参加米接力赛，若其中甲乙两人都不跑第三棒，共有多少种参赛方案？

分析：这是一个选排列问题，应位置优先。第一步谁跑第三棒有种方法；第二步从剩下的5人中选3人跑其余三棒，有种方法，根据分步计数原理，共有种不同的参赛方案。

四、“捆绑”分析，巧解问题

对于某些元素要求相邻排列，或要求分在一组中可以用“捆绑法”，当作一个元素与其他元素一起考虑，就很容易解决问题。捆绑在一起的元素，若是排列问题，还需“松绑”。

例45个男生3个女生排成一列，要求女生排在一起，共有几种排法？

分析：先把3个女生捆绑为一，与其他5个男生全排有种排法，同时，3个女生自身全排有种排法，有分步计数原理得共有种不同的排法。

例54名男歌手与2名女歌手联合举行一场演唱会，演出的出场顺序要求2名女歌手之间恰有2名男歌手，则出场方案有几种？

分析：这是一个全排列问题。2名女歌手和他们之间的2名男歌手组团为一，6名歌手转化成3名歌手的排列问题，有种排法；而2名女歌手有种排法，她们之间2名男歌手是从4名男歌手中选出的两名，有种选法。根据分步计数原理，共有种出场方案。

五、元素间隔，分位插入

对于某些元素，要求有间隔的排列用插入法。用插入法要注意三点：（1）插入时必须分清谁插入谁的问题，要先排无限制条件的元素，后插入必须间隔的元素；（2）数清可插入的位置数；（3）插入时是以组合的形式插入还是排列形式插入，要把握准确。

例65个男生和3个女生排成一排，要求女生不相邻，且不可排两头，共有多少种排法？

分析：第一步先排5名男生，有种排法；第二步在5名男生之间的四个间隙中插入3名女生，有种插法，根据分步计数原理，共有种排法。

六、元素定序，可不考虑

例7晚会上有5个不同的歌唱节目和3个不同的舞蹈节目，如果3个舞蹈顺序一定，那么可排除几种不同的节目单？

分析：由于3个舞蹈节目顺序一定，因此只需考虑5个歌唱节目的排列即可，一共可排出6720种不同的节目单。

七、排组混合，先选后排

例8从1、2、3、4、…8、9这九个数字中选出3个奇数2个偶数，可组成多少个没有重复数字的五位数？

分析：从1、3、5、7、9中选3个奇数，有种选法，从2、4、6、8中选2个偶数有种选法，再把这三个奇数和两个偶数进行排列，有种排法，根据分布计数原理，共可组成7200个没有重复数字的五位数。

八、分排问题，直排处理

若n个元素要分m排排列，可把每排首尾相连排成一列，对于每排的特殊要求只要分段考虑特殊元素，然后对其余元素作统一排列。

例92个老师，四个女生，12个男生，排成三排照相，要求第一排5人，第二排6人，第三排7人，且老师在第一排，女生在第二排，共有几种不同的排法？

分析：先把5+6+7共18个位置摆成一排，自左至右5个位，6个位，7个位三段，先在左边的5个位中排入2个老师有种排法，再在中段的6个人中插入4个女生有种排法，然后再其余位置上全排12个男生有种排法，由分步计数原理，共有种排法。

九、档板分隔，创设情景

较复杂的排列问题，可通过设计另一种情景，构造一个隔板模型来解决问题。

例10把10本相同的书发给编号为1、2、3的三个学生阅览室，每个阅览室分得的书的本数不小于其编号数，试求不同分法的种数。

分析：先让2、3号阅览室依次分得1本书、2本书；再对余下的7本书进行分配，保证每个阅览室至少得一本书，这相当于在7本相同书之间的6个“空档”内插入两个相同“I”（一般可视为“隔板”）共有种插法，即有15种分法。

十、均匀分组，先找规律

例1110本不同的书，分成三堆，其中一堆四本，一堆三本，一堆三本，问有多少种不同的分法？

分析：这是一个均匀分组与不均匀分组的问题，应先处理不均匀分组的问题。从10本不同的书中选4本有种选法，再把剩余的6本书分两堆，有种分法，根据分步计数原理，共有210种不同的分法。

上面对几种常见的几类排列组合问题，进行了策略分析，并找到了一定的规律，构造了相应的解决问题的模型。除了上述方法外，有时可以通过设未知数，借助方程来解答，简单一些的问题可采用列举法，还可以利用对称性或整体思想来解题等。

作者单位：湖北省云梦县第一中学

邮政编码：432500