组合数学Combinatorics马昱春 MA Yuchun myc@1组合数学Combinatorics组合数学:有人认为广义的组合数学就是离散数学，也有人认 为离散数学是狭义的组合数学和图论、代数结构、数理逻辑 等的总称。

但这只是不同学者在叫法上的区别。

总之，组合 数学是一门研究离散对象的科学。

/zh-cn/%E7%BB%84%E5%90%88%E6%95%B0%E5%AD%A6Combinatorics: Combinatorics is a branch of pure mathematics concerning the study of discrete (and usually finite) objects. It is related to many other areas of mathematics, such as algebra, probability theory, ergodic theory and geometry, as well as to applied subjects in computer science and statistical physics./wiki/Combinatorics 2组合数学与离散数学• 狭义的组合数学主要研究满足一定条件的组态（ 也称组合模型）的存在、计数以及构造等方面的 问题。

– 组合数学的主要内容有组合计数、组合设计、组合矩 阵、组合优化等。

• 离散数学(Discrete mathematics)是数学的几个分 支的总称，以研究离散量的结构和相互间的关系 为主要目标，其研究对象一般地是有限个或可数 无穷个元素；因此它充分描述了计算机科学离散 性的特点。

– 离散数学通常研究的领域包括：数理逻辑、集合论、 关系论、函数论、组合学、代数系统与图论。

。

3离散数学(目录)• • • • • • • • • • • • 离散数学（第四版） 作者： 耿素云，屈婉玲，张立昂 编著 第1章 命题逻辑 第2章 一阶逻辑 第1章 第3章 集合的基本概念和运算 第2章 第4章 二元关系和函数 第5章 代数系统的一般性质 第3章 第6章 几个典型的代数系统 第4章 第7章 图的基本概念 第5章 第8章 一些特殊的图 第6章 第9章 树 第7章 第10章 组合分析初步– – – – 10.1 10.2 10.3 10.4 加法法则和乘法法则 基本排列组合的计数方法 递推方程的求解与应用 题例分析排列与组合 递推关系与母函数 容斥原理与鸽巢原理 Burnside引理与Polya定理 区组设计 线性规划 编码简介 第8章 组合算法简介•第11章形式语言和自动机初步4前言• 组合数学研究的是事物按照某种规则的安排，主 要有：存在性问题、计数性问题和对已知安排的 研究 —— Richard A. BrualDi 所著 《Introductory Combinatorics》 • 组合数学就是对给定描述的事物有多少种或者某 种事物发生的途径有多少种的研究 ——Daniel I. A. Cohen 所著《Basic Techniques of Combinatorial Theory》 • 研究离散结构的存在、计数、分析和优化等问题 的一门学科 ——高洁 《浅谈组合数学的应用与 教学》5组合数学的历史组合数学是一个古老而又年轻的数学分支。

据传说，大禹在4000多年前(2200B.C.) 就观察到神龟背上的幻方…... A magic square: a square array of numbers in which the sum of all rows, all columns and both diagonals is the same.6组合数学的历史• 传说在公元前23世纪大禹 治水的时候，在黄河支流 洛水中，浮现出一个 大乌 龟，甲上背有9种花点的 图案，人们将图案中的花 点数了一下，竞惊奇地发 现9种花点数正巧是1—9 这9个数，各数位置的排 列也相当奇妙，横的3 行、纵的3列以及两对角 线上各自的数字之和都为 15。

大禹(2205BC -2105BC)4 3 89 5 12 7 67幻方问题• 组合数学中有许多象幻方这样精巧的结 构。

• 1977年美国旅行者1号、2号宇宙飞船 就带上了幻方以作为人类智慧的信号。

2200BC4 3 89 5 12 7 61 12 8 1315世纪 15 14 6 10 3 7 114 9 5４阶幻方神农幻方2 168阿基米德手稿• 用希腊文写在羊皮纸上的阿基米德手 稿副本，距今975年, 2003科学家借 助现代科技手段初步破译了古希腊数 学家阿基米德的这篇论文, 结论是这 篇论文解决的是组合数学问题。

• 在论文中阿基米德是在计算把14条 不规则的纸带拼成正方形一共能有多 少种不同的拼法。

这在现在被称为 tiling问题。

• 当今数学家借助计算机得出的答案是 17152种拼法，这在当时是相当困难 的。

9贾宪三角• 中国最早的组合数学 理论可追溯到宋朝时 期的”贾宪三角”, 后来 被杨辉引用, 所以普遍 称之为”杨辉三角”, 这 在西方是1654年由帕 斯卡提出，但比中国 晚了400多年。

10组合数学的历史1666年莱布尼兹所著《组合学论文》 一书问世，这是组合数学的第一部专著。

书 中首次使用了组合论（Combinatorics）一 词。

一切推理和发现，不管是否用语言描 述，都能归结为如数，字，声，色这些元素 经过某种组合的有序集合。

11组合数学的应用• 组合数学不仅在基础数学研究中具有极其重要的 地位，在其它的学科如计算机科学、编码和密码 学、物理、化学、生物等学科中，甚至在企业管 理，交通规划，战争指挥，金融分析，城市物流 等领域均有重要应用。

• 在美国有一家公司用组合数学的方法来提高企业 管理的效益，这家公司办得非常成功。

• 在美国已有专门的公司用组合设计的方法开发软 件，来解决工业界中的试验设计问题。

• 德国一位著名组合数学家利用组合数学方法研究 药物结构，为制药公司节省了大量的费用，引起 了制药业的关注。

12组合数学的应用• 著名的组合数学家 Thomas Tutte(1917-2002) 在组合数学界是泰斗级的 大师。

直到最近人们才知 道，原来他对提前结束“二 战”有着突出贡献。

• Tutte 从德军的两条情报密 码出发，用组合数学的方 法，重建了敌人的密码 机，确定了德军密码的内 部结构，从而获得了极为 重要的情报。

13四色问题• 在日常生活中我们常常可以遇到组合数学的问 题。

比如一个著名的世界难题“四色猜想” ：一 张地图，用一种颜色对一个地区着色，那么一共 只需要四种颜色就能保证每两个相邻的地区颜色 不同。

14四色问题• 1852年，刚从伦敦大学毕业的Francis Guthrie提出了四色猜想。

• 1878年著名的英国数学家Cayley向数学界征求 解答。

• 此后数学家 Heawood 花费了毕生的精力致力于四 色研究，于1890年证明了五色定理（每个平面图 都是5顶点可着色的）。

• 直到1976年6月，美国数学家 K. Appel与 W. Haken，在3台不同的电子计算机上，用了1200小 时，才终于完成了“四色猜想”的证明，从而使"四 色猜想"成为了四色定理。

15相识问题• 1958年，美国的《数学月刊》上登载着这 样一个有趣的问题：“任何6个人的聚会，其 中总会有3个人相互认识，或3个人相互不 认识”。

• 用6个顶点表示6个人，用红色连线表示两 者相识，用蓝色连线表示两者不相识。

于 是问题化为下述命题：16相识问题• 对6个顶点的完全图K6任意进行红、蓝两边 着色，则图中一定存在一个同色三角形。

17网络可靠性问题• 一个通讯网络怎样布局稳定性最好，而且 费用最节省？ • 美国的贝尔实验室和IBM公司都有世界一流 的组合数学家在研究这个问题，这个问题 直接关系到巨大的经济利益。

18最短网络问题• 如何用最短的线路将三部电话连起来？ • 此问题可抽象为设△ABC为等边三角形，，连接三顶点 的路线（称为网络）。

这种网络有许多个，其中最短路线 者显然是二边之和（如AB∪AC）。

AB |AB|+|AC| = 2C19最短网络问题• 但若增加一个周转站（新点P），连接4点的新网络的最 短路线为PA＋PB＋PC。

最短新路径之长N比原来只连三 点的最短路径O要短。

• 这样得到的网络不仅比原来节省材料，而且稳定性也更 好。

AP B |PA|+|PB|+|PC| = C320最小生成树和最小斯坦纳树Pollak－Gilbert猜想Pollak－Gilbert猜想Pollak－Gilbert猜想无尺度网络重要结论生物数学组合数学在计算机软件中的重要价值组合数学中的三大问题例:幻方存在性问题幻方的构造幻方的构造前言前言前言11.1加法法则与乘法法则1.1加法法则与乘法法则1.1加法法则与乘法法则1.1加法法则与乘法法则2)求小于10000的含0的正整数的个数1.2排列与组合1.2排列与组合1.2排列与组合排列组合问题的来源1.2排列与组合1.2排列与组合1.2排列与组合。