《排列组合教材分析参考》由会员分享，可在线阅读，更多相关《排列组合教材分析参考（66页珍藏版）》请在金锄头文库上搜索。
1、排列组合教材分析2021/3/101讲解：XX四色问题 任意一张地图，用一种颜色对一个地区着色，那么一共只需要四种颜色就能保证每两个相邻的地区颜色不同。2021/3/102讲解：XX稳定的婚姻问题 如果一个村子里每一个女孩都恰好认识k个男孩，并且每一个男孩也恰好认识k个女孩，那么每一个女孩都可以嫁给她认识的一个男孩，并且每一个男孩都可以娶一个他认识的女孩.2021/3/103讲解：XX稳定的婚姻问题 但是这样的婚姻安排方法不一定是最好的。假如能找到两对夫妇，彼此都更喜欢对方的配偶，那么这样婚姻有潜在的不稳定性。 我们能用某种数学算法找到一种婚姻的安排方法，使得没有上述的不稳定情况出现。2021
2、/3/104讲解：XX稳定的婚姻问题 这种方法有一个实际的用途：美国的医院在确定录取住院医生时，他们将考虑申请者的志愿的先后次序，同时也给申请者排序。按这样的次序，利用上述算法得出的总的方案将没有医院和申请者两者同时后悔的情况。2021/3/105讲解：XX相识问题 1958年，美国的数学月刊上登载着这样一个有趣的问题：“任何6个人的聚会，其中总会有3个人相互认识，或3个人相互不认识”。 用6个顶点表示6个人，用红色连线表示两者相识，用绿色连线表示两者不相识。于是问题化为下述命题：2021/3/106讲解：XX相识问题 对有六边形的任意两个顶点之间用红、绿色连线，则图中一定存在一个三边同色的三
3、角形。2021/3/107讲解：XX过河问题 船夫要把一匹狼、一只羊和一棵白菜运过河。只要船夫不在场，羊就会吃白菜、狼就会吃羊。船夫的船每次只能运送一种东西。怎样运才能把所有东西都安全运过河？ 2021/3/108讲解：XX 组合数学 有人认为广义的组合数学就是离散数学，也有人认为离散数学是狭义的组合数学和图论、数理逻辑等的总称。但这只是不同学者在说法上的不同。总之，组合数学是一门研究离散对象的科学。 随着计算机科学的日益发展，组合数学的重要性也日渐凸显，因为计算机科学的核心内容是使用算法处理离散数据。 2021/3/109讲解：XX 可以这样说，组合数学的发展奠定了本世纪计算机革命的基础。
4、它的发展改变了传统数学中分析和代数占统治地位的局面。 组合数学不仅在基础数学研究中具有极其重要的地位，在其它很多的学科中也有重要的应用，如计算机科学、编码和密码学、物理、化学、生物等学科中均有重要应用。 2021/3/1010讲解：XX 排列组合是学习组合数学的最初步的知识，它不仅在实际生产生活中应用广泛，而且也是我们后面学习概率统计知识的预备知识。 同时排列组合以计算完成事件的方法、种数为特征，思想方法独特灵活，所以它也是发展学生抽象能力和逻辑思维能力的好素材。2021/3/1011讲解：XX两个基本原理组合排列数公式组合数公式组合数性质应用问题一、知识结构排列2021/3/1012讲解：X
5、X二、学习要求1、掌握分类计数原理与分步计数原理，并能应用它们来分析和解决一些应用问题。2、理解排列与组合的意义，掌握排列数和组合数的计算公式，掌握组合数的两个性质，并能应用它们解决应用问题。2021/3/1013讲解：XX三、学习指导1、本章的重点内容是两个计数原理，排列和组合的意义，排列数和组合数的计算公式。2、本章的应用题的解决思路主要是：正向思考和逆向思考，正向思考时，可通过“分类”或“分步”，对稍复杂的问题进行分解；逆向思考时用集合的观点看，就是先从问题涉及的集合在全集的补集入手，使问题得到简化。3、注意排列和组合的内在联系和区别，计算应用题时避免重复和遗漏。2021/3/1014讲
6、解：XX10.1 两个基本原理 这两个原理是人们在大量实践经验的基础上归纳出来的基本规律，它体现了我们将复杂问题简单化的两种常用方法：将问题分类解决或是分步解决。这两个原理既是推导排列数和组合数公式的依据，而且其基本的思想方法贯穿在解决本章应用问题的始终。2021/3/1015讲解：XX分类计数原理问题 1. 从甲地到乙地，可以乘火车，也可以乘汽车，还可以乘轮船。一天中，火车有4 班, 汽车有2班，轮船有3班。那么一天中乘坐这些交通工具从甲地到乙地共有多少种不同的走法?分析: 从甲地到乙地有3类方法, 第一类方法, 乘火车，有4 种方法; 第二类方法, 乘汽车，有2 种方法; 第三类方法, 乘
7、轮船, 有3 种方法; 所以 从甲地到乙地共有 4 + 2 + 3 = 9 种方法。 2021/3/1016讲解：XX分步计数原理 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村共有 3 2 = 6 种不同的方法。2021/3/1017讲解：XX分类计数原理 做一件事情，完成它可以有n类办法,在第一类办法中有m1种不同的方法,在第二类办法中有m2种不同的方法，在第n类办法中有m
8、n种不同的方法。那么完成这件事共有 N=m1+m2+mn种不同的方法。 分步计数原理 做一件事情，完成它需要分成n个步骤，做第一步有m1种不同的方法，做第二步有m2种不同的方法，做第n步有mn种不同的方法，那么完成这件事有 N=m1m2mn种不同的方法。2021/3/1018讲解：XX 名称对比分类计数原理分步计数原理相同点均用于计计算做一件事或完成一项项工作的方法数事件完成与否每一类类中的任何一种办办法均能独立完成这这件事每一步中的办办法均不能独立完成这这件事，必须须各步顺顺序完成之后才能完成这这件事总的方法种数 各类类的方法数相加 各步的方法数相乘两个原理的区别与联系：2021/3/101
9、9讲解：XX 例：书架上层有5本不同的数学书，下层有4本不同的语文书，则(1)从书架上任取一本书，有多少种取法？(2)从两层中各取一本书，有多少种取法？2021/3/1020讲解：XX10.2 排列 本小节的知识体系在本章中处于承上启下的重要地位，它既在推导排列数公式的过程中使分步计数原理获得了重要应用，又使排列数公式成为推导组合数公式的主要依据。从而为我们以后学习概率统计知识打下基础。2021/3/1021讲解：XX排列的定义： 从n个不同元素中取出m(mn)个元素，按照一定的顺序排成一列，叫做从n个不同元素中取出m个元素的一个排列。2021/3/1022讲解：XX排列数的定义：从n个不同元
10、素中取出m(mn)个元素的所有排列的个数，叫做从n个不同元素中取出m个元素的排列数，用符号 表示。123mn-1nn-2n-m+1n-0n-(m-1)2021/3/1023讲解：XX排列数公式：全排列： n个不同的元素全部取出的一个排列叫做n个不同元素的一个全排列。全排列数公式：2021/3/1024讲解：XX10.3 组合 本节内容与本章其它内容均有密切联系：组合与排列研究的问题是平行的，组合数公式的推导要依据排列数公式；二项式系数就是一组有规律的组合数，推导二项式定理用到了组合数的性质；求等可能性事件的概率时，常常要涉及到组合数的计算。 2021/3/1025讲解：XX组合的定义 一般地说
11、，从 n 个不同元素中，任取 m (mn) 个元素并成一组，叫做从 n 个不同元素中取出 m 个元素的一个组合。2021/3/1026讲解：XX组合数的定义 从 n 个不同元素中取出 m (mn) 个元素的所有组合的个数，叫做从 n 个不同元素中取出 m 个元素的组合数，用符号 表示。2021/3/1027讲解：XX组合数公式2021/3/1028讲解：XX组合数的性质2021/3/1029讲解：XX排列和组合的区别和联系：排列组组合定义义数符号公式关系性质质 ，从n个不同元素中取出m个元素，按一定的顺序排成一列从n个不同元素中取出m个元素，把它并成一组所有排列的个数所有组合的个数2021/3
12、/1030讲解：XX例：某班有40名学生， (1)从中选出两名同学分别担任正副班长，有多少种选法？(2)从中选出两名同学代表去参加会议 ，有多少种选法？2021/3/1031讲解：XX排列组合应用题分析一一. .特殊元素特殊元素( (位置位置) )优先排（）优先排（）例1. 1名老师和4名学生排成一排，若老师不排在两端，则共有多少种不同的排法？2021/3/1032讲解：XX二二. .元素必相邻问题元素必相邻问题捆绑法捆绑法（）（）例2.3个女生与5个男生排在一起，女生必须排在一起，可以有多少种不同的方法？2021/3/1033讲解：XX三三. .不相邻问题不相邻问题插空法插空法（）（）例例3
13、.73.7人排成一排照相，若要求甲、乙、丙人排成一排照相，若要求甲、乙、丙三人不相邻，有多少种不同的排法？三人不相邻，有多少种不同的排法？2021/3/1034讲解：XX四.排列中部分元素顺序固定除法（）（）例4.7个节目，甲、乙、丙三个节目按给定顺序出现，有多少种排法？2021/3/1035讲解：XX五.允许重复的排列问题选择权（）（）例5.(1)将3封不同的信投入4个不同的信箱，有多少种不同的投法？(2)4名学生报名参加数学、物理、化学三个课外小组，有多少种不同的报名方法？分析:(1)中投信的人有选择权，所以投每封信都有4种可能，共有444 种投法。(2)中学生有选择权，所以每名同学报名都
14、有3种可能，共有3333 种报名方法。2021/3/1036讲解：XX六.圆排列问题例6.5人围着一张圆桌而坐,共有多少种坐法?分析：围桌而坐与坐成一排的不同点在于，坐成圆形没有首尾之分，所以固定一人A并从此位置把圆形展成直线，其余4人共有 种排法。ABCEDDAAB CE2021/3/1037讲解：XX 一般地一般地,n,n个不同元素作圆形排列个不同元素作圆形排列, ,共有共有(n-(n-1)!1)!种排法种排法. .如果从如果从n n个不同元素中取出个不同元素中取出mm个元个元素作圆形排列共有素作圆形排列共有个。个。2021/3/1038讲解：XX七七. .多排问题多排问题等同于单排考虑（
15、）等同于单排考虑（）例7.15人排成两排，前排7人，后排8人，共有多少种不同的方法？ 2021/3/1039讲解：XX 再如：8人排成前后两排,每排4人,其中甲乙在前排,丁在后排,共有多少排法？2021/3/1040讲解：XX八八. .排列组合混合问题排列组合混合问题先选后排（）先选后排（）例8.9名乒乓球运动员，其中男5名，女4名，现在要进行混合双打训练，有多少种不同分组法？2021/3/1041讲解：XX九九. .利用集合思想解决（）利用集合思想解决（）例9.从6名运动员中选出4个参加4100m接力赛，如果甲不跑第一棒，乙不跑第四棒，共有多少种不同参赛方法？ 分析：设全集6人中任取4人参赛
16、的排列，A甲第一棒的排列，B乙跑第四棒的排列，根据求集合元素个数的公式得参赛方法共有：2021/3/1042讲解：XX十.元素无差别问题隔板法例10.将10个相同的球放入3个不同的盒子中，(1)每个盒子不空，有多少种不同的放法？(2)盒子可以是空的，有多少种不同的放法？2021/3/1043讲解：XX 隔板法可推广到n个球，放到m个盒子中去的一般情况： 若盒子非空，则方法数为 若盒子可以为空，则方法数为 ，即 从m+n个位置中选出m个位置放隔板，其余位置则放球。2021/3/1044讲解：XX 上例可转化为：求方程xyz10的正整数解或非负整数解的个数。 2021/3/1045讲解：XX 再如：把10个相同的球放入三个不同的盒子中，使得每个盒子中的球数不少于2，则不同的放法有（ ） A、81种 B、15种 C、10种 D、4种2021/3/1046讲解：XX十一十一. .直接做法复杂直接做法复杂间接法（）间接法（）例11.从4台甲型和5台乙型电视机中任取出3台，其中至少要甲型和乙型电视机各一台，则不同取法共有A140种 B80种C70种D35种2021/3/1047讲解：XX十二.分组
