第01讲 绪论

沈晶第1讲绪论组合数学课程简介组合数学经典问题组合数学主要应用先从数学说起……数学是研究现实世界空间形式和数量关系的科学数学发展的三个阶段古代数学(17世纪前):算术、代数、几何近代数学(17~19上):解析几何初步、微积分现代数学(19~至今):抽象代数、拓扑学、泛函分析简单复杂低级高级特殊一般从连续到离散按研究对象的连续性，现代数学可以分为两大类研究连续对象的，如数学分析研究离散对象的，如组合数学计算机出现以后，由于离散对象的处理是计算机科学的核心，研究离散对象的组合数学得到迅猛发展！组合数学的定义组合数学是一门研究将离散对象按照一定规则进行安排或配置的方法的数学。

组合数学的研究内容存在问题：符合要求的安排方案存在吗？计数问题：符合要求的安排方案有多少种？构造问题：符合要求的安排方案都是什么？优化问题：符合要求的安排方案哪个最好？组合的魅力如果石头组合得好，则能形成宏伟的建筑；如果音符组合得好，则能形成美妙的乐章；如果色彩组合得好，则能形成传世的画卷；如果词句组合得好，则能形成不朽的诗篇；如果人群组合得好，则能形成无穷的力量；如果知识组合得好，则能形成伟大的创新。

组合理论能帮助我们设计和评价组合的好坏课程教学任务培养学生的组合思维方法和组合技巧的运用使学生掌握计数的基本原理和方法使学生了解一些优化问题和模型使学生了解组合设计的基础知识主要教材参考教材课程网站考核方式第1讲绪论组合数学课程简介组合数学经典问题组合数学主要应用河图洛书上古之际，黄河之岸孟津有龙马披此图以出，伏羲得之，画大易八卦，揭天地生成之理。

洛水之滨洛宁有神龟负此书为现，大禹得之，立洪范九畴，示治国安邦之法。

Melancholia（忧郁者）德国雕刻家Albrecht Duerer 完成于1514年的的作品定义将1, 2, …, n2个连续整数，填入n×n的方格中，使横竖各行、各列以及对角线上的数字的和等于常数存在性N阶幻方是否存在（N>2都存在）？计数如果N阶幻方存在，那么有多少种不同的“样式”？构造如果N阶幻方存在，应该如何构造？3阶幻方的构造杨辉法：九子斜排，左右相更，上下对易，四维挺出4阶幻方的构造把自然方阵两对角线分别倒排第2列和第3列互换可生成另一个4阶幻方492 357 81616 2 3 135 11 10 89 7 6 124 14 15 116 3 2135 10 1189 6 7124 15 1411997年美国旅行者1号、2号宇宙飞船就带上了幻方作为人类智慧的信号幻方已在计算机程序设计、图论、人工智能、对策论、组合分析等方面有广泛的应用杨辉三角形中国最早的组合数学理论可追溯到北宋时期（约1050年）贾宪提出的三角形后被南宋数学家杨辉在“详解九章算法”（1261年）引用，被普遍称之为“杨辉三角”法国数学家帕斯卡在1654年也发现了这个三角形，比中国晚400多年11，11，2，11，3，3，11，4，6，4，11，5，10，10，5，11，6，15，20，15，6，1杨辉贾宪帕斯卡Tiling问题（贴瓷砖问题）阿基米德上图是阿基米德用希腊文写在羊皮纸上的论文手稿，论文中阿基米德是在计算把14条不规则的纸带拼成正方形一共能有多少种不同的拼法，这在现在被称为Tiling问题。

当今数学家借助计算机得出的答案是17152种拼法，这在当时是相当困难的。

Tiling问题（贴瓷砖问题）周期贴法非周期贴法对称贴法彭罗斯贴法如果一个足球表面上共有12块黑色正五边形皮子，那么，这个足球应有白色正六边形皮子多少块？哥尼斯堡七桥问题一个人怎样才能一次走遍七座桥，每座桥只走过一次，最后回到出发点？如果一个图包含一条经过每条边恰好一次的闭途径，则称这个图为欧拉图。

对任意的非空连通图，若它是欧拉的，当且仅当它没有奇度点。

欧拉对七桥问题的研究开启了图论的先河。

Euler定理EulerEuler回路旅行商问题（TSP ）TSP 是指找到一条经过每个城市一次且回到起点的最小费用的环游。

若将每个城市看成图上的节点，费用C ij 为连接节点V i 和V j 的边的权值，则TSP 就是在一个具有n 个节点的完全图上寻找花费最小的Hamilton 回路。

Hamilton 问题是图论的一个重要问题，图论中的许多问题，包括四色问题、图的因子问题，最终都与Hamilton 问题有关。

普鲁士国王腓特烈大帝在一次阅兵时提出：从不同的6个军团各选6种不同军阶的6名军官共36人，排成一个6行6列的方队，使得各行各列的6名军官恰好来自不同的军团而且军阶各不相同，应如何排这个方队？拉丁方阵⎪⎪⎪⎭⎫ ⎝⎛132213321⎪⎪⎪⎪⎪⎪⎪⎪⎭⎫⎝⎛543216432165321654216543165432654321⎪⎪⎪⎭⎫⎝⎛213132321()()()()()()()()()⎪⎪⎪⎭⎫⎝⎛2,11,33,21,23,12,33,32,21,1欧拉猜想不存在6 阶正交拉丁方不存在4k+2 阶正交拉丁方结论对任意正整数n≠2,6，则存在n阶正交拉丁方任意一张地图，用一种颜色对一个地区着色，那么一共只需要4种颜色就能保证每两个相邻的地区颜色不同。

用数学语言表示，即“将平面任意地细分为不相重迭的区域，每一个区域总可以用1、2、3、4这四个数字之一来标记，而不会使相邻的两个区域得到相同的数字。

1852年伦敦大学毕业的弗南西斯·格思里提出四色猜想；1872年著名的英国数学家凯利向数学界征求解答；数学家Heawood 花费了毕生的精力致力于四色研究，于1890年证明了五色定理；直到1976年6月，美国数学家K. Appel与W.Haken，在3台不同的电子计算机上，用了1200小时，终于证明了四色定理。

在“四色问题”的研究过程中，不少新的数学理论随之产生，也发展了很多数学计算技巧。

如将地图的着色问题化为图论问题，丰富了图论的内容不仅如此，“四色问题”在有效地设计航空班机日程表，设计计算机的编码程序上都起到了推动作用。

1958年，美国的《数学月刊》上登载着这样一个有趣的问题：“任何6个人的聚会，其中总会有3个人相互认识，或3个人相互不认识”对6个顶点的完全图K6进行红、绿两边着色，则图中一定存在一个同色的三角形Ramsey数推广到一般情况：对于任意给定的正整数a 和b，总存在一个最小整数r(a,b)，使得r(a,b)个人中或者有a 个人互相认识，或者有b 个人互相不认识。

称r(a,b) 为Ramsey数假设博物馆里有若干个房间，每个房间里有一盏灯和一个开关，每次按下某个房间的开关，可以改变这个房间以及它相邻的房间的灯的状态问是否可以找到一种开灯的方案，使得所有房间的灯由全亮变为全灭？这就是Sutner 于1989年提出的“全一问题”（All-Ones Problem)最小全一问题求操作次数最少的解称为最小全一问题对于一般图上的最小全一问题是NP完全的陈永川教授与他人合作找到了一个线性时间算法，很好地解决了树和单圈图的最小全一问题。

南开大学陈永川教授如何用最短的线路将三部电话连起来？此问题可抽象为设△ABC为等边三角形，连接三顶点的路线（称为网络）。

这种网络有许多个，其中最短路线者显然是二边之和（如AB∪AC）。

AB C但若增加一个周转站（新点P），连接4点的新网络的最短路线为PA＋PB＋PC。

最短新路径之长N比原来只连三点的最短路径O 要短。

这样得到的网络不仅比原来节省材料，而且稳定性也更好。

APB C斯坦纳最小树斯坦纳（Steiner）最小树是可以在给定的点之外再增加若干个点(称为斯坦纳点)，然后将所有这些点连起来。

如果不允许增加任何额外的点作为网络的顶点，这种最短网络称为最小生成树。

在前面的例子中Steiner 最小树的长为而最小生成树的长为2。

3Jakob SteinerPollak －Gilbert 猜想1968年贝尔实验室数学中心主任波雷克(Pollak)和研究员吉尔伯特(Gilbert)提出如下猜想：平面上任意n 点集，斯坦纳最小树长与最小生成树之长的比值的最小值是这个猜想又被称为斯坦纳比猜想。

23第1讲绪论组合数学课程简介组合数学经典问题组合数学主要应用组合数学主要应用调度排课表、赛程安排、生产调度、航班表、列车时刻表……规划机器人路径规划、网络路由、交通运输、物流管理……编码密码、纠错码、数据压缩……实验设计新药（减少人为因素）、计量（降低仪器误差）……算法分析时间复杂度、空间复杂度……其他领域金融分析、军事指挥、基因数据分析……祝大家学有所成！。