网络路径问题、母函数与排列组合、容斥原理论文.doc

1、 本 科 毕 业 论 文 第 23 页 共 23 页1 引言说起来，组合数学是一门很古老的科学，人们对它的兴趣和研究肇源颇早，它起始于数学游戏，起初只是研究娱乐或审美要求所涉及的组合问题，据传，早在河图、洛书中我国人民就已对一些有趣的组合问题给出了正确的解答。贾宪，北宋数学家（约11世纪）著有黄帝九章细草、算法斅古集（“古算法导引”）都已失传。杨辉著详解九章算法（1261年）中曾引贾宪的“开方作法本源”图（即指数为正整数的二项式展开系数表，现称“杨辉三角形”）和“增乘开方法”（求高次幂的正根法）。前者比帕斯卡三角形早600年，后者比霍纳（William Geoge Horner，1786-18

2、37）的方法（1819）早770年。1666年莱布尼兹所著组合学论文一书问世，这是组合数学的第一部专著。书中首次使用了组合论（Combinatorics）一词。但是，这门学科的飞速发展和不完善则是近几十年的事。这是多种因素促进的结果。一方面，它受到了许多新兴的应用和理论学科的推动和刺激，诸如计算科学、数字通讯理论、规划论和试验设计等等。另一方面，它自身内部的要求和力量也使它不停息地向前发展，因而这门具有悠久历史的学科又焕发出青春的光彩，在近几十年来显得异常活跃，并且颇富成果。今天无论在基础理论方面还是在应用科学当中都起着非常重要的作用，它已经发展成为数学的一个重要分支，而且其影响正在迅速扩大。

3、还有一个重要的原因，就是计算机的发展对社会所产生和将继续产生的巨大冲击力。由于计算机的闪电般的运算速度，为用组合数学来解决实际问题提供了一个理想的工具，要解决过去根本无法想象的大规模问题，现在已经成为可能与现实。对于组合数学人们有不同的认识。有人认为广义的组合数学就是离散数学，也有人认为离散数学是狭义的组合数学和图论、代数结构、数理逻辑等的总称。但这只是不同学者在叫法上的区别。组合数学问题在生活中随处可见。例如， n个球队参赛，每队只和其他队比赛一次，计算在此赛制下总的比赛次数。网络路径问题，计算两点之间路径有几种。还有身边普遍的分组问题。所有这些都是组合数学问题。过去研究过的许多问题，不论出

4、于消遣还是出于对其美学的考虑，如今在纯科学和应用科学中都具有高度的重要性。组合数学算法与计算机技术的结合在现代科学技术领域发挥着极为重要的作用。对从事数学的人员来讲，学习数学组合可以提高分析问题的能力；对从事计算机的人员来讲，若没有组合数学的基础，就难以深入研究与分析有关算法。所以说，组合数学不仅是近年来最活跃、最迷人的数学分支，也是计算机科学技术的重要理论基础之一。组合数学近期发展的另一个重要原因是它对于那些过去很少与数学正式接触的学科的适用性。由此我们发现，组合数学的思想和技巧不仅仅正在用于数学应用的传统自然科学领域，而且也用于电子工程、数字通信、物理学、力学、管理科学等诸多领域。此外，组

5、合数学和组合学思想在许多数学分支中已经变得越来越重要。组合数学中有许多计数和归纳原理。本文主要讨论网络路径问题、母函数与排列组合、容斥原理以及几何图形计数。11 课题的背景及研究的目的和意义组合数学在在日常生活中的作用日益明显，本论文主要介绍研究组合数学中的四种组合方法。本论文主要目是对四种组合方法进行分析，研究其在简单数学问题中的应用。运用离散数学的思维培养自身分析、解决数学问题的能力。讨论组合方法在简单数学问题中的应用是本论文研究的中心。12 本课题研究的内容本论文主要研究的内容是对网络路径问题、母函数与排列组合、容斥原理以及几何图形计数等四种组合方法进行分析，研究其在简单数学中的应用。并

6、且给出四种组合方法的基本组合解释，并应用这些组合方法解决简单的组合问题，理解组合方法在组合数学研究中的重要意义。培养自己初步研究数学问题的能力，从而使自己具有一定的科研独立性。2 网络路径问题2.1 路径问题的矩阵算法路径问题是组合数学中的一个重要问题，本论文主要是在提出的矩阵算法的例子中总结出一般算法。首先规定所要讨论的图为简单的有向图，其中表示非空集合，其元素称为弧。定义矩阵，其中：若从点到点有边相连，则，若从点到点无边相连，则。中元素为1，表示1条从一步到的道路。我们再看，其中：.当且仅当，也就是说从到和从到都有直接相通的道路，所以的值表示从点出发经过，再到的路径数目。进而，一般有，其中

7、，表示从出发k步到达的路径数目。2.2 矩阵算法与乘法原理、加法原理的统一性2.2.1 加法、乘法原理加法原理：如果完成一件工作，只要采取n类方式中的某一种方式就可以完成，第一类方式有种做法，第2类方式有种做法，第n类方式有种做法，那么，完成这件工作共有种做法。乘法原理：如果完成一件工作，必须依次经过n个步骤，第1步有种做法，第2步有种做法，第n步有种做法，那么，完成这件工作共有种做法。2.2.2 建立模型例 下图为从重庆到义和的路线模型，问共有多少种不同的走法?2.2.2.1 用加法、乘法原理分析解决问题第一种，从重庆义和，1种走法；第二种，从重庆开县义和，种走法；第三种，从重庆达州开江县梅

8、家坝义和 开县义和 ，种走法。，所以从重庆到义和共有5种不同的走法。2.2.2.2 用矩阵方法分析解决问题为了方便表示，用分别表示重庆、达州、开江县、梅家坝、义和、开县、万县，得到一个单向图，其中表示7个地点，U表示路线，即下图所示。问题就转变为从到共有几条不同的道路。引进矩阵，其中：若从点到点有边相连，则；若从点到点无边相连，则.得到从A中可以看出到有一条直通道路，相当于上述分类中的第一类。从可以看出到有一条经过一个站的道路，相当于上述分类的第二类。.从中可以看出从到有一条经过两个车站的道路，相当于上述分类中的第三类。.从中可以看出从到有两条经过三个车站的道路，相当于上述分类中的第四类。因为

9、，表示没有五步到达的道路，也就是说从到经过四个车站的道路不存在，为0条。2.2.2.3 分析矩阵算法与乘法、加法原理的统一性表示按步骤分成四类，将所得出来的相加，这便是所要求的结果，应用了加法原理。而在得出值的过程中，应用了乘法原理。2.3 矩阵算法在组合数学中路径问题的应用组合数学中的路径问题在现实中错综复杂，用矩阵算法能较简便的解决这样的问题。现给出现实的实例，如下图所示，代表着6个城市。问：（1）从到是否有直接到达的车道？(2)从到经过三步到达的，共有几条不同的道路？解：（1）引进矩阵，若从到有边相连，则；若从到无边相连，则.则能独处矩阵从矩阵A中易得：能直达；能直达；能直达；能直达；能

10、直达；能直达。（2） 用矩阵法计算到京三步的道路。则由中可以看出，从经过三城到有6条不同的道路。路径问题是组合数学中重要的又比较复杂的问题，有时候借用矩阵算法会化繁为简，是个比较实用的解决方法。3 母函数与递推关系3.1定义定义1、普母函数：对于数列，称为数列的普母函数。定义2、指母函数：对于数列，称为数列的指母函数。定义3、递推关系：若数列的一般项间有恒等关系，则称为数列的递推关系。3.2 基本步骤利用母函数求解各类递推关系具有广泛的实用性，其基本步骤如下：（1） 令.（2） 将关于的递推关系式转化成关于的方程式。（3） 解出，将展开成x的幂级数，的系数既是。3.3 例子例1 设满足递推关系

11、：的数列，其中，求的一般公式。解：设序列的普母函数为，则有下列4个方程相加得由，得又因为，所以对常数解得：因此有又因为：因为因为是的生成函数，所以得：例2 求满足条件的递推关系：解：利用指母函数进行求解。把题目中的式子进行化简：，再令。用乘的两端，并求和，能够得到上式左边，而右边第一项为，第二项为，即的展开式。所以式子就变成了，因此有.把上式中的写成并展开，得到下列表达式.变形后得.因此的系数就变成了.这就是所求的的一般式。3.4 分析总结由上边的两个例子可以看出利用母函数求解递推关系的方法是比较适用的。组合数学的重要性在实际生活中已经日益明显。在各个方面已经得到了广泛的使用，由理论走向了实践

12、应用。利用母函数来求解递推关系在实际中也有其作用。递推关系在现实中进行分析预测时能够发挥很好的作用。递推关系是计数的一个强有力的工具，在进行算法分析时是必需的。上边所提出的求解递推关系的步骤是比较广泛适用的基本步骤，具体问题再具体分析。4 容斥原理与错位排列4.1 容斥原理容斥原理又称包含排斥原则，交叉分类原理，筛法公式，是计数法则和则的一种推广形式。容斥原理的简单形式：（1）集合内的容斥原理，又称容斥公式。设集合A包含这n个有限集合，则有（2）集合外的容斥原理，又称逐步淘汰公式。设，则有 容斥原理的一般形式：4.2限位排列定理1 限位排列数为，式子中，是有i个棋子布置到限位排列部分的方案数。

13、证明 一个棋子落入限位部分的方案数为，剩下的n-1个棋子为无限制条件的排列，所以至少有一个棋子进入限位部分的方案数为，两个棋子落入限位部分的方案数为，而其余n-2个棋子为无限制条件的排列，所以至少有两个棋子进入限位部分的方案数为，其余类推。根据容斥原理，n个棋子无一落入限位部分的方案数应为例 有甲乙丙丁四个人完成ABCD四项任务，但是甲不能从事任务B，乙不能从事任务BC，丙不能从事任务CD，丁不能从事任务D。若要求每人从事一项任务，有多少种不同的方案？解 每一种分配方案相当于ABCD的限位排列。限位部分的棋牌多项式为，即，所求的方案数。4.3 绝对错位排列定理2 对于，有绝对错位排列数为.证明

14、 设是集合的全部个排列中满足第j个位置上恰好是j的排列的特性，那么集合便是S的排列中所有满足性质的集合。所以有。由于中的每个排列均具有形式。其中是集合的一个排列。显然，这种排列有个。所以。又因为中的每个排列都具有形式。其中是集合的一个排列，显然，这种排列有个。因此，.对于的任意k组合，有.另外，由于存在集合的个k组合。应用容斥原理定理得证。例1 在一个聚会结束后，有10位先生要取回他们的帽子，有多少种方式使得这些人中没有人能够拿回他们来时所戴的帽子？解 用公式计算得.例2 数的全排列中，求偶数在原来位置上，其余都不在原来位置上的错排数目。解 由题意知，本题实际上是这5个数的错排问题。即所以 4

15、.4 相对的禁排列位置问题定理3 对于，证明 令为集合的全部个n排列的集合。为排列中出现模式的性质，。为满足性质的排列的集合，因此，。下面分析每个的数量。中的排列必定出现12这样的子串，即对进行全排列。所以对一般的每个有，将它们加起来得。对于中任意两个的交，比如是中的排列包含2种模式 共享同一个元素，如；没有共享的元素，如。情况下就如同排列中有子串，n个元素中有3个合并成1个，就是的全排列；情况下就如同排列中有子串就是的全排列；一般地，。更一般地，对于中的每个k组合有由于对每一个（有相邻的子串就一定少一个元素），存在集合的个k组合，应用容斥原理得到公式所以，定理得证。例 某班8个男生每天跑步，

16、他们排成一竖行，除了第一个领跑的男生外，每个男生前面都有另一个男生，为了不让他们总看见前面的同一个人，第二天要交换位置，使得前面的人与前一天的不同。他们有多少交换位置的方法？解 根据定理3得5 几何图形计数5.1 计数方法在几何学中，计数问题是比较有趣的，比如计算线段的条数，具备要求的三角形个数若干图分平面所得的区域数等等。此类的问题看似没有规律，但是通过分析，还是可以得到一些方法的。比如枚举法、加法原理和乘法原理法、递推法以及折线法。5.2 计数方法在几何图形中的应用5.2.1 枚举法例1 如下图所示，数一数图中有多少条不同的线段？解 对于两条线段，只要有一个端点不同，就是不同的线段，所以，

17、以左端点为标准，线段分5类计数。以A为左端点：AB,AC,AD,AE,AF共5条；以B为左端点：BC,BD,BE,BF共4条；以C为左端点：CD,CE,CF共3条；以D为左端点：DE,DF共2条；以E为左端点：EF只一条。所以不同的线段一共有5+4+3+2+1=15（条）如果一条线段上有个点（包括两个端点），那么这个点把这条线段一共分成的线段总数为例2 下图中有多少个三角形？解 枚举法 （三角形不重复计算）以为一边的三角形：共5个；以为一边的三角形：共4个；以为一边的三角形：共3个；以为一边的三角形：共2个；以为一边的三角形：只1个。所以，共有三角形个数：5+4+3+2+1=15（个）本三角形

18、图形中，不同三角形的个数就等于中不同线段的条数。一般情况下，当原三角形的一条边上有个点（包括两端点）时，它们与另一个顶点的连线所构成的三角形总数为5.2.2加法原理和乘法原理法例1 下图中一共有多少个长方形？所有这些长方形的面积和是多少?解 图中长边有5个分点（包括端点)，长边不同线段共有易得宽边不同线段也有10条。所以，共有长方形（个）长边10条线段长分别为：5,17,25,26,12,20,21,8,9,1；宽边10条线段长分别为：2,6,13,16,4,11,14,7,10,3.所以，所有长方形面积和为5.2.3 递推法例1 问8条直线最对能把平面分成多少部分？解 1条直线最多将平面分成

19、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个部分；

20、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 平面上两个格点与可用折线法相连的充要条件是且为偶数。证明 充分性 在折线的一节上，若左端点为，则右端点只能是或。所以如果有一条折线链

21、接与，则只能是加上若干个1或者-1的结果，且1与-1的总数为n。若设有k个1，n-k个-1，则，可以改写为或。由第一式及，即知；而由第二式，则知为偶数。必要性 因为是偶数，可令。因为，可知。则可在与如下连出折线：其中，第一段由斜率1的k节组成，第二段由斜率-1的节组成。定理2 设与为平面上可连折线的两点，则 到的折线条数等于，式中； 时，到的与x轴相交的折线条数等于，也等于到的折线条数，其中； 时，到的与仅在终点相交的折线条数，也等于到的与仅在始点相交的折线数，其中。证明 由定理1的证明易得，每条这样的折线是由k个1与n-k个-1的线形排列所决定的，所以折线共有条。 如图所示，实线所示为一条到

22、的与x轴相交的折线。设其与x轴的最左方交点为。将到的折线关于x轴的对称折线以虚线画出，这样就有了折线与折线的全部折线间的一一对应。进而，由即可得知折线条数。 如图所示，实线所示为一条到的与仅交于N点的折线。以中心P点为对称中心可得到虚线所示的一条折线，它与仅交于点M。这显然是一种一一对应。所以可以得知，定理所述两类折线条数相等。下面计算与仅交于M点的虚线折线条数。为此，将x轴平移到M点，所述折线既是新坐标系中与横轴仅交于M点一处（注意，此时点坐标已经变为及），即由到且与横轴不相交的。根据和的结论可知所求的折线条数为全部条数减去与横轴相交的条数。采用的记号，即是。例 有2n个人排队购入场券，每人

23、限购一张，票价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元的，则问题

24、的答案应当是格点到的不超越x轴的折线条数，如图所示。若将x轴向下平移一个单位，则它等价于到的不与x轴相交的折现条数按照定理2中的，它等于。然而持票人都是有区别的，对持1元币与持2元币的各n个人分别进行全排列，即知问题的最终答案为。结 论组合数学已经成为了现代数学学科中发展较快的一个分支，也是一个极为重要的分支。本文对路径问题，母函数与递推关系，容斥原理与排列问题以及几何图形计数问题进行了简单的阐述研究。不利用简单实际的例子来加深理解。这四种组合方法在解决数学问题是也比较实际。本文的重点是在这四种组合方法的应用上。本文在写作方法上采用的是逻辑顺序的观念。先对需要的组合方法进行简单的阐述，有了初步

25、的理解之后，再结合各种实际例子来理解组合方法在数学中的应用。我对相关资料进行了大量的收集，阅读了不少的文献，借鉴前人的成果，让理论与实际相结合。但是毕竟学习组合方法的时间还是很短，对一些重点，精华的部分还是把握不好，请各位老师批评指正。致 谢大学时间过得好快，转眼间就要离开这所学校了，大学四年，有许多的收获，也有些缺乏进取心的感慨。谈到感谢，首先要感谢河北科技大学，是科大给了我四年的学习机会，让我在这充满学习与浪漫色彩的校园学会了许多专业知识，学到了更多的为人处世的方式，使我在各个方面都有很大的进步。感谢未来的母校科大。大学四年，理学院老师让我领略到更多的数学风格，数学魅力，以及相关专业的老师

26、，是你们的教学使我学到了很多专业知识，为以后的人生道路指明了道路。谢谢各位老师。本论文是作者在吕仑老师悉心指导下完成的，在相处的几个月中，是吕仑老师让我了解到了组合数学的魅力所在，让我能够再次感受到数学的博大精深。是吕老师在忙碌的教学工作中抽出时间为我作指导，给我指出缺点，帮助我改正错误。吕老师有很深的数学造诣，他有着严谨的逻辑思维，深厚的数学功底。另外吕老师待人非常随和，和气。无论是学习专业知识还是做人方面，吕老师都是我学习的榜样。在此，感谢吕老师对我的学习上的批评与指导，感谢吕老师在做人方面对我的良好影响。祝愿吕老师工作顺利，在数学上有更多的成就。参考文献1 田秋成组合数学北京：电子工业出

27、版社，20062王元元，王庆瑞，黄纪麟组合数学理论与解题上海：上海科学技术文献出版社，19893 马光思组合数学西安：西安电子科技大学出版社，20024 卢开澄组合数学北京：清华大学出版社，19915 孙世新，张先迪. 组合原理及其应用.北京：国防工业出版社，20066 H.J.RyserCombinatorial MathematicsMathematical Association of America, Providence, 1963 7 吴正声，孙志人组合数学初步南京师范大学出版社, 20018 Richard A. BrualdiIntroductory Combinatorics America, 机械工业出版社，20059 屈婉玲组合数学北京大学出版社，198910 金成梁小学数学竞赛教程中国矿业大学出版社，199311 孙世新组合数学成都：电子科技大学出版社，200312 卢开澄，卢明华组合数学北京：清华大学出版社，2002忽略此处.