《组合数学课件》由会员分享，可在线阅读，更多相关《组合数学课件（53页珍藏版）》请在金锄头文库上搜索。
1、 组合数学组合数学 RichardA.Brualdi 著著 冯舜玺冯舜玺 等等 编译编译 机械工业出版社机械工业出版社 ： 1组合数学 办公室：软件学院四楼专业教研室办公室：软件学院四楼专业教研室 办公电话：办公电话：8 8 4 5 1 1 2 88 8 4 5 1 1 2 8 住宅电话：住宅电话：8 2 4 9 5 8 7 48 2 4 9 5 8 7 4 移动电话：移动电话：1 3 0 9 6 9 8 1 1 8 21 3 0 9 6 9 8 1 1 8 2 电子邮件：电子邮件： 2组合数学绪绪 论论 组合数学是一门古老的数学分支，其思想组合数学是一门古老的数学分支，其思想在社会科学、信息
2、论、生物科学以及其他传统在社会科学、信息论、生物科学以及其他传统自然科学领域得到了广泛的应用。自然科学领域得到了广泛的应用。组合数学在组合数学在计算机出现以后得以迅速发展。计算机科学就计算机出现以后得以迅速发展。计算机科学就是算法的科学，而计算机所处理的对象是离散是算法的科学，而计算机所处理的对象是离散的数据，所以离散对象的处理就成了计算机的数据，所以离散对象的处理就成了计算机3组合数学 科学的核心，而研究离散对象的科学恰恰就科学的核心，而研究离散对象的科学恰恰就是离散数学和组合数学；组合数学的发展改变是离散数学和组合数学；组合数学的发展改变了传统数学中分析和代数占统治地位的局面。了传统数学中
3、分析和代数占统治地位的局面。现代数学可以分为两大类：一类是研究连续对现代数学可以分为两大类：一类是研究连续对象的，如分析、方程等，另一类就是研究离散象的，如分析、方程等，另一类就是研究离散对象的组合数学。组合数学不仅在基础数学研对象的组合数学。组合数学不仅在基础数学研究中具有极其重要的地位，在其它的学科中也究中具有极其重要的地位，在其它的学科中也有重要的应用，如计算机科学、编码和有重要的应用，如计算机科学、编码和4组合数学 密码学、物理、化学、生物等学科中均有重要密码学、物理、化学、生物等学科中均有重要应用。微积分和近代数学的发展为近代的工业应用。微积分和近代数学的发展为近代的工业革命奠定了基
4、础。而组合数学的发展则是奠定革命奠定了基础。而组合数学的发展则是奠定了本世纪的计算机革命的基础。计算机之所以了本世纪的计算机革命的基础。计算机之所以可以被称为可以被称为电脑电脑，就是因为计算机被人编写了，就是因为计算机被人编写了程序，而程序就是算法，在绝大多数情况下，程序，而程序就是算法，在绝大多数情况下，计算机的算法是针对离散的对象计算机的算法是针对离散的对象，而不是在作而不是在作数值计算。数值计算。 5组合数学 正是因为有了组合算法才使人感到，计算机正是因为有了组合算法才使人感到，计算机好象是有思维的。好象是有思维的。 组合数学不仅在软件技术中有重要的应用价组合数学不仅在软件技术中有重要的
5、应用价值，在企业管理，交通规划，战争指挥，金融分值，在企业管理，交通规划，战争指挥，金融分析等领域都有重要的应用。在美国有一家用组合析等领域都有重要的应用。在美国有一家用组合数学命名的公司，他们用组合数学的方法来提高数学命名的公司，他们用组合数学的方法来提高企业管理的效益，这家公司办得非常成功。企业管理的效益，这家公司办得非常成功。 6组合数学 此外，试验设计也是具有很大应用价值的此外，试验设计也是具有很大应用价值的学科，它的数学原理就是组合设计。用组合设学科，它的数学原理就是组合设计。用组合设计的方法解决工业界中的试验设计问题，在美计的方法解决工业界中的试验设计问题，在美国已有专门的公司开发
6、这方面的软件。最近，国已有专门的公司开发这方面的软件。最近，德国一位著名组合数学家利用组合数学方法研德国一位著名组合数学家利用组合数学方法研究药物结构，为制药公司节省了大量的费用，究药物结构，为制药公司节省了大量的费用，引起了制药业的关注。引起了制药业的关注。7组合数学 组合数学与计算机软件 随着计算机网络的发展，计算机的使用已经随着计算机网络的发展，计算机的使用已经影响到了人们的工作，生活，学习，社会活动以影响到了人们的工作，生活，学习，社会活动以及商业活动，而计算机的应用根本上是通过软件及商业活动，而计算机的应用根本上是通过软件来实现的。在美国有一种说法：将来一个国家的来实现的。在美国有一
7、种说法：将来一个国家的经济实力可以直接从软件产业反映出来。经济实力可以直接从软件产业反映出来。 8组合数学 我国在软件上的落后，要说出根本的原因可我国在软件上的落后，要说出根本的原因可能并不是简单的事，除了技术和科学上的原能并不是简单的事，除了技术和科学上的原因外，可能还跟我们的文化因外，可能还跟我们的文化( (汉字汉字) )，管理水，管理水平，教育水平，思想素质等诸多因素有关。平，教育水平，思想素质等诸多因素有关。除去这些人文因素以外，一个最根本的原因除去这些人文因素以外，一个最根本的原因就是我国的信息技术的数学基础十分薄弱，就是我国的信息技术的数学基础十分薄弱，这个问题不解决，我们就难成为
8、软件强国。这个问题不解决，我们就难成为软件强国。 9组合数学 然而问题决不是这么简单，信息技术的发展然而问题决不是这么简单，信息技术的发展已经涉及到了很深的数学知识，而数学本身发已经涉及到了很深的数学知识，而数学本身发展程度并不是单凭几个聪明的头脑去想想就行展程度并不是单凭几个聪明的头脑去想想就行了，而更重要的是需要集体的合作和力量，就了，而更重要的是需要集体的合作和力量，就象软件的开发需要多方面的人员的合作。美国象软件的开发需要多方面的人员的合作。美国的软件之所以能领先，其关键就在于在数学基的软件之所以能领先，其关键就在于在数学基础上他们有很强的实力，有很多杰出的人才。础上他们有很强的实力，
9、有很多杰出的人才。10组合数学 一般人可能会认为数学是一门纯粹的基础科学，一般人可能会认为数学是一门纯粹的基础科学，1+1的解决可能不会有任何实际的意义。如果真的解决可能不会有任何实际的意义。如果真是这样，一门纯粹学科的发展落后几年，甚至是这样，一门纯粹学科的发展落后几年，甚至十年，关系也不大。然而中国的软件产业的发十年，关系也不大。然而中国的软件产业的发展已向数学基础提出了急切的需求：网络算法展已向数学基础提出了急切的需求：网络算法和分析、信息压缩、网络安全、编码技术、系和分析、信息压缩、网络安全、编码技术、系统软件、并行算法、数学机械化和计算机推理统软件、并行算法、数学机械化和计算机推理1
10、1组合数学 等等。此外，与实际应用有关的还有许多许多等等。此外，与实际应用有关的还有许多许多需要数学基础的算法，如运筹规划，金融工程，需要数学基础的算法，如运筹规划，金融工程，计算机辅助设计等。如果我们的软件产业还是计算机辅助设计等。如果我们的软件产业还是把眼光一直盯在应用软件和第二次开发，那么把眼光一直盯在应用软件和第二次开发，那么我们在应用软件这个领域也会让国外的企业抢我们在应用软件这个领域也会让国外的企业抢去很大的市场。如果我们现在在信息技术的数去很大的市场。如果我们现在在信息技术的数学基础上，大力支持和投入，那将是亡羊补牢，学基础上，大力支持和投入，那将是亡羊补牢，犹未为晚；犹未为晚；
11、 12组合数学 胡锦涛同志在胡锦涛同志在19981998年接见年接见“五四五四”青年奖青年奖章获得者时发表的讲话中指出：组合数学是不章获得者时发表的讲话中指出：组合数学是不同于传统的纯数学的一个分支，它还是一门应同于传统的纯数学的一个分支，它还是一门应用学科，一门交叉学科。他希望中国的组合数用学科，一门交叉学科。他希望中国的组合数学研究能够为国家的经济建设服务。学研究能够为国家的经济建设服务。 如果如果2121世纪是信息社会的世纪，那么世纪是信息社会的世纪，那么2121世世纪也必将是组合数学大有可为的世纪。纪也必将是组合数学大有可为的世纪。13组合数学 组合数学课每周上课两次，组合数学课每周上
12、课两次，4 4学时，安学时，安排排1414周，共周，共5656学时。根据教学计划和培养目标学时。根据教学计划和培养目标要求，我们学习以下内容：要求，我们学习以下内容：第一章第一章 什么是组合数学什么是组合数学 第二章第二章 鸽巢原理鸽巢原理 第三章第三章 排列与组合排列与组合 第四章第四章 生成排列与组合生成排列与组合 第五章第五章 二项式系数二项式系数 第六章第六章 容斥原理及其应用容斥原理及其应用 第七章第七章 递推关系与生成函数递推关系与生成函数第八章第八章特殊计数序列特殊计数序列14组合数学 考核方式：期末笔试占考核方式：期末笔试占70%70%，平时作业占，平时作业占30%30%， 每
13、星期一交一次作业。由各个班长送到四楼每星期一交一次作业。由各个班长送到四楼办公室。办公室。 本课件制作由廖虎独立完成，该课件几乎可本课件制作由廖虎独立完成，该课件几乎可以取代教材，已经公布在学院公共实验室网上，以取代教材，已经公布在学院公共实验室网上，同学们可以自己下载浏览。同学们可以自己下载浏览。15组合数学 第第1章章 什么是组合数学什么是组合数学 组合数学是一门古老的数学分支，其思组合数学是一门古老的数学分支，其思想在社会科学、信息论、生物科学以及其他想在社会科学、信息论、生物科学以及其他传统自然科学领域得到了广泛的应用。传统自然科学领域得到了广泛的应用。组合组合学问题在生活中随处可见。
14、学问题在生活中随处可见。在计算机科学领在计算机科学领域，组合数学是域，组合数学是算法设计理论算法设计理论以及以及算法分析算法分析理论理论的重要数学工具。的重要数学工具。16组合数学 例如，计算下列赛制下总的例如，计算下列赛制下总的比赛次数比赛次数：n个个球队参赛，每队只和其他队比赛一次球队参赛，每队只和其他队比赛一次;创建创建幻方幻方;在纸上画一个网络，用铅笔沿着网络的线路走，在纸上画一个网络，用铅笔沿着网络的线路走，在笔不离开纸面且不重复线路的条件下，笔画在笔不离开纸面且不重复线路的条件下，笔画出出网络图网络图(一笔画一笔画);在玩扑克牌游戏中，计算满在玩扑克牌游戏中，计算满堂红堂红(ful
15、lhoue)牌的手数，以确定出现一手满牌的手数，以确定出现一手满堂红牌的堂红牌的几率几率。所有这些。所有这些都是组合学问题。都是组合学问题。17组合数学 正如人们想到的，组合数学的历史渊源正如人们想到的，组合数学的历史渊源扎根于数学扎根于数学娱乐娱乐和和游戏游戏之中。过去研究过的许之中。过去研究过的许多问题，不论出于消遣还是出于对其美学的考多问题，不论出于消遣还是出于对其美学的考虑，如今在纯科学和应用科学中都具有高度的虑，如今在纯科学和应用科学中都具有高度的重要性。今天，组合数学是数学的一门重要分重要性。今天，组合数学是数学的一门重要分支，而且它的影响还在继续扩大。组合数学自支，而且它的影响还
16、在继续扩大。组合数学自6060年代以来急速发展的部分原因年代以来急速发展的部分原因18组合数学 就在于计算机在我们的社会中所发挥的重要就在于计算机在我们的社会中所发挥的重要影响，而且这种影响还在继续发挥。影响，而且这种影响还在继续发挥。 组合数学近期发展的另一个原因是它对于那组合数学近期发展的另一个原因是它对于那些过去很少与数学正式接触的学科的适用性。由些过去很少与数学正式接触的学科的适用性。由此我们发现，组合数学的思想和技巧不仅正在用此我们发现，组合数学的思想和技巧不仅正在用于数学应用的传统自然科学领域，而且也用于社于数学应用的传统自然科学领域，而且也用于社会科学、生物科学、信息论等领域。会
17、科学、生物科学、信息论等领域。19组合数学 组组合合数数学学涉涉及及到到将将一一个个集集合合的的物物体体排排列列成成满满足足一一些些指指定定规规则则的的格格式式。如如下下两两类类一一般般性性问问题题反复出现：反复出现：排列的存在性：如果有人想要排列一个集合的排列的存在性：如果有人想要排列一个集合的成员使得某些条件得以满足，那么这样一种排列成员使得某些条件得以满足，那么这样一种排列是否可行就显而易见的。这是最根本的问题。如是否可行就显而易见的。这是最根本的问题。如果这种排列不总是可能的，那么我们果这种排列不总是可能的，那么我们要问，这种要问，这种20组合数学排列在什么样的排列在什么样的(必要和充
18、分必要和充分)条件下能够实现？条件下能够实现？ 排排列列的的计计数数和和分分类类：如如果果一一个个指指定定的的排排列列是是可可能能的的，那那么么就就会会存存在在多多种种方方法法去去实实现现它它。此此时时，人们就可以计数并将它们分类。人们就可以计数并将它们分类。 研研究究一一个个已已知知的的排排列列：当当人人们们建建立立起起满满足足某某些些指指定定条条件件的的一一个个排排列列(可可能能不不容容易易)以以后后，可可能能要考察这个排列的性质和结构。要考察这个排列的性质和结构。21组合数学 这样这样的的结结构可能会涉及到分构可能会涉及到分类问题类问题，也，也许还许还涉及到一些潜在的应用，它还可能牵扯到
19、下面涉及到一些潜在的应用，它还可能牵扯到下面的问题。的问题。 构造一个最优的排列：如果有可能存在多于构造一个最优的排列：如果有可能存在多于一个的排列，人们也许想要确定满足某些优化一个的排列，人们也许想要确定满足某些优化准则的一个排列，即找出某种规定意义下的准则的一个排列，即找出某种规定意义下的“最好的最好的”或或“最优的最优的”的排列的排列。22组合数学 因因此此，组组合合数数学学可可以以一一般般地地描描述述为为：组组合合数数学学是是研研究究离离散散结结构构的的存存在在、计计数数、分分析析和和优优化化等问题的一门学科。等问题的一门学科。 虽虽然然某某些些离离散散结结构构是是无无限限的的，但但本
20、本书书一一般把离散视为般把离散视为有限的有限的。 23组合数学 一、问题描述一、问题描述 假假设设有有一一张张普普通通国国际际象象棋棋棋棋盘盘和和32张张domino牌牌，其其形形状状如如下下:88象象棋棋棋棋盘盘, , 一一张张12格格的的多多米诺牌米诺牌 domino 牌。牌。第一章第一章 什么是组合数学什么是组合数学 1.1 棋盘的完美覆盖棋盘的完美覆盖24组合数学 每张牌恰好覆盖棋盘上相邻的两个方格。每张牌恰好覆盖棋盘上相邻的两个方格。 问问题题（棋棋盘盘的的完完美美覆覆盖盖问问题题）：是是否否能能够够把把32张张domino牌牌摆摆放放在在棋棋盘盘上上，使使得得任任何何两两张张dom
21、ino牌牌均均不不重重叠叠，每每张张domino牌牌覆覆盖盖两两个个方方格格，并并且且棋棋盘盘上上所所有有方方格格都都被被覆覆盖盖住住？如如果果存存在在这这种种完完美美覆覆盖盖，那那么么总总共共有有多多少少种种不不同同的的完完美美覆覆盖盖？结结论论：国国际际象象棋棋棋棋盘盘的的不不同同的的完完美美覆覆盖总共有：盖总共有： 249012 = 12988816种种25组合数学 这这种种普普通通的的国国际际象象棋棋棋棋盘盘可可以以用用排排成成m行行n列列的的mn个个方方格格的的一一般般棋棋盘盘代代替替。此此时时，这这种种棋棋盘盘的的完完美美覆覆盖盖就就未未必必存存在在了了。比比如如，3行行3列列的的
22、棋棋盘盘就就确确实实不不存存在在完完美美覆覆盖盖。那那么么，对对于于什什么么样样的的m和和n存存在在完完美美覆覆盖盖呢呢?不不难难看看出出，当当且且仅仅当当m和和n中中至至少少有有一一个个是是偶偶数数时时,mn棋棋盘盘存存在在完完美美覆覆盖盖。或或者者说说，当当且且仅仅当当棋棋盘盘的的方方格格数数是是偶数时，偶数时， mn棋盘存在完美覆盖。棋盘存在完美覆盖。26组合数学 再再来来考考查查用用12格格的的多多米米诺诺骨骨牌牌覆覆盖盖去去掉掉了了两两个个对对角角处处格格子子的的88残残缺缺棋棋盘盘，问问能能否否用用31枚骨牌完美覆盖？枚骨牌完美覆盖？ 答答案案是是否否定定的的。证证明明方方法法很很
23、巧巧妙妙，可可以以先先将将88棋棋盘盘黑黑白白间间隔隔染染色色，去去掉掉的的两两个个对对角角处处格格子子不不是是同同白白，就就是是同同黑黑。因因此此，88残残缺缺棋棋盘盘剩剩余余的的64-2=62个个格格子子中中黑黑格格数数与与白白格格数数相差为相差为2。反之，。反之，27组合数学 白白白白白白白白白白白白白白白白白白黑黑黑黑黑黑黑黑黑黑黑黑黑黑黑黑黑黑黑黑31 黑黑 白白 若若设设能能用用31枚枚12格格的的骨骨牌牌，若若每每枚枚覆覆盖盖相邻的相邻的2个方格，恰将残缺棋盘砌满，个方格，恰将残缺棋盘砌满，28组合数学 则则黑黑格格数数与与白白格格数数应应该该相相等等。这这就就产产生生了了矛矛盾
24、盾。因因此此，不不存存在在要要求求的的覆覆盖盖。如如果果对对不不去去掉掉对对角角处处格格子子的的64格格88完完好好棋棋盘盘，则则存存在在用用32枚枚12格格的的骨骨牌牌恰恰将将其其覆覆盖盖的的许许多多方方法法。这这时时要要讨讨论论的的就就是是确确定定有有多多少少种种不不同同覆覆盖盖方方法法的的计数问题。计数问题。 32 黑黑 +30白白31 黑黑 白白29组合数学第一章第一章 什么是组合数学什么是组合数学 1.2 切割立方体切割立方体 1.2 切割立方体切割立方体 把一个把一个333的立方体木块切割成的立方体木块切割成27个个111的小立方块。如果切割过程中允许重新排的小立方块。如果切割过程
25、中允许重新排列已切割木块的位置，求完成整个切割的最列已切割木块的位置，求完成整个切割的最 少次数。少次数。 这里的最优即指具有最少切割次数的方案，这里的最优即指具有最少切割次数的方案，30组合数学 采采用用穷穷举举方方案案并并比比较较切切割割次次数数的的方方法法一一般般不不可可取取。 本本例例的的解解法法是是先先指指出出6次次即即可可完完成成全全部部切切割割，即即水水平平切切2次次，竖竖直直、交交叉叉各各切切2次次。其其次次， 可可以以证证明明少少于于6次次不不能能完完成成题题目目要要求求的的切切割割。事事实实上上，对对中中心心位位置置产产生生的的小小立立方方体体而而言言，因因其其也也具具有有
26、6个个面面且且每每个个面面都都须须被被独独立立地地切切割割一一次次才才能能出出现现。故故至至少少需需要要6次次才才能能切切割完，见书中割完，见书中P5。31组合数学第一章第一章 什么是组合数学什么是组合数学 1.3 幻方幻方 1.3 幻方幻方 幻方也称为幻方也称为洛书洛书、河图河图等，传说大禹治水时，等，传说大禹治水时，从河中浮起一只乌龟，乌龟的背上画有一个从河中浮起一只乌龟，乌龟的背上画有一个33 的九个方格子，格子中填有从的九个方格子，格子中填有从1,29九个数，填写九个数，填写的规则是：横、竖、斜各自格子中数之和相等。的规则是：横、竖、斜各自格子中数之和相等。32组合数学 左左图图称称为
27、为幻幻方方，右右图图称称为为幻幻圆圆，观观察察幻幻圆圆的的数数字字结结构构，紫紫色色框框里里的的数数字字之之差差的的绝绝对对值值相相等等；沿沿蓝蓝色色线线的的数数字字之之和和相相等等。大大家家有有精精力力也也能再找出其他的数字关系来。能再找出其他的数字关系来。49235781633组合数学 一一个个n阶阶幻幻方方是是由由数数字字1，2，3，n2组组成成的的nn方方阵阵，使使得得方方阵阵中中每每行行上上的的数数字字和和、每每列列上上的的数数字字和和以以及及每每条条对对角角线线上上的的数数字字和和均均等于同一个数等于同一个数S。称。称S为该幻方的为该幻方的幻和幻和。 中中国国历历史史上上研研究究3
28、3 = 9幻幻方方也也称称为为“九九宫宫填数填数”；34组合数学一个一个n阶幻方中所有数字的和为：阶幻方中所有数字的和为：1 + 2 + 3 + + n2 = =nS故故它它的的幻幻和和为为 S = 正正好好是是一一行行(列列)上上数数字字的的和和，从从而而, 关关于于幻幻方方的的问问题题可可归归结结为为: 35组合数学(1) 对任意的正整数对任意的正整数n，n阶幻方存在吗？阶幻方存在吗？(2) 对某个正整数对某个正整数n，如果，如果n阶幻方存在，有阶幻方存在，有多少不同的形式？多少不同的形式？(3) 构造存在的构造存在的n阶幻方。阶幻方。注意，给出一种算法，不仅要描述算法的步注意，给出一种算
29、法，不仅要描述算法的步骤，而且要证明算法的正确性，并对算法骤，而且要证明算法的正确性，并对算法进行时间分析。进行时间分析。 36组合数学 下面是构造的下面是构造的7阶幻方，幻和为阶幻方，幻和为175 ：3039481101928384779182729466817263537514162534364513152433424442123324143312223140492112037组合数学 不难看出，不可能存在不难看出，不可能存在2阶幻方；阶幻方； 够成幻方的方阵转置后仍然是个幻方。够成幻方的方阵转置后仍然是个幻方。 本书中给出了本书中给出了n为奇数时构造幻方的方法为奇数时构造幻方的方法和立体
30、幻方的概念，由于时间和难度的关系，和立体幻方的概念，由于时间和难度的关系，我们就不用再讨论。我们就不用再讨论。38组合数学第一章第一章 什么是组合数学什么是组合数学 1.4 四色问题四色问题 1.4 四色问题四色问题 在在一一张张地地图图中中每每个个国国家家均均是是一一个个连连通通的的区区域域，现现对对地地图图中中的的每每个个国国家家着着色色，使使得得具具有有共共同同边边界界的的两两个个国国家家涂涂成成不不同同的的颜颜色色，完完成成这这项项工工作作至至少少需需要要几几种种颜颜色色？在在离离散散数数学学中中我我们们利利用用对对偶偶图图已已经经证证明明用用5种种颜颜色色可可以对地图着色。以对地图着
31、色。39组合数学四色定理叙述起来简单，理解起来容易，它与四色定理叙述起来简单，理解起来容易，它与著名的三等分角问题一样著名的三等分角问题一样吸引着众多的非专业人员。吸引着众多的非专业人员。1890年年heawood证明了用证明了用5种颜色对任何地图着色。种颜色对任何地图着色。 42 3140组合数学第一章第一章 什么是组合数学什么是组合数学 1.5 36军官问题与拉丁方军官问题与拉丁方 1.5 36军官问题与拉丁方军官问题与拉丁方 设设有有6个个不不同同军军衔衔和和来来自自6个个不不同同团团队队的的36名名军军官官，问问能能否否将将他他们们排排成成66方方阵阵，使使得得每每行行每每列列均均有有
32、各各种种军军衔衔的的军军官官1名名，并并且且每每行行和和每每列列上上的不同军衔的的不同军衔的6名军官还分别来自不同的军团？名军官还分别来自不同的军团？41组合数学 我我们们把把一一个个军军官官表表示示为为一一个个序序偶偶（i，j），其其中中i表表示示该该军军官官的的军军衔衔（i1，2，6），而而j表表示示他他所所在在的的军军团团（j1，2，6），于于是上述是上述36军官问题可用数学语言描述成：军官问题可用数学语言描述成： 36个序偶（序偶（i，j）能否排成）能否排成66方阵，使得这方阵，使得这6个整数都能分别以某种顺序出现在序偶的第一个整数都能分别以某种顺序出现在序偶的第一个或第二个元素位置上
33、？个或第二个元素位置上？42组合数学 或或者者：是是否否存存在在这这样样的的两两个个66矩矩阵阵，其其元素取自元素取自1，2，6，使得，使得 1整数整数1，2，6以某种顺序出现在矩阵的以某种顺序出现在矩阵的每一行和每一列；每一行和每一列； 2当这两个矩阵并置时，所有当这两个矩阵并置时，所有36序偶（序偶（i，j） （i1，2，6）全部出现。）全部出现。43组合数学军团矩阵军团矩阵军衔矩阵军衔矩阵 以以9名名军军官官为为例例，设设i=1, 2, 3表表示示军军官官的的军军衔衔，j=1, 2, 3 表表示示军军官官的的团团队队，则则每每个个军军官官对对应一个序偶应一个序偶(i, j)。从而可以排出
34、：。从而可以排出：44组合数学分别 我我们们把把具具有有上上述述性性质质1的的两两个个66矩矩阵阵均均称称为为6 6阶阶拉拉丁丁方方。这这两两个个6阶阶拉拉丁丁方方若若同同时时具具有有上述性质上述性质2，则称它们是，则称它们是正交的正交的。 于于是是36军军官官问问题题又又可可描描述述为为：是是否否存存在在两两个正交的个正交的6阶拉丁方？阶拉丁方？45组合数学第一章第一章 什么是组合数学什么是组合数学 1.6 最短路径问题最短路径问题 (14) 1.6 最短路径问题最短路径问题 从甲地到乙地存在许多可能的路径。我们的问从甲地到乙地存在许多可能的路径。我们的问题是如何确定从甲地到乙地的距离最短的
35、路径？题是如何确定从甲地到乙地的距离最短的路径？ 最短路径问题有着广泛的应用，可以抽象为最短路径问题有着广泛的应用，可以抽象为图加以研究。我们的目标是设计出最有效的，计图加以研究。我们的目标是设计出最有效的，计算最短路径的算法已在离散数学中单独研究。算最短路径的算法已在离散数学中单独研究。46组合数学 以上列举的以上列举的6个问题均是组合数学所研究的个问题均是组合数学所研究的问题。从中我们可以看出组合数学所讨论的问问题。从中我们可以看出组合数学所讨论的问题在描述上具有以下特征：题在描述上具有以下特征： 1.能否排列能否排列 ？ 2.存在一个存在一个 吗？吗？ 3.能用多少方法能用多少方法 ？
36、4.计算计算 的数目？的数目？ 等等等等47组合数学 概概括括起起来来说说，组组合合数数学学的的研研究究涉涉及及如如下一般性问题：下一般性问题： 排列的存在性排列的存在性 排列的计数和分类排列的计数和分类 研究一个已知的排列研究一个已知的排列 构造一个优化的排列构造一个优化的排列48组合数学总总 结结 本次课我们介绍了组合数学的基本原本次课我们介绍了组合数学的基本原理和研究对象、方法、形式等知识。理和研究对象、方法、形式等知识。 目的是建立一个组合数学的概念，目的是建立一个组合数学的概念，为将来的学习作些铺垫。为将来的学习作些铺垫。49组合数学本次授课到此结束本次授课到此结束 作业如下作业如下
37、: P13 3, 5, 16, 283. 设想一个监狱设想一个监狱 由由64个囚室组成，这些囚室排列的恰如个囚室组成，这些囚室排列的恰如一张一张8行行8列的棋盘。所有相邻的囚室之间都有门相通列的棋盘。所有相邻的囚室之间都有门相通, 一个被囚在某个角上囚室的犯人被告之，如果他能够一个被囚在某个角上囚室的犯人被告之，如果他能够恰好通过每个一次而到达对角位置上的囚室，他就将恰好通过每个一次而到达对角位置上的囚室，他就将被释放。该犯人能否得到自由。被释放。该犯人能否得到自由。 50组合数学5. 找出用多米诺骨牌覆盖找出用多米诺骨牌覆盖4行行4列棋盘而形成的不同列棋盘而形成的不同的完美覆盖的个数。的完美
38、覆盖的个数。16.能将下列不完全的方形阵列填写成一个能将下列不完全的方形阵列填写成一个4阶幻方吗阶幻方吗？51组合数学28. 在下图中确定从在下图中确定从A到到B所有的最短路径。标出的数所有的最短路径。标出的数 据是各个路段的长度。据是各个路段的长度。下次上课内容：下次上课内容：2.1 鸽巢原理鸽巢原理 2.2 Ramsey定理定理1A34B1112223552组合数学Zr%u(x+B2E6H9KcOfRiUmXp!s&v)z0C3F7IaMdPgSkVnYq$t*x-A1D5G8JbNeQhTlWo#r%u(y+B2E6H9LcOfRjUmXp!s&w)z0C4F7IaMdPhSkVnZq$
39、t*x-A2D5G8KbNeQiTlXo#r%v(y+B3E6I9LcOgRjUmYp!s&w)z1C4F7JaMdPhSkWnZq$u*x-A2D5H8KbNfQiTlXo#s%v(y0B3E6I9LdOgRjVmYp!t&w-z1C4G7JaMePhTkWnZr$u*x+A2D5H8KcNfQiUlXo#s%v)y0B3F6I9LdOgSjVmYq!t&w-z1D4G7JbMePhTkWoZr$u(x+A2E5H9KcNfRiUlXp#s&v)y0C3F6IaLdPgSjVnYq!t*w-z1D4G8JbMeQhTkWoZr%u(x+B2E5H9KcOfRiUmXp#s&v)z0C3F7I
40、aLdPgSkVnYq$t*w-A1D5G8JbNeQhTlWo#r%u(y+B2E6H9KcOfRjUmXp!s&v)z0C4F7IaMdPgSkVnZq$t*x-A1D5G8KbNeQiTlWo#r%v(y+B3E6H9LcOgRjUmYp!s&w)z1C4F7JaMdPhSkVnZq$u*x-A2D5G8KbNfQiTlXo#r%v(y0B3E6I9LcOgRjVmYp!t&w)z1C4G7JaMePhSkWnZr$u*x+A2D5H8KcNfQiUlXo#s%v)y0B3F6I9LdOgRjVmYq!t&w-z1C4G7JbMePhTkWnZr$u(x+A2E5H8KcNfRiUlXp
41、#s%v)y0C3F6IaLdOgSjVnYq!t*w-z1D4G8JbMeQhTkWoZr$u(x+B2E5H9KcNfRiUmXp#s&v)y0C3F7IaLdPgSjVnYq$t*w-A1D4G8JbNeQhTlWoZr%y0C3F6IaLdOgSjVnYq!t*w-z1D4G7JbMeQhTkWoZr$u(x+B2E5H9KcNfRiUmXp#s&v)y0C3F7IaLdPgSjVnYq$t*w-A1D4G8JbNeQhTlWoZr%u(y+B2E6H9KcOfRiUmXp!s&v)z0C3F7IaMdPgSkVnYq$t*x-A1D5G8JbNeQiTlWo#r%u(y+B3E6H9
42、LcOfRjUmYp!s&w)z0C4F7JaMdPhSkVnZq$u*x-A2D5G8KbNeQiTlXo#r%v(y+B3E6I9LcOgRjUmYp!t&w)z1C4F7JaMePhSkWnZq$u*x+A2D5H8KbNfQiUlXo#s%v(y0B3F6I9LdOgRjVmYp!t&w-z1C4G7JaMePhTkWnZr$u*x+A2E5H8KcNfQiUlXp#s%v)y0B3F6IaLdOgSjVmYq!t*w-z1D4G7JbMeQhTkWoZr$u(x+A2E5H9KcNfRiUlXp#s&v)y0C3F6IaLdPgSjVnYq!t*w-A1D4G8JbMeQhTlWoZ
43、r%u(x+B2E6H9KcOfRiUmXp!s&v)z0C3F7IaMdPgSkVnYq$t*w-A1D5G8JbNeQhTlWo#r%u(y+B2E6H9LcOfRjUmXp!s&w)z0C4F7IaMdPhSkVnZq$t*x-A2D5G8KbNeQiTlXo#r%v(y+B3E6H9LcOgRjUmYp!s&w)z1C4F7JaMdPhSkWnZq$u*x-A2D5H8KbNfQiTlXo#s%v(y0B3E6I9LdOgRjVmYp!t&w-z1C4G7JaMePhSkWnZr$u*x+A2D5H8KcNfQiUlXo#s%v)y0B3F6I9LdOgSjVmYq!t&w-z1D4G
44、7JbMePhTkWoZr$u(x+A2E5H9KcNfRiUlXp#s&v)y0C3F6IaLdOgSjVnYq!t*w-z1D4G8JbMeQhTkWoZr%u(x+B2E5H9KcOfRiUmXp#s&v)z0C3F7IaLdPgSkVnYq$t*w-A1D5G8JbNeQhTlWoZr%u(y+B2E6H9KcOfnYq!t*w-z1D4G8JbMeQhTkWoZr%u(x+B2E5H9KcOfRiUmXp#s&v)z0C3F7IaLdPgSkVnYq$t*w-A1D4G8JbNeQhTlWoZr%u(y+B2E6H9KcOfRjUmXp!s&v)z0C4F7IaMdPgSkVnZq$
45、t*x-A1D5G8KbNeQiTlWo#r%v(y+B3E6H9LcOfRjUmYp!s&w)z0C4F7JaMdPhSkVnZq$u*x-A2D5G8KbNfQiTlXo#r%v(y0B3E6I9LcOgRjVmYp!t&w)z1C4G7JaMePhSkWnZq$u*x+A2D5H8KbNfQiUlXo#s%v(y0B3F6I9LdOgRjVmYq!t&w-z1C4G7JbMePhTkWnZr$u(x+A2E5H8KcNfRiUlXp#s%v)y0C3F6IaLdOgSjVmYq!t*w-z1D4G7JbMeQhTkWoZr$u(x+B2E5H9KcNfRiUmXp#s&v)y0C3F7I
46、aLdPgSjVnYq$t*w-A1D4G8JbNeQhTlWoZr%u(x+B2E6H9KcOfRiUmXp!s&v)z0C3F7IaMdPgSkVnYq$t*x-A1D5G8JbNeQiTlWo#r%u(y+B3E6H9LcOfRjUmYp!s&w)z0C4F7JaMdPhSkVnZq$t*x-A2D5G8KbNeQiTlXo#r%v(y+B3E6I9LcOgRjUmYp!t&w)z1C4F7JaMePhSkWnZq$u*x+A2D5H8KbNfQiUlXo#s%v(y0B3E6I9LdOgRjVmYp!t&w-z1C4G7JaMePhTkWnZr$u*x+A2E5H8KcNfQiUlXp
47、#s%v)y0B3F6IaLdOgSjVmYq!t*w-z1D4G7JbMePhTkWoZr$u(x+A2E5H9KcNfRiUlXp#s&v)y0C3F6MePhTkWnZr$u*x+A2E5H8KcNfQiUlXp#s%v)y0B3F6IaLdOgSjVmYq!t&w-z1D4G7JbMePhTkWoZr$u(x+A2E5H9KcNfRiUlXp#s&v)y0C3F6IaLdPgSjVnYq!t*w-A1D4G8JbMeQhTlW%v)y0B3F6I9LdOgSjVmYq!t&w-z1D4G7JbMePhTkWoZr$u(x+A2E5H9KcNfRiUlXp#s&v)y0C3F6IaLdP
48、gSjVnYq!t*w-A1D4G8JbMeQhTkWoZr%u(x+B2E5H9KcOfRiUmXp#s&z1D4G7JbMePhTkWoZr$u(x+A2E5H9KcNfRiUlXp#s&v)y0C3F6IaLdOgSjVnYq!t*w-z1D4G8JbMeQhTkWoZr%u(x+B2E5H9KcOfRiUmXp#s&v)z0C3F7IaLdPgSkVnYq$t*w-A1D5G8JbNeQhTlWo#r%u(y+B2E6H9KcOfRjUmt*w-z1D4G8JbMeQhTkWoZr%u(x+B2E5H9KcOfRiUmXp#s&v)z0C3F7IaLdPgSkVnYq$t*w-A1D4
49、G8JbNeQhTlWoZr%u(y+B2E6H9KcOfRjUmXp!s&v)z0C4F7IeQhTkWoZr%u(x+B2E5H9KcOfRiUmXp#s&v)z0C3F7IaLdPgSjVnYq$t*w-A1D4G8JbNeQhTlWoZr%u(y+B2E6H9KcOfRjUmXp!s&v)z0C4F7IaMdPgSkVn%u(x+B2E5H9KcNfRiUmXp#s&v)y0C3F7IaLdPgSjVnYq$t*w-A1D4G8JbNeQhTlWoZr%u(y+B2E6H9KcOfRjUmXp!s&v)z0C4F7IaMdPgSkVnZq$t*x-A1D5G8JbNeQiTlWo#r%
50、u(y+B3E6H9LcOfRjU$t*w-A1D4G8JbNeQhTlWoZr%u(y+B2E6H9KcOfRjUmXp!s&v)z0C3F7IaMdPgSkVnYq$t*x-A1D5G8JbNeQiTlWo#r%u(y+B3E6H9LcOfRjUmYt*w-A1D4G8JbNeQhTlWoZr%u(y+B2E6H9KcOfRiUmXp!s&v)z0C3F7IaMdPgSkVnYq$t*x-A1D5G8JbNeQiTlWo#r%u(y+B3E6H9LcOfRjUmYp!s&w)z0C4F7JaMdPhSkVnZq$t*x-A2D5cOfRiUmXp!s&v)z0C3F7IaMdPgSkVnY
51、q$t*x-A1D5G8JbNeQiTlWo#r%u(y+B3E6H9LcOfRjUmYp!s&w)z0C4F7IaMdPhSkVnZq$t*x2E6H9KcOfRiUmXp!s&v)z0C3F7IaMdPgSkVnYq$t*x-A1D5G8JbNeQiTlWo#r%u(y+B2E6H9LcOfRjUmXp!s&w)z0C4F7IaMdPhSZr%u(x+B2E6H9KcOfRiUmXp!s&v)z0C3F7IaMdPgSkVnYq$t*x-A1D5G8JbNeQhTlWo#r%u(y+B2E6H9LcOfRjUmXp!s&w)z0C4F7IaMdPhSkVnZq$t*x-A2D5G8KbNe
52、QiXp!s&v)z0C3F7IaLdPgSkVnYq$t*w-A1D5G8JbNeQhTlWo#r%u(y+B2E6H9LcOfRjUmXp!s&w)z0C4F7IaMdPhSkVnZq$t*B2E6H9KcOfRiUmXp#s&v)z0C3F7IaLdPgSkVnYq$t*w-A1D5G8JbNeQhTlWo#r%u(y+B2E6H9LcOfRjUmXp!s&w)z0C4F7IaMdPhSkVnZq$t*x-A1D5G8KbNeQiT#s&v)z0C3F7IaLdPgSkVnYq$t*w-A1D5G8JbNeQhTlWo#r%u(y+B2E6H9LcOfRjUmXp!s&w)z0C4F7I
53、aMdPgSkVnZq(x+B2E5H9KcOfRiUmXp#s&v)z0C3F7IaLdPgSkVnYq$t*w-A1D5G8JbNeQhTlWo#r%u(y+B2E6H9KcOfRjUmXp!s&v)z0C4F7IaMdPgSkVnZq$t*x-A1DKcOfRiUmXp#s&v)z0C3F7IaLdPgSkVnYq$t*w-A1D5G8JbNeQhTlWoZr%u(y+B2E6H9KcOfRjUmXp!s&v)z0C4FbMeQhTkWoZr%u(x+B2E5H9KcOfRiUmXp#s&v)z0C3F7IaLdPgSjVnYq$t*w-A1D4G8JbNeQhTlWoZr%u(y+B2
54、E6H9KcOfRjU!t*w-z1D4G8JbMeQhTkWoZr%u(x+B2E5H9KcOfRiUmXp#s&v)y0C3F7IaLdPgSjVnYq$t*w-A1D4G8JbNeQhTlWoZr%u(y+B2E6LdOgSjVnYq!t*w-z1D4G8JbMeQhTkWoZr$u(x+B2E5H9KcNfRiUmXp#s&v)y0C3F7IaLdPgSjVnYq$t*w2E5H8KcNfRiUlXp#s%v)y0C3F6IaLdOgSjVnYq!t*w-z1D4G7JbMeQhTkWoZr$u(x+B2E5H9KcNfRiUmXp#s&v)y0C3F7IaLdPgSjVnYq$+A2E5H8KcNfRiUlXp#s%v)y0B3F6IaLdOgSjVmYq!t*w-z1D4G7JbMeQhTkWoZr$u(x+B2E5H9KcNjVmYq!t&w-z153组合数学
