1.2排列与组合

排列与组合排列N=m1+m2+…+mn做一件事情，完成它可以有n类办法,在第一类办法中有m1种不同的方法，在第二类办法中有m2种不同的方法，……，在第n类办法中有mn种不同的方法。那么完成这件事共有.种不同的方法分类加法计数原理N=m1×m2×…×mn做一件事情，完成它需要分成n个步骤，做第一步有m1种不同的方法，做第二步有m2种不同的方法，……，做第n步有mn种不同的方法，那么完成这件事有_____________________种不同的方法.分步乘法计数原理上节例9随着人们生活水平的提高，某城市家庭汽车拥有量迅速增长，汽车牌照号码需要扩容.交通管理部门出台了一种汽车牌照组成方法，每一个汽车牌照都必须有3个不重复的英文字母和3个不重复的阿拉伯数字，并且3个字母必须合成一组出现，3个数字也必须合成一组出现.那么这种办法共能给多少辆汽车上牌照？解：将汽车牌照分为2类，一类的字母组合在左，另一类的字母组合在右．字母组合在左时，分6个步骤确定一个牌照的字母和数字：第1步,从26个字母中选1个,放在首位,有26种选法;第2步,从剩下的25个字母中选1个,放在第2位,有25种选法;第3步,从剩下的24个字母中选1个,放在第3位,有24种选法;第4步,从10个数字中选1个,放在第4位,有10种选法;第5步,从剩下的9个数字中选1个,放在第5位,有9种选法;第6步,从剩下的8个字母中选1个,放在第6位,有8种选法;根据分步乘法计数原理，字母组合在左的牌照共有:26×25×24×10×9×8=11232000个.同理，字母组合在右的牌照也有11232000个．所以，共能给11232000+11232000=22464000(个)辆汽车上牌照.例9中我们看到,用分步乘法计数原理解决这个问题时,因做了一些重复性工作而显得繁琐,能否对这一类计数问题给出一种简捷的方法呢?问题1：从甲、乙、丙3名同学中选出2名参加一项活动，其中1名同学参加上午的活动，另名同学参加下午的活动，有多少种不同的选法？分析：把题目转化为从甲、乙、丙3名同学中选2名，按照参加上午的活动在前，参加下午的活动在后的顺序排列，求一共有多少种不同的排法？上午下午相应的排法甲乙丙乙甲丙丙甲乙甲丙甲乙乙甲乙丙丙甲丙乙第一步：确定参加上午活动的同学即从3名中任选1名，有3种选法.第二步：确定参加下午活动的同学，有2种方法根据分步计数原理：3×2=6即共6种方法。把上面问题中被取的对象叫做元素,于是问题１就可以叙述为：从3个不同的元素a,b,c中任取2个，然后按照一定的顺序排成一列，一共有多少种不同的排列方法？ab,ac,ba,bc,ca,cb问题2：从1，2，3，4这4个数中，每次取出3个排成一个三位数，共可得到多少个不同的三位数？分析：解决这个问题分三个步骤：第一步先确定左边的字母，在4个字母中任取1个，有4种方法；第二步确定中间的字母，从余下的3个字母中取，有3种方法；第三步确定右边的字母，从余下的2个字母中取，有2种方法。根据分步乘法计数原理，共有4×3×2＝24种不同的排法。如下图所示有此可写出所有的三位数：123，124，132，134，142，143;213，214，231，234，241，243，312，314，321，324，341，342;412，413，421，423，431，432。同样，问题２可以归结为：从４个不同的元素a，b，c，d中任取３个，然后按照一定的顺序排成一列，共有多少种不同的排列方法？abc,abd,acb,acd,adb,adc;bac,bad,bca,bcd,bda,bdc;cab,cad,cba,cbd,cda,cdb;dab,dac,dba,dbc,dca,dcb.上面两个问题有什么共同特征？可以用怎样的数学模型来刻画？(1)有顺序的(2)不论是排列之前，还是之后，所有的元素都不相等?一般的，从n个不同的元素中取出m(m≤n)个元素，按照一定的顺序排成一列，叫做从n个不同元素中取出m个元素的一个排列。排列的定义：排列的特征(1)排列问题实际包含两个过程：①先从n个不同元素中取出m个不同的元素;②再把这m个不同元素按照一定的顺序排成一列.(2)两个排列相同的条件：①元素完全相同;②元素的排列顺序也相同.例如123与213为什么是不同的排列。例1下列问题中哪些是排列问题？（1）10名学生中抽2名学生开会的选法；（2）10名学生中选2名做正、副组长的选法；（3）从2,3,5,7,11中任取两个数相乘积的个数；（4）从2,3,5,7,11中任取两个数相除商的个数；（5）20位同学互通一次电话的次数；（6）以圆上的10个点为端点作弦的条数；（7）以圆上的10个点中的某一点为起点，作过另一个点的射线的条数；（8）有10个车站，共需要多少种车票；（9）安排5个学生为班里的5个班干部，每人一个职位.那些是全排列？排列中的注意点：1、元素不能重复。n个中不能重复，m个中也不能重复。2、“按一定顺序”就是与位置有关，这是判断一个问题是否是排列问题的关键。3、两个排列相同，当且仅当这两个排列中的元素完全相同，而且元素的排列顺序也完全相同。4、m＝n时的排列叫全排列。5、为了使写出的所有排列情况既不重复也不遗漏，最好采用“树形图”。排列数：mnA从n个不同的元素中取出m(m≤n)个元素的所有排列的个数，叫做从n个不同的元素中取出m个元素的排列数。用符号表示。“排列”和“排列数”有什么区别和联系？“一个排列”是指：从n个不同元素中，任取m个元素按照一定的顺序排成一列，不是数；mnA“排列数”是指从n个不同元素中，任取m个元素的所有排列的个数，是一个数；所以符号只表示排列数，而不表示具体的排列.23326A3443224A23A问题1中是求从3个不同元素中取出2个元素的排列数，记为:34A问题2中是求从4个不同元素中取出3个元素的排列数，记为:2nA从n个不同元素中取出2个元素的排列数是多少？第1位第2位nn-1An3An2)1(nn)2)(1(nnn第1位第2位第3位n-2nn-13nA同理可以这样计算)1()2()1(mnnnnAmn······第1位第2位第3位第m位nn-1n-2n-(m-1)1mn)(mnAmn一般地可以这样计算：排列数公式)1()2()1(mnnnnAmn,,mnNmn观察排列数公式有何特征：（1）第一个因数是n，后面每一个因数比它前面一个因数少1．（2）最后一个因数是n－m＋1．（3）共有m个因数．n个不同元素全部取出的一个排列，叫做n个元素的一个全排列，这时公式中的n=m，即有:123)2)(1(nnnAnn就是说，n个不同元素全部取出的排列数，等于正整数1到n的连乘积，正整数1到n的连乘积，叫做n的阶乘，用n!表示，！nAnn所以n个不同元素的全排列数公式可以写成另外，我们规定0!＝1)!(!mnn12)(12))(1()1(mnmnmnnn)1()2()1(mnnnnAmn例1计算：3101A）（5182A）（131318183AA）（我们发现：518A13131818AA这个结果有一般性吗？1415161569nA．17161554mnA例2(1)若,则n=，m=．解：（1）n=17，m=14．,nN(55)(56)(68)(69)nnnn(2)若则用排列数符号表示为．)16,,()16()1)(((3)axNaxxaxax9199A12nnA15a16xA9911109(1)用排列数公式表示：练习nn)1(1413(2)例3某年全国足球甲级（A组）联赛共有14个队参加，每队要与其余各队在主、客场分别比赛一次，求总共要进行多少场比赛.214A解：任意两队间进行1次主场比赛与1次客场比赛，对应于从14个元素中任取2个元素的一个排列．因此，比赛的总场次是=14×13=182.例4（1）从5本不同的书中选3本送给3名同学，每人各1本，共有多少种不同的送法？（2）从5种不同的书中买3本送给3名同学，每人各1本，共有多少种不同的送法？3560A=(种)35125=(种)百位十位个位解法一：直接法648899181919AAA6488992919AA或0是“特殊元素”，特殊元素要特殊（优先）处理。有限制条件的排列问题1特殊元素、特殊位置问题例5用0到9这十个数字，可以组成多少个没有重复数字的三位数？对排列方法分步思考。解法三：间接法.A310.648898910A310A29∴所求的三位数的个数是:求以0为排头的排列数为:A29从总数中去掉不合条件的排列的种数求总数：从0到9这十个数字中任取三个数字的排列数为:解法二：直接法322999648AAA．第一类：每一位数字都不是0的三位数有第二类：个位数字是0的三位数有第三类：十位数字是0的三位数有29A29A39A符合条件的三位数的个数是:小结一：对于“在”与“不在”等有特殊元素或特殊位置的排列问题，通常是先排特殊元素或特殊位置，称为优先处理特殊元素（位置）法（优限法）。练习用0,1,2,3,4,5可组成多少个无重复数字的1)五位数；2)六位偶数；3)大于213045的自然数.1)解1位置分析法：首位是特殊位置，0不能排，有5种排法,其余4个位置有A45种排法，由乘法原理知共有5·A45=5·5·4·3·2=6001)解2.（间接法）6个数中取5个数的排列中有不满足要求的数如02134等，O这样的数共有:A56-A45=600第二类个位不是0,个位有两种排法，首位有4种排法，中间四位有A44种排法，第二类共有2·4·A44=192,2)可分为两类，第一类是个位为0的有A55个;由加法原理共有A55+192=312练习用0,1,2,3,4,5可组成多少个无重复数字的大于213045的自然数.A13·A55A13·A44A12·A33A12·A22第五类：形如21054有一个因此满足要求的数共有449个第一类：形如3,4,5,这样的数都是满足条件的数共有：第二类：形如23，24，25这样的数都是满足条件的数共有：第三类：形如214,215这样的数都是满足条件的数共有：第四类：形如2134,2135的数有A66=720.共有A61A66=4320.,共有A61A66=4320.所以共有A77-A66=7A66-A66=4320.例6⑴7位同学站成一排，共有多少种不同的排法？A77＝5040.⑵7位同学站成一排，其中甲站在中间的位置，共有多少种不同的排法？解：问题可以看作：余下的6个元素的全排列解：问题可以看作：7个元素的全排列⑶7位同学站成一排，其中甲不站在首位，共有多少种不同的排法？解一：甲站其余六个位置之一有A61种，其余6人全排列有A66种，解二：从其他6人中先选出一人站首位，有A61剩下6人(含甲)全排列,有A66解三：7人全排列有A77,甲在首位的有A66解：根据分步计数原理：第一步甲,乙站在两端有则共有A22A55=240种排列方法①②③④⑤⑥⑦①②③④⑤⑥⑦甲乙乙甲abcdeebdcaA55A22例6(4)7位同学站成一排．甲、乙只能站在两端的排法共有多少种？A22种.第二步余下的5名同学进行全排列有A55种所以一共有A52A55＝2400种排列方法．例6(5)7位同学站成一排，甲、乙不能站在排头和排尾的排法共有多少种？解：第一步从（除去甲、乙）其余的5位同学中选2位同学站在排头和排尾有A52种方法第二步从余下的5位同学中选5位进行排列（全排列）有A55种方法3000551515AAA72066A例6(6)若甲不在排头,乙不在排尾,有多少种不同的排法?解法一（直接法）：以甲作为分类标准,分为两类：第一类：先安排甲在