组合数学的历史、方法及在生活中的应用.doc

组合数学的历史、方法及在生活中的应用摘 要:组合数学从数千年前开始萌芽，经历了著名的幻方问题和杨辉三角，直到莱布尼茨正式提出这一科学门类。组合数学也称为组合分析或者组合学. 简单地说, 组合数学是“按照一定的规则（模式)来安排一些离散个体”.组合数学在基础理论方面和生活应用方面都发挥着越来越重要的作用, 如在计算机科学、编码和密码学、物理、化学、生物等学科中均有重要应用。本文从对组合数学历史、基本内容和基本思想,结合具体的应用举例介绍组合数学。关键词:组合数学;历史起源；基本方法；生活应用一、组合数学的历史。组合数学是一个古老而又年轻的数学分支。最早起源于幻方问题。据传说，大禹在4000多年前(2200B.C.)就观察到神龟背上的幻方.1977年美国旅行者1号、2号宇宙飞船就带上了幻方以作为人类智慧的信号。之后，希腊文写在羊皮纸上的阿基米德手稿副本，距今约1000年。2003年，科学家借助现代科技手段初步破译了这篇论文, 结论是这篇论文解决的是组合数学问题十四巧板。中国最早的组合数学理论可追溯到宋朝时期的”贾宪三角”, 后来被杨辉引用, 所以普遍称之为”杨辉三角”, 这在西方是1654年由帕斯卡提出，但比中国晚了400多年。最后是组合数学的正式提出。1666年莱布尼兹所著论组合的艺术一书问世，这是组合数学的第一部专著。书中首次使用了组合论（Combinatorics）一词。一切推理和发现，不管是否用语言描述，都能归结为如数，字，声，色这些元素经过某种组合的有序集合。2、 组合数学的基本内容与方法组合数学最早是同数论和概率论交叉在一起的.本世纪五十年代以来,特别是由于计算机科学的巨大发展,促使组合数学成为一支富有生命力的新兴数学分支.与传统的数学课程相比,组合数学研究的主要是一些离散事物之间所存在的某些数学关系,包括计数性问题、存在性问题、最优化问题以及构造性问题等,其内容主要是枚举和计数.组合学中研究最多的主要是计数问题,该问题通常出现在所有的数学分支之中.计算机科学通常需要研究有关算法的内容,就必须估计出算法所需的存储单元和运算量,即分析算法的空间复杂性和时间复杂性.关于组合数学的基本方法有一下几种：排列与组合、母函数与递推关系、容斥原理、反演公式、鸽巢原理、Plya计数定理、区组设计与编码理论等内容.仅仅知道方法是远远不够的，组合数学的一些相关思想也是非常重要的，这里总结一下几条。首先是组合对应法，在组合数学的学习中经常使用此法,可以毫不夸张的说贯穿于组合数学始终,并且该思想极易理解.设有一集合,要确定其元素个数,若直接求的元素个数则相对困难,我们可另找一集合,若在集与集间可建立一一对应的关系,并能确定中的元素个数,那么也能得到种元素的个数.其次是组合分析法，或称组合解释法,此法对组合数学的初学者来说相对重要一些,它与代数演算法有明显的区别,其思想主要是给组合数以确定的现实意义,对提出的问题给以组合解释.这种方法的特点是相对直观,便于理解和记忆,富有启发性,类似于我们在连续型数学学习中常说的“几何意义”.第三是分类法在组合数学中使用频率也较高.此方法的基本思想是:设有某一集合,根据某一准则(具体问题具体确定),将分成若干两两不交子集之并.最后，是放球模型法，此法是把很多组合问题用放球模型来模拟,尽管组合数学中处理问题的方法不带一般性,但利用此法能解决不少组合问题. 3、 组合数学在生活中的应用 组合数学是十分贴近于人们的生活的，因此组合问题在生活中非常常见。这样一个简单的组合数学问题：一个船夫要把一只狼，一只羊和一棵白菜运过河。而当人不在场时，狼要吃羊，羊要吃白菜，而他的船每趟只能运其中的一个，问人怎样才能把三者都运过河。下面介绍几种组合数学中的著名问题。中国邮差问题：由中国组合数学家管梅谷教授提出。邮递员要穿过城市的每一条路至少一次，怎样行走走过的路程最短？这不是一个NP完全问题，存在多项式复杂度算法：先求出度为奇数的点，用匹配算法算出这些点间的连接方式，然后再用欧拉路径算法求解。、 信息检索是计算机科学中一个基本而又重要的问题。如何组织数据, 使用什么样的查找方法, 对检索的效率有很大的影响。所熟知的在有序表结构上的二分搜索算法是一种很有效的方法, 那么二分搜索是最好的算法吗?Yao 4 利用Ramsey 数对这一问题作了肯定的回答。 地图着色问题：对世界地图着色，每一个国家使用一种颜色。如果要求相邻国家的颜色相异，是否总共只需四种颜色？四色定理是一个著名的数学定理。它指出，如果将平面分成一些邻接的区域，那么可以用不多于四种颜色来给这些区域染色，使得每两个邻接区域染的颜色都不一样。尽管四色定理最初提出是和地图染色工作有关，但四色定理本身对地图着色工作并没有特别的意义。人们发现，要证明宽松一点的“五定理”（即“只用五种颜色就能为所有地图染色”）很容易，但四色问题却出人意料地异常困难。曾经有许多人发表了四色问题的证明或反例，但都被证实是错误的。1977年，数学家Kenneth Appl和Wolfgang Haken借助电子计算机首次得到了一个完全的证明，四色问题也终于成为了四色定理。这是首个主要由计算机证明的定理。这个证明一开始并不为许多数学家接受，因为不少人认为这个证明无法用人手直接验证。尽管随着计算机的普及，数学界对计算机辅助证明更能接受，但仍有数学家对四色定理的证明存疑。 是否存在稳定婚姻的问题：假如能找到两对夫妇（如张（男）-李（女）和赵（男）-王（女），如果张（男）更喜欢王（女），而王（女）也更喜欢张（男），那么这样就可能有潜在的不稳定性。组合数学的方法可以找到一种婚姻的安排方法，使得没有上述的不稳定情况出现（当然这只是理论上的结论）。这种组合数学的方法却有 一个实际的用途：美国的医院在确定录取住院医生时，他们将考虑申请者的志愿的先后次序，同时也给申请排序。按这样的 次序考虑出的总的方案将没有医院和申请者两者同时后悔的情况。 实际上，高考学生的最后录取方案也可以用这种方法。组合数学还可用于金融分析：组合数学还可用于金融分析，投资方案的确定，怎样找出好的投资组合以降低投资风险。南开大学组合数学研究中心开发出了金沙股市风险分析系统现已投放市场，为短线投资者提供了有效的风险防范工具。 总之，组合数学无处不在，它的主要应用就是在各种复杂关系中找出最优的方案。所以组合数学完全可以看成是一门量化的关系学，一门量化了的运筹学，一门量化了的管理学。参考资料 4 A. C. Yao. Should T ables Be Sorted J . ACM, 1981, 28.1 陈家.组合数学在计算机科学中的应用J.成都信息工程学院学报,2006(21):94-97.2 陈永川.话说组合数学J.科学中国人,2003(5):15-17.6 左光纪.组合数学的科学艺术表现J.青海