组合数学在生活中的应用.doc

组合数学在生活中的应用数计学院 姓名：廖梓文 班别： 11数本3班 学号：2011224323 摘 要本文从对组合数学的一些基本概念和方法入手,结合具体的应用举例和数学史上的著名故事作为论题进行研究,进行了较全面的资料搜集.使人们加深对组合数学的理解,并应用于生活. 关键词:组合数学;数学游戏1 引言本文通过具体的应用实例和数学史上的一些故事和难题,介绍了组合数学是如何在生活中应用的.在研究了一些典型的例子和趣味性的故事的基础上,系统的查阅了相关文献，并结合生活中涉及组合数学的相关知识进行阐述,具体说明了组合数学的基本方法及其在生活中的应用.这样就使组合数学显得更加形象,也使抽象的理论概念变得浅显具体,更易被初学者理解和接受,以至于可以激发人们在生活中应用组合数学的意识.2 组合数学的历史组合数学是一门既古老又年轻的数学分支。随着计算机的普及推广,组合数学这门古老的学科焕发出蓬勃的生机. 组合数学不仅在基础数学研究中具有极其重要的地位，在其他的学科中也有重要的应用，如在计算机科学、编码和密码学、物理、化学、生物等学科中均有重要应用。我国古人在河图洛书中便已经对一些有趣的组合问题给出了正确的解答。中国最早的组合数学理论可追溯到宋朝时期的”贾宪三角”, 后来被杨辉引用, 所以普遍称之为“杨辉三角”, 这在西方是1654年由帕斯卡提出，但比中国晚了400多年。 近代，由于计算机的出现，组合数学这门学科得以迅猛发展，成为了一个重要的数学分支。近代图论的历史可追溯到18世纪的七桥问题穿过Knigsberg城的七座桥，要求每座桥通过一次且仅通过一次。Euler1736年证明了不可能存在这样的路线。4.组合数学的基本解题方法4.1 组合分析法组合分析法,或称组合解释法,此法对组合数学的初学者来说相对重要一些,它与代数演算法有明显的区别,其思想主要是给组合数以确定的现实意义,对提出的问题给以组合解释.这种方法的特点是相对直观,便于理解和记忆,富有启发性,类似于我们在连续型数学学习中常说的“几何意义”.例1 在一群1个人中存在两个人,他们在这群人中有相同数目的熟人（假设没有人与他/她自己是熟人）. 证明 将这个人编号为,记第i个人的熟人数为,则.如果某个人的熟人数为0,则其余-1的熟人数的范围为1,2,-2,则由鸽巢原理知必有两个人的熟人数是相同的.4.2 分类法分类法在组合数学中使用频率也较高.此方法的基本思想是:设有某一集合,根据某一准则(具体问题具体确定),将分成若干两两不交子集之并.例2 在3个孩子之间分发12个完全相同的苹果和1个橘子,使每个孩子至少得到一个水果有多少种分发方法？解 对橘子的选择与否分2种情况进行讨论,(1)先讨论橘子不分的情况.设分别为三个孩子得到的苹果数,并设他们得到的苹果数的总和为,此时的分发方法数相当于方程,其中1的整数解的个数,有种不同的分法,其中,对k求和可得该情况下的分发方法数；(2)再讨论将一个橘子分给一个孩子的情况.可从3个孩子中选择1个得到橘子,有种取法,其次再如上考虑,的意义同上,此时对苹果数总和为,分发方法数的计数相当于方程,其中0,1的整数解的个数,可算得共有种不同的分法,其中=2,3,12,对求和即可计算.综上所述可得总的分法数为.5.组合数学在生活中的应用举例组合数学在生活中的应用是方方面面的,现在就从以下几个方面来简要说明,以达到抛砖引玉的效果.5.1 乘法原则与加法原则的应用举例这两种原则是组合数学当中两个最常用和最基本的原则.那么我们就先看看这两种原则在生活中的实际应用.（以下假设和是两类互不关联、互不相同的事件.）加法原则可定义为:设事件有种选择方式,事件有种选择方式,则选或共有种方式.例如,大于1小于9的的奇数有3个,分别为3,5,7,9;大于1小于9的偶数有4个,分别为2,4,6,8.则大于1小于9的整数有7个,即2,3,4,5,6,7,8.这里事件为大于1小于9的奇数,事件为大于1小于9的偶数.而大于1小于9的整数即是属于或者属于.乘法原则可以定义为:设事件有种选取方式,事件有种选取方式,那么选取以后再选取共有种方式.例如,从3个黑人、5个白人、9个黄种人中各选出1位的方式有种方式.而从中共选出一人的方式有种方式.下面再用一个实例看看这两个法则是如何应用的.例5 某旅行社开辟了从北京去长白山和天山2条旅游线路,称为北线；从北京去西湖、黄山、峨眉山3条旅游线路,称为南线.问该社共有多少条不同的线路？如某人选定了从北京去四川,先要在西安中转,北京到西安有3种航班可选,西安到四川又有2种航班可选,问共有多少种不同的航班配置方式？分析 由所学的概率知识可知,互不相容事件,则其和的概率等于各自概率之和,即;同理,二个独立事件同时发生的概率.解 由加法原理可知,该社共有的线路条数条.由乘法原理可知,共有的航班配置方式种.5.2 哥尼斯堡七桥问题18世纪初在东普鲁土有这样一个问题:某条河上有两个岛屿,城市中的四部分可以由七个桥来连接起来那么可否经过每个桥并且每个桥只能走一次？（如图1上图所示）图1在18世纪中期,欧拉成功论证了该问题,也即是合适的方案并没有,不可能每座桥走过且仅走过一次欧拉把该实际问题形象地简化成同一平面上线与点的组合问题,将每一座桥看成一条线,每座桥所连接的地方看作点.因此,从某一点出发再回到这一点的问题,可转化成一个一笔画的问题。欧拉采用概念映像法来解决该类问题,亦即抽象分析法.将七桥问题中的桥与陆地之间的关系结构用S表示,用表示一次可否同时走过此七座桥的问题.欧拉使用了一种方法,即用概念映像将桥视为几何线,将连接的地点视为几何点,则在映像下可得到(S;)(;).如此,S则可表示如图1下图的点线图.之前的问题便对应变成能否一笔画出如图1下图所示的平面图问题.也即就是关于上述点线图的一笔画问题.欧拉的这种方法就是组合数学中后来的关系映像反演方法的