排列组合教材分析ppt课件

排列组合教材分析,四色问题,任意一张地图，用一种颜色对一个地区着色，那么一共只需要四种颜色就能保证每两个相邻的地区颜色不同。,稳定的婚姻问题,如果一个村子里每一个女孩都恰好认识k个男孩，并且每一个男孩也恰好认识k个女孩，那么每一个女孩都可以嫁给她认识的一个男孩，并且每一个男孩都可以娶一个他认识的女孩.,稳定的婚姻问题,但是这样的婚姻安排方法不一定是最好的。假如能找到两对夫妇，彼此都更喜欢对方的配偶，那么这样婚姻有潜在的不稳定性。我们能用某种数学算法找到一种婚姻的安排方法，使得没有上述的不稳定情况出现。,稳定的婚姻问题,这种方法有一个实际的用途：美国的医院在确定录取住院医生时，他们将考虑申请者的志愿的先后次序，同时也给申请者排序。按这样的次序，利用上述算法得出的总的方案将没有医院和申请者两者同时后悔的情况。,相识问题,1958年，美国的数学月刊上登载着这样一个有趣的问题：“任何6个人的聚会，其中总会有3个人相互认识，或3个人相互不认识”。用6个顶点表示6个人，用红色连线表示两者相识，用绿色连线表示两者不相识。于是问题化为下述命题：,相识问题,对有六边形的任意两个顶点之间用红、绿色连线，则图中一定存在一个三边同色的三角形。,过河问题,船夫要把一匹狼、一只羊和一棵白菜运过河。只要船夫不在场，羊就会吃白菜、狼就会吃羊。船夫的船每次只能运送一种东西。怎样运才能把所有东西都安全运过河？,组合数学有人认为广义的组合数学就是离散数学，也有人认为离散数学是狭义的组合数学和图论、数理逻辑等的总称。但这只是不同学者在说法上的不同。总之，组合数学是一门研究离散对象的科学。随着计算机科学的日益发展，组合数学的重要性也日渐凸显，因为计算机科学的核心内容是使用算法处理离散数据。,可以这样说，组合数学的发展奠定了本世纪计算机革命的基础。它的发展改变了传统数学中分析和代数占统治地位的局面。组合数学不仅在基础数学研究中具有极其重要的地位，在其它很多的学科中也有重要的应用，如计算机科学、编码和密码学、物理、化学、生物等学科中均有重要应用。,排列组合是学习组合数学的最初步的知识，它不仅在实际生产生活中应用广泛，而且也是我们后面学习概率统计知识的预备知识。同时排列组合以计算完成事件的方法、种数为特征，思想方法独特灵活，所以它也是发展学生抽象能力和逻辑思维能力的好素材。,两个基本原理,组合,排列数公式,组合数公式,组合数性质,应用问题,一、知识结构,排列,二、学习要求,1、掌握分类计数原理与分步计数原理，并能应用它们来分析和解决一些应用问题。2、理解排列与组合的意义，掌握排列数和组合数的计算公式，掌握组合数的两个性质，并能应用它们解决应用问题。,三、学习指导,1、本章的重点内容是两个计数原理，排列和组合的意义，排列数和组合数的计算公式。2、本章的应用题的解决思路主要是：正向思考和逆向思考，正向思考时，可通过“分类”或“分步”，对稍复杂的问题进行分解；逆向思考时用集合的观点看，就是先从问题涉及的集合在全集的补集入手，使问题得到简化。3、注意排列和组合的内在联系和区别，计算应用题时避免重复和遗漏。,10.1两个基本原理,这两个原理是人们在大量实践经验的基础上归纳出来的基本规律，它体现了我们将复杂问题简单化的两种常用方法：将问题分类解决或是分步解决。这两个原理既是推导排列数和组合数公式的依据，而且其基本的思想方法贯穿在解决本章应用问题的始终。,分类计数原理,问题1.从甲地到乙地，可以乘火车，也可以乘汽车，还可以乘轮船。一天中，火车有4班,汽车有2班，轮船有3班。那么一天中乘坐这些交通工具从甲地到乙地共有多少种不同的走法?,分析:从甲地到乙地有3类方法,第一类方法,乘火车，有4种方法;第二类方法,乘汽车，有2种方法;第三类方法,乘轮船,有3种方法;所以从甲地到乙地共有4+2+3=9种方法。,分步计数原理,2.如图,由A村去B村的道路有3条，由B村去C村的道路有2条。从A村经B村去C村，共有多少种不同的走法?,A村,B村,C村,北,南,中,北,南,分析:从A村经B村去C村有2步,第一步,由A村去B村有3种方法,第二步,由B村去C村有2种方法,所以从A村经B村去C村共有32=6种不同的方法。,分类计数原理做一件事情，完成它可以有n类办法,在第一类办法中有m1种不同的方法,在第二类办法中有m2种不同的方法，在第n类办法中有mn种不同的方法。那么完成这件事共有N=m1+m2+mn种不同的方法。,分步计数原理做一件事情，完成它需要分成n个步骤，做第一步有m1种不同的方法，做第二步有m2种不同的方法，做第n步有mn种不同的方法，那么完成这件事有N=m1m2mn种不同的方法。,两个原理的区别与联系：,例：书架上层有5本不同的数学书，下层有4本不同的语文书，则(1)从书架上任取一本书，有多少种取法？(2)从两层中各取一本书，有多少种取法？,10.2排列,本小节的知识体系在本章中处于承上启下的重要地位，它既在推导排列数公式的过程中使分步计数原理获得了重要应用，又使排列数公式成为推导组合数公式的主要依据。从而为我们以后学习概率统计知识打下基础。,排列的定义：从n个不同元素中取出m(mn)个元素，按照一定的顺序排成一列，叫做从n个不同元素中取出m个元素的一个排列。,排列数的定义：,从n个不同元素中取出m(mn)个元素的所有排列的个数，叫做从n个不同元素中取出m个元素的排列数，用符号表示。,1,2,3,m,n-1,n,n-2,n-m+1,n-0,n-(m-1),排列数公式：,全排列：n个不同的元素全部取出的一个排列叫做n个不同元素的一个全排列。,全排列数公式：,10.3组合,本节内容与本章其它内容均有密切联系：组合与排列研究的问题是平行的，组合数公式的推导要依据排列数公式；二项式系数就是一组有规律的组合数，推导二项式定理用到了组合数的性质；求等可能性事件的概率时，常常要涉及到组合数的计算。,组合的定义,一般地说，从n个不同元素中，任取m(mn)个元素并成一组，叫做从n个不同元素中取出m个元素的一个组合。,组合数的定义,从n个不同元素中取出m(mn)个元素的所有组合的个数，叫做从n个不同元素中取出m个元素的组合数，用符号表示。,组合数公式,组合数的性质,排列和组合的区别和联系：,从n个不同元素中取出m个元素，按一定的顺序排成一列,从n个不同元素中取出m个元素，把它并成一组,所有排列的个数,所有组合的个数,例：某班有40名学生，(1)从中选出两名同学分别担任正副班长，有多少种选法？(2)从中选出两名同学代表去参加会议，有多少种选法？,排列组合应用题分析,一.特殊元素(位置)优先排（）例1.1名老师和4名学生排成一排，若老师不排在两端，则共有多少种不同的排法？,二.元素必相邻问题捆绑法（）例2.3个女生与5个男生排在一起，女生必须排在一起，可以有多少种不同的方法？,三.不相邻问题插空法（）例3.7人排成一排照相，若要求甲、乙、丙三人不相邻，有多少种不同的排法？,四.排列中部分元素顺序固定除法（）例4.7个节目，甲、乙、丙三个节目按给定顺序出现，有多少种排法？,五.允许重复的排列问题选择权（）例5.(1)将3封不同的信投入4个不同的信箱，有多少种不同的投法？(2)4名学生报名参加数学、物理、化学三个课外小组，有多少种不同的报名方法？,分析:(1)中投信的人有选择权，所以投每封信都有4种可能，共有444种投法。(2)中学生有选择权，所以每名同学报名都有3种可能，共有3333种报名方法。,六.圆排列问题例6.5人围着一张圆桌而坐,共有多少种坐法?,分析：围桌而坐与坐成一排的不同点在于，坐成圆形没有首尾之分，所以固定一人A并从此位置把圆形展成直线，其余4人共有种排法。,一般地,n个不同元素作圆形排列,共有(n-1)!种排法.如果从n个不同元素中取出m个元素作圆形排列共有个。,七.多排问题等同于单排考虑（）例7.15人排成两排，前排7人，后排8人，共有多少种不同的方法？,再如：8人排成前后两排,每排4人,其中甲乙在前排,丁在后排,共有多少排法？,八.排列组合混合问题先选后排（）例8.9名乒乓球运动员，其中男5名，女4名，现在要进行混合双打训练，有多少种不同分组法？,九.利用集合思想解决（）例9.从6名运动员中选出4个参加4100m接力赛，如果甲不跑第一棒，乙不跑第四棒，共有多少种不同参赛方法？,分析：设全集6人中任取4人参赛的排列，A甲第一棒的排列，B乙跑第四棒的排列，根据求集合元素个数的公式得参赛方法共有：,十.元素无差别问题隔板法例10.将10个相同的球放入3个不同的盒子中，(1)每个盒子不空，有多少种不同的放法？(2)盒子可以是空的，有多少种不同的放法？,隔板法可推广到n个球，放到m个盒子中去的一般情况：若盒子非空，则方法数为若盒子可以为空，则方法数为，即从m+n个位置中选出m个位置放隔板，其余位置则放球。,上例可转化为：求方程xyz10的正整数解或非负整数解的个数。,再如：把10个相同的球放入三个不同的盒子中，使得每个盒子中的球数不少于2，则不同的放法有（）A、81种B、15种C、10种D、4种,十一.直接做法复杂间接法（）例11.从4台甲型和5台乙型电视机中任取出3台，其中至少要甲型和乙型电视机各一台，则不同取法共有A140种B80种C70种D35种,十二.分组问题例12.现有9名同学参加实验：(1)平均分三组，参加不同实验，有多少种分法？(2)平均分三组，参加相同实验，有多少种分法？(3)分三组，各组分别有2，3，4人，参加相同实验，有多少种分法？(4)分三组，各组分别有2，3，4人，参加不同实验，有多少种分法？(5)分三组，一组5人，其余每组各2人，参加相同实验，有多少种分法？(6)分三组，一组5人，其余每组各2人，参加不同实验，有多少种分法？,十三.利用分类讨论思想解决例13.在一次演唱会上共10名演员,其中8人能唱歌,5人会跳舞,现要演出一个2人唱歌2人伴舞的节目,有多少选派方法?,分析：10演员中有5人只会唱歌，2人只会跳舞,3人为全能演员。以只会唱歌的5人是否选上唱歌人员为标准进行分类，只会唱的5人中没有人选上唱歌人员共有_种,只会唱的5人中有1人选上唱歌人员_种,只会唱的5人中有2人选上唱歌人员有_种，由分类计数原理共有_种。,十四.化不熟悉问题为熟悉问题例14.马路上有编号为1,2,3,4,5,6,7,8,9的九只路灯,现要关掉其中的3盏,但不能关掉相邻的2盏或3盏,也不能关掉两端的2盏,求满足条件的关灯方法有多少种？,分析：将此问题转化为将三盏不亮的灯插入到亮着的六盏灯所形成的5个空隙中去解决，也就是不相邻问题，共有种可能。,再如：已知两个实数集A=a1，a2，a60与B=b1，b2，b25，若从A到B的映射f使得B中每个元素都有原象，且f（a1）f（a2）f（a60），则这样的映射共有多少个？,十五.穷举法例15.三边长均为整数，最长边为8的三角形有多少个？,分析：另两边用字母x、y表示，且不妨设1xy8，x+y9当y=8时，x=1,2,8,有8个。当y=7时，x=2,37有6个。当y=6时，x=3,4,5,6,有4个当y=5时，x=4,5,有2个。所以，所求的三角形的个数为8+6+4+2=20。,再如：四人各写出一张贺卡，先集中起来，然后每人从中拿一张别人送出的贺卡，则四张贺卡的不同分配方式有（B）种。A.6B.9C.11D.32,分析：ADCADBABCBCDACDABDCABDACDBACBA,十六.分解因式例16.30030能被多少个不同的偶数整除？,分析：先把30030分解成质因数的乘积形式30030=23571113。,十七.递推公式17.10人有相应的10个指纹档案，每个指纹档案上都记录有相应人的指纹痕迹，并有检测指示灯和检测时的手指按钮，10人某人把手指按在键钮上，若是他的档案，则指示灯出现绿色，否则出现红色，现在这10人把手指按在10个指纹档案的键钮上去检测，规定一个人只能在一个档案上去检测，并且两个人不能在同一档案上去检测，这时指示灯全部出现红色，这样的情况共有种。,十八.数形结合例18.25人排成55方队,现从中选3人,要求3人不在同一行也不在同一列,不同的选法有多少种？,又如：如图，从56方格中的顶点A到顶点B的最短线路有多少条？,上述问题可转化为：动点从（0，0）沿水平或竖直方向运动到达（6，5），要使行驶的路程最小，有多少种走法？,十九.立体几何中的排列组合（）例19.在四棱锥P