排列组合解题经典方法全解

浅谈排列组合解题策略参与者:王衡1特殊元素优先安排法(山东卷10)2合理分组,准确分步3正难则反,等价转化(山东卷10)4分排问题直接处理5“小集团”排列问题先整体后局部(浙江14题)6挡板法这是解决排列组合最基本的方法，主要适用于将元素无区别的分为几部分的问题。例1.1[1]将8个大小相同的球放入三个不同的盒子,每个盒子至少放一球,问有多少不同的放法?分析本题要保证每个盒子至少有一球，则仍然可以用挡板法解决。此题实质是8个球产生7个空隙，将8个完全相同的球分为3部分，只需要两块挡板插入空隙，这样分出的每堆球的数目，就对应着每个盒子里放的球的个数。因此共有27C=21种不同的放法。挡板法适用范围很广，可用于方程求解有多少组正整数解、把相同物体放入不同盒子（每个盒子非空）、把相同物品分为几堆等情形，是解决排列组合最重要的方法之一。7捆绑法(北京卷12题)这也是解题中常用的基本方法。主要是利用把所给条件中相关元素捆绑在一起，再进行排列组合的原理。例2．1求8名同学排成一排，其中甲、乙必须排一起的不同排法。分析题中条件要求必须将甲、乙排一起，故捆绑甲乙，视为1个人，则与其他6人共有77A种方法，而甲乙之间的排法有22A种，故由乘法原理，按题中要求不同的排法有77A·22A=10080种。捆绑法一般是依据题目中的条件，先将部分特定物品捆绑在一起视为一个整体，再进行讨论。主要适用于解相邻元素的排列问题，做题时应注意排序问题。8插空法(大纲卷14题)这种方法往往和其他方法共同使用，是非常重要的方法。通过元素之间产生的空隙而进行插空。主要适用于元素不相邻的排列问题。例3．1[1]一排九个座位有六个人坐,若每个空位两边都坐有人,共有多少种不同的坐法?分析九个座位六个人坐,空了三个座位,每个空位两边都有人,等价于三个空位互不相邻,可以看做将六个人先依次坐好，有66A种不同的坐法。再将三个空座位“插入”到坐好的六个人之间的五个“间隙”(不包括两端)之中的三个不同的位置上有35C种不同的“插入”方法。根据乘法原理,共有66A·35C=7200种不同的坐法。插空法对于解决要求某些元素不能相邻，由其他元素将它们间隔开的情形。一般先将其他元素排好，再将所指定的不相邻元素插入他们产生的空隙及两端位置。对于两端位置的取舍应依据题意。9减少位置法通过减少位置的方法把问题固定，然后把减少的位置再插进固定的方法里。例4．1[2]一排6张椅子上坐3人,每2人之间至少有一张空椅子,求共有多少种不同的坐法?分析将问题转化成——3个人坐5张椅子,然后插一把空椅子问题.3个人若坐5张椅子,每2人之间有一张空椅子,坐法是固定的有33A种不同的坐法。然后,将余下的那张椅子插入3个坐位的4个空隙（包括两端）,有4种插法.所以共有433A=24种不同的坐法.减少位置法是根据特殊数据排列方式一定，通过减少位置以构造特殊数据，这样排法就确定了，再将减少的位置按题意插入确定的情形中。主要用于人坐位置且中间有间隔的情形。10除法主要用于某些元素要按一定顺序排列的定序问题和均匀分组问题。在均匀分组上是最容易出错的，必须得引起学者的注意。(1)1、非平均分组无归属问题，即将相异的P（P=12mnnn）个物件分成任意12,mnnn件无记号的m堆且这m堆的个数互不等，其分法数为N=121nnmnnppnmCCC2、平均分组无归属问题,即将相异的P(P=mn)个物件分成无记号的m堆，其分法数为N=2nnnnppnnnmmCCCCA3、部分平均分组无归属问题，即将相异的P（P=12mnnn）个物件分成任意12,mnnn件无记号的m堆，且12,mnnn这m个数中分别有a,b,c个相等，其分法数为N=2nnnnppnnnabcabcCCCCAAA例1:现有12件不同礼品①平均分成三堆;②分成件数为2,4,6三堆;③分成件数为2,2,2,3,3五堆，其方法数分别为多少?(答:4441284133CCCNA;246212106NCCC;22233121086333232CCCCCNAA)(1)主要用于某些元素要按一定顺序排列的定序问题和均匀分组问题。在均匀分组上是最容易出错的，必须得引起学者的注意。例5.1将六人分为3组下棋，有多少种分组方法？分析有序分组有26C·24C·22C种方法，但应消除因有序分组造成的重复，故不同的分组方法有55C·24C·22C÷33A=15种。(2)定序问题除法处理(浙江14题)一般用于有相同元素的几类元素的定序排列问题。例6.1用2面红旗、3面黄旗由下往上挂到旗杆上，问：可以组成多少组不同的标志？分析5面旗的全排列为55A种，由于2面红旗、3面黄旗分别全排列只能作一次挂法，故共有55A/（22A·33A）=10种。缩倍法主要用于在排列问题中限制某几个元素必须保持一定顺序的定序问题，这种方法与除法有时可交叉使用。泥于死板的题型与方法，而开拓出一种题型的多种求解方法，从而给解题提供更多的思路，达到迅速、准确解题的目的。