组合数学前沿介绍.pdf

1 组合数学组合数学 C o m b i n a t o r i c s 马昱春马昱春 MA Yuchun myc 2 组合数学组合数学 C o m b i n a t o r i c s 组合数学组合数学 有人认为广义的组合数学组合数学就是离散数学 也有人认 为离散数学是狭义的组合数学和图论 代数结构 数理逻辑 等的总称 但这只是不同学者在叫法上的区别 总之 组合 数学是一门研究离散对象的科学 http zh wikipedia org zh cn E7 BB 84 E5 90 88 E6 95 B0 E5 AD A6 Combinatorics 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 http en wikipedia org wiki Combinatorics 3 组合数学与离散数学 狭义的组合数学主要研究满足一定条件的组态 也称组合模型 的存在 计数以及构造等方面的 问题 组合数学的主要内容有组合计数 组合设计 组合矩 阵 组合优化等 离散数学 Discrete mathematics 是数学的几个分 支的总称 以研究离散量的结构和相互间的关系 为主要目标 其研究对象一般地是有限个或可数 无穷个元素 因此它充分描述了计算机科学离散 性的特点 离散数学通常研究的领域包括 数理逻辑 集合论 关系论 函数论 组合学 代数系统与图论 4 离散数学 目录 离散数学 第四版 作者 耿素云 屈婉玲 张立昂 编著 第1章命题逻辑 第2章一阶逻辑 第3章集合的基本概念和运算 第4章二元关系和函数 第5章代数系统的一般性质 第6章几个典型的代数系统 第7章图的基本概念 第8章一些特殊的图 第9章树 第10章组合分析初步 10 1加法法则和乘法法则 10 2基本排列组合的计数方法 10 3递推方程的求解与应用 10 4题例分析 第11章形式语言和自动机初步 第1章 排列与组合 第2章 递推关系与母函数 第3章 容斥原理与鸽巢原理 第4章Burnside引理与Polya定理 第5章区组设计 第6章线性规划 第7章编码简介 第8章组合算法简介 5 前言 组合数学研究的是事物按照某种规则的安排 主 要有 存在性问题 计数性问题和对已知安排的 研究 Richard A BrualDi 所著 Introductory Combinatorics 组合数学就是对给定描述的事物有多少种或者某 种事物发生的途径有多少种的研究 Daniel I A Cohen 所著 Basic Techniques of Combinatorial Theory 研究离散结构的存在 计数 分析和优化等问题 的一门学科 高洁 浅谈组合数学的应用与 教学 6 组合数学的历史 组合数学是一个古老而又年轻的数学分支 据传说 大禹在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 7 组合数学的历史 传说在公元前23世纪大禹 治水的时候 在黄河支流 洛水中 浮现出一个 大乌 龟 甲上背有9种花点的 图案 人们将图案中的花 点数了一下 竞惊奇地发 现9种花点数正巧是1 9 这9个数 各数位置的排 列也相当奇妙 横的3 行 纵的3列以及两对角 线上各自的数字之和都为 15 大禹 2205BC 2105BC 492 357 816 8 幻方问题 组合数学中有许多象幻方这样精巧的结 构 1977年美国旅行者1号 2号宇宙飞船 就带上了幻方以作为人类智慧的信号 神农幻方 492 357 816 2200BC 1 15 14 4 12 6 7 9 8 10 11 5 13 3 2 16 15世纪 阶幻方 9 阿基米德手稿 用希腊文写在羊皮纸上的阿基米德手 稿副本 距今975年 2003科学家借 助现代科技手段初步破译了古希腊数 学家阿基米德的这篇论文 结论是这 篇论文解决的是组合数学问题 在论文中阿基米德是在计算把14条 不规则的纸带拼成正方形一共能有多 少种不同的拼法 这在现在被称为 tiling问题 当今数学家借助计算机得出的答案是 17152种拼法 这在当时是相当困难 的 10 贾宪三角 中国最早的组合数学 理论可追溯到宋朝时 期的 贾宪三角贾宪三角 后来 被杨辉引用 所以普遍 称之为 杨辉三角杨辉三角 这 在西方是1654年由帕 斯卡提出 但比中国 晚了400多年 11 组合数学的历史 1666年莱布尼兹所著 组合学论文 一书问世 这是组合数学的第一部专著 书 中首次使用了组合论 Combinatorics 一 词 一切推理和发现 不管是否用语言描 述 都能归结为如数 字 声 色这些元素 经过某种组合的有序集合 12 组合数学的应用 组合数学不仅在基础数学研究中具有极其重要的 地位 在其它的学科如计算机科学 编码和密码 学 物理 化学 生物等学科中 甚至在企业管 理 交通规划 战争指挥 金融分析 城市物流 等领域均有重要应用 在美国有一家公司用组合数学的方法来提高企业 管理的效益 这家公司办得非常成功 在美国已有专门的公司用组合设计的方法开发软 件 来解决工业界中的试验设计问题 德国一位著名组合数学家利用组合数学方法研究 药物结构 为制药公司节省了大量的费用 引起 了制药业的关注 13 组合数学的应用 著名的组合数学家 Thomas Tutte 1917 2002 在组合数学界是泰斗级的 大师 直到最近人们才知 道 原来他对提前结束 二 战 有着突出贡献 Tutte 从德军的两条情报密 码出发 用组合数学的方 法 重建了敌人的密码 机 确定了德军密码的内 部结构 从而获得了极为 重要的情报 14 四色问题 在日常生活中我们常常可以遇到组合数学的问 题 比如一个著名的世界难题 四色猜想四色猜想 一 张地图 用一种颜色对一个地区着色 那么一共 只需要四种颜色就能保证每两个相邻的地区颜色 不同 15 四色问题 1852年 刚从伦敦大学毕业的Francis Guthrie提出了四色猜想 1878年著名的英国数学家Cayley向数学界征求 解答 此后数学家 Heawood 花费了毕生的精力致力于四 色研究 于1890年证明了五色定理 每个平面图 都是5顶点可着色的 直到1976年6月 美国数学家 K Appel与 W Haken 在3台不同的电子计算机上 用了1200小 时 才终于完成了 四色猜想 的证明 从而使 四 色猜想 成为了四色定理 16 相识问题 1958年 美国的 数学月刊 上登载着这 样一个有趣的问题 任何6个人的聚会 其 中总会有3个人相互认识 或3个人相互不 认识 用6个顶点表示6个人 用红色连线表示两 者相识 用蓝色连线表示两者不相识 于 是问题化为下述命题 17 相识问题 对6个顶点的完全图K6任意进行红 蓝两边 着色 则图中一定存在一个同色三角形 18 网络可靠性问题 一个通讯网络怎样布局稳定性最好 而且 费用最节省 美国的贝尔实验室和IBM公司都有世界一流 的组合数学家在研究这个问题 这个问题 直接关系到巨大的经济利益 19 最短网络问题 如何用最短的线路将三部电话连起来 此问题可抽象为设 ABC为等边三角形 连接三顶点 的路线 称为网络 这种网络有许多个 其中最短路线 者显然是二边之和 如AB AC A B C AB AC 2 20 最短网络问题 但若增加一个周转站 新点P 连接4点的新网络的最 短路线为PA PB PC 最短新路径之长N比原来只连三 点的最短路径O要短 这样得到的网络不仅比原来节省材料 而且稳定性也更 好 A BC P PA PB PC 3 21 最小生成树和最小斯坦纳树斯坦纳树 由于最短网络在运输 通讯和计算机等现 代经济与科技领域中都有重要的应用 对 这个问题的研究也越来越深入 问题的对 象已由三个点扩展到任意有限个点集 斯坦纳 Steiner 最小树斯坦纳 Steiner 最小树是可以在给定的 点之外再增加若干个点 称为斯坦纳点斯坦纳点 然后将所有这些点连起来 如果不允许增加任何额外的点作为网络的 顶点 这种最短网络称为最小生成树最小生成树 在前面的例子中Steiner最小树的长为 而最小生成树的长为2 3 22 Pollak Gilbert猜想 1968年贝尔实验室数学中心主任波雷克 Pollak 和研究员吉尔伯特 Gilbert 提出 如下猜想 平面上任意n点集 斯坦纳最小树长与最小 生成树之长的比值的最小值是 这个猜想又被称为斯坦纳比猜想斯坦纳比猜想 2 3 23 Pollak Gilbert猜想 Pollak Gilbert猜想起源于在美国贝尔电话公司 发生的一个富有戏剧性的事件 1967年前 贝尔公司按照连结各分部的最小生成 树的长度来收费 1967年一家航空公司戳了贝尔 公司一个大洞 当时这家企业申请要求贝尔公司 增加一些服务点 而这些服务点恰恰位于构造该 公司各分部的斯坦纳最小树需增加的斯坦纳顶点 上 这使得贝尔公司不仅要拉新线 增加服务网 点 而且还要减少收费 这一意外事件迫使贝尔 公司自此以后便采用了斯坦纳最小树原则 24 Pollak Gilbert猜想 1990年 中科院应用数学所研究员堵丁柱与美籍 华人黄光明合作 证明了Pollak Gilbert猜想 在美国离散数学界引起轰动 被列为1989 1990年度美国离散数学界与理论计算机科学界的 两项重大成果之一 在 不列颠百科全书1992年鉴 的数学评论中 该成果被列为世界上当年六项数学成果首项 该成果被我国列为1992年十大科技成就之一 25 无尺度网络 20世纪20年代 由Karinthy提出 1950年 Pool 和 Kochen提出这样一个问题 两个毫无关系的人 要让他们互相认识 至少要 经过多少人 美国哈佛大学社会心理学家S Milgram在1967年 做过一项有趣的实验 据说他从内布拉斯加州的 奥马哈随机选了300人 然后请他们每个人尝试 寄一封信到波士顿的一位证券业务员 寄信的规 则很简单 就是任何收信者只能把信寄给自己熟 识的人 26 重要结论 6度分离 对每个人来说 平均大约只需要通过 个人就能将信寄到目的地 研究无尺度网络 对于防备黑客攻击 防治流行 病 和开发新药等 都具有重要的意义 在1999年 Barab asi et al 发现在因特网上 任 意两个网页间的链接即网页之间的 距离 平均为 18 59 从任意一个网页出发 原则上可以通过 不超过19次链接到达互联网中的任何网页 Nature 401 1999 27 生物数学 目前 计算生物学 基因理论 生物信息 学都是最前沿的研究领域 随着人类基因组计划的完成和其他基因计 划的完成 所有公认的和潜在的蛋白质元 都可以被确定 通过大规模的实验技术 可以生成大量的生物学数据 如何处理这些数据来获得生物学的信息 这里组合数学和随机图论都起到了关键的 作用 28 组合数学在计算机软件中的重要价值组合数学在计算机软件中的重要价值 网络算法和分析 信息压缩 网络安全 编 码技术 系统软件 并行算法 数学机械化 和计算机推理 等等 与实际应用有关的还有许多许多需要数学基 础的算法 如运筹规划 金融工程 计算机 辅助设计等 29 组合数学中的三大问题 存在 existence problem 是否存在合理的解 计数 counting problem 有多少种解的可能 优化 optimization problem 依照某种标准 所有解中那个是最优的 30 例 幻方 一个n阶幻方是由整数1 2 3 n2按下述方 式组成的n n方阵 该方阵每行上的整数 的和 每列上的整数的和以及两条对角线 中每条对角线上的整数和都等于同一数s 该整数s即为该幻方的幻和 1 2 3 n2 整数和为 1 2 3 n2 n2 n2 1 2 n阶幻方共有n行 每行的和为s ns n2 n2 1 2 s n n2 1 2 31 存在性问题 是否存在2阶幻方 2阶幻方的幻和为5 假设存在2阶幻方 a b c d b d 0 与假设矛盾 a b c d是 1 4 的各不相同的整数 不存在2阶幻方 a b 5 c d 5 a d 5 c b 5 32 幻方的构造 17世纪de la Loubere提出了n阶幻方构造 方法 其中n为奇数 将1放在最上一行的中间 然后按照自左下 到右上的对角线顺序来放置 同时遵循如下 规则 到达顶行 则下一个数放在底行 位置相应错过 去 到达最右边一列 下一个整数放在最左边 位置 相应错位 如果要放的位置上已经填好了整数 或者已经放 到了右上角 则放在紧挨着该位置的下方 33 幻方的构造 将1放在最上一行的中 间 然后按照自左下到 右上的对角线顺序来放 置 同时遵循如下规 则 到达顶行 则下一个数 放在底行 位置相应错 过去 到达最右边一列 下一 个整数放在最左边 位 置相应错位 如果要放的位置上已经 填好了整数 或者已经 放到了右上角 则放在 紧挨着该位置的下方 8 3 4 16 5 9 7 2 34 前言 组合数学的历史渊源扎根于数学娱乐和游戏之 中 过去的研究往往出于消遣或者美学的考 虑 组合数学的蓬勃发展则是在计算机问世和普遍 应用之后 程序的基础往往是求解问题的组合数学算法 算法的运行时间效率和存储需求分析都需要组合数 学的思想 过去研究过的许多问题如今在研究和应用中具有高 度的重要性 广泛应用在社会科学 生物科学 信息论等 由于组合数学涉及面广 内容庞杂 并且仍在 很快地发展着 因而还没有一个统一而有效的 理论体系 这与数学分析形成了对照 35 前言 本学期主要讲组合分析 计数和枚举 以及组 合优化的一部分 线性 规划的单纯形解法 教材 清华大学出版社 组合数学 卢开澄 第四版 参考书目 Introductory Combinatorics by Bruali R A Applied Combinatorics by Roberts F S 第1章 排列与组合 第2章 递推关系与母函数 第3章 容斥原理与鸽巢原理 第4章 Burnside引理与Polya定理 第5章 区组设计 第6章 线性规划 第7章 编码简介 第8章 组合算法简介 36 前言 组合数学经常使用的方法并不高深复杂 最 主要的方法是计数时的合理分类计数时的合理分类和组合模型 的转换 组合模型 的转换 要学好组合数学并非易事 既需要一定的数 学修养 也要进行相当的训练 考核标准 作业 30 考试 70 答疑 课后答疑 网上答疑 习题课 Projects 10 37 37 1 第一章排列组合 1 1 加法法则与乘法法则 分类计数和分步计数 从甲地到乙地 可以乘火车 也可以乘汽车 一天中 火车有3班 汽车有2班 那么一 天中 乘坐这些交通工具从甲地到乙地共有 多少种不同的走法 解答 解答 3 2 5 种不同的走法种不同的走法 从甲地到乙地 要从甲地选乘火车到丙地 再 于次日从丙地乘汽车到乙地 一天中 火车有 3班 汽车有2班 那么两天中 从甲地到乙地 共有多少种不同的走法 解答 共有解答 共有 3 2 6 种不同的走法种不同的走法 2 1 1 加法法则与乘法法则 加法法则加法法则 The Sum Rule 设事件A有m种产生方 式 事件B有n种产生方式 则事件A或B之一 有m n种产生方式 集合论语言 若 A m B n A B 则 A B m n 例 某班选修企业管理的有 18 人 不选 的有 10 人 则该班共有 18 10 28 人 3 1 1 加法法则与乘法法则 乘法法则乘法法则 The Product Rule 设事件A有m种 产生式 事件B有n种产生方式 则事件A与B 有 m n种产生方式 集合论语言 若 A m B n A B a b a A b B 则 A B m n 例 某种字符串由两个字符组成 第一个字符 可选自 a b c d e 第二个字符可选自 1 2 3 则这种字符串共有5 3 15 个 4 1 1 加法法则与乘法法则 例例 某种样式的运动服的着色由底色和装饰 条纹的颜色配成 底色可选红 蓝 橙 黄 条纹色可选黑 白 则共有4 2 8种 着色方案 若此例改成底色和条纹都用红 蓝 橙 黄 四种颜色的话 则 方案数就不是4 4 16 而只有 4 3 12 种 在乘法法则中要注意事件 A 和 事件 B 的相 互独立性 5 1 1 加法法则与乘法法则 例例1 求小于10000的含1的正整数的个数 2 求小于10000的含0的正整数的个数 1 小于10000的不含1的正整数可看做4位数 但0000除外 故有9 9 9 9 1 6560个 含1的有 9999 6560 3439个 另 全部4位数有104个 不含1的四位数有94个 含1的4位数为两个的差 104 94 3439个 6 2 求小于10000的含0的正整数的个数 含含0 和和 含含1 是否可以直接套用 是否可以直接套用 0019含含1但不含但不含0 在组合的习题中有许多类似的 在组合的习题中有许多类似的隐含隐含的 规定 要特别留神 不含 的 规定 要特别留神 不含0的的1位数有位数有9个 个 2位数有位数有92个 个 3位数有位数有93个 个 4位数有位数有94个 不含 个 不含0小于小于10000的正整数有的正整数有 9 92 93 94 95 1 9 1 7380个 含 个 含0小于小于10000的正整数有的正整数有 9999 7380 2619个个 7 1 2排列与组合 定义 排列定义 排列 Permutation 从n个不同的元素 中 取r个不重复的元素 按次序排列 称为 从n个中取r个的无重排列 排列的个数用P n r 表示 或者 当r n时称为全排列 一般不 说可重即无重 定义 组合定义 组合 Combinations 从n个不同元素中 取r个不重复的元素组成一个子集 而不考虑 其元素的顺序 称为从n个中取r个的无重组 合 组合的个数用C C n n r r 表示或者 r n P r n C 8 1 2排列与组合 从n个中取r个的排列的典型例子是从n个不 同的球中 取出r个 放入r个不同的盒子里 每盒1个 第1个盒子有n种选择 第2个有n 1种 选择 第r个有n r 1种选择 故有P n r n n 1 n r 1 有时也用 n r记n n 1 n r 1 全排列 P n n n 递推关系 P n r nP n 1 r 1 P n 1 r rP n 1 r 1 rn n 9 1 2排列与组合 若球不同 盒子相同相同 则是从n个中取r个 的组合组合的模型 若放入盒子后再将盒子标号区别 则又回 到排列模型 每一个组合可有r 个标号方 案 故有C n r r P n r C n r P n r r n r r n r rnr n rn n 10 排列组合问题的来源排列组合问题的来源 排列组合问题 最早见于我国的 易经 一书 所谓 四象 就是每次取两个爻 y o 的排列 八卦 是每次取三个爻 的排列 在汉代数学家徐岳的 数术记遗 公元2世纪 中 也曾记 载有与占卜有关的 八卦算 即把卦按不同的方法在八个 方位中排列起来 它与 八个人围一张圆桌而坐 问有多少 种不同坐法 这一典型的排列问题类似 11世纪时 邵雍还 进一步研究了六十四卦的排列问题 唐朝僧人一行曾经研究过围棋布局的总数问题 古代的棋 盘共有17路 289个点 后来发展到19路361个点 一行曾 计算过一切可能摆出的棋局总数 后来 17世纪 北宋时期沈括在 梦溪笔谈 中 进一步讨 论了围棋布局总数问题 他利用一些排列 组合的办法对 一行的计算作了分析 沈括指出 当361个棋子全用上时 棋局总数达到1000052的数量级 11 1 2排列与组合 例例有5本不同的日文书 7本不同的英 文书 10本不同的中文书 1 取2本不同文字的书 5 7 5 10 7 10 155 2 取2本相同文字的书 C 5 2 C 7 2 C 10 2 10 21 45 76 3 任取两本书 155 76 231 C 5 7 10 2 12 1 2排列与组合 多重排列 2个a 3个b 4个c 其多重排列记为 加上下标以区别 a1a2b1b2b3c1c2c3c4 a下标排列有2 b下标排列有3 c下标排 列有4 432 9 9 4 3 2 432 9 4 3 2 9 432 9 13 1 2排列与组合 求r1个1 r2个2 rt个t的排列数 设 r1 r2 rt n 设此排列数为P n r1 r2 rt 对1 2 t分别加下标 得到 P n r1 r2 rt r1 r2 rt n P n r1 r2 rt 多项式展开 nk knk nk knkn baknCba knk n ba 00 nraa rr n aaa i rt t r t n t 1 1 1 21 21t rrr n t rrr n 21 14 1 2排列与组合 圆排列 从n个中取r个的圆排列的排列数为 P n r r 2 r n 以4个元素为例 1 2 4 3 1234 1 2 4 3 2341 1 2 4 3 3412 1 2 4 3 4123 15 1 2排列与组合 项链排列 排列的方法和项链一样 在圆 排列的基础上 正面向上和反面向上两 种方式放置各个数是同一个排列 例例 下面两种方式实际上表示的都是3个 元素的同一种排列 从n个中取r个的项链排列的排列数为 P n r 2r 3 r n 1 1 2 3 3 2 16 1 2排列与组合 例例从 1 300 中取3个不同的数 使这3个数的 和能被3整除 有多少种方案 解解 将 1 300 分成3类 A i i 1 mod 3 1 4 7 298 B i i 2 mod 3 2 5 8 299 C i i 3 mod 3 3 6 9 300 要满足条件 有四种可能 1 3个数同属于A 2 3个数同属于B 3 3个数同属于C 4 A B C各取一数 故共有3C 100 3 1003 485100 1000000 1485100 17 1 2排列与组合 例某车站有6个入口处 每个入口处每次只 能进一人 一组9个人进站的方案有多少 例某车站有6个入口处 每个入口处每次只 能进一人 一组9个人进站的方案有多少 解 一进站方案表示成 XX11 XX 1X1X1XXX 其中 X 表示某人 1 表示门框 其中 X 是不 同元 1 是相同元 任意进站方案可表示成上 面14个元素的一个排列 271459836 18 1 2排列与组合 XX11 XX 1X1X1XXX 解法1 给每个方案的门标号可产生5 个14 个元的全排列 故若设x为所求方案数 则 x 5 14 x 14 5 726485760 解法2 在14个元的排列中先确定 1 的位 置 有C 14 5 种选择 再确定人的位置 有 9 种选择 故C 14 5 9 即所求 19 1 2排列与组合 解法3 把全部选择分解成若干步 使每步宜于计 算 不妨设9个人编成1至9号 1号有6种选择 2号除可有1号的所有选择外 还可 也必须 选 择当与1号同一门时在1号的前面还是后面 故2号 有7种选择