解决排列组合问题的十五法宝

解决排列组合问题的“十五”法宝一、相邻问题捆绑法把题中规定相邻的几个元素并为一组（当作一个元素）参与排列例1：A、B、C、D、E五人并排成一排，如果A、B必须相邻且B在A的右边，那么不同的排法有（）A．60B．48C．36D．24分析：把A、B视为1人，且B固定在A的右边，则本题相当于4人全排列，即＝24二、相离问题插空法元素相离（即不相邻）问题，可先把无位置要求的几个元素全排列，再把规定相离的几个元素插入上述几个元素间的空位和两端。例2：七个站成一排，如果甲、乙二人必须不相邻，则排法有（）A．1440B．3600C．4820D．4800分析：除甲、乙外，其余5人排列为种，再用甲、乙去插六个空位，有种，不同排法种数为＝3600。三、定序问题对称法在排列问题中限制某几个元素必须保持一定的顺序，可用对称思想解题，先排后除，即。例3：A、B、C、D、E五个站一排，B必须站A右边，则不同的排法（）A．25B．60C．90D．120分析：五个全排列，B在A右边和B在A左边排法数相同，即＝60。引例：晚会原定的5个节目已排成节目单，开演前又加了2个节目，若将这2个节目插入原节目单中，则不同的插法有（）种。分析：原定的5个节目顺序已定，则不同的插法有，亦可：（插队定理：几个不同的元素按一定的顺序排成一排，若将m个不同的元素插入其中，则不同的插法数为）四、定位问题优先法某个（或几个）元素要排在指定位置，可先排这个（或几个）元素再排其他元素。例4：一个老师和四名学生排成一排，老师不在两端，则不同的排法有（）种。分析：老师在中间3个位置上选一个位置有种，四名同学在其余四个位置有种，其＝72种。五、多排问题单排法把元素排成几排的问题，可归纳为一排考虑，再分段处理。例5：8人站前后2排，每排4人，其中某2人站在前排，某1人站在后排有（）种排法。分析：看成一排，某2个人在前半段4个位置中选排2个，有种，某1人在后半段4个人位置中选一个有种，其余5人在余下5个位上有种，故共有＝5760种排法。六、乱座问题分步法把元素排列到指定号码位置上，可先把某个元素按规定排入，第2步再排另一个元素，如此继续下去，依次即可完成。例6：将数了1，2，3，4，填入标号为1，2，3，4的四个方格，每格填一个数，则每个方格的标号与所填数字均不相同的填法有（）种。分析：先把1填入方格，符合条件有3种，第2步把被填入方格的对应数字填入其他3个方格，又有3种方法，第3步填余下的2个数字，只有1种填法，故共有3×3×1＝9种。引申：n封装入n个信封时全部装错的装法总数为。通常称为伯努利一欧拉错装信封问题，又称为乱序排列，即把n个元素的排列a1，a2，L，an重新排列，使每个元素都不在原来的位置上的排列问题。七、多元问题娄类法元素多，取出的情况也有多种，可按结果要求，分成不相容几类情况，分别计算，最后总计。例7：由0，1，2，3，4，5组成没有重复数字的六位数，其中个位数字小于十位数字的共有（）个。分析：个位数字只能是0，1，2，3，4共有5种情况，分别有，个，合并总计300个。八、“至少”问题间接法例8：从4台甲型和5台乙型电视机中任取3台，其中至少要甲、乙电视各一台，则不同取法共有（）种。分析：至少各一台反面就是分别只取一种型号，不取另一种型号，故种。九、条件问题排除法在被选总数中，只有一部分符合条件，可从总数中减去不合条件者。例9：正六边形中心和顶点共7个点，以其中3个点为顶点的三角形共有（）个。分析：7点取3点有种，但有3组3点共线，不构成三角形，故种。十、选排问题，先取后排法。从n类元素中取出符合题意的n个元素，再安排到一定位置上，可用先取后排法。例10：四个不同球放入编号1，2，3，4四个盒子中，则恰有一个空盒的放法共有（）种。分析：先取4个球中的2个为一组，另2组各1球有种，然后排列，在4个盒中每次排3组有种，共有＝144种。十一、指标问题用“隔板法”例11：将10个保送生预选指标分配给某重点中学高三年级六个班，每班至少一名，共有多少种分配方案？分析：将10个名额并成一排，名额之间有9个空，用5块隔板插入9个空，就可将10个名额分成6部分，每一种插法就对应一种分配方法，故有种方案。注意：隔板法与插空法是不同的，隔板法只适用于相同元素的分配问题。十二、平均分堆到指定位置用“填空法”例12：将6本不同的书平均分给三位同学，求不同的分法数？分析：甲同学得2本种分法，乙同学得2本有种分法，丙同学得2本有种分法，故总分法数为=90种。十三、平均分堆不到指定位置，其分法数为：平分到指定位置、堆数的阶乘，分堆到位相当于分堆后各堆再全排列，即平均分堆到位的分法数―平均分堆不到指定位置×堆数的阶乘例13：将6本不同的书平均分成3堆有种。十四、几何问题例14．以长方体的顶点为顶点能