还剩21页未读,继续阅读
本资源只提供10页预览,全部文档请下载后查看!喜欢就下载吧,查找使用更方便
文本内容:
本科毕业论文第22页共23页1引言说起来,组合数学是一门很古老的科学,人们对它的兴趣和研究肇源颇早,它起始于数学游戏,起初只是研究娱乐或审美要求所涉及的组合问题,据传,早在《河图》、《洛书》中我国人民就已对一些有趣的组合问题给出了正确的解答贾宪,北宋数学家(约11世纪)著有《黄帝九章细草》、《算法斅古集》(“古算法导引”)都已失传杨辉著《详解九章算法》(1261年)中曾引贾宪的“开方作法本源”图(即指数为正整数的二项式展开系数表,现称“杨辉三角形”)和“增乘开方法”(求高次幂的正根法)前者比帕斯卡三角形早600年,后者比霍纳(WilliamGeogeHorner,1786-1837)的方法
(1819)早770年1666年莱布尼兹所著《组合学论文》一书问世,这是组合数学的第一部专著书中首次使用了组合论(Combinatorics)一词但是,这门学科的飞速发展和不完善则是近几十年的事这是多种因素促进的结果一方面,它受到了许多新兴的应用和理论学科的推动和__,诸如计算科学、数字通讯理论、规划论和试验设计等等另一方面,它自身内部的要求和力量也使它不停息地向前发展,因而这门具有悠久___学科又焕发出青春的光彩,在近几十年来显得异常活跃,并且颇富成果今天无论在基础理论方面还是在应用科学当中都起着非常重要的作用,它已经发展成为数学的一个重要分支,而且其影响正在迅速扩大还有一个重要的原因,就是计算机的发展对社会所产生和将继续产生的巨大冲击力由于计算机的闪电般的运算速度,为用组合数学来解决实际问题提供了一个理想的工具,要解决过去根本无法想象的大规模问题,现在已经成为可能与现实对于组合数学人们有不同的认识有人认为广义的组合数学就是离散数学http://zh._________.org/w/index.phptitle=%E7%A6%BB%E6%95%A3%E6%95%B0%E5%AD%A6variant=zh-cn\o离散数学,也有人认为离散数学是狭义的组合数学和图论http://zh._________.org/w/index.phptitle=%E5%9B%BE%E8%AE%BAvariant=zh-cn\o图论、代数结构http://zh._________.org/w/index.phptitle=%E4%BB%A3%E6%95%B0%E7%BB%93%E6%9E%84variant=zh-cn\o代数结构、数理逻辑http://zh._________.org/w/index.phptitle=%E6%95%B0%E7%90%86%E9%80%BB%E8%BE%91variant=zh-cn\o数理逻辑等的总称但这只是不同学者在叫法上的区别组合数学问题在生活中随处可见例如,n个球队参赛,每队只和其他队比赛一次,计算在此赛制下总的比赛次数网络路径问题,计算两点之间路径有几种还有身边普遍的分组问题所有这些都是组合数学问题过去研究过的许多问题,不论出于消遣还是出于对其美学的考虑,如今在纯科学和应用科学中都具有高度的重要性组合数学算法与计算机技术的结合在现代科学技术领域发挥着极为重要的作用对从事数学的人员来讲,学习数学组合可以提高分析问题的能力;对从事计算机的人员来讲,若没有组合数学的基础,就难以深入研究与分析有关算法所以说,组合数学不仅是近年来最活跃、最迷人的数学分支,也是计算机科学技术的重要理论基础之一组合数学近期发展的另一个重要原因是它对于那些过去很少与数学正式接触的学科的适用性由此我们发现,组合数学的思想和技巧不仅仅正在用于数学应用的传统自然科学领域,而且也用于电子工程、数字通信、物理学、力学、管理科学等诸多领域此外,组合数学和组合学思想在许多数学分支中已经变得越来越重要组合数学中有许多计数和归纳原理本文主要讨论网络路径问题、母函数与排列组合、容斥原理以及几何图形计数1.1课题的背景及研究的目的和意义组合数学在在日常生活中的作用日益明显,本论文主要介绍研究组合数学中的四种组合方法本论文主要目是对四种组合方法进行分析,研究其在简单数学问题中的应用运用离散数学的思维培养自身分析、解决数学问题的能力讨论组合方法在简单数学问题中的应用是本论文研究的中心1.2本课题研究的内容本论文主要研究的内容是对网络路径问题、母函数与排列组合、容斥原理以及几何图形计数等四种组合方法进行分析,研究其在简单数学中的应用并且给出四种组合方法的基本组合解释,并应用这些组合方法解决简单的组合问题,理解组合方法在组合数学研究中的重要意义培养自己初步研究数学问题的能力,从而使自己具有一定的科研__性2网络路径问题
2.1路径问题的矩阵算法路径问题是组合数学中的一个重要问题,本论文主要是在提出的矩阵算法的例子中总结出一般算法首先规定所要讨论的图为简单的有向图,其中表示非空__,,其元素称为弧定义矩阵,其中若从点到点有边相连,则,若从点到点无边相连,则中元素为1,表示1条从一步到的道路我们再看,其中.当且仅当,也就是说从到和从到都有直接相通的道路,所以的值表示从点出发经过,再到的路径数目进而,一般有,其中,表示从出发k步到达的路径数目
2.2矩阵算法与乘法原理、加法原理的统一性
2.
2.1加法、乘法原理加法原理如果完成一件工作,只要采取n类方式中的某一种方式就可以完成,第一类方式有种做法,第2类方式有种做法,,第n类方式有种做法,那么,完成这件工作共有种做法乘法原理如果完成一件工作,必须依次经过n个步骤,第1步有种做法,第2步有种做法,,第n步有种做法,那么,完成这件工作共有种做法
2.
2.2建立模型例下图为从重庆到义和的路线模型,问共有多少种不同的走法
2.
2.
2.1用加法、乘法原理分析解决问题第一种,从重庆→义和,1种走法;第二种,从重庆→开县→义和,种走法;第三种,从重庆→达州→开江县→梅家坝→义和↓→开县→义和,种走法,所以从重庆到义和共有5种不同的走法
2.
2.
2.2用矩阵方法分析解决问题为了方便表示,用分别表示重庆、达州、开江县、梅家坝、义和、开县、万县,得到一个单向图,其中表示7个地点,U表示路线,即下图所示问题就转变为从到共有几条不同的道路引进矩阵,其中若从点到点有边相连,则;若从点到点无边相连,则.得到从A中可以看出到有一条直通道路,相当于上述分类中的第一类从可以看出到有一条经过一个站的道路,相当于上述分类的第二类.从中可以看出从到有一条经过两个车站的道路,相当于上述分类中的第三类.从中可以看出从到有两条经过三个车站的道路,相当于上述分类中的第四类因为,表示没有五步到达的道路,也就是说从到经过四个车站的道路不存在,为0条
2.
2.
2.3分析矩阵算法与乘法、加法原理的统一性表示按步骤分成四类,将所得出来的相加,这便是所要求的结果,应用了加法原理而在得出值的过程中,应用了乘法原理
2.3矩阵算法在组合数学中路径问题的应用组合数学中的路径问题在现实中错综复杂,用矩阵算法能较简便的解决这样的问题现给出现实的实例,如下图所示,代表着6个城市问
(1)从到是否有直接到达的车道?2从到经过三步到达的,共有几条不同的道路?解
(1)引进矩阵,若从到有边相连,则;若从到无边相连,则.则能独处矩阵从矩阵A中易得能直达;能直达;能直达;能直达;能直达;能直达
(2)用矩阵法计算到京三步的道路则由中可以看出,从经过三城到有6条不同的道路路径问题是组合数学中重要的又比较复杂的问题,有时候借用矩阵算__化繁为简,是个比较实用的解决方法3母函数与递推关系
3.1定义定义
1、普母函数对于数列,称为数列的普母函数定义
2、指母函数对于数列,称为数列的指母函数定义
3、递推关系若数列的一般项间有恒等关系,则称为数列的递推关系
3.2基本步骤利用母函数求解各类递推关系具有广泛的实用性,其基本步骤如下
(1)令.
(2)将关于的递推关系式转化成关于的方程式
(3)解出,将展开成x的幂级数,的系数既是
3.3例子例1设满足递推关系的数列,其中,求的一般公式解设序列的普母函数为,则有下列4个方程相加得由,得又因为,所以对常数解得因此有又因为因为因为是的生成函数,所以得例2求满足条件的递推关系解利用指母函数进行求解把题目中的式子进行化简,再令用乘的两端,并求和,能够得到上式左边,而右边第一项为,第二项为,即的展开式所以式子就变成了,因此有.把上式中的写成并展开,得到下列表达式.变形后得.因此的系数就变成了.这就是所求的的一般式
3.4分析总结由上边的两个例子可以看出利用母函数求解递推关系的方法是比较适用的组合数学的重要性在实际生活中已经日益明显在各个方面已经得到了广泛的使用,由理论走向了实践应用利用母函数来求解递推关系在实际中也有其作用递推关系在现实中进行分析预测时能够发挥很好的作用递推关系是计数的一个强有力的工具,在进行算法分析时是必需的上边所提出的求解递推关系的步骤是比较广泛适用的基本步骤,具体问题再具体分析4容斥原理与错位排列
4.1容斥原理容斥原理又称包含排斥原则,交叉分类原理,筛法公式,是计数法则——和则的一种__形式容斥原理的简单形式
(1)__内的容斥原理,又称容斥公式设__A包含这n个有限__,则有
(2)__外的容斥原理,又称逐步淘汰公式设,则有容斥原理的一般形式
4.2限位排列定理1限位排列数为,式子中,是有i个棋子布置到限位排列部分的方案数证明一个棋子落入限位部分的方案数为,剩下的n-1个棋子为无限制条件的排列,所以至少有一个棋子进入限位部分的方案数为,两个棋子落入限位部分的方案数为,而其余n-2个棋子为无限制条件的排列,所以至少有两个棋子进入限位部分的方案数为,其余类推根据容斥原理,n个棋子无一落入限位部分的方案数应为例有甲乙丙丁四个人完成ABCD四项任务,但是甲不能从事任务B,乙不能从事任务BC,丙不能从事任务CD,丁不能从事任务D若要求每人从事一项任务,有多少种不同的方案?解每一种分配方案相当于ABCD的限位排列限位部分的棋牌多项式为,即,所求的方案数
4.3绝对错位排列定理2对于,有绝对错位排列数为.证明设是__的全部个排列中满足第j个位置上恰好是j的排列的特性,那么__便是S的排列中所有满足性质的__所以有由于中的每个排列均具有形式其中是__的一个—排列显然,这种排列有个所以又因为中的每个排列都具有形式其中是__的一个—排列,显然,这种排列有个因此,.对于的任意k—组合,有.另外,由于存在__的个k—组合应用容斥原理定理得证例1在一个聚会结束后,有10位先生要取回他们的帽子,有多少种方式使得这些人中没有人能够拿回他们来时所戴的帽子?解用公式计算得.例2数的全排列中,求偶数在原来位置上,其余都不在原来位置上的错排数目解由题意知,本题实际上是这5个数的错排问题即所以
4.4相对的禁排列位置问题定理3对于,证明令为__的全部个n—排列的__为排列中出现模式的性质,为满足性质的排列的__,因此,下面分析每个的数量中的排列必定出现12这样的子串,即对进行全排列所以对一般的每个有,将它们加起来得对于中任意两个的交,比如是中的排列包含2种模式共享同一个元素,如;没有共享的元素,如情况下就如同排列中有子串,n个元素中有3个合并成1个,就是的全排列;;情况下就如同排列中有子串就是的全排列;;一般地,更一般地,对于中的每个k—组合有由于对每一个(有相邻的子串就一定少一个元素),存在__的个k—组合,应用容斥原理得到公式所以,定理得证例某班8个男生每天跑步,他们排成一竖行,除了第一个领跑的男生外,每个男生前面都有另一个男生,为了不让他们总看见前面的同一个人,第二天要交换位置,使得前面的人与前一天的不同他们有多少交换位置的方法?解根据定理3得5几何图形计数
5.1计数方法在几何学中,计数问题是比较有趣的,比如计算线段的条数,具备要求的三角形个数若干图分平面所得的区域数等等此类的问题看似没有规律,但是通过分析,还是可以得到一些方法的比如枚举法、加法原理和乘法原理法、递推法以及折线法
5.2计数方法在几何图形中的应用
5.
2.1枚举法例1如下图所示,数一数图中有多少条不同的线段?解对于两条线段,只要有一个端点不同,就是不同的线段,所以,以左端点为标准,线段分5类计数以A为左端点ABACADAEAF共5条;以B为左端点BCBDBEBF共4条;以C为左端点CD__CF共3条;以D为左端点DEDF共2条;以E为左端点EF只一条所以不同的线段一共有5+4+3+2+1=15(条)如果一条线段上有个点(包括两个端点),那么这个点把这条线段一共分成的线段总数为例2下图中有多少个三角形?解枚举法(三角形不重复计算)以为一边的三角形共5个;以为一边的三角形共4个;以为一边的三角形共3个;以为一边的三角形共2个;以为一边的三角形只1个所以,共有三角形个数5+4+3+2+1=15(个)本三角形图形中,不同三角形的个数就等于中不同线段的条数一般情况下,当原三角形的一条边上有个点(包括两端点)时,它们与另一个顶点的连线所构成的三角形总数为
5.
2.2加法原理和乘法原理法例1下图中一共有多少个长方形?所有这些长方形的__和是多少解图中长边有5个分点(包括端点,长边不同线段共有易得宽边不同线段也有10条所以,共有长方形(个)长边10条线段长分别为5172526122021891;宽边10条线段长分别为
261316411147103.所以,所有长方形__和为
5.
2.3递推法例1问8条直线最对能把平面分成多少部分?解1条直线最多将平面分成2部分;2条直线最多将平面分成4部分;3条直线最多将平面分成7部分;现在加上第4条直线,它与前面的3条直线最多有3个交点,这三个交点将第4条直线分成4段,其中每一段将原来所在平面部分再一分为二,如下图,所以,4条直线最多将平面分成7+4=11个部分类似地,5条直线最多将平面分成11+5=16个部分;6条直线最多将平面分成16+6=22个部分;7条直线最多将平面分成22+7=29个部分;8条直线最多将平面分成29+8=37个部分因此,8条直线最多将平面分成37个部分结论一般地,n条直线最多将平面分成个部分例2平面上5个圆最多能把平面分成多少个部分?解1个圆最多能把平面分成2个部分;2个圆最多能把平面分成4个部分;3个圆最多能把平面分成8个部分;现在加入第4个圆,为了使分成的部分最多,第4个圆必须与前面的3个圆都有2个交点,如图中所示所以得到6个交点,这6个交点将第4个圆的圆周分成6段圆弧,而每一段圆弧将原来的部分一分为二,即增加了一个部分,于是,4个圆最多将平面分成8+6=14个部分类似的,5个圆最多将平面分成14+8=22个部分因此,5个圆周最多将平面分成22个部分结论,一般地,n个圆最多分平面的部分书为
5.
2.4折线法定理1平面上两个格点与可用折线法相连的充要条件是且为偶数证明充分性在折线的一节上,若左端点为,则右端点只能是或所以如果有一条折线链接与,则只能是加上若干个1或者-1的结果,且1与-1的总数为n若设有k个1,n-k个-1,则,可以改写为或由第一式及,即知;而由第二式,则知为偶数必要性因为是偶数,可令因为,可知则可在与如下连出折线其中,第一段由斜率1的k节组成,第二段由斜率-1的节组成定理2设与为平面上可连折线的两点,则到的折线条数等于,式中;时,到的与x轴相交的折线条数等于,也等于到的折线条数,其中;时,到的与仅在终点相交的折线条数,也等于到的与仅在始点相交的折线数,其中证明由定理1的证明易得,每条这样的折线是由k个1与n-k个-1的线形排列所决定的,所以折线共有条如图所示,实线所示为一条到的与x轴相交的折线设其与x轴的最左方交点为将到的折线关于x轴的对称折线以虚线画出,这样就有了折线与折线的全部折线间的一一对应进而,由即可得知折线条数如图所示,实线所示为一条到的与仅交于N点的折线以中心P点为对称中心可得到虚线所示的一条折线,它与仅交于点M这显然是一种一一对应所以可以得知,定理所述两类折线条数相等下面计算与仅交于M点的虚线折线条数为此,将x轴平移到M点,所述折线既是新坐标系中与横轴仅交于M点一处(注意,此时点坐标已经变为及),即由到且与横轴不相交的根据和的结论可知所求的折线条数为全部条数减去与横轴相交的条数采用的记号,即是例有2n个人排队购入场券,每人限购一张,票价1元若有n个人仅各有1元人民币一张,另n个人仅各有2元人民币一张售票处开始售票时只有3张1元人民币问有多少种队形排列可使所有的人均顺利购票(不发生找不开钱的情况)?解以记售票处卖第k个人的票时1元人民币的收支情况若第k个人持1元款,则(即售票处收入一张1元币);若持2元币则(即售票处支出一张1元币)令(即未卖票时售票处有3张1元币),则将表示售票处卖出k张票后尚留有的1元人民币的张数按照题目的要求,需要对任意的始终有显然,且(因为取1或者-1的值各1个)因为恒为1或者-1,所以可考察折线如果不考虑人与人之间的区别,仅考虑他们所持有的币是1元的还是2元的,则问题的答案应当是格点到的不超越x轴的折线条数,如图所示若将x轴向下平移一个单位,则它等价于到的不与x轴相交的折现条数按照定理2中的,它等于然而持票人都是有区别的,对持1元币与持2元币的各n个人分别进行全排列,即知问题的最终答案为结论组合数学已经成为了现代数学学科中发展较快的一个分支,也是一个极为重要的分支本文对路径问题,母函数与递推关系,容斥原理与排列问题以及几何图形计数问题进行了简单的阐述研究不利用简单实际的例子来加深理解这四种组合方法在解决数学问题是也比较实际本文的重点是在这四种组合方法的应用上本文在写作方法上采用的是逻辑顺序的观念先对需要的组合方法进行简单的阐述,有了初步的理解之后,再结合各种实际例子来理解组合方法在数学中的应用我对相关资料进行了大量的收集,阅读了不少的文献,借鉴前人的成果,让理论与实际相结合但是毕竟学习组合方法的时间还是很短,对一些重点,精华的部分还是把握不好,请各位老师批评指正致谢大学时间过得好快,转眼间就要离开这所学校了,大学四年,有许多的收获,也有些缺乏进取心的感慨谈到感谢,首先要感谢河北科技大学,是科大给了我四年的学习机会,让我在这充满学习与浪漫色彩的校园学会了许多专业知识,学到了更多的为人处世的方式,使我在各个方面都有很大的进步感谢未来的母校——科大大学四年,理学院老师让我领略到更多的数学风格,数学魅力,以及相关专业的老师,是你们的教学使我学到了很多专业知识,为以后的人生道路指明了道路谢谢各位老师本论文是__在吕仑老师悉心指导下完成的,在相处的几个月中,是吕仑老师让我了解到了组合数学的魅力所在,让我能够再次__到数学的博大精深是吕老师在___教学工作中抽出时间为我作指导,给我指出缺点,帮助我改正错误吕老师有很深的数学造诣,他有着严谨的逻辑思维,深厚的数学功底另外吕老师待人非常随和,和气无论是学习专业知识还是做人方面,吕老师都是我学习的榜样在此,感谢吕老师对我的学习上的批评与指导,感谢吕老师在做人方面对我的良好影响祝愿吕老师工作顺利,在数学上有更多的成就____1田秋成.组合数学.北京电子工业出版社,20062 王元元,王庆瑞,黄纪麟.组合数学理论与解题.____科学技术文献出版社,19__3马光思.组合数学.西安西安电子科技大学出版社,20024卢开澄.组合数学.北京清华大学出版社,19915孙世新,张先迪.组合原理及其应用.北京国防工业出版社,20066H.J.Ryser.Combinatorial__the__tics.__the__ticalAssociationofAmericaProvidence19637吴正声,孙志人.组合数学初步.南京师范大学出版社20018RichardA.Brualdi.IntroductoryCombinatorics.America机械工业出版社,20059屈婉玲.组合数学.北京大学出版社,19__10金成梁.小学数学竞赛教程.中国矿业大学出版社,199311孙世新.组合数学.成都电子科技大学出版社,200312卢开澄,卢明华.组合数学.北京清华大学出版社,2002PAGE。