《网络路径问题、母函数与排列组合、容斥原理论》由会员分享，可在线阅读，更多相关《网络路径问题、母函数与排列组合、容斥原理论（23页珍藏版）》请在金锄头文库上搜索。
1、 本 科 毕 业 论 文 第 24 页 共 24 页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个男生每天跑步，他们排成一竖行，除了第一个领跑的男生外，每个男生前面都有另一个男生，为了不让他们总看见前面的同一个人，第二天要交换位置，使得前面的人与前一天的不同。他们有多少交换位置的方法？解 根据定理3得
