排列组合问题的基本类型及解题方法.doc

《排列组合问题的基本类型及解题方法.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、排列组合问题的基本类型及解题方法解决排列组合问题要讲究策略，首先要认真审题，弄清楚是排列(有序)还是组合(无序)，还是排列与组合混合问题。其次，要抓住问题的本质特征，准确合理地利用两个基本原则进行“分类与分步”。加法原理的特征是分类解决问题，分类必须满足两个条件：①类与类必须互斥(不相容)，②总类必须完备(不遗漏)；乘法原理的特征是分步解决问题，分步必须做到步与步互相独立，互不干扰并确保连续性。分类与分步是解决排列组合问题的最基本的思想策略，在实际操作中往往是“步”与“类”交叉，有机结合，可以是类中有步，也可以是步中有类。以上解题思路分析，可以用顺口溜概括为：审明题意，排（组）分清；合理分类

2、，用准加乘；周密思考，防漏防重；直接间接，思路可循；元素位置，特殊先行；一题多解，检验真伪。（一）特殊元素的“优先安排法”对于特殊元素的排列组合问题，一般先考虑特殊元素，再考虑其他元素的安排。在操作时，针对实际问题，有时“元素优先”，有时“位置优先”。例1： 这五个数字，组成没有重复数字的三位数，其中偶数共有几个？解法一：(元素优先)分两类：第一类，含，在个位有种，在十位有种；第二类，不含，有种。故共有种。注：在考虑每一类时，又要优先考虑个位。解法二：(位置优先)分两类：第一类，在个位有种；第二类，不在个位，先从两个偶数中选一个放个位，再选一个放百位，最后考虑十位，有种。   故共有（二）总

3、体淘汰法对于含有否定词语的问题，还可以从总体中把不符合要求的除去，此时应注意既不能多减也不能少减，例如在例中也可以用此法解答：个数字组成三位数的全排列为，排好后发现不能在首位，而且和不能排在末尾，这两种不合题意的排法要除去，故有个偶数．（三）合理分类与准确分步解含有约束条件的排列组合问题，应按元素的性质进行分类，事情的发生的连续过程分步，做到分类标准明确，分布层次清楚，不重不漏．例2：个人从左到右站成一排，甲不站排头，乙不站第二个位置，不同的站法有　　　　　　　　　解：由题意，可先安排甲，并按其进行分类讨论：（1）若甲在第二个位置上，则剩下的四人可自由安排，有种方法；（2）若甲在第三个或第四

4、个位置上，则根据分布计数原理不同的站法有种站法；再根据分类计数原理，不同的站法共有：种．（四）相邻问题：捆绑法对于某些元素要求相邻排列的问题，可先将相邻元素捆绑成整体并看作一个元素再与其　　它元素进行排列，同时对相邻元素内部进行自排。例3： 个男生个女生排成一列，要求女生排一起，共有几种排法？解：先把个女生捆绑为一个整体再与其他个男生全排列。同时，个女生自身也应　　全排列。由乘法原理共有种。（五）不相邻问题用“插空法”对于某几个元素不相邻的排列问题，可先将其他元素排好，再将不相邻的元素在已排好的元素之间及两端的空隙之间插入即可（注意有时候两端的空隙的插法是不符合题意的）.　例4： 个男生个女

5、生排成一列，要求女生不相邻且不可排两头，共有几种排法？解：先排无限制条件的男生，女生插在个男生间的个空隙，由乘法原理共有种。注意：①分清“谁插入谁”的问题。要先排无限制条件的元素，再插入必须间隔的元素；　　　　　②数清可插的位置数；③插入时是以组合形式插入还是以排列形式插入要把握准。例5： 马路上有编号为的盏路灯，现要关掉其中的三盏，但不能同时关掉相邻的两盏或三盏，也不能关两端的路灯，则满足要求的关灯方法有几种？解：由于问题中有盏亮盏暗，又两端不可暗，故可在盏亮的个间隙中插入个暗的即可，有种。（六）顺序固定问题用“除法”或选位不排或先定后插对于某几个元素顺序一定的排列问题，可先把这几个元素与

6、其他元素一起进行排列，然后用总排列数除以这几个元素之间的全排列数。或先在总位置中选出顺序一定元素的位置而不参加排列，然后对其它元素进行排列。也可先放好顺序一定元素，再一一插入其它元素。例6： 人参加百米跑，若无同时到达终点的情况，则甲比乙先到有几种情况？解法一：先人全排有种，由于全排中有甲、乙的全排种数，而这里只有种是　　　　符合要求的，故要除以定序元素的全排列种，所以有种。解法二：先在个位置中选个位置放定序元素(甲、乙)有种，再排列其它人有，　　　　　由乘法原理得共有种。解法三：先固定甲、乙，再插入另三个中的第一人有种方法，接着插入第二人有种　　　　方法，最后插入第三人有种方法。由乘法原理

7、得共有种。（七）“小团体”排列，先“团体”后整体　　对于某些排列问题中的某些元素要求组成“小团体”时，可先按制约条件“组团”并视为一个元素再与其它元素排列。例7:四名男歌手与两名女歌手联合举行一场演唱会，演出的出场顺序要求两名女歌手之　　　间有两名男歌手，则出场方案有几种？解：先从四名男歌手中选人排入两女歌手之间进行“组团”有种，把这个“女男男女”小团体视为人再与其余男进行排列有种，由乘法原理，共有种．（八）