搜索
第十九讲排列组合一、排列问题在实际生活中经常会遇到这样的问题，就是要把一些事物排在一起，构成一列，计算有多少种排法，就是排列问题．在排的过程中，不仅与参与排列的事物有关，而且与各事物所在的先后顺序有关．一般地，从n个不同的元素中取出m(mn)个元素，按照一定的顺序排成一列，叫做从n个不同元素中取出m个元素的一个排列．根据排列的定义，两个排列相同，指的是两个排列的元素完全相同，并且元素的排列顺序也相同．如果两个排列中，元素不完全相同，它们是不同的排列；如果两个排列中，虽然元素完全相同，但元素的排列顺序不同，它们也是不同的排列．排列的基本问题是计算排列的总个数．从n个不同的元素中取出m(mn)个元素的所有排列的个数，叫做从n个不同的元素的排列中取出m个元素的排列数，我们把它记做mnP．根据排列的定义，做一个m元素的排列由m个步骤完成：步骤1：从n个不同的元素中任取一个元素排在第一位，有n种方法；步骤2：从剩下的(1n)个元素中任取一个元素排在第二位，有(1n)种方法；……步骤m：从剩下的[(1)]nm个元素中任取一个元素排在第m个位置，有11nmnm（）(种)方法；由乘法原理，从n个不同元素中取出m个元素的排列数是121nnnnm（）（）（），即12.1mnPnnnnm（）（）（），这里，mn，且等号右边从n开始，后面每个因数比前一个因数小1，共有m个因数相乘．二、排列数一般地，对于mn的情况，排列数公式变为12321nnPnnn（）（）．表示从n个不同元素中取n个元素排成一列所构成排列的排列数．这种n个排列全部取出的排列，叫做n个不同元素的全排列．式子右边是从n开始，后面每一个因数比前一个因数小1，一直乘到1的乘积，记为!n，读做n的阶乘，则nnP还可以写为：!nnPn，其中!12321nnnn（）（） ．在排列问题中，有时候会要求某些物体或元素必须相邻；求某些物体必须相邻的方法数量，可以将这些物体当作一个整体捆绑在一起进行计算．三、组合问题日常生活中有很多“分组”问题．如在体育比赛中，把参赛队分为几个组，从全班同学中选出几人参加某项活动等等．这种“分组”问题，就是我们将要讨论的组合问题，这里，我们将着重研究有多少种分组方法的问题．一般地，从n个不同元素中取出m个(mn)元素组成一组不计较组内各元素的次序，叫做从n个不同元素中取出m个元素的一个组合．从排列和组合的定义可以知道，排列与元素的顺序有关，而组合与顺序无关．如果两个组合中的元素完全相同，那么不管元素的顺序如何，都是相同的组合，只有当两个组合中的元素不完全相同时，才是不同的组合．从n个不同元素中取出m个元素(mn)的所有组合的个数，叫做从n个不同元素中取出m个不同元素的组合数．记作mnC．一般地，求从n个不同元素中取出的m个元素的排列数mnP可分成以下两步：第一步：从n个不同元素中取出m个元素组成一组，共有mnC种方法；第二步：将每一个组合中的m个元素进行全排列，共有mmP种排法．根据乘法原理，得到mmmnnmPCP．因此，组合数12)112321mmnnmmPnnnnmCmmmP（）（（）（）（）．这个公式就是组合数公式．四、组合数的重要性质一般地，组合数有下面的重要性质：mnmnnCC(mn)这个公式的直观意义是：mnC表示从n个元素中取出m个元素组成一组的所有分组方法．nmnC表示从n个元素中取出(nm)个元素组成一组的所有分组方法．显然，从n个元素中选出m个元素的分组方法恰是从n个元素中选m个元素剩下的(nm)个元素的分组方法．例如，从5人中选3人开会的方法和从5人中选出2人不去开会的方法是一样多的，即3255CC．规定1nnC，01nC．五、插板法一般用来解决求分解一定数量的无差别物体的方法的总数，使用插板法一般有三个要求：①所要分解的物体一般是相同的：②所要分解的物体必须全部分完：③参与分物体的组至少都分到1个物体，不能有没分到物体的组出现．在有些题目中，已知条件与上面的三个要求并不一定完全相符，对此应当对已知条件进行适当的变形，使得它与一般的要求相符，再适用插板法．六、使用插板法一般有如下三种类型：⑴m个人分n个东西，要求每个人至少有一个．这个时候我们只需要把所有的东西排成一排，在其中的(1)n个空隙中放上(1)m个插板，所以分法的数目为11mnC．⑵m个人分n个东西，要求每个人至少有a个．这个时候，我们先发给每个人(1)a个，还剩下[(1)]nma个东西，这个时候，我们把剩下的东西按照类型⑴来处理就可以了．所以分法的数目为1(1)1mnmaC．⑶m个人分n个东西，允许有人没有分到．这个时候，我们不妨先借来m个东西，每个人多发1个，这样就和类型⑴一样了，不过这时候物品总数变成了()nm个，因此分法的数目为11mnmC．1.使学生正确理解排列、组合的意义；正确区分排列、组合问题；2.了解排列、排列数和组合数的意义，能根据具体的问题，写出符合要求的排列或组合；3.掌握排列组合的计算公式以及组合数与排列数之间的关系；4.会、分析与数字有关的计数问题，以及与其他专题的综合运用，培养学生的抽象能力和逻辑思维能力；通过本讲的学习，对排列组合的一些计数问题进行归纳总结，重点掌握排列与组合的联系和区别，并掌握一些排列组合技巧，如捆绑法、挡板法等。5.根据不同题目灵活运用计数方法进行计数。例1：小新、阿呆等七个同学照像，分别求出在下列条件下有多少种站法？（1）七个人排成一排；（2）七个人排成一排，小新必须站在中间.（3）七个人排成一排，小新、阿呆必须有一人站在中间.（4）七个人排成一排，小新、阿呆必须都站在两边.（5）七个人排成一排，小新、阿呆都没有站在边上.（6）七个人战成两排，前排三人，后排四人.（7）七个人战成两排，前排三人，后排四人.小新、阿呆不在同一排。【解析】（1）775040P（种）。（2）只需排其余6个人站剩下的6个位置．66720P（种）.（3）先确定中间的位置站谁，冉排剩下的6个位置．2×66P=1440(种)．（4）先排两边，再排剩下的5个位置，其中两边的小新和阿呆还可以互换位置．552240P(种)．（5）先排两边，从除小新、阿呆之外的5个人中选2人，再排剩下的5个人，25552400PP（种）.（6）七个人排成一排时，7个位置就是各不相同的．现在排成两排，不管前后排各有几个人，7个位置还是各不相同的，所以本题实质就是7个元素的全排列．775040P（种）.（7）可以分为两类情况：“小新在前，阿呆在后”和“小新在前，阿呆在后”，两种情况是对等的，所以只要求出其中一种的排法数，再乘以2即可．4×3×55P×2=2880(种)．排队问题，一般先考虑特殊情况再去全排列。例2：用1、2、3、4、5、6可以组成多少个没有重复数字的个位是5的三位数？【解析】个位数字已知，问题变成从从5个元素中取2个元素的排列问题，已知5n，2m，根据排列数公式，一共可以组成255420P(个)符合题意的三位数。例3：用1、2、3、4、5这五个数字，不许重复，位数不限，能写出多少个3的倍数？【解析】按位数来分类考虑：⑴一位数只有1个3；⑵两位数：由1与2，1与5，2与4，4与5四组数字组成，每一组可以组成22212P(个)不同的两位数，共可组成248(个)不同的两位数；⑶三位数：由1，2与3；1，3与5；2，3与4；3，4与5四组数字组成，每一组可以组成333216P(个)不同的三位数，共可组成6424(个)不同的三位数；⑷四位数：可由1，2，4，5这四个数字组成，有44432124P(个)不同的四位数；⑸五位数：可由1，2，3，4，5组成，共有5554321120P(个)不同的五位数．由加法原理，一共有182424120177(个)能被3整除的数，即3的倍数．例4：某管理员忘记了自己小保险柜的密码数字，只记得是由四个非0数码组成，且四个数码之和是9，那么确保打开保险柜至少要试几次？【解析】四个非0数码之和等于9的组合有1，1，1，6；1，1，2，5；1，1，3，4；1，2，2，4；1，2，3，3；2，2，2，3六种。第一种中，可以组成多少个密码呢？只要考虑6的位置就可以了，6可以任意选择4个位置中的一个，其余位置放1，共有4种选择；第二种中，先考虑放2，有4种选择，再考虑5的位置，可以有3种选择，剩下的位置放1，共有4312(种)选择同样的方法，可以得出第三、四、五种都各有12种选择．最后一种，与第一种的情形相似，3的位置有4种选择，其余位置放2，共有4种选择．综上所述，由加法原理，一共可以组成412121212456(个)不同的四位数，即确保能打开保险柜至少要试56次．例5：两对三胞胎喜相逢，他们围坐在桌子旁，要求每个人都不与自己的同胞兄妹相邻，(同一位置上坐不同的人算不同的坐法)，那么共有多少种不同的坐法？【解析】第一个位置在6个人中任选一个，有166C(种)选法，第二个位置在另一胞胎的3人中任选一个，有133C(种)选法．同理，第3，4，5，6个位置依次有2，2，1，1种选法．由乘法原理，不同的坐法有11111163221163221172PPPPPP(种)。例6：一种电子表在6时24分30秒时的显示为6:24：30，那么从8时到9时这段时间里，此表的5个数字都不相同的时刻一共有多少个?【解析】设A:BCDE是满足题意的时刻，有A为8，B、D应从0，1，2，3，4，5这6个数字中选择两个不同的数字，所以有26P种选法，而C、E应从剩下的7个数字中选择两个不同的数字，所以有27P种选法，所以共有26P×27P=1260种选法。从8时到9时这段时间里，此表的5个数字都不相同的时刻一共有1260个。例7：一个六位数能被11整除，它的各位数字非零且互不相同的．将这个六位数的6个数字重新排列，最少还能排出多少个能被11整除的六位数?【解析】设这个六位数为abcdef，则有()ace、()bdf的差为0或11的倍数．且a、b、c、d、e、f均不为0，任何一个数作为首位都是一个六位数。先考虑a、c、e偶数位内，b、d、f奇数位内的组内交换，有33P×33P=36种顺序；再考虑形如badcfe这种奇数位与偶数位的组间调换，也有33P×33P=36种顺序。所以，用均不为0的a、b、c、d、e、f最少可排出36+36=72个能被11整除的数(包含原来的abcdef)。所以最少还能排出72-1=71个能被11整除的六位数。例8：已知在由甲、乙、丙、丁、戊共5名同学进行的手工制作比赛中，决出了第一至第五名的名次．甲、乙两名参赛者去询问成绩，回答者对甲说：“很遗憾，你和乙都未拿到冠军．”对乙说：“你当然不会是最差的．”从这个回答分析，5人的名次排列共有多少种不同的情况？【解析】这道题乍一看不太像是排列问题，这就需要灵活地对问题进行转化．仔细审题，已知“甲和乙都未拿到冠军”，而且“乙不是最差的”，也就等价于5人排成一排，甲、乙都不站在排头且乙不站在排尾的排法数，因为乙的限制最多，所以先排乙，有3种排法，再排甲，也有3种排法，剩下的人随意排，有333216P(种)排法．由乘法原理，一共有33654(种)不同的排法。例9：4名男生，5名女生，全体排成一行，问下列情形各有多少种不同的排法：⑴甲不在中间也不在两端；⑵甲、乙两人必须排在两端；⑶男、女生分别排在一起；⑷男女相间．【解析】⑴先排甲，9个位置除了中间和两端之外的6个位置都可以，有6种选择，剩下的8个人随意排，也就是8个元素全排列的问题，有888765432140320P(种)选择．由乘法原理，共有640320241920(种)排法．⑵甲、乙先排，有22212P(种)排法；剩下的7个人随