1.2排列与组合1.ppt

1.2排列与组合,(一),1.2.1排列,教学目标：1.知道排列的有关概念及计算方法。并能解决一些简单应用题。2.推导排列数的两个公式，理解并掌握解决排列应用题的常用方法。3.培养学生一题多解和一题多变的能力。重点：理解概念，公式推导。难点：排列问题的综合应用,做一件事情，完成它可以有n类办法,在第一类办法中有m1种不同的方法，在第二类办法中有m2种不同的方法，在第n类办法中有mn种不同的方法。那么完成这件事共有.种不同的方法,N=m1+m2+mn,分类加法计数原理,N=m1m2mn,做一件事情，完成它需要分成n个步骤，做第一步有m1种不同的方法，做第二步有m2种不同的方法，做第n步有mn种不同的方法，那么完成这件事有_种不同的方法.,分步乘法计数原理,复习引入：,例9中我们看到,用分步乘法计数原理解决这个问题时,因做了一些重复性工作而显得繁琐,能否对这一类计数问题给出一种简捷的方法呢?,问题1：从甲、乙、丙3名同学中选出2名参加一项活动，其中1名同学参加上午的活动，另1名同学参加下午的活动，有多少种不同的选法？,分析：把题目转化为从甲、乙、丙3名同学中选2名，按照参加上午的活动在前，参加下午的活动在后的顺序排列，求一共有多少种不同的排法？,探究,为了寻求简便的计数方法，我们先来分析这类问题的两个简单例子.,甲丙,甲乙,乙甲,乙丙,丙甲,丙乙,第一步：确定参加上午活动的同学即从3名中任选1名，有3种选法.,第二步：确定参加下午活动的同学，有2种方法,根据分步计数原理：32=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种方法。,根据分步乘法计数原理，共有43224种不同的排法。如下图所示,有此可写出所有的三位数：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(mn)个元素，按照一定的顺序排成一列，叫做从n个不同元素中取出m个元素的一个排列。,排列的定义：,排列的特征,(1)排列问题实际包含两个过程：,先从n个不同元素中取出m个不同的元素;,再把这m个不同元素按照一定的顺序排成一列.,(2)两个排列相同的条件：,元素完全相同;,元素的排列顺序也相同.,例1下列问题中哪些是排列问题？,（1）10名学生中抽2名学生开会的选法；,（2）10名学生中选2名做正、副组长的选法；,（3）从2,3,5,7,11中任取；两个数相乘积的个数,（4）从2,3,5,7,11中任取两个数相除商的个数；,（6）以圆上的10个点为端点作弦的条数；,（7）以圆上的10个点中的某一点为起点，作过另一个点的射线的条数；,（8）有10个车站，共需要多少种车票；,（5）安排5个学生为班里的5个班干部，每人一个职位.,24578,“排列数”是指从n个不同元素中，任取m个元素的所有排列的个数，是一个数；所以符号只表示排列数，而不表示具体的排列.,排列数：,从n个不同的元素中取出m(mn)个元素的所有排列的个数，叫做从n个不同的元素中取出m个元素的排列数。用符号表示。,“排列”和“排列数”有什么区别和联系？,“一个排列”是指：从n个不同元素中，任取m个元素按照一定的顺序排成一列，不是数；,问题1中是求从3个不同元素中取出2个元素的排列数，记为:,问题2中是求从4个不同元素中取出3个元素的排列数，记为:,从n个不同元素中取出2个元素的排列数是多少？,同理可以这样计算,一般地可以这样计算：,（3）共有m个因数,排列数公式,观察排列数公式有何特征：,（1）第一个因数是n，后面每一个因数比它前面一个因数少1,（2）最后一个因数是nm1,n个不同元素全部取出的一个排列，叫做n个元素的一个全排列，这时公式中的n=m，即有:,就是说，n个不同元素全部取出的排列数，等于正整数1到n的连乘积，,正整数1到n的连乘积，叫做n的阶乘，用n!表示，,所以n个不同元素的全排列数公式可以写成,另外，我们规定0!1,例1计算：,17,14,例3某年全国足球甲级（A组）联赛共有14个队参加，每队要与其余各队在主、客场分别比赛一次，求总共要进行多少场比赛.,解：任意两队间进行1次主场比赛与1次客场比赛，对应于从14个元素中任取2个元素的一个排列因此，比赛的总场次是,=1413=182.,例4（1）从5本不同的书中选3本送给3名同学，每人各1本，共有多少种不同的送法？（2）从5种不同的书中买3本送给3名同学，每人各1本，共有多少种不同的送法？,(种),(种),解法一：直接法,0是“特殊元素”，特殊元素要特殊（优先）处理。,有限制条件的排列问题,1特殊元素、特殊位置问题,例5用0到9这十个数字，可以组成多少个没有重复数字的三位数？,对排列方法分步思考。,求总数：从0到9这十个数字中任取三个数字的排列数为:,解法三：间接法.,所求的三位数的个数是:,求以0为排头的排列数为:,从总数中去掉不合条件的排列的种数,解法二：直接法,第一类：每一位数字都不是0的三位数有,第二类：个位数字是0的三位数有,第三类：十位数字是0的三位数有,符合条件的三位数的个数是:,小结一：对于“在”与“不在”等有特殊元素或特殊位置的排列问题，通常是先排特殊元素或特殊位置，称为优先处理特殊元素（位置）法（优限法）。,练习（1）用0,1,2,3,4,5可组成多少个无重复数字的五位数；,解法1（位置分析法）首位是特殊位置，0不能排，有5种排法,其余4个位置有A45种排法，由乘法原理知共有5A45=55432=600,解法2.（间接法）6个数中取5个数的排列减去0排首位的排列，共有:A56-A45=600,第二类：个位不是0,个位有两种排法，首位有4种排法，中间四位有A44种排法，所以第二类共有24A44=192,解；可分为两类，,第一类：是个位为0的有A55个;,由加法原理共有A55+192=312,练习（2）用0,1,2,3,4,5可组成多少个无重复数字的六位偶数；,练习（3）用0,1,2,3,4,5可组成多少个无重复数字的大于213045的自然数.,A13A55,A13A44,A12A33,A12A22,第五类：形如213054有一个,因此满足要求的数共有449个,第一类：第一位排3或4或5,共有：,第二类:第一位排2，第二位排3或4或5，共有：,第三类：第一二位排21，第三位排4或5共有：,第四类：第一二三位排213第四位排4或5，共有,A66=720.,共有A61A66=4320.,共有A61A66=4320.,例67位同学站成一排，共有多少种不同的排法？,A775040.,7位同学站成一排，其中甲站在中间的位置，共有多少种不同的排法？,解：问题可以看作：余下的6个元素的全排列,解：问题可以看作：7个元素的全排列,7位同学站成一排，其中甲不站在首位，共有多少种不同的排法？,解法1：甲站其余六个位置之一有A61种，,其余6人全排列有A66种，,解法2：从其他6人中先选出一人站首位，有,A61,剩下6人(含甲)全排列,有,A66,解：根据分步计数原理：第一步甲,乙站在两端有,则共有A22A55=240种排列方法,例6(4)7位同学站成一排甲、乙只能站在两端的排法共有多少种？,A22种.,第二步余下的5名同学进行全排列有,A55种,解法3：7人全排列有,甲在首位的有,A66,所以共有A77-A66=7A66-A66=4320.,所以一共有A52A552400种排列方法,例6(5)7位同学站成一排，甲、乙不能站在排头和排尾的排法共有多少种？,解：第一步从（除去甲、乙）其余的5位同学中选2位同学站在排头和排尾有,A52种方法,第二步从余下的5位同学中选5位进行排列（全排列）有,A55种方法,例6(6)若甲不在排头,乙不在排尾,有多少种不同的排法?,解法一（直接法）：,以甲作为分类标准,分为两类：,第一类：先安排甲在中间,再安排乙,有,第二类：先安排甲在排尾,再安排其他人,有,共有：3720种方法,例6(6)若甲不在排头,乙不在排尾,有多少种不同的排法?,解法二（间接法）：,所有排法中除去不符合的.,所有排法：,甲在排头：,乙在排尾：,甲在排头、乙在排尾：,共有：,3720种方法,(7)7位同学站成两排(前3后4),共有多少种不同的排法？,解:可以看成是排成一排的全排列：=76543217！=5040.,有限制条件的排列问题,2相邻问题,(9)甲、乙两同学不能相邻的排法共有多少种？,例6(8)甲、乙两同学相邻的排法共有多少种？,解:甲、乙合在一起有A22种排法,与另五个同学全排列有A66种排法，,共有N=A22A66=720,捆绑法,3不相邻问题,解法一：间接法,(11)甲、乙、丙按指定顺序排列。,(10)甲、乙和丙三个同学都不能相邻的排法共有多少种？,解法二：先将其余五个同学排好有:,再将甲、乙同学分别插入这六个“空位”有:,种方法，,此时他们留下六个“空位”，,种方法,插空法,A44A53=1440,其余四人在7个位置中选4个，有:,A74方法，,甲、乙和丙三个同学在其余3个位置中，只有一种方法,共有N=A741=840种站法.,练习1若有四个男孩和三个女孩站成一排照相：,若其中的A小孩必须站在B小孩的左边，有多少种不同的排法？,所以在全排列中，A在B左边与A在B右边的排法数相等,解:A在B左边的一种排法必对应着A在B右边的一种排法,插空法,若三个女孩要站在一起，四个男孩也要站在一起，有多少种不同的排法？,捆绑法,若三个女孩互不相邻，有多少种不同的排法？,解：先把四个男孩排成一排有A44种排法，,五个空档(包括两端)再把三个女孩插入空档中有A53种方法,插空法,练习2某人射击8枪，命中4枪，4枪命种恰好3枪连在一起的不同种数有多少？,解：连续命中的3枪和命中的另一枪被未命中的4枪所隔开，如图表示没有命中，,_,命中的三枪看作一个元素和另外命中的一枪共两个元素插到五个空档中有A52=54=20种排法,练习3.一排长椅上共有10个座位，现有4人就座，恰有五个连续空位的坐法种数为。（用数字作答）,480,如果女生全排在一起，有多少种不同排法？如果女生全分开，有多少种不同排法？如果两端都不能排女生，有多少种不同排法？如果两端不能都排女生，有多少种不同排法？,（1）A66A33=4320,（2）A55A63=14400,（3）A52A66=14400,（4）A52A66+2A31A51A66=36000或A88-A32A66=36000,练习5三名女生和五名男生排成一排，,例题7.同室4名学生各写一张贺卡，放在一起，然后各人从中各拿一张，但均不能拿自己写的那张，共有多少种拿法？,解法1：设四张货卡分别为a，b，c，d,由题意知，某人（不妨设为a卡的供卡人）取卡的情况有3种，据此将卡的分配方式分为3类，用树状图可得共有9种不同的分配方式。,解法2：让a，b，c，d四人依次拿一张别人送出的贺年卡，则可以分3步，,由乘法原理共有3311=9种拿法,第一步，a先拿，有3种不同的方法；,第三步，剩下的两人都各有一种取法；,第二步，让被a拿走的那张卡片的主人拿，有3种不同的方法；,练习7（1）.a,b,c,d排成一行，其中a不排第一，b不排第二，c不排第三，d不排第四的不同排法有多少种?（2）.有四张卡片，每张分别写着1，2，3，4，有四个空箱，分别写着号码1，2，3，4.把卡片放到空箱中，每箱必须且只能放一张，且卡片号码与箱子号码不一致，有多少种放法？,数学、体育均不排在第一节和第六节，有种,例8某天课表共六节课，要排政治、语文、数学、物理、化学、体育共六门课程，如果第一节不排体育，最后一节不排数学，共有多少种不同的排课方法？,第一类,数学排在第一节、体育排在第六节有种,第三类,第四类,其他有种，,共有种；,其他有种，,一,第二类,共有种；,数学排在第一节、体育不在第六节有种，,其他有种，,共有种；,数学不排在第一节、体育排在第六节有种，,其他有种，,共有种；,所以符合条件的排法共有种,对特殊元素:数学和体育进行分类解决.,例8某天课表共六节课，要排政治、语文、数学、物理、化学、体育共六门课程，如果第一节不排体育，最后一节不排数学，共有多少种不同的排课方法？,本题也可采用间接排除法解决,解法2：,不考虑任何限制条件共有种排法，,不符合题目要求的排法有：,（1）数学排在第六节有种；,（2）体育排在第一节有种；,考虑到这两种情况均包含了数学排在第六节和体育排在第一节的情况种,所以符合条件的排法共有种。,例9某校高三年级举行一次演讲赛共有10位同学参赛，其中一班有3位，二班有2位，其它班有5位，若采用抽签的方式确定他们的演讲顺序，则一班有3位同学恰好被排在一起（指演讲序号相连），而二班的2位同学没有被排在一起的概率为多少？,第一步:将一班的3位同学“捆绑”成一个大元素;,第二步:这个大元素与其它班5位同学共6个元素的全排列,第三步:这个大元素与其它班的5位同学共6个元素的全排列排好后产生的7个空挡中排列二班的2位同学;,第四步:“释放”一班的3位同学“捆绑”成的大元素，,解：符合要求的基本事件（排法）共有：,所以共有个；,而基本事件总数为个;,所以符合条件的概率为,例10：在由数字0，1，2，3，4，5所组成的没有重复数字的四位数中，不能被5整除的数共有个.,解：本题在解答时只须考虑个位和千位这两个特殊位置的限制;,个位为1、2、3、4中的某一个有4种方法;,十位和百位方法数为种,千位在余下的4个非0数中选择也有4种方法，,故方法总数为种,例11.用1、2、3、4、5、6、7、8组成没有重复数字的八位数，要求1和2相邻，3与4相邻，5与6相邻，而7与8不相邻，这样的八位数共有个.（用数字作答）,解：,第一步:将1和2“捆绑”成一个大元素，3和4“捆绑”成一个大