hao《排列与组合》.ppt

引例引例 问问问问题题题题1 1 从甲、乙、丙3名同学中选出2名参加某天的一项活动，其中1名同学参加上午的活动，1名同学参加下午的活动，有多少种不同的方法？第1步，确定参加上午活动的同学，从3人中任选1人有3种方法；第2步，确定参加下午活动的同学，只能从余下的2人中选，有2种方法 根据分步计数原理分步计数原理分步计数原理分步计数原理，共有：326 种不同的方法解决这个问题，需分2 2个步骤个步骤个步骤个步骤：问题问题2 2：从：从a a、b b、c c这这3 3个字母中，每次个字母中，每次取出取出2 2个按顺序排成一列，共有多少种不同个按顺序排成一列，共有多少种不同的排法？并列出所有不同的排法。的排法？并列出所有不同的排法。这里的每一种排法就是一个排列。这里的每一种排法就是一个排列。一般地，从n个不同元素中取出m（mn）个元素，按照一定的顺序排成一列，叫做从n个不同元素中取出m个元素的一个排列排列排列排列 排列的定义中包含两个基本内容：一是“取出元素取出元素取出元素取出元素”；二是“按照一定顺序排列按照一定顺序排列按照一定顺序排列按照一定顺序排列”“一定顺序”就是与位置有关，这也是判断一个问题是不是排列问题的重要标志 根据排列的定义，两个排列相同两个排列相同两个排列相同两个排列相同，当且仅当这两个排列的元素完全相同，而且元素的排列顺序也完全相同排列定义排列定义 如果两个排列所含的元素不完全一样，那么就可以肯定是不同的排列；如果两个排列所含的元素完全一样，但摆的顺序不同，那么也是不同的排列不同的排列不同的排列不同的排列 练习练习1下列问题中哪些是排列问题？如果是在题后括号内打“”，否则打“”练习练习 （1）某商场有4个大门，若从一个门进去，购物后从一个门出来，有多少种不同的出入方式？（）（2）平面内有8个点，其中任意3点不共线，由这些点可得到多少条射线？（）（3）平面内有8个点，其中任意3点不共线，由这些点可得到多少条直线？（）从从n n个不同的元素中取出个不同的元素中取出m(mn)m(mn)个元素个元素的所有排列的个数，叫做从的所有排列的个数，叫做从n n个不同的元素中个不同的元素中取出取出m m个元素的排列数。用符号个元素的排列数。用符号 表示。表示。从从n n个不同元素中取出个不同元素中取出2 2个元素的排列数个元素的排列数 是多少？是多少？呢？呢？呢？呢？问题问题1：从：从3个不同的元素中取出个不同的元素中取出2个元素的排列个元素的排列数数,记为记为 问题问题2：从从4个不同的元素中取出个不同的元素中取出3个元素的排个元素的排列数列数,记为记为 1.1.排列数公式的特点：第一个因数是排列数公式的特点：第一个因数是n,后面每一个因后面每一个因数比它前面一个因数少数比它前面一个因数少1,1,最后一个因数是最后一个因数是nm1,1,共共有有m个因数个因数 阶乘变形阶乘变形 例例2：化简：化简：1!22!+33!+nn!排列问题，是取出m个元素后，还要按一定的顺序排成一列，取出同样的m个元素，只要排列顺序不排列顺序不排列顺序不排列顺序不同同同同，就视为完成这件事的两种不同的方法（两个不同的排列）小结小结 由排列的定义可知，排列与元素的顺序有关排列与元素的顺序有关排列与元素的顺序有关排列与元素的顺序有关，也就是说与位置有关的问题才能归结为排列问题当元素较少时，可以根据排列的意义写出所有的排列 排列与组合复习排列与组合复习 从从n个不同的元素中，任取个不同的元素中，任取A个元素，个元素，按照一定的顺序排成一列，叫做从按照一定的顺序排成一列，叫做从n个个不同的元素中取出不同的元素中取出A个元素的一个个元素的一个 排列排列。排列与排列数排列与排列数所有排列的个数叫做所有排列的个数叫做 排列数排列数，用，用表示。表示。判断判断下列几个问题是不是排列问题下列几个问题是不是排列问题?从班级从班级5名优秀团员中选出名优秀团员中选出3人参加上午的团委会人参加上午的团委会1000本参考书中选出本参考书中选出100本本给给100位同学每人一本位同学每人一本1000名来宾中选名来宾中选20名贵宾分名贵宾分别坐别坐120号贵宾席号贵宾席解179(r+36)(x-1)1）由数字由数字1，2，3，4，5 组成没有重复数字的组成没有重复数字的五位数，其中偶数共有五位数，其中偶数共有 个。个。2）用用 0，1，2，3，4，5 组成没有重复数字的组成没有重复数字的三位数，共有三位数，共有 个。个。3）五名同学排成一排，其中的甲乙两同学必五名同学排成一排，其中的甲乙两同学必须站在两端须站在两端，共有，共有 种不同排法。种不同排法。4810012例例2例例 3 若若 ,则则 方方 程程 可可表表示示多多少少个个焦焦点点在在 x轴轴上上的的相相异异椭椭圆圆.例例4 从从1到到6这这六六个个数数字字中中任任取取5个个数数字字组组成成没没有有重重复复数数字字的的五五位位数数,且且个个位位和和百百位位必必须须是是奇奇数数,这这样样的的五五位位数数共共有有多多少少个个?万万千千百百十十个个万万千千百百十十个个万万千千百百十十个个解解法法一一:N=144个个解解法法二二:N=-=144个个 用用1、2、3、4、5组成没有重复数字的组成没有重复数字的四位数。四位数。(1)十位数字比个位数字大的数有多少个十位数字比个位数字大的数有多少个？(2)将这些数字按从小到大的顺序排列将这些数字按从小到大的顺序排列,2351是第几位？是第几位？有有条条件件的的排排列列问问题题有有条条件件的的排排列列问问题题 例例5 5 七个家庭一起外出旅游，若其中四家是一个男孩，三家是一个女孩，现将这七个小孩站成一排照相留念。a)若三个女孩要站在一起，有多少种不同的排法？解：将三个女孩看作一人与四个男孩排队，有 种排法，而三个女孩之间有 种排法，所以不同的排法共有：（种）。捆捆 绑绑 法法有有条条件件的的排排列列问问题题 七个家庭一起外出旅游，若其中四家是男孩，三家是女孩，现将这七个小孩站成一排照相留念。b)若三个女孩要站在一起，四个男孩也 要站在一起，有多少种不同的排法？不同的排法有：（种）说一说说一说捆绑法一般适用于 问题的处理。相邻相邻有有条条件件的的排排列列问问题题 七个家庭一起外出旅游，若其中四家是男孩，三家是女孩，现将这七个小孩站成一排照相留念。c)若三个女孩互不相邻，有多少种不同的排法？解：先把四个男孩排成一排有 种排法，在每一排列中有五个空档（包括两端），再把三个女孩插入空档中有 种方法，所以共有：（种）排法。有有条条件件的的排排列列问问题题 七个家庭一起外出旅游，若其中四家是男孩，三家是女孩，现将这七个小孩站成一排照相留念。c)若三个女孩互不相邻，有多少种不同的排法？插插 空空 法法有有条条件件的的排排列列问问题题 七个家庭一起外出旅游，若其中四家是男孩，三家是女孩，现将这七个小孩站成一排照相留念。d)若三个女孩互不相邻，四个男孩也互不相邻，有多少种不同的排法？不同的排法共有：（种）说一说说一说插空法一般适用于 问题的处理。互不相邻互不相邻B*有有条条件件的的排排列列问问题题 七个家庭一起外出旅游，若其中四家是男孩，三家是女孩，现将这七个小孩站成一排照相留念。e)若其中的A小孩必须站在B小孩的左边，有多少种不同的排法？BAA解：A在B左边的一种排法必对应着A在B右边的一种排法，所以在全排列中，A在B左边与A在B右边的 排 法 数 相 等，因 此 有：排法。（种）有有条条件件的的排排列列问问题题 七个家庭一起外出旅游，若其中四家是男孩，三家是女孩，现将这七个小孩站成一排照相留念。e)若其中的A小孩必须站在B小孩的左边，有多少种不同的排法？BA对对应应思思想想有有条条件件的的排排列列问问题题 七个家庭一起外出旅游，若其中四家是男孩，三家是女孩，现将这七个小孩站成两排两排照相留念。f）若前排站三人，后排站四人，其中的A.B两小孩必须站前排且相邻，有多少种不同的排法？AB解：A，B两小孩的站法有：（种），其余人的站法有 （种），所以共有 （种）排法。例6 某班一天有数学、语文、物理、英某班一天有数学、语文、物理、英语、语、体育、自习六节课体育、自习六节课,按下例要求排课表按下例要求排课表,分别有分别有多少种不同的排法？多少种不同的排法？(1)第一节不排体育第一节不排体育,自习。自习。(2)体育不排在首末。体育不排在首末。(3)数学不排在下午两节数学不排在下午两节,体育不排在一体育不排在一,四节。四节。解排列问题问题时，当问题分成互斥各类时，根据加法原理，可用分类法；当问题考虑先后次序 时，根据乘法原理，可用位置法；这两种方法又称作直接法当问题的反面简单明了时，可通过求差 排除采用间接法求解；另外，排列中“相邻”问题可以用“捆绑法”；“分离”问题可能用“插空法”等 解排列问题和组合问题，一定要防止“重复”与“遗漏”互斥分类分类法 先后有序位置法 反面明了排除法 相邻排列捆绑法 分离排列插空法 例1 求不同的排法种数：（1）6男2女排成一排，2女相邻；（2）6男2女排成一排，2女不能相邻；（3）4男4女排成一排，同性者相邻；（4）4男4女排成一排，同性者不能相邻组组 合合 从n个不同元素中取出m(mn)个元素并成一组,叫做从n个不同元素中取出m个元素的一个组合一个组合两个组合的元素完全相同为相同组合注注n个不同元素mn组合与元素的顺序无关排列与元素的顺序有关 从n个不同元素中取出m(mn)个元素的所有组合的个数,叫做从n个不同元素中取出m个元素的组合数组合数表示方法表示方法CmnC Cn nm m=A An nm mA Am mm m=n(n-1)(n-2)n(n-1)(n-2)(n-m+1)(n-m+1)mm判断判断 下列几个问题下列几个问题是排列问题还是是排列问题还是组合问题组合问题?四个足球队举行单循环比赛四个足球队举行单循环比赛(每两队比赛一每两队比赛一场场)共有多少种比赛共有多少种比赛?四个足球队举行单循环比赛的所有冠亚军四个足球队举行单循环比赛的所有冠亚军的可能性情况有多少种的可能性情况有多少种?从从2,3,4,5,6中任取两数构成指数中任取两数构成指数,有多少个有多少个不同的指数不同的指数?从从2,3,4,5,6中任取两数相加中任取两数相加,有多少个不同有多少个不同的结果的结果?十个人相互通了一封信十个人相互通了一封信,共有多少封信共有多少封信?十个人相互通了一次电话十个人相互通了一次电话,共打了多少个电话共打了多少个电话?例1 计算计算:C10 7(2)C7 4(1)C例2 求证求证 mCnCn m+1=m+1n-m应用举例应用举例例例3 从数字从数字1,2,5,7中任选两个中任选两个 (1)可以得到多少个不同的和可以得到多少个不同的和?(2)可以得到多少个不同的差可以得到多少个不同的差?例例4 有不同的英文书有不同的英文书5本本,不同的中文书不同的中文书7本本,从中选从中选出两本书出两本书.(1)若其中一本为中文书若其中一本为中文书,一本为英文书一本为英文书.问共有多少问共有多少种选法种选法?(2)若不限条件若不限条件,问共有多少种选法问共有多少种选法?例例5 有有12名划船运动员名划船运动员,其中其中3人只会划左舷人只会划左舷,4人只人只会划右舷会划右舷,其它其它5人既会划左舷人既会划左舷,又会划右舷又会划右舷,现要从现要从这这12名运动员中选出名运动员中选出6人平均分在左右舷参加划船比人平均分在左右舷参加划船比赛赛,有多少种不同的选法有多少种不同的选法?例例6 在在MON的边的边OM上有上有5个异于个异于O点的点点的点,ON上上有有4个异于个异于O点的点点的点,以这十个点以这十个点(含含O)为顶点为顶点,可以得可以得到多少个三角形到多少个三角形?NOMABCDEFGHI思思 考考:如图如图,在以在以AB为直径的半圆周上有异于为直径的半圆周上有异于A,B的六个点的六个点C1,C2,C3,C4,C5 ,C6 ,AB上有异于上有异于A,B的四个点的四个点D1,D2 ,D3 ,D4,问问 (1)以这以这10个点中的个点中的3个点为顶点可作多少个三角个点为顶点可作多少个三角形形?(2)以图中以图中12个点个点(包括包括A,B)中的四个为顶点中的四个为顶点,可作可作多少个四边形多少个四边形?ABD1D2D3D4C1C2C3C4C5C6