1、高等运筹学高等运筹学大连海事大学大连海事大学刘巍刘巍目录 第一篇第一篇 运筹学发展历史运筹学发展历史 第二篇第二篇 运筹学中的数学规划运筹学中的数学规划 第三篇第三篇 运筹学中的组合优化运筹学中的组合优化 第四篇第四篇 运筹学中的随机优化运筹学中的随机优化 第五篇第五篇 运筹学中的博弈论运筹学中的博弈论 第六篇第六篇 运筹学中管理科学运筹学中管理科学 第七篇第七篇 运筹学中智能计算运筹学中智能计算 第八篇第八篇 运筹学发展势态运筹学发展势态第九讲内容第九讲内容第十一章 组合数学及相关问题第十一章 组合数学及相关问题 组合数学概述组合数学概述 排列组合排列组合 容斥原理容斥原理 鸽巢原理鸽巢原理
2、 递推关系与母函数递推关系与母函数 组合数学概述 组合数学是近几十年来发展最为迅速的一个数学组合数学是近几十年来发展最为迅速的一个数学分支，它与分析、代数、数论、概率论等基础数分支，它与分析、代数、数论、概率论等基础数学的多个学科有密切联系，组合结构已经成为许学的多个学科有密切联系，组合结构已经成为许多数学理论不可或缺的组成部分。离散结构在信多数学理论不可或缺的组成部分。离散结构在信息科学、物理学、生物学和化学等众多领域中大息科学、物理学、生物学和化学等众多领域中大量出现，为组合数学的发展提供了强大的动力。量出现，为组合数学的发展提供了强大的动力。近年来，组合数学的思想和方法在数据结构和算近年
3、来，组合数学的思想和方法在数据结构和算法分析中都有重要的应用法分析中都有重要的应用;利用符号计算中的算利用符号计算中的算法，数学软件正在为越来越多的数学领域服务。法，数学软件正在为越来越多的数学领域服务。组合设计为现代移动通信以及光纤通信中的编码组合设计为现代移动通信以及光纤通信中的编码技术提供了基础技术提供了基础;它还应用于身份认证、密钥分它还应用于身份认证、密钥分享、数字签名等密码系统的设计中。此外，利用享、数字签名等密码系统的设计中。此外，利用组合数学为处理基因序列比对和物种关系分析中组合数学为处理基因序列比对和物种关系分析中的大量数据提供了一个有效的途径。组合数学在的大量数据提供了一个
4、有效的途径。组合数学在信息时代将有着非常广阔的应用研究前景。信息时代将有着非常广阔的应用研究前景。两个传说在我国古老的易经中有这样一句话：“河出图，洛出书，圣人则之。”后来，人们根据这句话传出许多神话。传说在伏羲氏时代，黄河里跃出一匹龙马，龙马背上驮了一幅图，上面有黑白点55个，用直线连成10数（如图），后人称之为“河图”。又传说在公元前23世纪大禹治水的时候，在黄河支流洛水中，浮现出一个 大乌龟，甲上背有9种花点的图案，9种花点数正巧是19这9个数，各数位置的排列也相当奇妙，横行、纵列以及两对角线上各自的数字之和都为15（如图），后人称之为“洛书”。河图、洛书两图中黑点组成的数都是偶数（古代
5、称阴数），白点表示的数是奇数（古代称阳数）。其中把“洛书”用数字表达就是下面的数表，其任意横、竖、斜各条直线上的三个数之和均相等（等于15），这就是我们今天所说的“幻方”。492357816 幻方可以看作是一个幻方可以看作是一个 3 3阶方阵，其元素是阶方阵，其元素是1 1 到到9 9的正整数，每行、的正整数，每行、每列以及两条对角线每列以及两条对角线 的和都是的和都是1515。519372486 1666年莱布尼兹所著年莱布尼兹所著组合学论文组合学论文一书一书问世，这是组合数学的第一部专著。书中首问世，这是组合数学的第一部专著。书中首次使用了组合论（次使用了组合论（Combinatorics
6、）一词。）一词。组合数学的蓬勃发展则是在计算机问世和组合数学的蓬勃发展则是在计算机问世和普遍应用之后。由于组合数学涉及面广，内普遍应用之后。由于组合数学涉及面广，内容庞杂，并且仍在很快地发展着，因而还没容庞杂，并且仍在很快地发展着，因而还没有一个统一而有效的理论体系。这与数学分有一个统一而有效的理论体系。这与数学分析形成了对照。析形成了对照。组合数学研究的中心问题是按一定规则将组合数学研究的中心问题是按一定规则将一些事物安排成各式各样模式的问题。包括一些事物安排成各式各样模式的问题。包括安排的存在问题、计数问题、构造问题以及安排的存在问题、计数问题、构造问题以及给出了优化标准后如何求出最优安排
7、问题。给出了优化标准后如何求出最优安排问题。概念理解 广义的组合数学就是离散数学；广义的组合数学就是离散数学；狭义的组合数学是图论、代数结构、数狭义的组合数学是图论、代数结构、数理逻辑等的总称。理逻辑等的总称。狭义的组合数学主要研究满足一定条件狭义的组合数学主要研究满足一定条件的组态（也称组合模型）的存在、计数的组态（也称组合模型）的存在、计数以及构造等方面的问题。以及构造等方面的问题。组合数学的主组合数学的主要内容有组合计数、组合设计、组合矩要内容有组合计数、组合设计、组合矩阵、组合优化（最佳组合）等阵、组合优化（最佳组合）等组合数学是一门研究离散对象的科学 组合数学在国外早已成为十分重要的
8、学科，甚组合数学在国外早已成为十分重要的学科，甚至可以说是计算机科学的基础。一些大公司，至可以说是计算机科学的基础。一些大公司，如如IBM，AT&T都有全世界最强的组合研究中都有全世界最强的组合研究中心。心。Microsoft 的的Bill Gates近来也在提倡和支近来也在提倡和支持计算机科学的基础研究。例如，持计算机科学的基础研究。例如，Bell实验室实验室的有关线性规划算法的实现，以及有关计算机的有关线性规划算法的实现，以及有关计算机网络的算法，由于有明显的商业价值，显然是网络的算法，由于有明显的商业价值，显然是没有对外公开的。美国已经有一种趋势，就是没有对外公开的。美国已经有一种趋势，
9、就是与新的算法有关的软件是可以申请专利的。如与新的算法有关的软件是可以申请专利的。如果照这种趋势发展，世界各国对组合数学和计果照这种趋势发展，世界各国对组合数学和计算机算法的投入和竞争必然日趋激烈算机算法的投入和竞争必然日趋激烈 美国政府也成立了离散数学及理论计算美国政府也成立了离散数学及理论计算机科学中心机科学中心DIMACS（与（与Princeton大学大学，Rutgers大学，大学，AT&T 联合创办的，设联合创办的，设在在Rutgers大学），该中心已是组合数学大学），该中心已是组合数学及理论计算机科学的重要研究阵地。美及理论计算机科学的重要研究阵地。美国国家数学科学研究所（国国家数学
10、科学研究所（Mathematical Sciences Research Institute，由陈省身先，由陈省身先生创立）在生创立）在1997年选择了组合数学作为年选择了组合数学作为研究专题，组织了为期一年的研究活动研究专题，组织了为期一年的研究活动 美国重要的国家实际室（美国重要的国家实际室（Los Alamos国家实验国家实验室，以造出第一颗原子弹著称于世），从曼哈室，以造出第一颗原子弹著称于世），从曼哈顿计划以来一直重视应用数学的研究，包括组顿计划以来一直重视应用数学的研究，包括组合数学的研究。不仅如此，该实验室最近还在合数学的研究。不仅如此，该实验室最近还在积极充实组合数学方面的研究
11、实力。美国另外积极充实组合数学方面的研究实力。美国另外一个重要的国家实验室一个重要的国家实验室Sandia国家实验室有一国家实验室有一个专门研究组合数学和计算机科学的机构，主个专门研究组合数学和计算机科学的机构，主要从事组合编码理论和密码学的研究，在美国要从事组合编码理论和密码学的研究，在美国政府以及国际学术界都具有很高的地位。政府以及国际学术界都具有很高的地位。欧洲也在积极发展组合数学，英国、法欧洲也在积极发展组合数学，英国、法国、德国、荷兰、丹麦、奥地利、瑞典国、德国、荷兰、丹麦、奥地利、瑞典、意大利、西班牙等国家都建立了各种、意大利、西班牙等国家都建立了各种形式的组合数学研究中心。近几年
12、，南形式的组合数学研究中心。近几年，南美国家也在积极推动组合数学的研究。美国家也在积极推动组合数学的研究。澳大利亚，新西兰也组建了很强的组合澳大利亚，新西兰也组建了很强的组合数学研究机构数学研究机构 亚洲的发达国家也十分重视组合数学的亚洲的发达国家也十分重视组合数学的研究。日本有组合数学研究中心，并且研究。日本有组合数学研究中心，并且从美国引进人才，不仅支持日本国内的从美国引进人才，不仅支持日本国内的研究，还出资支持美国的有关课题的研研究，还出资支持美国的有关课题的研究，这样使日本的组合数学这几年的发究，这样使日本的组合数学这几年的发展极为迅速展极为迅速组合花絮（1）-四色问题 如果你仔细留心
13、一张世界地图，你会发如果你仔细留心一张世界地图，你会发现用一种颜色对一个国家着色，那么一现用一种颜色对一个国家着色，那么一共只需要四种颜色就能保证每两个相邻共只需要四种颜色就能保证每两个相邻的国家的颜色不同。这样的着色效果能的国家的颜色不同。这样的着色效果能使每一个国家都能清楚地显示出来。但使每一个国家都能清楚地显示出来。但要证明这个结论却是一个著名的世界难要证明这个结论却是一个著名的世界难题，题，1976年数学家通过计算机运算得到年数学家通过计算机运算得到证明而成为四色定理。证明而成为四色定理。组合花絮（2）-中国邮递员问题 著名图论问题之一。邮递员从邮局出发著名图论问题之一。邮递员从邮局出
14、发送信，要求对辖区内每条街，都至少通送信，要求对辖区内每条街，都至少通过一次，再回邮局。在此条件下，怎样过一次，再回邮局。在此条件下，怎样选择一条最短路线？此问题由中国数学选择一条最短路线？此问题由中国数学家管梅谷于家管梅谷于1960年首先研究并给出算法年首先研究并给出算法，故名。，故名。组合花絮（3）-任务分配问题 有一些员工要完成一些任务。各个员工有一些员工要完成一些任务。各个员工完成不同任务所花费的时间都不同。每完成不同任务所花费的时间都不同。每个员工只分配一项任务。每项任务只被个员工只分配一项任务。每项任务只被分配给一个员工。怎样分配员工与任务分配给一个员工。怎样分配员工与任务以使所花
15、费的时间最少？以使所花费的时间最少？组合花絮（4）-河洛图 我国古代的河洛图上记载了三阶幻方，我国古代的河洛图上记载了三阶幻方，即把从一到九这九个数按三行三列的队即把从一到九这九个数按三行三列的队行排列，使得每行，每列，以及两条对行排列，使得每行，每列，以及两条对角线上的三个数之和都是一十五。组合角线上的三个数之和都是一十五。组合数学中有许多象幻方这样精巧的结构。数学中有许多象幻方这样精巧的结构。1977年美国旅行者年美国旅行者1号、号、2号宇宙飞船就号宇宙飞船就带上了幻方以作为人类智慧的信号带上了幻方以作为人类智慧的信号组合花絮（5）-装箱问题 当你装一个箱子时，你会发现要使箱子当你装一个箱
16、子时，你会发现要使箱子尽可能装满不是一件很容易的事，你往尽可能装满不是一件很容易的事，你往往需要做些调整。从理论上讲，装箱问往需要做些调整。从理论上讲，装箱问题是一个很难的组合数学问题，即使用题是一个很难的组合数学问题，即使用计算机也是不容易解决的。计算机也是不容易解决的。组合花絮（6）-过河问题 在中小学的数学游戏中，有这样一个问在中小学的数学游戏中，有这样一个问题，一个船夫要把一只狼，一只羊和一题，一个船夫要把一只狼，一只羊和一棵白菜运过河。问题是当人不在场时，棵白菜运过河。问题是当人不在场时，狼要吃羊，羊要吃白菜，而他的船每趟狼要吃羊，羊要吃白菜，而他的船每趟只能运其中的一个。他怎样才能
17、把三者只能运其中的一个。他怎样才能把三者都运过河呢？这就是一个很典型、很简都运过河呢？这就是一个很典型、很简单的组合数学问题。单的组合数学问题。组合花絮（7）-稳定婚姻问题稳定婚姻问题 假如能找到两对夫妇（如张（男）假如能找到两对夫妇（如张（男）-李（女）和赵（男李（女）和赵（男）-王（女），如果张（男）更喜欢王（女），而王王（女），如果张（男）更喜欢王（女），而王（女）也更喜欢张（男），那么这样就可能有潜在的不（女）也更喜欢张（男），那么这样就可能有潜在的不稳定性。组合数学的方法可以找到一种婚姻的安排方法稳定性。组合数学的方法可以找到一种婚姻的安排方法，使得没有上述的不稳定情况出现（当然这只
18、是理论上，使得没有上述的不稳定情况出现（当然这只是理论上的结论）。这种组合数学的方法却有的结论）。这种组合数学的方法却有 一个实际的用途一个实际的用途：美国的医院在确定录取住院医生时，他们将考虑申请：美国的医院在确定录取住院医生时，他们将考虑申请者的志愿的先后次序，同时也给申请排序。按这样的者的志愿的先后次序，同时也给申请排序。按这样的 次序考虑出的总的方案将没有医院和申请者两者同时后次序考虑出的总的方案将没有医院和申请者两者同时后悔的情况。悔的情况。实际上，高考学生的最后录取方案也可以实际上，高考学生的最后录取方案也可以用这种方法用这种方法组合花絮（8）-管理调度 我们还会遇到更复杂的调度和
19、安排问题。例如，我们还会遇到更复杂的调度和安排问题。例如，在生产原子弹的曼哈顿计划中，涉及到很多工序在生产原子弹的曼哈顿计划中，涉及到很多工序，许多人员的安排，很多元件的生产，怎样安排，许多人员的安排，很多元件的生产，怎样安排各种人员的工作，以及各种工序间的衔接，从而各种人员的工作，以及各种工序间的衔接，从而使整个工期的时间尽可能短？这些都是组合数学使整个工期的时间尽可能短？这些都是组合数学典型例子。又比如，假日饭店的管理中，也严格典型例子。又比如，假日饭店的管理中，也严格规定了有关的工序，如清洁工的第一步是换什么规定了有关的工序，如清洁工的第一步是换什么，清洗什么，第二步又做什么，总之，他进
20、出房，清洗什么，第二步又做什么，总之，他进出房间的次数应该最少。既然，这样一个简单的工作间的次数应该最少。既然，这样一个简单的工作都需要讲究工序，那么一个复杂的工程就更不用都需要讲究工序，那么一个复杂的工程就更不用说了说了组合花絮（9）-库房和运输的管理库房和运输的管理 怎样安排运输使得库房充分发挥作用，怎样安排运输使得库房充分发挥作用，进一步来说，货物放在什么地方最便于进一步来说，货物放在什么地方最便于存取（如存储时间短的应该放在容易存存取（如存储时间短的应该放在容易存取的地方）取的地方）。组合花絮（10）-铺地砖问题铺地砖问题 我们知道，用形状相同的方型砖块可以我们知道，用形状相同的方型砖
21、块可以把一个地面铺满（不考虑边缘的情况）把一个地面铺满（不考虑边缘的情况），但是如果用不同形状，而又非方型的，但是如果用不同形状，而又非方型的砖块来铺一个地面，能否铺满呢？这不砖块来铺一个地面，能否铺满呢？这不仅是一个与实际相关的问题，也涉及到仅是一个与实际相关的问题，也涉及到很深的组合数学问题很深的组合数学问题组合花絮（11）-金融分析金融分析 组合数学还可用于金融分析，投资方案组合数学还可用于金融分析，投资方案的确定，怎样找出好的投资组合以降低的确定，怎样找出好的投资组合以降低投资风险。南开大学组合数学研究中心投资风险。南开大学组合数学研究中心开发出了开发出了金沙股市风险分析系统金沙股市风
22、险分析系统现已现已投放市场，为短线投资者提供了有效的投放市场，为短线投资者提供了有效的风险防范工具风险防范工具核心内容 依据一定的规则来安排某些事物的有关依据一定的规则来安排某些事物的有关数学问题，这些问题包括数学问题，这些问题包括4个方面：个方面：这种安排是否存在，即存在性问题；这种安排是否存在，即存在性问题；如果符合要求的安排是存在的，那么这样的如果符合要求的安排是存在的，那么这样的安排又有多少，即计数问题（包括枚举的验安排又有多少，即计数问题（包括枚举的验证与效率）；证与效率）；怎样构造这种安排，即算法构造问题；怎样构造这种安排，即算法构造问题；如果给出了最优化标准，又怎样得到最优安如果
23、给出了最优化标准，又怎样得到最优安排，即最优化问题。排，即最优化问题。相关问题 排列组合排列组合 容斥原理容斥原理 鸽巢原理鸽巢原理 递推关系与母函数递推关系与母函数 二分图的最大匹配二分图的最大匹配1.1 1.1 加法法则与乘法法则加法法则与乘法法则.加法法则加法法则 设事件设事件A有有m种产生方式，种产生方式，事件事件B有有n种产生方式，则事件种产生方式，则事件A或或B之一有之一有m+n种种产生方式。产生方式。集合论语言：集合论语言：若若|A|=m,|B|=n,A|A|=m,|B|=n,A B=B=,则则|A|A B|=m+n B|=m+n。一、排列组合 例例 某班选修企业管理的有某班选修
24、企业管理的有 18 18 人，不选的有人，不选的有 10 10 人，人，则该班共有则该班共有 18+10=28 18+10=28 人。人。例例 北京每天直达上海的客车有北京每天直达上海的客车有 5 5 次，客机有次，客机有 3 3 次，次，则每天由北京直达上海的旅行方式有则每天由北京直达上海的旅行方式有 5+3=8 5+3=8 种。种。乘法法则乘法法则 设事件设事件A A有有m m种产生式，事件种产生式，事件B B有有n n种产种产生方式，则事件生方式，则事件A A与与B B有有 m nm n种产生方式。种产生方式。集合论语言：集合论语言：若若|A|=m,|B|=n,|A|=m,|B|=n,A
25、 A B=(a,b)|a B=(a,b)|a A,b A,b B,B,则则|A|A B|=m B|=m n n。例例 某种字符串由两个字符组成，第一个字符可选自某种字符串由两个字符组成，第一个字符可选自aa，b b，c c，d d，ee，第二个字符可选自，第二个字符可选自11，2 2，33，则这，则这种字符串共有种字符串共有5 5 3=15 3=15 个。个。例例 从从A A到到B B有三条道路，从有三条道路，从B B到到C C有两条道路，则从有两条道路，则从A A经经B B到到C C有有3 3 2=6 2=6 条道路。条道路。n例例 某种样式的运动服的着色由底色和装饰条纹的颜色配成。某种样式
26、的运动服的着色由底色和装饰条纹的颜色配成。底色可选红、蓝、橙、黄，条纹色可选黑、白，则共有底色可选红、蓝、橙、黄，条纹色可选黑、白，则共有4 4 2 =2 =8 8种着色方案。种着色方案。n若此例改成底色和条纹都用红、蓝、橙、黄四种颜色的话，则若此例改成底色和条纹都用红、蓝、橙、黄四种颜色的话，则方案数就不是方案数就不是4 4 4=16 4=16，而只有而只有 4 4 3=12 3=12 种。种。n在乘法法则中要注意事件在乘法法则中要注意事件 A A 和和 事件事件 B B 的相互相容性。的相互相容性。n定义：定义：从从n n个不同的元素中，取个不同的元素中，取r r个不重复的元素，按次序排列
27、，个不重复的元素，按次序排列，称为从称为从n n个中取个中取r r个的个的排列排列。其排列的个数记为。其排列的个数记为P P(n,r)(n,r)表示。表示。若取出若取出r r个元素而不考虑次序，则称从个元素而不考虑次序，则称从n n个不同元中取个不同元中取r r个元个元的组合。其组合的个数记为的组合。其组合的个数记为C(n,r)C(n,r)规定：规定：rnrnrnP001),(rnrnrnrnC001),(从从n n个不同元中取个不同元中取n n个的排列称为个的排列称为n n的的全排列全排列我们有下列排列与组合的计数公式：我们有下列排列与组合的计数公式：)!(!)1()1(),(rnnrnnn
28、rnP 特别地，对于全排列有特别地，对于全排列有P P(n n,n n)=)=n n!。)!(!),(),(rnrnrrnPrnC n 从从n n个中取个中取r r个的排列的典型例子是从个的排列的典型例子是从n n个不同的球中个不同的球中,取出取出r r个个,放入放入r r个不同的盒子里个不同的盒子里,每盒每盒1 1个。第个。第1 1个盒子有个盒子有n n种选择，种选择，第第2 2个有个有n-1n-1种选择，种选择，第，第r r个有个有n-r+1n-r+1种选择。种选择。n 故有故有P(n,r)=n(n-1)(n-r+1)P(n,r)=n(n-1)(n-r+1)n 有时也用有时也用nrnr记记
29、P(n,r)P(n,r)n 若球不同，盒子相同，则是从若球不同，盒子相同，则是从n n个中取个中取r r个的个的组合组合的模型。若的模型。若放入盒子后再将盒子标号区别，则又回到排列模型。每一个放入盒子后再将盒子标号区别，则又回到排列模型。每一个组合可有组合可有r!r!个标号方案。个标号方案。n 故有故有 C(n,r)C(n,r)r!=P(n,r),r!=P(n,r),n C(n,r)C(n,r)=P(n,r)/r!=nr/r!=P(n,r)/r!=nr/r!6位女士和6位先生围着一张圆桌聚餐，要求安排女士和先生交替就座。问：有多少可能的安排方案。解解.由于要求安排女士和先生交替就座，因此可以先
30、安排六位女士坐下，两位之间留出一个空位，然后再安排先生就座。安排六位女士坐下（圆排列）的方案数是 （种）由于已经有女士在位，安排先生在六个空位上就座时，就不再是圆排列了，因为原先被看成相同圆排列的六位先生的就座方式所产生的全体人员的圆排列是不同的。故安排先生在六个空位上就座的方案数是 6！720 于是我们得到满足要求安排方案共计有A（0,0）B（5,4）求求n*m的方格图形中，从点（的方格图形中，从点（0，0）到点（）到点（n，m）的最）的最短路径数目短路径数目 我们用组合数学的思路来解题。最短路我们用组合数学的思路来解题。最短路径必定是一条只向右上走的路。设向右径必定是一条只向右上走的路。设
31、向右走一步为走一步为x，向上走一步为，向上走一步为y。则每一条。则每一条路线一定对应由路线一定对应由n个个x，m个个y共共m+n个元个元素组成的排列。以素组成的排列。以n=5,m=4为例为例 任意一条路线如下图所示，对应的任意一条路线如下图所示，对应的xy序序列为：列为：xyxxxyxyy 可见，只要能确定可见，只要能确定9个位置中个位置中4个个y的位置的位置 就唯一确定了一条路径。就唯一确定了一条路径。所以，本题答案就是所以，本题答案就是C(5+4,4)=126 一般地，一般地，n*m个方格情况就是个方格情况就是C(n+m,m)1.31.3模型转换模型转换n“一一对应一一对应”概念是一个在计
32、数中极为基本的概念。一一对应概念是一个在计数中极为基本的概念。一一对应既是单射又是满射。既是单射又是满射。n如我们说如我们说A A集合有集合有n n个元素个元素|A|=n|A|=n，无非是建立了将，无非是建立了将A A中元与中元与1,n1,n元一一对应的关系元一一对应的关系.n在组合计数时往往借助于一一对应实现模型转换。在组合计数时往往借助于一一对应实现模型转换。n比如要对比如要对A A集合计数，但直接计数有困难集合计数，但直接计数有困难,于是可设法构造一易于是可设法构造一易于计数的于计数的B B，使得，使得A A与与B B一一对应。一一对应。二、容斥原理二、容斥原理 例 求1，20中2或3的
33、倍数的个数。解 2的倍数是：2,4,6,8,10,12,14,16,18,20.(10个)3的倍数是：3，6，9，12，15，18。(6个)但答案不是10+6=16 个，因为6，12，18在两类中重复计数，应减去。故答案是：16-3=13容斥原理研究有限集合的交或并的计数。DeMorgan定理:设论域U，补集A的补集定义为|Ax xUxA且,则有(a)ABAB(b)ABABDeMogan定理的推广：1,2,.,nA AAU是的 子 集设：nnAAAAAAb2121)(nnAAAAAAa2121)(则则容斥原理：最简单的计数问题是求有限集合A和B的并的元素数目。显然有ABABAB定理：UBABA
34、定理：ABCABCABBCABC AC-ABCBACBACBCAU 例：一个学校只有三门课程：数学、物理、化学。已知修这三门课的学生分别有170、130、120人；同时修数学、物理两门课的学生45人；同时修数学、化学的20人；同时修物理化学的22人。同时修三门的3人。问这学校共有多少学生？解：令，M为修数学的学生集合；P 为修物理的学生集合；C 为修化学的学生集合；所以有3|,22|,20|,45|,120|,130|,170|CPMCPCMPMCPM170 130 120 45 20 22 3336MP CPCMPMMCP CMP C M 即学校学生数为336人。一般地，我们可得定理：定理：
35、设A1,A2,Am均为有限集，m2,则|)1(|111111mmmiijjkkjimiijjimiimAAAAAAAAAA ，其中N是集合U的元素个数，即不属于A的元素个数等于集合的全体减去属于A的元素的个数。一般有：|ANA 又又|)1(|111111mmmiijjkkjimiijjimiimmAAAAAAAANAANAA 容斥原理指的就是这两个式子。例1 求a,b,c,d,e,f六个字母的全排列中不允许出现ace和df图象的排列数。解：设A为ace作为一个元素出现的排列集，B为 df作为一个元素出现的排列集，则AB 为同时出现ace、df的排列数。根据容斥原理，不出现ace和df的排列数为
36、：!.3|,!5|,!4|BABA=6!-(5!+4!)+3!=582|BA 例2 求从1到500的整数中能被3或5除尽的数的个数。解：令 A为从1到500的整数中被3除尽的数的集合，B为被5除尽的数的集合,则3353500|,1005500|,1663500|BABA23333100166|:|BABABA所以所以 例3 求由a,b,c,d四个字母构成的n位符号串中，a,b,c至少出现一次的符号串数目。解：令A、B、C分别为n位符号串中不出现a，b，c符号的集合。由于n位符号串中每一位都可取a，b，c，d四种符号中的一个，故不允许出现a的n位符号串的个数应是：3n。1|,2|,3|CBACA
37、CBBACBAnn故有故有 a，b，c至少出现一次的n位符号串集合即为ABC123334|)|(|)|(|4|4|nnnnnCBACACBBACBACBACBA所以有所以有三、鸽巢原理鸽巢原理鸽巢原理我们可能经常会遇到这样的情况：在一桌酒席上，十来个本来不相识的人坐在一起，经过不太久的交流，马上会有人找到自己的“知音”，他们可能是校友、同行、同乡、同姓、同年龄、同属相或者是朋友的朋友、朋友的同乡、同乡的朋友等。这种情况几乎在每次酒席中都会发生，以致让人感觉到这世界真是太小。难道这都是巧合吗？聚会认友聚会认友我们经常会参加各种聚会。如果我说：在任何一种聚会中，一定有两个人，他们在场的朋友数是一样
38、多的。你一定会很吃惊。但是，我们可以用鸽巢原理来说明，这是千真万确的。聚会的朋友聚会的朋友在任何6个人中，一定可以找到3个人，他们或者互相都认识，或者互相都不认识。六个人的聚会六个人的聚会3.1鸽巢原理之一 鸽巢原理是组合数学中最简单也是最基本鸽巢原理是组合数学中最简单也是最基本的原理，也叫抽屉原理。即的原理，也叫抽屉原理。即 “若有若有n n个鸽子巢，个鸽子巢，n+1n+1个鸽子，则至少有个鸽子，则至少有一个巢内有至少有两个鸽子。一个巢内有至少有两个鸽子。”例367人中至少有人的生日相同。例10双手套中任取11只，其中至少有两只是完整配对的。例参加一会议的人中至少有人认识的别的参加者的人数相
39、等。3.2鸽巢原理之二鸽巢原理二m1,m2,mn都是正整数，并有m1+m2+mnn+1个鸽子住进n个鸽巢，则至少对某个 i 有第 i 个巢中至少有mi个鸽子，i=1,2,n 上一小节的鸽巢原理一是这一原理的特殊情况，即m1=m2=mn=2，m1+m2+mnn+1=n+1 如若不然，则对任一 i，都有第 i 个巢中的鸽子数mi1则鸽子总数 m1+m2+mnn，与假设相矛盾推论n(m1)+1只鸽子进n个巢，至少有一个巢内至少有m只鸽子推论若n个整数的平均数大于r-1，则至少有一个整数大于等于r。例4 9名数学家相遇，其中任意3人中至少有2人有共同语言，每位数学家最多会讲3种语言。证明，至少有3位数
40、学家可以用同一种语言对话。证明 把每一位数学家看成一个顶点vi，i=1，2，3,9.如果某两位数学家能用某种语言对话，则认为其相应的顶点之间有一条边（相邻），并涂相应颜色。问题是：证明至少存在3个顶点vi,vj,vk,使边 同色。913121,.,vvvvvv 考虑v1，分两种情况：（1）v1与v2,v3,v9均相邻 由于每位数学家最多会讲3种语言，故8条边 至多有三种不同的颜色，因此由鸽巢原理，至少有三条边是同色的，与此三边相关的四位数学家是有共同语言的。913121,.,vvvvvv（2）存在 j 1,使v1与 vj不相邻 此时，不妨设 j=2，由于任意3人中至少有2人有共同语言（相邻），
41、故另外七位数学家v3,v4,v9中的每一位必与v1,v2 之一相邻，从而其中至少有四位与v1或v2 相邻，不妨设v3,v4,v5,v6与v1相邻。于是四个边至多有三种不同的颜色，因此由抽屉原则，至少有两条边是同色的，与此二边相关的三位数学家是有共同语言的。注：若将9位数学家改为8位数学家，结论不真。61514131,vvvvvvvv例5 20名网球运动员进行14场单打比赛，每人至少上场一次。求证：必有6场比赛，其参赛的12名运动员各不相同。证明 把每一位运动员看成一个顶点vi，i=1，2，3,20.如果某两位运动员进行一场比赛，则认为其相应的顶点之间有一条边，如此构成一个图G。根据条件知，边数
42、为14，且 问题是：证明至少有六条边的12个顶点是互不相同的。28)(,1)(iivdvd 事实上，如果某个球员参加比赛超过一场，我们只保留其一场记录，而将其它场次去掉。用图的语言就是：在每个顶点vi处抹去d(vi)-1条边（一条边可以同时在其两端点抹去），则抹去的边数不超过 条，故剩下的图G1至少有14-8=6条边。G1中每个顶点的次数不超过1，因此6场比赛参赛者各不相同。82028 1)(201iivd四、母函数与递推关系四、母函数与递推关系 递推关系是计数的一个强有力的工具，特别是在做算法分析时是必需的。递推关系的求解主要是利用母函数。当然母函数尚有其他用处，但这主要是介绍解递推关系上的
43、应用。例如1)-1-(2 )()(1)1()1)(1(212131212121nnnnnnxaaaxaaaaaaxaaaxaxaxa 4.1 母函数定义：给定序列(a0,a1,an,)，记为an.函数f(x)=a0+a1x+anxn+称为该序列的普通母函数，简称母函数。例 常数列(1,1,)的母函数为f(x)=1+x+xn+=1/(1-x)数列C(n,i),i=0,1,2,n的母函数为nniixxinCxf)1(),()(0 这里的母函数只是“形式幂级数”，运算均按收敛幂级数进行。母函数的组合意义：考察.)()()(1.)()(1.)()(1.)()(133223222232222212121
44、 xcbccbbabcaccaabbaaxcbcbacabaxcbacxcxbxbxaxax其中：x前的系数为a,b,c的所有可重1-组合，x2前的系数为a,b,c的所有可重2-组合，一般地：xn前的系数为a,b,c的所有可重n-组合，在前式中取a=b=c=1,则xn前的系数为a,b,c的所有可重n-组合数F(3,n).0323321212121),3(.10631)1(1.)1(.)1.)(1.)(1(nnxnFxxxxxxxxxxxx所以，构造某组合问题的组合数an的母函数f(x)的基本方法为：用一个乘积因子(1+x+x2+)来代表一个所选元素，若该元素可重复n次，则因子中应出现xn。例
45、设有2个红球，3个白球，1个黑球和1个黄球.求从这些球中取出5个的不同方案数。解：设从所给球中取出i个的不同方案数为ai,则由题设可得ai的母函数为7654322322481111841)1)(1)(1()(xxxxxxxxxxxxxxf 例 求用1元和2元的钞票支付n元的不同方式数。解：设所求不同方式数为an,则由题设可得an的母函数为23222221111)()(11)(xxxxxxxxf xxxxx1111)1(241)1)(1(122 11120)1()1(1 11nnnnnnxnnxxxx两两边边求求导导数数得得由由 00004)1(32)1()1(241)(nnnnnnnnnnxn
46、xxxnxf于是定义：给定序列(a0,a1,an,)，记为an.函数称为该序列的指数型母函数,简称指数母函数。.!.!2!1)(2210 nxaxaxaaxfnne例 常数列(1,1,)的母函数为xneenxxxxf .!.!2!11)(2例 从 n 个不同元素中取 r 个的排列数P(n，r)指数母函数为：nnrrnrrexxrnCrxrnPxf)1(),(!),()(00 例 n 个不同元素的可重 r-排列数 nr(r=0,1,2,)的指数母函数为 02!.)!2!11(rnrnxnrxnexx例 求用1,2,3,4,5五个数字组成的n位数的个数，要求1出现的次数为偶数，2 出现的次数为奇数
47、，并且3至少出现一次。解：设所求n位数的个数为an，则由题设可得an的指数母函数为：.!3!2!1.!5!3!1 .!4!21.!2!11)(32534222xxxxxxxxxxxfe )1(414)1()1(22452222 xxxxxxxxxxxxxeeeeeeeeeeeee 1000!41451!)4(!)5(41)(nnnnnnnnnnenxnxnxnxxf从而有所以,.2,1 ,4145 nannn4.2 递推关系定义：设(a0,a1,an,)是一个序列，把该序列中 an 与它前面几个ai(0in)关联起来的方程称为递推关系。序列中的一些已知条件称为初始条件。例如13 ,121 na
48、anaaannnnn 2 ,122121aaaaannnn123(1)1f n=1时时,123(2)3f n=2时时,n=1时时,(1)1f 123(3)7f n=3时时,(2)3f n=2时时,n=1时时,(1)1f 1233(2)1(2)ff 1 3(2)3f n=2时时,n=1时时,(1)1f(3)fn=3时时,123(3)f 15 n=4时时,n=3时时,(2)3f n=2时时,n=1时时,(1)1f(3)7f(2)1(2)ff 1(3)f(4)f(4)f 15n=4时时,n=3时时,(2)3f n=2时时,n=1时时,(1)1f(3)7f(2)1(2)ff 1,1()2(1)1,2n
49、f nf nn (3)1(3)ff 归纳归纳:()21nf n 4.3 递推关系的求解方法（1）迭代法例如前面的Hanoi Tower（河内塔）问题：11211aaann我们有122223323212(21)12212(21)212221.nnnnnnaaaaaa 1212.22212.222321132111 nnnnannna（2）母函数法例如前面的Hanoi Tower（河内塔）问题：11211aaann由递推关系，我们有 0)(nnnxaxf01201011 aaaa我们设an的母函数为由递推关系可得 101111111111222)12(nnnnnnnnnnnnnnnnnnnnnxx
50、axxxaxxxaxaxa故有xxxfxxaxxaxaxfnnnnnnnnnnn 11)(221)(0010解得121()(12)(1)121f xxxxx 001021 ()2(2)121 (21)nnnnnnnf xxxxxx 所以12 nna（3）常系数线性递关系的解法定义：若序列（a1,a2,）满足.)(,0,.,)(.21332211为为已已知知函函数数且且为为常常数数其其中中nfbbbbnfababababakkknknnnn 则称序列an为k阶常系数线性递推关系。若 f(n)=0 则称序列an为k阶常系数线性齐次递推关系。称：xk+b1xk-1+.+bk-1x+bk=0为k阶常系
