组合数学（combinatorial mathematics），又称为离散数学。狭义的组合数学主要研究满足一定条件的组态（也称组合模型）的存在、计数以及构造等方面问题。组合数学主要内容有组合计数、组合设计、组合矩阵、组合优化等。有时人们也把组合数学和图论加在一起看作离散数学。组合数学是计算机出现以后迅速发展起来的一门数学分支。计算机科学即算法的科学，而计算机所处理的对象是离散的数据，所以离散对象的处理就成了计算机科学的核心，而研究离散对象的科学恰恰就是组合数学。组合数学的发展改变了传统数学中分析和代数占统治地位的局面。

简介

国外状况

花絮(四色问题 中国邮差问题 任务分配问题（也称婚配问题） 河洛图 装箱问题 过河问题 是否存在稳定婚姻的问题 管理调度问题 库房和运输的管理问题 铺地砖问题 组合数学还可用于金融分析)

相关书籍《组合数学》(基本信息 内容简介 图书目录)

清华大学出版社图书(图书信息 图书简介 前言 目录)

简介

现代数学可以分为两大类：一类是研究连续对象的，如分析、方程等，另一类就是研究离散对象的组合数学。组合数学不仅在基础数学研究中具有极其重要的地位，在其它的学科中也有重要的应用，如计算机科学、编码和密码学、物理、化学、生物等学科中均有重要应用。微积分和近代数学的发展为近代的工业革命奠定了基础。而组合数学的发展则是奠定了本世纪的计算机革命的基础。计算机之所以可以被称为电脑，就是因为计算机被人编写了程序，而程序就是算法，在绝大多数情况下，计算机的算法是针对离散的对象，而不是在作数值计算。正是因为有了组合算法才使人感到，计算机好像是有思维的。

组合数学不仅在软件技术中有重要的应用价值，在企业管理，交通规划，战争指挥，金融分析等领域都有重要的应用。在美国有一家用组合数学命名的公司，他们用组合数学的方法来提高企业管理的效益，这家公司办得非常成功。此外，试验设计也是具有很大应用价值的学科，它的数学原理就是组合设计。用组合设计的方法解决工业界中的试验设计问题，在美国已有专门的公司开发这方面的软件。

国外状况

组合数学在国外早已成为十分重要的学科，甚至可以说是计算机科学的基础。一些大公司，如IBM，AT&T都有全世界最强的组合研究中心。Microsoft 的Bill Gates近来也在提倡和支持计算机科学的基础研究。例如，Bell实验室的有关线性规划算法的实现，以及有关计算机网络的算法，由于有明显的商业价值，显然是没有对外公开的。美国已经有一种趋势，就是与新的算法有关的软件是可以申请专利的。如果照这种趋势发展，世界各国对组合数学和计算机算法的投入和竞争必然日趋激烈。美国政府也成立了离散数学及理论计算机科学中心DIMACS（与Princeton大学，Rutgers大学，AT&T 联合创办的，设在Rutgers大学），该中心已是组合数学理论计算机科学的重要研究阵地。美国国家数学科学研究所（Mathematical Sciences Research Institute，由陈省身先生创立）在1997年选择了组合数学作为研究专题，组织了为期一年的研究活动。日本的NEC公司还在美国的设立了研究中心，理论计算机科学和组合数学已是他们重要的研究课题，该中心主任R. Tarjan即是组合数学的权威。美国重要的国家实际室（Los Alamos国家实验室，以造出第一颗原子弹著称于世），从曼哈顿计划以来一直重视应用数学的研究，包括组合数学的研究。不仅如此，该实验室最近还在积极充实组合数学方面的研究实力。美国另外一个重要的国家实验室Sandia国家实验室有一个专门研究组合数学和计算机科学的机构，主要从事组合编码理论和密码学的研究，在美国政府以及国际学术界都具有很高的地位。

由于生物学中的DNA的结构和生物现象与组合数学有密切的联系，各国对生物信息学的研究都很重视，这也是组合数学可以发挥作用的一个重要领域。由于DNA就是组合数学中的一个序列结构，美国科学院院士，近代组合数学的奠基人Rota教授预言，生物学中的组合问题将成为组合数学的一个前沿领域。

传统的计算机算法可以分为两大类，一类是组合算法，一类是数值算法（包括计算数学和与处理各种信息数据有关的信息学）。近年来计算机算法又多了一类：那就是符号计算算法。吴文俊院士开创的机器证明方法就属于符号计算，引起了国际上的高度评价，被称为吴方法。而国际上还有专门的符号计算杂志。符号算法和吴方法跟代数组合学也有十分密切的联系。组合数学，数值计算（包括计算数学，科学计算，非线性科学，和与处理各种信息数据有关的信息学）和统计学可能是应用最广的数学分支，而组合数学的价值甚至不亚于统计学和数值计算。由于数学机械化近年来的发展和在计算机科学中的重要性，把数学机械化，科学计算和组合数学组合起来，就可以说是中国信息产业的基础。组合数学家H. Wilf和D. Zeilberger1998因为在组合恒等式的机械化证明方面的成果，获得1998年美国数学会的Steele奖。

Thomson Science公司创刊的一份电子刊物《离散数学和理论计算机科学》即是一个很好的说明。它的内容涉及离散数学和计算机科学的众多方面。由于计算机软件的促进和需求，组合数学已成为一门既广博又深奥的学科，需要很深的数学基础，逐渐成为了数学的主流分支。

除上述以外，欧洲也在积极发展组合数学，英国、法国、德国、荷兰、丹麦、奥地利、瑞典、意大利、西班牙等国家都建立了各种形式的组合数学研究中心。近几年，南美国家也在积极推动组合数学的研究。澳大利亚，新西兰也组建了很强的组合数学研究机构。值得一提的是亚洲的发达国家也十分重视组合数学的研究。日本有组合数学研究中心，并且从美国引进人才，不仅支持日本国内的研究，还出资支持美国的有关课题的研究，这样使日本的组合数学这几年的发展极为迅速。台湾、香港两地也从美国引进人才，大力发展组合数学。新加坡，韩国，马来西亚也在积极推动组合数学的研究和人才培养。台湾的数学研究中心也正在考虑把组合数学作为重点方向来发展。

花絮

四色问题

如果你仔细留心一张世界地图，你会发现用一种颜色对一个国家着色，那么一共只需要四种颜色就能保证每两个相邻的国家的颜色不同。这样的着色效果能使每一个国家都能清楚地显示出来。但要证明这个结论确是一个著名的世界难题，1976年数学家通过计算机运算得到证明而成为四色定理，最近人们才发现了一个更简单的证明。

中国邮差问题

由中国组合数学家管梅谷教授提出。邮递员要穿过城市的每一条路至少一次，怎样行走走过的路程最短？这是一个NP完全问题。由中国组合数学家管梅谷教授提出，著名组合数学家，J. Edmonds和他的合作者给出了一个解答。

任务分配问题（也称婚配问题）

有一些员工要完成一些任务。各个员工完成不同任务所花费的时间都不同。每个员工只分配一项任务。每项任务只被分配给一个员工。怎样分配员工与任务以使所花费的时间最少？

河洛图

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

装箱问题

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

过河问题

在中小学的数学游戏中，有这样一个问题，一个船夫要把一只狼，一只羊和一棵白菜运过河。问题是当人不在场时，狼要吃羊，羊要吃白菜，而他的船每趟只能运其中的一个。他怎样才能把三者都运过河呢？这就是一个很典型、很简单的组合数学问题。

是否存在稳定婚姻的问题

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

管理调度问题

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

库房和运输的管理问题

怎样安排运输使得库房充分发挥作用，进一步来说，货物放在什么地方最便于存取（如存储时间短的应该放在容易存取的地方）。

铺地砖问题

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

组合数学还可用于金融分析

组合数学还可用于金融分析，投资方案的确定，怎样找出好的投资组合以降低投资风险。南开大学组合数学研究中心开发出了"金沙股市风险分析系统"现已投放市场，为短线投资者提供了有效的风险防范工具。

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

相关书籍《组合数学》

基本信息

书名：　组合数学 (原书第4版) (2-1)

出 版 社：　机械工业出版社

作者：　Richard A.Brualdi

适用学科：　电子信息

书号：　978-7-111-15360-3

出版时间：　2005-02-01

定价：　45.00元

内容简介

本书是系统阐述组合数学基础、理论、方法和实例的优秀教材，出版近30年来多次改版，被MIT、哥伦比亚大学、UIUC、威斯康星大学等众多国外高校采用，对国内外组合数学教学产生了较大影n向，也是相关学科的主要参考文献之一。 本书侧重于组合数学的概念和思想，包括鸽巢原理、计数技术、排列组合、Polya计数法、二项式系数、容斥原理、生成函数和递推关系以及组合结构(匹配、实验设计、图)等，深入浅出地表达了作者对该领域全面和深刻的理解，介绍了历史上源于数学游戏和娱乐的大量实例，其中对Polya计数、Burnside定理等的完美处理使得不熟悉群论的学生也能够读懂。除包含第3版中的内容外，本版又进行了更新，增加了莫比乌斯反演(作为容斥原理的推广)、格路径、Schroder数等内容。此外，各章均包含大量练习题，并在书末给出了参考答案与提示。

图书目录

出版者的话

专家指导委员会

译者序

前言

第1章 什么是组合数学

1．1 例：棋盘的完美覆盖

1．2 例：切割立方体

1．3 例：幻方

1．4 例：四色问题

1．5 例：36军官问题

1．6 例：最短路径问题

1．7 例：nim取子游戏

1．8 练习题

第2章 鸽巢原理

2．1 鸽巢原理：简单形式

2．2 鸽巢原理：加强形式

2．3 ramsey定理

2．4 练习题

第3章 排列与组合

3．1 四个基本的计数原理

.3．2 集合的排列

3．3 集合的组合

3．4 多重集的排列

3．5 多重集的组合

3．6 练习题

第4章 生成排列和组合

4．1 生成排列

4．2 排列中的逆序

4．3 生成组合

4．4 生成卜组合

4．5 偏序和等价关系

4．6 练习题

第5章 二项式系数

5．1 pascal公式

5．2 二项式定理

5．3 一些恒等式

5．4 二项式系数的单峰性

5．5 多项式定理

5．6 牛顿二项式定理

5．7 再论偏序集

5．8 练习题

第6章 容斥原理及应用

6．1 容斥原理

6．2 具有重复的组合

6．3 错位排列

6．4 带有禁止位置的排列

6．5 另外的禁排位置问题

6．6 莫比乌斯反演

6．7 练习题

第7章 递推关系和生成函数

7．1 一些数列

7．2 线性齐次递推关系

7．3 非齐次递推关系

7．4 生成函数

7．5 递归和生成函数

7．6 一个几何的例子

7．7 指数生成函数

7．8 练习题

第8章 特殊计数序列

8．1 catalan数

8．2 差分序列和stirling数

8．3 分拆数

8．4 一个几何问题

8．5 格路径和schroder数

8．6 练习题

第9章 二分图中的匹配

9．1 一般问题表述

9．2 匹配

9．3 互异代表系统

9．4 稳定婚姻

9．5 练习题

第10章 组合设计

10．1 模运算

10．2 区组设计

10．3 steiner三元系统

10．4 拉丁方

10．5 练习题

第11章 图论导引

11．1 基本性质

11．2 欧拉迹

11．3 hamilton路径和hamilton圈

11．4 二分多重图

11．5 树

11．6 shannon开关游戏

11．7 再论树

11．8 练习题

第12章 有向图及网络

12．1 有向图

12．2 网络

12．3 练习题

第13章 再论图

13．1 色数

13．2 平面和平面图

13．3 五色定理

13．4 独立数和团数

13．5 连通性

13．6 练习题

第14章 polya计数法

14．1 置换群与对称群

14．2 burnside定理

14．3 polya计数公式

14．4 练习题

练题的答案与提示

参考文献

索引

清华大学出版社图书

图书信息

书名：组合数学

ISBN：9787302261261

作者：周炜

定价：21元

出版日期：2011-9-1

出版社：清华大学出版社

图书简介

本书是作者多年教学和研究成果的结晶，系统地研究了组合计数、组合设计以及相关数学理论。全书分为10章： 集合与函数，排列组合与多项式定理，整除性理论，数论函数，不定方程，同余式，线性递归方程与母函数，鸽巢原理和Ramsey（拉姆齐）定理，Burnside（伯恩赛德）引理和Pólya（波利亚）定理，相异代表组和区组设计。

本书可以作为计算机科学与技术、数学、密码学和其他相关专业研究生和本科生的教材使用，也可作为广大师生和工程技术人员的自学用书或参考书。

前言

传说公元前23世纪大禹治水的时候，洛水中出现了一个神龟，龟背上有9组花点图案，排成了一个正方形。人们惊奇地发现，这9组花点图案正好代表了1~9这9个数字，纵、横各3行及两对角线上数字之和都为15。这便是现在人们熟悉的3×3幻方。幻方是组合数学中研究的有趣问题之一。1977年美国旅行者1号、2号宇宙飞船进入太空时就带上了幻方作为人类智慧的信号。

1666年，Leibniz（莱布尼茨）发表了一篇题为《论组合的艺术》的数理逻辑论文。这篇闪耀着创新智慧和数学天才的论文是他的第一篇数学论文，其主要思想是将理论的真理性论证归结为一种数学计算的结果。在论文中，Leibniz曾预言组合数学将会渗透到许多学科并得到很大发展。如今，计算机科学、计算数学、统计学、运筹学等学科尤其是计算机网络的迅速发展从根本上改变着人们的生活方式、生产方式和科学研究方法，同时也使组合数学的思想、方法和理论像Leibniz所预言的那样渗透到了人们的日常生活、社会经济、交通运输、金融分析、行政管理、信息对抗、军事指挥、科学研究和技术开发的各个角落。组合数学成为近若干年来最活跃的数学分支之一，也成为计算机科学不可分割的重要组成部分。随着各个行业的技术进步，组合数学方法推动着计算机科学日新月异地向前发展，也成为培养学生智慧和解决实际问题能力的有力工具。

我国最早的组合数学理论可追溯到宋代的“贾宪三角形”。贾宪三角形后来被杨辉引用，所以现在人们普遍称其为“杨辉三角形”。在西方，直到1654年才由Pascal(帕斯卡)提出了我们所说的杨辉三角形，比我国晚了400多年。

1962年我国数学家管梅谷教授提出了著名的“中国邮递员问题”。1976年6月，美国数学家Appel(阿佩尔)与Haken(哈肯)用了1200小时在3台不同的电子计算机上证明了四色定理。这些都是现代组合数学历史上的大事。我国数学家吴文俊教授从1976年开始研究几何定理的机器证明，并开创了吴方法。周咸青教授发展了吴方法，编制出计算机软件，证明了500多条几何定理，并在美国出版了几何定理机器证明方面的专著。

组合数学是计算机软件业的基础。广义的组合数学就是人们常说的离散数学。狭义的组合数学又叫组合学、组合论、组合分析。组合数学研究的对象是按照一定的规则来安排一些离散事物的有关数学问题。这些数学问题包括存在性问题、计数问题、枚举问题(构造问题)和优化问题。换句话说，对离散对象的满足一定条件的安排方案是否存在？如果存在，这样的方案有多少？怎样构造出所需要的安排方案？怎样从所有的安排方案中找出最优方案？

本书主要研究存在性问题、计数问题、枚举问题和与之有互相支撑作用的数论和集合论知识。目前各种教科书所介绍的组合优化问题主要是线性规划、动态规划、网络流和图论问题，这些问题同时也是运筹学研究的主要问题，因此本书没有写入组合优化这部分内容。考虑到计算机专业的研究生和本科生可能涉足信息安全领域的研究、开发和教学工作，本书写入了与信息安全有关且与组合数学互相有一定支撑作用的数论和集合论知识。

本书内容具体安排分为10章： 集合与函数，排列组合与多项式定理，整除性理论，数论函数，不定方程，同余式，线性递归方程与母函数，鸽巢原理和Ramsey(拉姆齐)定理，Burnside(伯恩赛德)引理和Pólya(波利亚)定理，相异代表组和区组设计。每章又分为若干节和小节。这些章节，有些内容比较浅显，便于掌握； 有些内容理论性较强(比如Pólya基本定理的证明)，工科学生阅读起来有一定的困难，可以暂时绕过。每章后面配有一定数量难度不一的习题，可供选做。

本书内容根据作者多年的教学经验和研究成果整理而成，对理论知识的表述和处理均以集合与函数为基础，与现有的组合数学著作和教科书有很大的不同。比如对置换的循环分解理论的处理、对排列组合问题的处理、对线性递归方程的处理、对鸽巢原理和Ramsey定理的处理、对无向完全图着色问题的处理、对Burnside引理和Pólya定理的处理、对群和有限域的处理、对正交Latin(拉丁)方和Hadamard(阿达马)矩阵的处理等。这些不同之处请读者自己细心体会。

本书可以作为计算机科学与技术、数学、密码学及相关专业研究生和本科生的教材，也可作为其他各专业、不同层次师生和工程技术人员的自学用书或参考书，标*号的内容供选学。若作为教材，学时安排建议为： 研究生40~50学时，本科生50~60学时。

本书大部分内容已在空军工程大学导弹学院计算机科学与技术专业研究生中讲授多年。但由于作者水平有限，书中一定还有未发现的错误、缺点和纰漏，恳请广大读者批评指正，作者不胜感激！

作者2010年10月

目录

第1章集合与函数

1.1集合论基础

1.1.1集合的基本概念

1.1.2集合的代数运算及性质

1.1.3集合的运算性质

1.2函数、置换的循环分解

1.2.1函数的基本概念和一般性质

1.2.2置换的循环分解

1.3集合的基数、对合映射不动点定理

1.4集合上的二元关系

1.4.1二元关系的基本概念

1.4.2几种特殊的简单二元关系

1.4.3等价关系、商集

1.5容斥原理及应用

1.5.1容斥原理

1.5.2错位排列问题

1.5.3容斥原理应用举例

1.6Abel恒等式

1.7习题

第2章排列组合与多项式定理

2.1排列组合及其性质

2.1.1无重复排列和无限可重复排列

2.1.2无重复组合及其性质、多项式反演定理

2.1.3无重复有序分组、无重复无序分组

2.1.4无限可重复分组、无限可重复组合、多项式定理

2.1.5有限可重复组合与有限可重复排列

2.2排列组合应用举例

2.3Stirling公式

2.3.1Wallis公式

2.3.2Stirling公式

2.4习题

第3章整除性理论

3.1整数的整除性

3.2最大公约数和最小公倍数

3.3连分数

3.3.1实数的连分数表示

3.3.2实数的近似分数

3.3.3近似分数的既约性

*3.3.4近似分数的误差估计

3.3.5整数线性组合ax-by=1的生成

3.4素数、二平方定理、算术基本定理

3.5习题

第4章数论函数

4.1[x]与{x}

4.2积性函数

4.3因子数τ(n)与因子和S(n)

4.4Euler函数?(n)

4.5M?bius函数和M?bius反演定理

4.5.1M?bius函数及其性质

4.5.2M?bius反演定理

4.5.3圆排列问题

4.6习题

第5章不定方程

5.1二元一次不定方程

5.2三元一次不定方程

5.3勾股数定理

5.4习题

第6章同余式

6.1同余式的定义与性质

6.2完全剩余系和缩剩余系

6.3一元一次同余方程

6.4一元一次同余方程和方程组、中国剩余定理

*6.5一元多项式同余方程

6.6习题

第7章线性递归方程与母函数

7.1递归方程

7.1.1线性递归方程解的结构、降阶定理

7.1.2常系数齐次线性递归方程的通解

7.1.3常系数非齐次线性递归方程的求解

7.1.4线性递归方程求解举例

7.2Fibonacci数列

7.2.1Fibonacci问题的求解

7.2.2Fibonacci数列的性质

7.2.3Fibonacci数列在优选法中的应用

7.3母函数及其性质

7.3.1母函数的定义

7.3.2母函数的一般性质

7.4错位排列和禁位排列

7.4.1错位排列问题

*7.4.2棋盘多项式与禁位排列

*7.5正整数分拆和Ferrers图

7.5.1正整数分拆

7.5.2Ferrers图

7.6Stirling数

7.6.1第一类Stirling数

7.6.2第二类Stirling数

7.6.3Stirling反演定理

7.7Catalan数

7.8Bernoulli数

7.9习题

第8章鸽巢原理和Ramsey定理

8.1鸽巢原理

*8.2无向完全图的着色问题

8.3Ramsey定理

*8.4Ramsey数的性质

8.5习题

第9章Burnside引理和Pólya定理

9.1群的基本知识

9.1.1半群、亚群、元素的阶

9.1.2群、陪集、Lagrange定理

9.2Burnside引理和Pólya定理

9.2.1Burnside引理

9.2.2简化的Pólya定理

*9.2.3Pólya基本定理

9.3习题

第10章相异代表组和区组设计

10.1相异代表组

10.2公共代表组

10.3完全区组设计与拉丁方

10.4有限域基础

10.5正交拉丁方

*10.6均衡不完全区组设计(BIBD)

10.6.1BIBD的概念

10.6.2三连组系

10.6.3对称BIBD

10.6.4由对称BIBD构造其他BIBD

10.7Hadamard矩阵

10.8习题

参考文献