组合数学论文

生活中的组合数学

摘 要:组合数学在基础理论方面和生活应用方面都发挥着越来越重要的作用, 组合数学不仅在基础数学研究中具有极其重要的地位，在其他的学科中也有重要的应用，如在计算机科学、编码和密码学、物理、化学、生物等学科中均有重要应用。如果说微积分和近代数学的发展为近代的工业革命奠定了基础，那么组合数学的发展则是奠定了21世纪计算机革命的基础。因此随着计算机科学和其它许多新兴应用学科的发展, 组合数学在基础理论方面和生活应用方面都发挥着越来越重要的作用, 进而需要我们对其进行更加深层次的研究.

关键词:组合数学; 鸽巢原理; 数学游戏

引言

随着计算机的普及推广, 组合数学这门古老的学科焕发出蓬勃的生机. 组合数学是一门研究内容丰富、应用广泛的学科, 同时它也是一门讲究方法, 讲究技巧的学科. 组合数学的魅力在于找到巧妙的解法来完善的解决一个组合数学问题, 计算机强大的计算能力为寻求组合数学问题的巧妙解法提供了无限的可能, 同时组合数学也反过来有效地推动了计算机科学的发展.

组合数学在国外已有较快发展, 在很多大学已设立组合数学与优化理论专业来培养专门人才. 我国对组合数学的研究具有一定的基础, 特别是图论研究和区组设计等方面已取得一定的成果.

组合数学的发展显然已经改变了传统数学中分析和代数占统治地位的局面, 奠定了本世纪的计算机革命的基础. 因此需要对其进行更加深入的理论探讨和实践. 本文正是基于这种思想, 希望借以简单的阐述引起人们对组合数学的更深层次的理解, 并能够将其灵活应用于生活中.

所以我想通过一些实例和数学史上的一些故事和难题, 介绍了组合数学是如何在生活中应用的. 在研究了一些典型的例子和趣味性的故事的基础上, 系统的查阅了相关文献，并结合生活中涉及组合数学的相关知识进行阐述, 具体说明了组合数学的基本方法及其在生活中的应用. 这样就使得晦涩的组合数学显得更加形象, 也使抽象的理论概念变得浅显具体, 更易被初学者理解和接受, 以至于可以激发人们在生活中应用组合数学的意识.

1. 组合数学的基本内容

1.1概念

伴随着计算机科学的高速发展, 近年来, 组合数学已渐渐成为一门新兴起来的边缘性、综合性学科. 关于组合数学到底是什么, 数学界有许多种的看法.Richard

A.Brualdi 在其所著的《Introductory Combinatorics》一书中提到组合数学研究的是事物按照一定的规则安排, 其中包括:对已知安排问题的研究，计数性问题, 存在性问题. 在《Basic Techniques of Combinatorial Theory》中有如此描述: 组合数学即为对已给定描述事物的研究有多少种或者是对某事物发生的途径有多少种. 综上所述, 组合数学主要研究的就是事物安排中所涉及的有关数学问题[1].

组合数学是研究任意一组离散性事物按照一定规则安排或配置的数学. 特别是当指定的规则较简单时, 计算一切可能的安排或配置的方法数, 就成为它研究的主要问题. 现代组合数学有两个主要特点:其一, 它大量应用了抽象代数学工具和矩阵工具促使问题的提法和处理方法表现出极大的普遍性; 其二, 为了适应计算机科学的发展, 它很注重对方法的能行性和程序化问题进行研究. 这样, 它又派生出算法组合学和组合算法等新的亚分支学科.

1.2主要内容

组合数学最早是同数论和概率论交叉在一起的. 本世纪五十年代以来, 特别是由于计算机科学的巨大发展, 促使组合数学成为一支富有生命力的新兴数学分支.

与传统的数学课程相比, 组合数学研究的主要是一些离散事物之间所存在的某些数学关系, 包括计数性问题、存在性问题、最优化问题以及构造性问题等, 其内容主要是枚举和计数. 组合学中研究最多的主要是计数问题, 该问题通常出现在所有的数学分支之中. 计算机科学通常需要研究有关算法的内容, 就必须估计出算法所需的存储单元和运算量, 即分析算法的空间复杂性和时间复杂性[2].

综上, 组合数学主要研究:排列组合、递推关系和生成函数、鸽巢原理和容斥原理、贝恩赛特引理与波利亚定理以及区组设计与编码等等.

2. 组合数学的基本解题方法

组合数学是离散数学的一个分支, 其内容零散, 思想方法繁多, 对于长期接受

连续性数学学习的我们来说, 通常感到很难抓住其要领, 无从下手, 尤其是对新颖繁多的各种组合方法感到有些茫然. 组合数学的方法很多, 如加乘法则, 抽屉法则, 母函数法, 逐步淘汰法等等, 了解这些方法有助于培养我们学生的组合思维。

3. 组合数学在生活中的应用举例

组合数学是十分贴近于人们的生活的，因此组合问题在生活中非常常见。 例如，求n 个球队参加比赛，每队只和其他队比赛一次的总比赛场数。例如，在纸上画一个网络，用铅笔沿着网络的线路揍，在笔不离开纸面而且不重复线路的条件下，一笔画出网络图。又例如这样一个简单的组合数学问题：一个船夫要把一只狼，一只羊和一棵白菜运过河。而当人不在场时，狼要吃羊，羊要吃白菜，而他的船每趟只能运其中的一个，问人怎样才能把三者都运过河。下面介绍几种组合数学中的著名问题。

1. 地图着色为题：对世界地图着色，每一个国家使用一种颜色。如果要求相邻国家的颜色相异，是否总共只需四种颜色？四色定理是一个著名的数学定理。它指出，如果将平面分成一些邻接的区域，那么可以用不多于四种颜色来给这些区域染色，使得每两个邻接区域染的颜色都不一样。另一个通俗的说法是：每个（无飞地的）地图都可以用不多于四种颜色来染色，而且没有两个邻接的区域颜色相同。被称为邻接的两个区域是指它们有一段公共的边界，而不仅仅是一个公共的交点。例如右图左下角的四色圆盘中，红色部分和绿色部分是邻接的区域，而黄色部分和红色部分则不是临界区域。

尽管四色定理最初提出是和地图染色工作有关，但四色定理本身对地图着色工作并没有特别的意义。据凯尼斯·梅在一篇文章中所言：“（实际中）用四种颜色着色的地图是不多见的，而且这些地图往往最少只需要三种颜色来染色。制图学和地图制图史相关的书籍也没有四色定理的记载。”

一些简单的地图只需要三种颜色就够了，但有时候第四种颜色也是必须的。比如说当一个区域被三个区域包围，而这三个区域又两两相邻时，就得用四种颜色才行了。“是否只用四种颜色就能为所有地图染色”的问题最早是由一位英国制图员在1852年提出的，被称为“四色问题”。人们发现，要证明宽松一点的“五定理”（即“只用五种颜色就能为所有地图染色”）很容易，但四色问题却出人意料地异常困难。曾经有许多人发表了四色问题的证明或反例，但都被证实是错误的。

1977年，数学家凯尼斯·阿佩尔（英语：Kenneth Appl ）和沃夫冈·哈肯（英语：Wolfgang Haken）借助电子计算机首次得到了一个完全的证明，四色问题也终于成为了四色定理。这是首个主要由计算机证明的定理。这个证明一开始并不为许多数学家接受，因为不少人认为这个证明无法用人手直接验证。尽管随着计算机的普及，数学界对计算机辅助证明更能接受，但仍有数学家对四色定理的证明存疑。

船夫过河问题：船夫要把一匹狼、一只羊和一棵白菜运过河。只要船夫不在场，羊就会吃白菜、狼就会吃羊。船夫的船每次只能运送一种东西。怎样把所有东西都运过河？这是线性规划的问题。

中国邮差问题：由中国组合数学家管梅谷教授提出。邮递员要穿过城市的每一条路至少一次，怎样行走走过的路程最短？这不是一个NP 完全问题，存在多项式复杂度算法：先求出度为奇数的点，用匹配算法算出这些点间的连接方式，然后再用欧拉路径算法求解。

河洛图：我国古代的河洛图上记载了三阶幻方，即把从一到九这九个数按三行三列的队行排列，使得每行，每列，以及两条对角线上的三个数之和都是一十五。组合数学中有许多象幻方这样精巧的结构。1977年美国旅行者1号、2号宇宙飞船就带上了幻方以作为人类智慧的信号。

装箱问题：当你装一个箱子时，你会发现要使箱子尽可能装满不是一件很容易的事，你往往需要做些调整。从理论上讲，装箱问题是一个很难的组合数学问题，即使用计算机也是不容易解决的。

是否存在稳定婚姻的问题：假如能找到两对夫妇（如张（男）--李（女）和赵（男）--王（女）），如果张（男）更喜欢王（女），而王（女）也更喜欢张（男），那么这样就可能有潜在的不稳定性。组合数学的方法可以找到一种婚姻的安排方法，使得没有上述的不稳定情况出现（当然这只是理论上的结论）。这种组合数学的方法却有 一个实际的用途：美国的医院在确定录取住院医生时，他们将考虑申请者的志愿的先后次序，同时也给申请排序。按这样的 次序考虑出的总的方案将没有医院和申请者两者同时后悔的情况。 实际上，高考学生的最后录取方案也可以用这种方法。

管理调度问题：我们还会遇到更复杂的调度和安排问题。例如，在生产原子弹的曼哈顿计划中，涉及到很多工序，许多人员的安排，很多元件的生产，怎样安排各种人员的工作，以及各种工序间的衔接，从而使整个工期的时间尽可能短？这些都是组合数学典型例子。又比如，假日饭店的管理中，也严格规定了有关的工序，如清洁工的第一步是换什么，清洗什么，第二步又做什么，总之，他进出房间的次数应该最少。既然，这样一个简单的工作都需要讲究工序，那么一个复杂的工程就更不用说了。

铺地砖问题：我们知道，用形状相同的方型砖块可以把一个地面铺满（不考虑边缘的情况），但是如果用不同形状，而又非方型的砖块来铺一个地面，能否铺满呢？这不仅是一个与实际相关的问题，也涉及到很深的组合数学问题。

组合数学还可用于金融分析：组合数学还可用于金融分析，投资方案的确定，怎样找出好的投资组合以降低投资风险。南开大学组合数学研究中心开发出了"

金沙股市风险分析系统" 现已投放市场，为短线投资者提供了有效的风险防范工具。

总之，组合数学无处不在，它的主要应用就是在各种复杂关系中找出最优的方案。所以组合数学完全可以看成是一门量化的关系学，一门量化了的运筹学，一门量化了的管理学。

3.1 乘法原则与加法原则的应用举例

下面看看组合数学在生活中的实际应用. （以下假设A 和B 是两类互不关联、互不相同的事件. ）组合数学问题在生活中非常常见。 例如，求n 个球队参加比赛，每队只和其他队比赛一次的总比赛场数。例如，在纸上画一个网络，用铅笔沿着网络的线路揍，在笔不离开纸面而且不重复线路的条件下，一笔画出网络图。又例如这样一个简单的组合数学问题：一个船夫要把一只狼，一只羊和一棵白菜运过河。而当人不在场时，狼要吃羊，羊要吃白菜，而他的船每趟只能运其中的一个，问人怎样才能把三者都运过河。

加法原则可定义为:设事件A 有m 种选择方式, 事件B 有n 种选择方式, 则选A 或B 共有m +n 种方式.

例如, 大于1小于9的的奇数有3个, 分别为3,5,7,9; 大于1小于9的偶数有4个, 分别为2,4,6,8. 则大于1小于9的整数有7个, 即2,3,4,5,6,7,8. 这里事件A 为大于1小于9的奇数, 事件B 为大于1小于9的偶数. 而大于1小于9的整数即是属于A 或者属于B .

乘法原则可以定义为:设事件A 有m 种选取方式, 事件B 有n 种选取方式, 那么选取A 以后再选取B 共有m ⋅n 种方式.

例如, 从3个黑人、5个白人、9个黄种人中各选出1位的方式有3⨯5⨯9=135种方式. 而从中共选出一人的方式有3+5+9=17种方式.

下面再用一个实例看看这两个法则是如何应用的.

例5 某旅行社开辟了从北京去长白山和天山2条旅游线路, 称为北线；从北京去西湖、黄山、峨眉山3条旅游线路, 称为南线. 问该社共有多少条不同的线路？如某人选定了从北京去四川, 先要在西安中转, 北京到西安有3种航班可选, 西安到四川又有2种航班可选, 问共有多少种不同的航班配置方式？

分析 由所学的概率知识可知, 互不相容事件A 1、A 2, 则其和的概率等于各自

概率之和, 即P (A 1+A 2) =P (A 1)+P (A 2); 同理, 二个独立事件同时发生的概率

P (A 1⋅A 2)=P (A 1)⋅P (A 2).

解 由加法原理可知, 该社共有的线路条数P 1=2+3=5条.

由乘法原理可知, 共有的航班配置方式P 2=3⨯2=6种.

3.2 Ramsey定理的应用举例

首先是抽屉原理, 大家也许早就听说过这样的智力问题“:从10双鞋子中随便拿几只能保证有一双相配的鞋? ”答案显然是至少3只. 大家不难根据同样的原理编造出许多新问题. 这个原理本身可以很形象的表述为:“把多于n 个东西任意放进n 个抽屉, 那么一定有一个抽屉放进了不止一个东西”.

因为19世纪德国数学家狄利克雷曾用这个原理证明过数学命题, 所以把它叫做狄氏抽屉原理, 或简称抽屉原理. 它虽然简单, 但利用它可以证明不少并不简单的结论.

其次是鸽巢原理. 鸽巢原理是组合数学中最简单最基本的原理, 和抽屉原理其实是异曲同工. 鸽巢原理可简单的描述为:“若有n 个鸽巢, 而鸽子多余n 只, 若每只鸽子必须进巢, 则至少有一个鸽巢内的鸽子多于一只. ”

下面简要举一个用鸽巢原理解决实际问题的例子.

例6 一间屋内有10个人, 他们当中没有人超过60岁（年龄只以整数给出）但又至少不低于1岁. 试证明:总能找出两组人（两组不含相同的人）, 各组的年龄和是相同的.

解 设Y ={y 1, y 2, ⋅⋅⋅, y 10}为屋内10个人的年龄构成的集合, 集合Y 的所有k 个

121010k +C 10+⋅⋅⋅+C 10=2-1种, 不同元素之和共有C 10, 则所有可能的不同元素之和有C 10

记这些和为S ={s 1, s 2, ⋅⋅⋅, s 1023}, 由题设条件可知:

1≤s i ≤60, i =1, 2, ⋅⋅⋅, 1023.

因此, 由鸽巢原理原理可知S 中至少有两个元素是相同的, 设为s i =s j . 如果年龄和

s i 和s j 的人中有相同的人, 则把这些相同的人去掉, 即为要找的两组年龄和相同的

人.

最后就是集会问题. 这也是一个广为流传的趣味数学问题:“证明在至少有6个人参加的集会上, 与会者中或者有3个人以前互相认识, 或者有3个人以前彼此都不认识. ”因为6人集会中成员间的情况共有215=32728种. 下面就针对这个问题给予简单证明.

例7[7] 试证明6个人中一定有3个人相互认识或相互不认识.

证明 先考虑6个人中的任意一个人, 不妨把这个人称作p. 则其他的5个人可以分为下面的两个集合F 和S. 其中F 表示与p 相识的人的集合,S 表示与p 不相识的人的集合.

由鸽巢原理知, 这两个集合中至少有一个集合包含有3个人. 若F 包含有3个人, 则这3个人或者彼此不相识, 或者有两个人彼此相识. 如果F 中有3个人彼此不相识, 则结论成立. 如果F 中有2人相识, 则由于这两个人都与p 相识, 因此有3人彼此相识, 故定理结论成立.

类似的, 如果S 包含3个人, 则这3个人或者彼此相识, 或者有两个人彼此不相识. 如果这3个人彼此相识, 则结论成立. 如果有两个人彼此不相识, 则由于这两个人都与p 也不相识, 因此有3个人彼此不相识, 故定理结论成立.

3.3 线性规划法的应用实例

线性规划是最简单, 应用最广泛的一种数学规划方法, 也是使用最早的一种 优化方法. 在组合数学中, 线性规划问题可以归结为一类条件极值问题.

例8 某电视机厂有100台彩电的订单要在三周内交货, 在第一, 第一和第三周生产x 台彩电的费用分别是120x , 1. 2x 2, 1. 5x 2. 求每周生产彩电的数目的最优策略.

解 假设x i (i =1, 2, 3)表示在第i 周生产的彩电数, f i (x i )表示第i 周生产x i 台彩

电的费用, 则此问题的数学模型为

min y =f 1(x 1)+f 2(x 2)+f 3(x 3)=120x 1+1. 2x 22+1. 5x 32,

s.t. x 1+x 2+x 3=100,

x i ≥0, i =1, 2, 3.

假设F k (x )表示在前k 周生产x 台彩电所得到的最小费用, 则由最优原理可得

出如下的递归方程

F 1(x )=f 1(x ),

F k (x )=min 0≤x k ≤x {f k (x k )+F k -1(x -x k )}, k

0≤x ≤100. =2, 3,

原问题的解就是F . （100）3

由上式可知

F 1(x )=f 1(x )=120x ,

F 2(x )=min 0≤x 2≤x {f 2(x 2)+F 1(x -x 2)},

{f 3(x 3)+F (x -x 3)}. F 3(x )=min 0≤x 3≤x

解上面的递归方程, 可得当x 1=10, x 2=50, x 3=40时有最小值

F 3(100)=6600.

即第一周生产10台彩电, 第二周生产50台彩电, 第三周生产40台彩电, 可获得最小费用6600.

3.4 游戏中的组合数学

3.4.1哥尼斯堡七桥问题

18世纪初在东普鲁土有这样一个问题:某条河上有两个岛屿, 城市中的四部分可以由七个桥来连接起来．那么可否经过每个桥并且每个桥只能走一次？（如图1上图所示）．

图1

在18世纪中期, 欧拉成功论证了该问题, 也即是合适的方案并没有, 不可能每座桥走过且仅走过一次．欧拉把该实际问题形象地简化成同一平面上线与点的组合问题, 将每一座桥看成一条线, 每座桥所连接的地方看作点. 因此, 从某一点出发再回

到这一点的问题, 可转化成一个一笔画的问题[8].

欧拉采用概念映像法来解决该类问题, 亦即抽象分析法. 将七桥问题中的桥与陆地之间的关系结构用S 表示, 用x 表示一次可否同时走过此七座桥的问题. 欧拉使用了一种方法, 即用概念映像ϕ将桥视为几何线, 将连接的地点视为几何点, 则在ϕ映像下可得到(S;x ) →(S n ; x n ). 如此,S n 则可表示如图1下图的点线图. 之前的问题x 便对应变成能否一笔画出如图1下图所示的平面图问题x n . 也即x n 就是关于上述点线图的一笔画问题. 欧拉的这种方法就是组合数学中后来的关系映像反演方法的最早体现．

3.4.2“三同六变”的问题

中国的王文紊在其所著的《算学宝鉴》一书中详细记载了一个名为“三同六变”的题目:

“假令二十四老人, 长者寿高一百, 次者递减一岁, 止于七十七．共积总寿二千一百二十有四．卜(疑为‘赴’) 会三社, 八老相会, 七百八岁, 盖因人情逸顺, 散而复会, 共换六次, 其积(即和) 仍均七百有八, 屯(疑为‘求’) 见连用之道．”[8]

它的意思也即是说:有24位老人, 每8人一起, 分三处赴会, 每处年龄之和均为708岁, 并且年龄从100岁到77岁, 依次递减1岁．那么如何分配, 分配方法有多少种?

在该书当中共列出了6种解答, 并且作了注释, “其变尤多, 不及备述”．

对这个问题加以推广, 便可得到一类 “n 同k 聚”的问题:在自然数集合N 内, 任意选取nk (k =2,3,4, „) 个连续自然数作为集合M, 将M 任意划分为n 个互不相交子集M 1, M 2, M 3, , M n , 而每个子集均有k 个元素, 并且各个子集元素之和相等, 求

M 1, M 2, M 3, , M n ．这个问题为中国传统数学中的浑圆图给出了另一解释.

结束语

这篇论文只是介绍了组合数学在生活中的应用的一小部分, 希望借此论文可以激起我们对组合数学的关注, 学会在生活中运用组合数学来解决具体的问题. 组合数学这个富有生命力的数学分支, 涉及生活中的各个领域, 作为计算机专业的学生，我们必须把组合数学的学习放在一个重要的位置上来，掌握基本的组合数学原理，培养专业的数学思维，这样才能在以后的工作学习中掌握主动和先机。才能在将来为中国的计算机软件事业做出自己的贡献。

参考资料

百度知道：http://zhidao.baidu.com

百度百科：http://baike.baidu.com/view/44868.htm

http://zhidao.baidu.com/question/33561976.html

百度文库；http://wenku.baidu.com/view/b7d3f019f18583d0496459e9.html http://wenku.baidu.com/view/41879a15cc7931b764ce1507.html http://wenku.baidu.com/view/d0bc7b1dc281e53a5802ffeb.html http://wenku.baidu.com/view/a42acc270722192e4536f63b.html http://wenku.baidu.com/view/9bacf1f9f705cc1755270986.html http://wenku.baidu.com/view/33e0ad[1**********]11c9213.html

维基百科：http://zh.wikipedia.org/wiki/%E7%BB%84%E5%90%88%E6%95%B0%E5%AD%A6