解排列组合问题的策略

解排列组合问题的策略要正确解答排列组合问题，第一要认真审题，弄清楚是排列问题还是组合问题、还是排列与组合混合问题；第二要抓住问题的本质特征，采用合理恰当的方法来处理，做到不重不漏；第三要计算正确．下面将通过对若干例题的分析，探讨解答排列组合问题的一些常见策略，供大家参考．一、解含有特殊元素、特殊位置的题——采用特殊优先安排的策略对于带有特殊元素的排列问题，一般应先考虑特殊元素、特殊位置，再考虑其他元素与其他位置，也就是解题过程中的一种主元思想．例1：用0，2，3，4，5这五个数字，组成没有重复数字的三位数，其中偶数共有（）A．24个B．30个C．40个D．60个解：因组成的三位数为偶数，末尾的数字必须是偶数，又0不能排在首位，故0是其中的“特殊”元素，应优先安排，按0排在末尾和0不排在末尾分为两类：①当0排在末尾时，有个；②当0不排在末尾时，三位偶数有个，据加法原理，其中偶数共有+＝30个，选B．若含有两个或两个以上的特殊位置或特殊元素，则应使用集合的思想来考虑．这里仅举以下几例．(1)无关型(两个特殊位置上分别可取的元素所组成的集合的交是空集)例2：用0，1，2，3，4，5六个数字可组成多少个被10整除且数字不同的六位数?解：由题意可知，两个特殊位置在首位和末位，特殊元素是“0，首位可取元素的集合A＝{1，2，3，4，5}，末位可取元素的集合B＝{0}，A∩B＝．如图1所示．末位上有种排法，首位上有种不同排法，其余位置有种不同排法．所以，组成的符合题意的六位数是＝120(个)．说明：这个类型的题目，两个特殊位置上所取的元素是无关的．先分别求出两个特殊位置上的排列数(不需考虑顺序)，再求出其余位置上的排列数，最后利用乘法原理，问题即可得到解决．(2)包合型(两个特殊位置上分别可取的元素所组成集合具有包合关系)例3：用0，1，2，3，4，5六个数字可组成多少个被5整除且数字不同的六位奇数?解：由题意可知，首位、末位是两个特殊位置，“0”是特殊元素，首位可取元素的集合A＝{1，2，3，4，5}，末位可取元素的集合B＝{5}，BA，用图2表示。末位上只能取5，有种取法，首位上虽然有五个元素可取但元素5已经排在末位了，故只有种不同取法，其余四个位置上有种不同排法，所以组成的符合题意的六位数有＝96(个)．说明：这个类型的题目，两个特殊位置上所取的元素组成的集合具有包含关系，先求被包合的集合中的元素在特殊位置上的排列数，再求另一个位置上的排列数，次求其它位置上排列数，最后利用乘法原理，问题就可解决．(3)影响型(两个特殊位置上可取的元素既有相同的，又有不同的．这类题型在高考中比较常见．)例4：用1，2，3，4，5这五个数字，可以组成比20000大并且百位数字不是3的没有重复数字的五位数有多少个?解：由题意可知，首位和百位是两个特殊位置，“3”是特殊元素．首位上可取元素的集合A＝{2，3，4，5}，百位上可取元素的集合B＝{1，2，4，5}．用图3表示．从图中可以看出，影响型可分成无关型和包含型．①首先考虑首位是3的五位数共有：个；②再考虑首位上不是3的五位数，由于要比20000大，∴首位上应该是2、4、5中的任一个，种选择；其次3应排在千位、十位与个位三个位置中的某一个上，种选择，最后还有三个数、三个位置，有种排法，于是首位上不是3的大于20000的五位数共有个．综上①②，知满足题设条件的五位数共有：+＝78个．二、解含有约束条件的排列组合问题一――采用合理分类与准确分步的策略解含有约束条件的排列组合问题，应按元素的性质进行分类，按事件发生的连贯过程分步，做到分类标准明确、分步层次清楚，不重不漏．例5：平面上4条平行直线与另外5条平行直线互相垂直，则它们构成的矩形共有________个．简析：按构成矩形的过程可分为如下两步：第一步．先在4条平行线中任取两条，有种取法；第二步再在5条平行线中任取两条，有种取法．这样取出的四条直线构成一个矩形，据乘法原理，构成的矩形共有·＝60个．例6：在正方体的8个顶点，12条棱的中点，6个面的中心及正方体的中心共27个点中，共线的三点组的个数是多少?解：依题意，共线的三点组可分为三类：两端点皆为顶点的共线三点组共有＝28(个)；两端点皆为面的中心的共线三点组共有＝3(个)；两端点皆为各棱中点的共线三点组共有＝18(个)．所以总共有28+3+18＝49个．例7：某种产品有4只次品和6只正品(每只产品均可区分)．每次取一只测试，直到4只次品全部测出为止．求第4只次品在第五次被发现的不同情形有多少种?解：先考虑第五次测试的产品有4种情况，在前四次测试中包含其余的3只次品和1只正品，它们排列的方法数是6。依据乘法原理得所求的不同情形有4×6＝576种．有些排列组合问题元素多，取出的情况也有多种，对于这类问题常用的处理方法是：可按结果要求，分成不相容的几类情况分别计算，最后计算总和．例8：由数字0，1，2，3，4，5组成没有重复的6位数，其中个位数字小于十位数字的共有（）A、210个B、300个C、464个D、600个分析：按题意个位数字只可能是0，1，2，3，4共5种情况，符合题的分别有，，，，个．合并总计，共有++++＝300(个)．故选B．说明：此题也可用定序问题缩位法求解，先考虑所有6位数：个，因个位数字须小于个位数字，故所求6位数有()/＝300(个)．处理此类问题应做到不重不漏．即每两类的交集为空集，所有类的并集为合集．因此要求合理分类．例9：已知集合A和集合B各含12个元素，A∩B含有4个元素，试求同时满足下面的两个条件的集合C的个数：(1)CA∪B，且C中含有3个元素；(2)C∩A≠（表示空集)。分析：由题意知，属于集合B而不属于集合A元素个数为12-4＝8，因此满足条件(1)、(2)的集合C可分为三类：第一类：含A中一个元素的集C有个；第二类：含A中二个元素的集C有个；第三类：含A中三个元素的集C有个。故所求集C的个数是++＝1084．有序分配问题是指把元素按要求分成若干组，分别分配到不同的位置上，对于这类问题的常用解法，是先将元素逐一分组，然后再进行全排列、但在分组时要注意是否为均匀分组．例10：3名医生和6名护士被分配到3所学校为学生体检，每校分配1名医生和2名护土，不同的分配方法共有()．A．90种B．180种C．270种D．540种分析：(一)先分组、后分配：第一步：将3名医生分成3组，每组一人只有一种分法．第二步：将6名护士分成3组，每组2人有：()/种分法．第三步：将医生3组及护士3组进行搭配，使每组有一名医生、2名护士，有种搭配方法．第四步：将所得的3组分配到3所不同的学校有种分配法．故共有不同的分配方法：·＝540(种)．故选(D)．分析：(二)第一步：先将6名护士分配到3所不同学校，每所学校2名，则有(种)分法．第二步：再将3名医生分配到3所不同的学校，每所学校1人，有种分法．故共有=540(种)故选(D)．说明：处理此类问题应注意准确分步．三、解排列组合混合问题——采用先选后排策略对于排列与组合的混合问题，可采取先选出元素，后进行排列的策略．例11：4个不同小球放入编号为1、2、3、4的四个盒子，则恰有一个空盒的放法有_________种．简析：这是一个排列与组合的混合问题．因恰有一个空盒，所以必有一个盒子要放2个球，故可分两步进行：第一步选，从4个球中任选2个球，有种选法。从4个盒子中选出3个，有种选法；第二步排列，把选出的2个球视为一个元素，与其余的2个球共3个元素对选出的3个盒子作全排列，有种排法．所以满足条件的放法共有=144种．四、正难则反、等价转化策略对某些排列组合问题，当从正面入手情况复杂，不易解决时，可考虑从反面入手，将其等价转化为一个较简单的问题来处理．即采用先求总的排列数(或组合数)，再减去不符合要求的排列数(或组合数)，从而使问题获得解决的方法．其实它就是补集思想．例12：马路上有编号为1、2、3、…、9的9只路灯，为节约用电，现要求把其中的三只灯关掉，但不能同时关掉相邻的两只或三只，也不能关掉两端的路灯，则满足条件的关灯方法共有_______种．简析：关掉一只灯的方法有7种，关第二只、第三只灯时要分类讨论，情况较为复杂，换一个角度，从反面入手考虑．因每一种关灯的方法唯一对应着一种满足题设条件的亮灯与暗灯的排列，于是问题转化为在6只亮灯中插入3只暗灯，且任何两只暗灯不相邻、且暗灯不在两端，即从6只亮灯所形成的5个间隙中选3个插入3只暗灯，其方法有＝10种。故满足条件的关灯的方法共有10种．例13：甲、乙两队各出7名队员按事先排好的顺序出场参加围棋擂台赛，双方先由1号队员比赛，负者被淘汰，胜者再与负方2号队员比赛，……直到有一方队员全被淘汰为止，另一方获胜，形成—种比赛过程，那么所有可能出现的比赛过程共有多少种?解：设甲队队员为al，a2,…a7，乙队队员为b1，b2,……，b7，下标表示事先安排好的出场顺序，若以依次被淘汰的队员为顺序，比赛过程可类比为这14个字母互相穿插的一个排列，最后是胜队中获胜队员和可能未参赛的队员．如a1a2b1b2a3b3b4b5a4b6b7a5a6a7.所表示为14个位置中取7个位置安排甲队队员，其余位置安排乙队队员，故比赛过程的总数为＝3432.例14：有2个a，3个b，4个c共九个字母排成一排，有多少种排法?分析：若将字母作为元素，1—9号位置作为位子，那么这是一个“不尽相异元素的全排列”问题，若转换角色，将1—9号位置作为元素，字母作为位子，那么问题便转化成一个相异元素不许重复的组合问题．即共有＝1260(种)不同的排法．有些问题反面的情况为数不多，容易讨论，则可用剔除法．对有限制条件的问题，先以总体考虑，再把不符合条件的所有情况剔除．这是解决排列组合应用题时一种常用的解题策略．例15：四面体的顶点和各棱中点共有10个点，在其中取4个不共面的点，不同的取法共有()A．150种B．147种C．14种D．141种分析：在这10个点中，不共面的不易寻找，而共面的容易找．因此，采用剔除法，由10个点中取出4个点的组合数(减去4个点共面的个数即为所求)．4点共面情形可分三类：第一类：四面体每个面中的四个点共面，共有4×＝60种；第二类：四面体的每2组对棱的中点构成平行四边形，则这四点共面，共有3种；第三类：四面体的一条棱上三点共线，这三点与对棱中点共面，共有6种．故4点不共面的取法有-(4+6+3)＝141种．例16：从0、1、2、3、4、5、6、7、8、9这10个数中取出3个数，使和为不小于10的偶数，不同的取法有多少种．解：从这10个数中取出3个不同的偶数的取法有种；取1个偶数和2个奇数的取法有种．另外，从这10个数中取出3个数，使其和为小于10的偶数，有9种不同取法．因此，符合题设条件的不同取法有+-9＝51种．五、解相邻问题——采用“捆绑”策略对于某几个元素要求相邻的排列问题，可先将相邻的元素“捆绑”起来看作一个元素与其他元素排列，然后再在相邻元素之间排列．事实上，这种方法就是将相邻的某几个元素，优先考虑。让这些特殊元素合成一个元素，与普通元素排列后，再松绑．例17：A，B，C，D，E五人并排站成一排，如A，B必相邻，且B在A右边，那么不同排法有（）A．24种B．60种C．90种D．120种分析：将特殊元素A，B按B在A的右边“捆绑”看成一个大元素，与另外三个元素全排列，由A，B不能交换，故不再“松绑”，选A．例18：5人成一排，要求甲、乙相邻，有几种排法?解：将甲、乙“捆绑”成一个元素，加上其他3元素，共4元素，全排列有种，甲、乙内部的排列有种．故共有＝48种．也可以这样理解：先让甲、丙、丁、戊，排成一列有种，再将乙插入甲的左边或右边，有种，共＝48种．例19：计划展出10幅不同的画，其中一幅水彩画、4幅油画、5幅国画，排成一行陈列，要求同一品种的画必须连在一起，并且水彩画不放在两端，那么不同的陈列方式有多少种?()A、B、C、D、分析：先把3种品种的画各看成整体，而水彩画不能放在头尾，故只能放在中间，