排列、组合中常见的解题思路与方法

解决与排列、组合有关的问题，首先，必须认真审题，明确这个问题是排列问题，还是组合问题？其次，抓住问题的本质特征，灵活运用基本计数原理和排列数、组合数公式进行分析、解答.实践证明，备考的有效方法是题型和解法归类，识别模式，熟练运用.下面例谈排列、组合问题中常见的解题思路和方法.

一、分组（堆）问题

分组（堆）问题的6个模型：①无序不等分;②无序等分;③无序局部等分;④有序不等分;⑤有序等分;⑥有序局部等分.

处理问题的原则：

（1）若干个不同的元素“等分”为n堆，要将选取出每一个堆的组合数的乘积除以n！;

（2）若干个不同的元素局部“等分”有k个均等堆，要将选取出每一个堆的组合数的乘积除以k！;

（3）非均分堆问题，只要按比例取出分完再用乘法原理作积;

（4）要明确堆的顺序时，必须先分堆后，再把堆数当作元素个数进行全排列.

例1 有4项不同的工程，要分包给3个工程队，要求每个工程队至少分到一项工程，共有多少种不同的分包方式？

解：要完成分包这件事，可以分为两个步骤：

①先将4项工程分为3“堆”，有C24C12C11A22=6种分法;

②再将分好的3“堆”依次分给3个工程队，有3！=6种分法.所以，共有6×6=36种不同的分包方式.

二、不相邻元素“插空法”

解决一些不相邻问题时，可以先排“一般”元素，然后插入“特殊”元素，使问题得以解决.

例2 7人排成一排，甲、乙两人不相邻，有多少种不同的排法？

解：分两步进行：

①把除甲乙以外的其他5人排列，有A55=120种排法;

②将甲乙分别插入到不同的间隙或两端中（插空），有A26=30种插入法.

所以，共有120×30=3600种排法.

注意：几个元素不能相邻时，先排一般元素，再让特殊元素插空.

三、相邻元素“捆绑法”

相邻元素的排列，可以采用“局部到整体”的排法，即将相邻的元素局部排列当成“一个”元素，然后再进行整体排列.

例3 6人排成一排，甲、乙两人必须相邻，有多少种不同的排法？

解：可分两步进行：

①把甲乙排列（捆绑），有A22=2种捆法;

②把甲乙两人的捆看作一个人与其他的4人排队，有A55=120种排法.

所以，共有2×120=240种排法.

注意：几个元素必须相邻时，先捆绑成一个元素，再与其它的进行排列.

四、消序法（留空法）

几个元素顺序一定的排列问题，一般是先排列，再消去这几个元素的顺序，或者先让其它元素选取位置排列，留下来的空位置自然就是顺序一定的了.

例4 5个人站成一排，甲总是站在乙的右侧有多少种站法？

解法1：将5个人依次站成一排，有A55种站法，然后再消去甲乙之间的顺序数A22，所以甲总站在乙的右侧站法总数为A55A22=A35=60.

解法2：先让甲乙之外的3人从5个位置选出3个站好，有A35种站法，留下的两个位置自然给甲乙，有1种站法.所以，甲总站在乙右侧的站法总数为A35×1=A35.

五、隔板法

n个相同小球放入m（m≤n）个盒子里，要求每个盒子里至少有一个小球的放法等价于n个相同的小球穿成一串，从间隙里选m-1个结点剪截成m段.

例5 某校准备参加今年高中数学联赛，把16名选手名额分配到高三年级的1～4个教学班，每班至少一个名额，则不同的分配方案共有    种.

解：问题等价于把16个相同的小球放入4个盒子里，每个盒子里至少有一个小球的放法种数问题.将16个小球穿成一串，截为4段有C315=455种截断法，对应放到4个盒子里.因此，不同的分配方案共有455种.

变式：某校准备参加今年高中数学联赛，把16个选手名额分配到高三年级的1～4个数学班，每班的名额不少于该班序号数，则不同的分配方案共有多少种？

解：问题等价于先给2班1个，3班2个，4班3个，再把剩余的10个相同小球放入4个盒子里，每个盒子至少有一个小球的方法种数问题.将10个小球穿成一串，截为4段，有C39种截法，对应放到4个盒子里.因此，不同的分配方案共C39=84种.

六、错位法

编号为1至n的n个小球放入编号为1到n的n个盒子里，每个盒子里放一个小球，要求小球与盒子的编号都不同，这种排列称为错位排列.

例6 编号为1至6的6个小球放入编号为1至6的6个盒子里，每个盒子放一个小球，其中恰有2个小球与盒子的编号相同的放法有多少种？

解：选取编号相同的两组球和盒子的方法有C26=15种，其余4组球与盒子需错位排列有9种方法.故所求方法有：15×9=135种.

七、剔除法

从总体中排除不符合条件的方法数，这是一种间接解题的方法.排列组合应用题往往和代数、三角、立体几何、平面解析几何的某些知识联系，从而增加了问题的综合性.

例7 以正方体的顶点为顶点的四面体有多少个？

解：正方体8个顶点从中每次取4个，理论上可构成C48种四面体，但6个表面和6个对角面的4个顶点共面就不能构成四面体.所以四面体实际有C48-12=58个.

变式：某校开设A类选修课3门，B类选修课4门，一位同学从中共选3门，若要求两类课程中各至少选一门，则不同的选法共有    种.

解法1：分两类：①A类选修课2门，B类选修课1门，有C23×C14种;②A类选修课1门，B类选修课2门，有C13×C24种.故共有C23×C14+C13×C24=30种.

解法2：从7门中任意选修3门，有C37种，减去3门同时在A类选修课（C33）或B类选修课（C34）中，故共有C37-C33-C34=30种.

八、圆排问题线排法

n个元素圆排列数有n！n种.

例8 5对姐妹站成一圈，要求每对姐妹相邻，有多少种不同的站法？

解：根据乘法原理，分两步：第一步是把5对姐妹看作5个整体，进行排列有5！种不同的排法，但是因为是围成一个首尾相接的圆圈，就会产生5个重复，因此实际排法只有5！5=24种.第二步每一对姐妹之间又可以相互交换位置，也就是说每一对姐妹均有2种排法，共有25=32种.所以应有24×32=768种站法.

九、可重复的排列求幂法

重复排列问题要区分两类元素：一类可以重复，另一类不能重复.把不能重复的元素看作“客”，能重复的元素看作“店”，则通过“住店法”可顺利解题，在这类问题使用住店处理的策略中，关键是正确判断哪个是底数，哪个是指数.

例9 8名同学争夺3项冠军，获得冠军的可能性有    种.

解：冠军不能重复，但同一个学生可获得多项冠军，把8名学生看作8家“店”，3项冠军看作3个“客”，他们都可能住进任意一家“店”，每个“客”有8种可能.因此共有83种不同的结果.

（作者：丁称兴，江苏省溧水高级中学）