第一章(Chapter 1) 什么是组合数学

组合数学引论IntroductoryCombinatorics（第四版）(美)RichardA.Brualdi著冯舜玺罗平裴伟东译卢开澄冯舜玺校主讲教师：李向军2008年9月于南昌大学第一章(Chapter1)什么是组合数学?WhatisCombinatorics?一、组合数学发展概述组合数学问题在生活中随处可见:例如：计算下列赛制下总的比赛次数：n支球队参赛，每队只能和其他队比赛一次；创建幻方；一笔画问题（在纸上画一个网络，用铅笔沿着网络路线走，在笔不离开纸面且不重复线路的条件下，一笔画出网络）；在玩扑克牌的游戏中，计算满堂红(full-house)牌的手数，以确定出现一手满堂红的几率……等等所有这些都是组合数学问题。组合数学，又称为离散数学，但有时人们也把组合数学和图论加在一起算成是离散数学。计算机科学就是算法的科学，而计算机所处理的对象是离散的数据，所以离散对象的处理就成了计算机科学的核心，而研究离散对象的科学恰恰就是组合数学。现代数学可以分为两大类：一类是研究连续对象的，如分析、方程等，另一类就是研究离散对象的组合数学。组合数学不仅在基础数学研究中具有极其重要的地位，在其它的学科中也有重要的应用，如计算机科学、编码和密码学、物理、化学、生物等学科中均有重要应用。微积分和近代数学的发展为近代的工业革命奠定了基础，而组合数学的发展则是奠定了本世纪的计算机革命的基础。计算机之所以可以被称为电脑，就是因为计算机被人编写了程序，而程序就是算法，在绝大多数情况下，计算机的算法是针对离散的对象，而不是在作数值计算。正是因为有了组合算法才使人感到，计算机好象是有思维的。组合数学涉及到将一个集合的物体排列成满足一些指定规则的格式。研究排列的存在性（存在的必要和充分条件）研究排列的计数和分类研究研究一个已知排列的性质和结构构造一个最优的排列因此，组合数学可以一般地描述为：组合数学是研究离散结构的存在、计数、分析和优化等问题的一门科学。组合数学是一个古老而又年轻的数学分支，据传说，大禹在4000多年前就观察到了神龟背上的幻方……。贾宪，北宋数学家（约11世纪）著有：《黄帝九章细草》、《算法敩古集》（又称“古算法导引”），都已失传。杨辉著《详解九章算法》（1261年）中曾引贾宪的“开方作法本源图”（即指数为正数的二项式展开系数表，现称“杨辉三角”）和“增乘方法”（求高次幂的正根法）。前者比帕斯卡（Pascal）三角形早600年，后者比霍纳（WilliamGeoge.Horner,1786-1837）的方法（1819年）早770年。1666年莱布尼兹所著的《组合数学论文》一书问世，这是组合数学的第一部专著，书中首次使用了组合学（Combinatorics）一词。组合数学于60年代以来迅速发展的原因有：一是计算机运行程序的算法中，运行时间效率和存储需求分析需要大量的组合数学思想；二是组合数学的思想和技巧不仅正在用于数学应用的传统自然科学领域，而且也越来越多地用于社会科学、生物科学、信息论等领域。二、组合数学与计算机软件传统的计算机算法可以分为两大类，一类是组合算法，一类是数值算法（包括计算数学和与处理各种信息数据有关的信息学）。南开大学陈永川教授认为，近年来计算机算法又多了一类：那就是符号计算算法。吴文俊院士开创的机器证明方法就属于符号计算，引起了国际上的高度评价，被称为吴方法。而国际上还有专门的符号计算杂志。符号算法和吴方法跟代数组合学也有十分密切的联系。组合数学，数值计算（包括计算数学，科学计算，非线性科学，和与处理各种信息数据有关的信息学）和统计学可能是应用最广的数学分支，而组合数学的价值甚至不亚于统计学和数值计算。由于数学机械化近年来的发展和在计算机科学中的重要性，把数学机械化，科学计算和组合数学组合起来，就可以说是信息产业的基础。组合数学家H.Wilf和D.Zeilberger1998因为在组合恒等式的机械化证明方面的成果，获得1998年美国数学会的Steele奖。随着计算机网络的发展，计算机的使用已经影响到了人们的工作，生活，学习，社会活动以及商业活动，而计算机的应用根本上是通过软件来实现的。在美国有这样一种说法，将来一个国家的经济实力可以直接从软件产业反映出来。美国及欧洲的软件之所以能领先，其关键就在于在数学基础上他们有很强的实力，有很多杰出的人才。值得注意的是，印度有很好的统计和组合数学基础，这可能也是印度的软件产业近几年有很大发展的主要原因之一。目前，我国在软件产业上落后与美国等西方国家，要说出根本的原因可能并不是很简单的事，除了技术和科学上的原因外，可能还跟我们的文化，管理水平，教育水平，思想素质等诸多因素有关。除去这些人文因素以外，一个最根本的原因就是我国的信息技术的数学基础十分薄弱，这个问题不解决，我们就难成为软件强国。中国的软件产业的发展已向数学基础提出了急切的需求：网络算法和分析，信息压缩，网络安全，编码技术，系统软件，并行算法，数学机械化和计算机推理等等。与实际应用有关的还有许多许多需要数学基础的算法，如运筹规划，金融工程，计算机辅助设计等。组合数学是计算机软件产业的基础，中国最终一定能成为一个软件大国，但是要实现这个目标的一个突破点就是发展组合数学。中国在软件技术上远远落后于美国，而在组合数学上则更是落后于美国和欧洲。如果中国只是想在软件技术上跟着西方走，而不在组合数学上下功夫，那么中国的软件将一直处于落后的状态。如果我们的软件产业还是把眼光一直盯在应用软件和第二次开发，那么我们在应用软件这个领域也会让国外的企业抢去很大的市场。如果我们现在在信息技术的数学基础上，大力支持和投入，那将是亡羊补牢，犹未为晚。吴文俊院士开创和领导的数学机械化研究，为中国在信息技术领域占领了一个重要的阵地，有了雄厚的数学基础，自然就有了软件开发的竞争力。这样的阵地多几个，我们的软件产业就会产生新的局面。三、组合数学在国内外的状况纵观全世界软件产业的情况，易见一个奇特的现象：美国处于绝对的垄断地位。造成这种现象的一个根本的原因就是计算机科学在美国的飞速发展。当今计算机科学界的最权威人士很多都是研究组合数学出身的。美国最重要的计算机科学系（MIT，Princeton，Stanford，Harvard，Yale，….）都有第一流的组合数学家。组合数学在国外早已成为十分重要的学科，甚至可以说是计算机科学的基础。一些大公司，如IBM，AT&T都有全世界最强的组合研究中心。Microsoft的BillGates近来也在提倡和支持计算机科学的基础研究。例如，Bell实验室的有关线性规划算法的实现，以及有关计算机网络的算法，由于有明显的商业价值，并没有对外公开。美国已经有一种趋势，就是与新的算法有关的软件是可以申请专利的。如果照这种趋势发展，世界各国对组合数学和计算机算法的投入和竞争必然日趋激烈。美国政府也成立了离散数学及理论计算机科学中心DIMACS（与Princeton大学，Rutgers大学，AT&T联合创办的，设在Rutgers大学），该中心已是组合数学理论计算机科学的重要研究阵地。美国国家数学科学研究所（MathematicalSciencesResearchInstitute，由陈省身先生创立）在1997年选择了组合数学作为研究专题，组织了为期一年的研究活动。日本的NEC公司还在美国的设立了研究中心，理论计算机科学和组合数学已是他们重要的研究课题，该中心主任R.Tarjan即是组合数学的权威。美国重要的国家实际室（LosAlamos国家实验室，以造出第一颗原子弹著称于世），从曼哈顿计划以来一直重视应用数学的研究，包括组合数学的研究。据说该实验室承担过有关组合数学的计算机模拟项目经费达三千万美元。不仅如此，该实验室最近还在积极充实组合数学方面的研究实力。美国另外一个重要的国家实验室Sandia国家实验室有一个专门研究组合数学和计算机科学的机构，主要从事组合编码理论和密码学的研究，在美国政府以及国际学术界都具有很高的地位。由于生物学中的DNA的结构和生物现象与组合数学有密切的联系，各国对生物信息学的研究都很重视，这也是组合数学可以发挥作用的一个重要领域。据说IBM也将成立一个生物信息学研究中心。由于DNA就是组合数学中的一个序列结构，美国科学院院士，近代组合数学的奠基人Rota教授预言，生物学中的组合问题将成为组合数学的一个前沿领域。美国的大学，国家研究机构，工业界，军方和情报部门都有许多组合数学的研究中心，在研究上投入了大量的经费。但他们得到的收益远远超过了他们的投入，更主要的是他们还聚集了组合数学领域全世界最优秀的人才。高层次的软件产品处处用到组合数学，更确切地说就是组合算法。欧洲也在积极发展组合数学，英国、法国、德国、荷兰、丹麦、奥地利、瑞典、意大利、西班牙等国家都建立了各种形式的组合数学研究中心。南美国家也在积极推动组合数学的研究。澳大利亚，新西兰也组建了很强的组合数学研究机构。亚洲的发达国家也十分重视组合数学的研究。日本有组合数学研究中心，并且从美国引进人才，不仅支持日本国内的研究，还出资支持美国的有关课题的研究，这样使日本的组合数学这几年的发展极为迅速。台湾、香港两地也从美国引进人才，大力发展组合数学。新加坡，韩国，马来西亚也在积极推动组合数学的研究和人才培养。台湾的数学研究中心也正在考虑把组合数学作为重点方向来发展。中国自1997年11月的南开大学组合数学研究中心成立以来，北京大学、清华大学、东南大学、华南理工大学等高校先后成立了组合数学研究所或研究小组，并分别召开了多次组合数学与计算理论方向的国际、国内会议，共同推动我国组合数学的研究和人才培养。组合数学主要研究工具之一为：数学归纳法。一般来说，用数学归纳法证明一个强结果比证明一个弱结果更容易，其技巧在于找到假设的正确平衡来进行归纳。学好组合数学的方法：必须具有钻研精神和敏锐的洞察力，并会利用它们掌握我们后续阶段将要介绍的组合数学的一般原则和方法，通过大量的实践积累这些原则和方法的应用经验。一句话，“用组合数学解决问题一般说来和用数学解决问题一样，你解决的问题越多，那么能够解决下一个问题的可能性也就越大”。四、组合数学研究工具和学习特点棋盘的完美覆盖切割立方体幻方四色问题36军官问题最短路经问题Nim取子游戏其他例子五、组合数学花絮棋盘的完美覆盖设有8×8的国际象棋盘一张，形状一样的多米诺牌32张（每张牌恰好覆盖棋盘上相邻的两个方格），那么能否将这32张牌摆放到棋盘上，使得任何两张牌均不重叠，每张牌覆盖两个方格，并且棋盘上所有方格都被覆盖住？我们称这样的一种排列为期盼的完美覆盖。这是一个简单的排列问题，容易构造许多不同的完美覆盖。但是，计算不同的完美覆盖的总数却不是一件容易的事。（最早，由Fischer在1961年发现，它是12988816=24×（901）2）切割立方体现有一个边长为3英尺的立方体木块，希望把它切割成27个边长为1英尺的小立方体，完成这项工作所需的最少切割次数是多少？如果在每次切割后重新排放所切得的方块，是否能用更少的切割次数完成这项工作？实际上，要切的木头块数以及木头块的排列方式数随着切割的进行而增加，这是一个比较难分析的困难问题。幻方N阶幻方可以看作是一个n阶方阵，其元素是1到n×n的正整数，每行每列以及两条对角线上元素之和都等于同一个数s（幻方的幻和），如图一所示是一个三阶幻方：618753294图一组合数学中有许多象幻方这样精巧的结构。1977年美国旅行者1号、2号宇宙飞船就带上了幻方以作为人类智慧的信号。四色问题考虑一张平面地图或球面地图，地图上的国家都是连同的区域，为区分不同国家，需要对这些国家着色，以使得具有共同边界的国家被涂成不同的颜色，那么能够保证如此着色每一张地图所需的最少颜色数是多少？这个问题由FrancisGuthrie于1850年首先提出。1976年Apple与Haken宣称已得到问题的证明（一共只需要四种颜色），最近人们才发现了一个更简单的证明。（计算机计算大约1200小时，100亿个分离的