解排列组合问题的几种方法

解排列组合问题的几种方法郑勇山东省济宁市微山县第三中学272195排列组合问题是高中数学的重点和难点之一，也是新教材中学习概率的基础，是近年高考必考内容。排列组合是研究计数问题的策略学，首先根据题意弄清是排列还是组合问题以及排列组合混合问题，抓住问题的本质特征，准确合理地利用两个基本原则。分析计数原理满足两个条件，①类与类互斥，②总类完备。分步计数原理的特征是，分步解决问题，分步必须做到步与步互相独立，互不干扰并确保连续性。这是解决排列组合问题的最基本的方法手段。具体的题中，这两种原理交叉结合来解决问题。下面谈一些粗浅的认识及常用的方法，仅供参考。1、特殊元素•优先法对于有要求的特殊元素，特殊位置要优先安排，在做题时，针对实际问题，有时“元素优先”，有时“位置优先”。合理分配，准确分步是确保解决问题的前提。例1，0、3、5、6、8这五个数字，组成没有重复数字的三位数，其中偶数有几个？分析：这里百位及个位是特殊位置，0是特殊元素，若以“元素优先”考虑，则先对0分两类。第一类：这三位数中含有0，再分两类：①0在个位上分两步，（首先个位安排0，百位十位从4个元素中任取2个排序有A%）有AiiA24个。②0不在个位上分三步（首先安排0在十位上，再安排好个位，从两个偶数中取一个有A12，最后安排百位有A13）有AiiAi2Ai3个；第二类：这三位数不含有0,此时只有个位是特殊位置分两步（先安排个位有A12再安排十位百位有A2）有A1A2。由分类计数原理偶数共有（A1A2+A1A1A1）+AiA2=30个，，若从3231412323“位置优先”考虑，可分0再个位和0不再个位两类：①0在个位有A24，②0不在个位有如如如，由分类计数原理得偶数共有入24+知如知=30个。"2、、间接法4233对含有否定字眼的问题可以从总体中把不符合要求的删去，此时注意既不能多减又不能少减。例2,7人按甲不在排头，乙不在排尾站成一排，有多少种排列方法。分析：甲在排头有A66种排法，乙在排尾有A66种排法，甲在排已在排尾有A55种方法，则共有A77-A66-A66+A55=3700种方法。3、元素相邻•捆绑法对于某几个元素要求相邻的排列问题，可先将相邻的元素“捆绑”起来，看作一个大元素和其他元素并列，然后再松绑，对捆绑的元素进行排列。例3：4个老师3个学生排成一列，要求学生排在一起，共有几种排法？分析：将题中三个学生捆绑起来作为一个大元素，与其与4位老师共5个元素进行全排列有A55种排法，再给三个学生松绑，他们之间又有A33种排法，由分步计数原理得共有A5A3=7200种排法。534、元素不相邻插空法对于某几个元素不相邻的排列的问题，首先分清“谁插谁”的问题。要先排无限制条件的元素，再插入必须间隔的元素；其次，数清可插的未知数；最后还注意，插入时是以组合形式还是以排列形式插入，要把握准。例4,5个男生3个女生排成一排，要求女生不相邻且不可排两头，共有几种排法？分析：先排限制条件的5个男生有A55种，由于女生不相邻且不可派两头，故3个女生只能分别排在5个男生的4个间隙中，有A%种（若允许女生排两头，5个男生产生6个空有A36种插法），由分步计数原理得共有A55A34种排法。例4':大街上有编号为1、2、3……10的十盏路灯，为了节约用电又不影响照明，可关掉其中的三盏灯，但不能同时关掉相邻的两盏或三盏，也不能关掉两端的路灯，那么有多少种关灯方法？分析：由于问题中的7盏灯亮3盏灯灭，两端又不准灭，故可把亮灯作为无限制条件的元素产生6个空隙，在这6个空隙中插入3个熄灭的灯即可，由C36种关灯方法。思考：从1、2、3……10个数中任选三个互不相邻的自然数，有多少种不同的选法？1.（7个数看作无限制条件的产生8个空，插入3个数，插法即选法有C3种选法）85、元素顺序固定•除法处理法对于某几个元素顺序一定的排列问题，可先把这几个元素和其他元素一同进行排列，然后用总排列数除以这几个元素的全排列数。例5,由数字0、1、2、3、4、5组成没有重复数字的六位数，其中个位数字小于十位数字的共有多少个？分析：无条件限制的总排列数为A1A5个，而十位与个位的全排列数为A2，符合条件的552只有一种，故满足条件的六位数有：A15A55-A22=300个。例5'，7人站成一排，甲、乙、丙顺序固定，由多少种不同的排列方法？分析：此题全排列有A77种方法，而甲、乙、丙的排列法有A33种，其中只有一种符合条件的，则符合条件的排法有A77-A33=840种不同方法。3思考：5人参加百米赛跑:若无同时到达终点的情况，则甲比乙先到有几种情况？简析：按元素定序除法处理法得A-A=60种，或者先排甲、乙有C种，再排其他3人有A种，由分步计数原理得C•A=60种。注：对于元素定序问题，除了用除法处理法，还可以先在总位置中选出定序元素的位置而不参加排列，然后对其他元素进行排列。6元素分排，直排处理法若n个元素要分m排排列，可把每排首位连成一列，对于每排的特殊要求，只要分段考虑特殊元素，然后对其余元素作统一排列。例6,2个老师，4个女生，12个男生，排成三排照相，要求第一排5人，第二排6人，第三排7人，且老师在第一排，女生在第二排，共有几种不同的排法？分析：先把18个人看成一排，从左到右分5个位，6个位，7个位三段，先从左边的5个位中排入2个老师有A25种，再在中段的6个位中排入4个女生有A46种，然后在其余的位置上全排12个男生有A%：种，由乘法原理，共有A25A46A1212种。67、环状排列•剪断直排法…12n人围成一圈的排列称为环状排列。对于环状排列，我们可以想象成这n人手拉手的排列，因此可采用剪断直排筏。由于n人有n个连接点，故友n种剪断得方法，故共有An/n种排法。例7,4名学生和2名老师围圆桌入座，①有n种入座方法？②如果老师必须相邻，有几种入座方法？③如果老师必不相邻，有几种入座方法？④如果甲老师与乙老师相邻，但甲必在乙的左边有几种入座方法？分析：①6人全排列有A%种方法，由于6种剪断直排对应同一种圆排，故共有A6/6=120种。②由于老师相邻，先把两个老师看作一个人，等价于5人全排有A55种，又由于老师之间可以交换位置有A22种，所以师生全排有A22A55种，又由于有5种剪断法:故共有A22A55/5=48种。③只要在所有圆排中减去老师相邻的种数即为老师不相邻的了，共有A6/6顼2折/5=72625种。④因为两老师有固定顺序所以无须两位老师再进行排列，共有A5/5=24种。58、“小集团”问题•先“集团”后整体或先整体后“集团”法对于某些排列问题中的某些元素要求组成“小集团”时，可先按制约条件“组团”，并看作一个大元素和其他元素进行排列或先看作一个大元素与其他元素进行排列，再进行“小集团”制约条件的排列。例8,四名男生和两名女生举行一场诗歌朗诵，出场顺序要求两名女生之间恰有两名男生，则出场方案有几种？分析：由于要求有“女男男女”这样的“小集团”，可先“组团”。从4名男生中选2人排入两女生之间，有A24A22种，（2名女生有A22种排法），把这样的“小集团”看为一个元素和其他两名男生进行排列，有A33种，故共有A24A22A33种，或者先整体后“集团”法共有A33A24A22种。3J'9、表格法对于选派问题，还有淘汰赛（参加队伍不多）通常使用表格法。例9，9人组成篮球队，其中7人善打锋，3人善打卫，现选5人（3锋2卫，锋分左中右锋，卫分左中右卫）组队出场。有多少种不同的组队方法？分析：共9人，7人善锋，3人善卫，这说明1人即善锋又善卫，只会锋的6人，只会卫的2人，不妨列表使其直观化。人数6人只会锋2人只会卫1人既锋又卫结果不同选法32A3A26_2311（卫）A36C12A22221（锋）C2A3A26~3—2则共有A3A2+A3C1A2+C2A3A2=900种方法。62622632思考：某旅游局有5名翻译人员，4名会英语，2人会日语，今需派2名会英语1名会日语的人员做导游，有多少种派法？（9种）10、单循环与双循环赛事安排法单循环赛：如有n个队参加，不论n是奇数还是偶数共有n（n-1）/2场比赛，而双循环比赛（如我们平时说的主客场）的比赛，场数为n（n-1）场。例10，7个球队踢单循环比赛，共有多少场比赛？分析：结果很简单，直接求出有21场比赛，具体赛程可由无向图表示。11、不同元素进盒•先分堆再排列对于不同的元素放入不同的盒内，当有的盒内忧不少于2个元素时，不可分批进入，必须先分堆再排入。例11，5个老师分配到3个班级内搞活动，每班至少一人，有几种不同的分法？分析：先把5位分成3堆，有两种分法①3、1、1分法②2、2、1分法（其中①分法有C35种，②分法有C25C23/A22种），再排列到3个班级里全排列，由分类、分步计数原理，共有（C35+C25C23/A22）A33种。12、相同元素进盒•隔板法对于相同元素的分配问题，可设计一种情景来解决，就是我们的挡板分隔。例12,从5个班级中选10人组成篮球队，每班至少一人，有几种选法？分析：这里只是人数而已，与顺序无关，故可把10个相同的小球放入5个不同的盒内，每盒至少一球。可先把10球排成一列，再在其中的9个间隙中选4个位置插入4块“挡板”分成5格（构成5格盒子），有C49种方法。例12'，7个相同的球放入4个不同的盒子中，每盒不空有多少种方法？分析：7个球放入4个不同的盒，即把7个球分成4组，不妨将7个球摆放一列，设法分成4部分（每一种分法对应一种放法），要想分成4部分，只需用3个隔板将7个球隔开。其中7个球产生6个空，选3个空放隔板，则有C3=20中方法。613、两类元素的排列•用组合选位法例13：10级楼梯，要求7步跨完，且每步最多跨2级，问几种不同夸法?分析：由题意知，有3步跨2级，4步跨1级，因此这是1级与2级两类不同元素的排列，所以只要在7步中任选3步为2级即可，有C37种跨法。例13'，3面红旗2面黄旗，全部升上旗杆作为信号，可打出几种不同的信号？简析：由题意知，这是3面红旗和2面黄旗两种不同元素的排列问题，这要在5个旗杆上选2个旗杆放黄旗即可。共有C2=10种不同的信号5思考：①沿图中格线从顶点A到顶点B最短的路线有几条？（C37条）7②从5个班中选10人组成校篮球队（无任何要求）有几种A—"选法？（有C414种）（提示：此题不同于例12,嗟因为无任何要求选队员，可以看成10个球与4个班的排列问题，即两类元素的排列。）③（a+b+c+d）10的展开式有几项？（有C313项）（提示：同思考②，这仍是10个球与3个挡板的排列问题）注：两类元素的问题涉及面很广，解决此问题的关键是把问题等价转换为两类元素的排列问题。14、个数不少于盒子编号数•用填满分隔法例14，10个相同的小球放入编号1、2、3的三个盒子内，要求每个盒子的球数不小于它的编号数，则不同的方法有多少种？分析：由于球是相同的，故先用6个球按编号分入各盒，再把剩下4球放入这3个盒即可。同上面的参考②，可用2个挡板与4个球一起排列（即为两类元素的排列问题），有C26种。思考：现有40辆新车需分到7个运输队（车队含有1、2、3、4、5、6、7编号），车队得到的新车数不少于车队的编好书，则有多少种不同分法？15、混合问题•先选后排法对于排列组合的混合问题，可采用先选元素后排列的办法。例15,4个不同的小球放入编号为1、2、3、4的四个盒子里，则恰有一个空盒的放法有多少种？分析：可以分步处理。第一步，从4个盒子中选出1个空盒子有C14种；第二步，从4个球中选出2个球有C%种；第三步，把先取出的2个球为一个元素与其与2个球组成3个元素，放入剩下的3个盒中，进行全排列有A33种；由分步计数原理得共有C14C24A33种放法。16、概率法求排列组合3I'我们知道计算概率的基础是排列组合数，反过来可利用某事件的概率可求排列组合的问题。但利用概率思想解排列组合问题的条件，那就是由等可能事件组成的事件，否则会出现错误。例16,4名男生和6名女生组成至少有一位男生参加的三