全面的计算机2014组合数学—CHO1

1、组合数学,吉林大学 计算机科学与技术学院 2014年9月,关于我,姓名：卢奕南 教研室：图像处理与虚拟现实研究团队 主要研究方向：图形图像、数据挖掘等,参考书： 机械工业出版社：组合数学，布鲁迪 (Brualdi R.A.) (作者), 冯舜玺 (译者) 清华大学出版社：组合数学，卢开澄等 习题（网上查） 组合数学（姜建国等），西安电子科技大学,本学期涉及到的内容（组合分析） 鸽巢原理和Ramsey定理 基本计数方法 容斥原理 生成函数 递推关系 Plya定理 二分图的匹配 组合设计 组合优化 组合矩阵,计 数,考试形式：作业+笔试 作业：20-40% 共10次作业（也许有小考）,怎样学好组合

2、数学,基本原则、容斥原理、生成函数、递推关系、polya等。 其他： 数学归纳法 组合模型的转换（一一对应技术） 数论 殊途同归法 反证法 要学好组合数学并非易事，既需要一定的数学修养，也要进行相当的训练。 计数时的合理分类，可从规模小的模型着手，从中找到规律性的东西，再推及一般。 你解决的问题越多，那么你能够解决下一个问题的可能性也越大。,8,第一章 引言,组合数学(简称组合学）是数学的一个分支, 它起源于古代的娱乐和休闲游戏。 广义的组合数学就是离散数学， 离散数学是狭义的组合数学和图论、代数结构、数理逻辑等的总称。,组合数学中的著名问题,如何构造幻方，比赛的场次等。 计算一些物品在特定条

3、件下分组的方法数目。这些是关于排列、组合和整数分拆的。 地图着色问题：对世界地图着色，每一个国家使用一种颜色。如果要求相邻国家的颜色相异，是否总共只需四种颜色？ 船夫过河问题：船夫要把一匹狼、一只羊和一棵白菜运过河。只要船夫不在场，羊就会吃白菜、狼就会吃羊。船夫的船每次只能运送一种东西。怎样把所有东西都运过河？。 中国邮差问题：由中国组合数学家管梅谷教授提出。邮递员要穿过城市的每一条路至少一次，怎样行走走过的路程最短？ 1856年，哈密尔顿（Kirkman）, 旅行商问题。 任务分配问题：各个员工完成不同任务所花费的时间不同。每个员工只分配一项任务。每项任务只被分配给一个员工。怎样分配员工与任

4、务以使所花费的时间最少？,组合数学的起源,幻方最早记载于我国公元前500年的春秋时期大戴礼中，这说明我国人民早在2500年前就已经知道了幻方的排列规律。而在国外，公元130年，希腊人塞翁才第一次提起幻方 ； 公园1275年（宋代），杨辉的著作中出现10阶幻方问题和杨辉三角的记载； 1666年，莱布尼茨发表组合的艺术(De Art Combinatoria)，这是组合数学的第一部专著。书中首次使用了组合论（Combinatorics）一词。标志组合数学的诞生。 莱布尼茨：德国最重要的自然科学家、数学家、物理学家、历史学家和哲学家，一个举世罕见的科学天才，和牛顿（1643年1月4日1727年3月3

5、1日）同为微积分的创建人。 杨辉，中国南宋时期杰出的数学家和数学教育家。,11,组合数学的蓬勃发展则是在计算机问世和普遍应用之后。 一方面，当我们研究的组合问题规模很大的时候，计算量会很大，计算机为求解这些问题提供了有力手段。 另一方面，在计算机科学的算法研究中 数据结构+算法+编程语言 时间复杂性和空间复杂性 计算复杂性理论、 算法设计与分析的基础课。 组合分析 组合算法,在其他领域：生物学、化学、心理学及基因工程等的应用。,2020年9月15日,12,什么是组合数学,组合数学就是研究按照一定的规则来安排一些离散个体的问题。它涉及面广，内容庞杂（涉及到组合分析、图论、组合算法、近代密码学、编

6、码理论等），并且仍在很快地发展着，因而还没有一个统一而有效的理论体系。 研究的对象是离散结构，一般可以用1，2，、，n表示。本书仅限于讨论n是有限的自然数的情况。 组合数学是研究离散结构的存在、计数、构造和优化等问题的一门学科。,14,组合数学的主要问题,（1）存在性问题 满足一定条件的安排的存在性. 如果某种安排不一定总存在，我们就需要研究存在的条件。 存在性是数学研究最重要的问题之一. 许多问题的存在性至今也无法解决？ 例如数论中很多难题：哥德巴赫猜想,（2）安排的枚举、分类和计数 如果所要求的安排存在，则可能有多种不同的安排。此时，需要计数不同的方案数，并将它们进行枚举和分类。 当实际问

7、题比较复杂的时候，必须有好的数学方法来解决.,（3）构造性问题 一个组合问题，如果已经判定解是存在的，那么将所有可能的安排构造出来是一个关键问题。 与计算机算法密切相关 典型问题：组合设计,（4）优化问题 在给定的优化条件下从所有的安排方案中找出最优的安排方案。 与算法分析密切相关 传统方法：动态规划 现代智能方法,本学期涉及到的内容（组合分析） 鸽巢原理和Ramsey定理（存在性问题） 基本计数方法 容斥原理 生成函数 递推关系 Plya定理,计 数,19,幻方问题有趣的数学游戏 幻方在娱乐数学中的地位以及它的意义非同一般，它是中国人的首创。 公元前2200年易经提到洛书与河图,1.1 幻方

8、问题,一个n阶幻方是由整数1，2，3，n2按下述方式组成的nn方阵：该方阵每行上的整数的和、每列上的整数的和以及两条对角线中每条对角线上的整数的和都等于同一个数s,21,3阶幻方的所有整数和为15；,每一行（或列或对角线）数字的和称为幻方的和（幻和）： S= n (n2+1)/2 。,关于幻方的问题归结为 （一）存在性问题 对任意的正整数n，n阶幻方存在吗？ （二）组合计数问题 如果存在，那么应该有多少个不同的 n阶幻方。 （三）构造问题 奇数阶幻方：连续摆数法(de La Loubre法) 双偶数（4k）阶幻方：对称法 单偶数(4k+2)阶幻方：斯特雷奇法（1918）,2020年9月15日,

9、23,（一）幻方的存在性问题 例1.1 证明了不存在2阶幻方。 对其余的正整数n，由于n阶幻方都能构造出来，当然就证明了（正整数）阶幻方的存在性。,24,例 1.1 证明不存在2阶幻方,证明：反证法。假定存在2阶幻方，如图所示：,根据幻方的定义，它的幻和是5，于是a1+ a2= a1+ a3=5，可得a2= a3，因为a1，a2，a3， a4必定彼此不同，所以不可能，矛盾。因此不存在2阶幻方。,2020年9月15日,25,（二） 幻方的构造性问题 （1）奇数阶幻方的构造,连续摆放法（de la Loubre法）。 规则为：假定构造n阶（n为奇数）幻方。 首先将1放在(n+1)/2列第1行的方格

10、中， 然后按照副对角线方向（即行号减1，列号加1）依次把从小到大的各个数字放入相应的方格中。,2020年9月15日,26,如果行号变成0（第1行上面一行），则改成第n行相应列对应的方格。 如果列号变成n+1（第n列右面一列），则改成第1列相应行对应的方格。 如果轮到的方格已经填有数字或者到了第0行第n+1列对应的方格，则退到前一个方格正下方的方格。,27,例1.2 利用连续摆放法构造5阶幻方,即行号减1，列号加1,28,（2）偶数阶幻方的构造 当n=4k的时候，即双偶数的情况， 对称法。 先把nn的方阵分成上、下、左、右四个2k2k的方阵。 然后对于左上的2k2k方阵进行处理，每行每列任意取一

11、半（k个）的方格做标记，如我们把这些方格涂成阴影。,29,然后按照对称轴将这种标记方式向下和向右作对称图形。经过处理后使得nn的方阵的每一行和每一列都有一半（n/2）的方格被涂成阴影。 接下来，把从1开始的数字依次往方格里面填。第一遍：从第1行第1列的方格开始往右，不是阴影，则填数字，如果是阴影的方格，不填数字，但相应的数字加1。第1行填完后，是第2行第1列的方格，依次，最后是第n行第n列的方格。,30,这样填完之后，有一半的方格被填上了数字。 第二遍，从第n行第n列的方格开始依次往左，规则同前，从1开始的数字依次往方格里面填。第n行结束之后，是第n-1行第n列的方格。依次，最后是第1行第1列

12、的方格。 最后就得到了幻方。,2020年9月15日,31,例1.3 利用对称法构造4阶幻方,32,当n=4k+2,所谓的单偶数的情况。 首先把nn的方阵分成上、下、左、右四个(2k+1)(2k+1)的方阵,为了表达方便，依次把左上、右下、右上、左下的方阵编号为A,B,C,D。 采用连续摆数法，把1(2k+1)2放在A中做成第一个幻方；把(2k+1)2 12(2k+1)2放在B中成第二个幻方。,33,把2(2k+1)213(2k+1)2放在C中成第三个幻方。 把3(2k+1)214(2k+1)2放在D中成第四个幻方。 然后，在A的各行从第1列开始向右取m个(m=(n-2)/4)方格，但中间一行（

13、k+1行）从第2列开始。,把这些方格中的数字与D中相应位置的数字对换。 在C中各行最后一列右起向左各取m1个方格，把这些方格中的数字与B中相应位置的数字对换。最后，就得到了幻方。,34,35,例1.4 构造6阶幻方,A C D B m=1 2k+1=3,36,37,（三）幻方的计数问题,3阶幻方 基本形式只有一种 若经过旋转和翻转 一共有8种变形,1 6 6 1 8 5 7 7 5 3 9 2 2 9 4,4阶幻方 分类枚举 基本形式有880个 变形有7040个,5 阶幻方 基本形式有275305224个,6 阶及以上幻方 即使通过大型计算机的计算仍然难以获得精确的数字，目前只能估计出它的取值

14、范围,39,2020年9月15日,在3维情形下的推广，n阶幻方体,是由整数1,2,3，。，n3构造成一个n*n*n的立方体阵列，其在下述每一条直线上的n个元素之和都是相同的s： （1）平行于立方体一条边的直线。 （2）每个截面上的两条对角线。 （3）四条空间对角线。,幻和s 值为（n4+n)/2 不存在 2阶幻方体、 3阶幻方体、 4阶幻方体。 反证不存在3阶幻方体,2020年9月15日,41,1.2 拉丁方问题,2020年9月15日,42,拉丁方是另一类典型的组合数学问题 n阶拉丁方定义为由数字1,2,n构成的nn的方阵，使得在每1行、每1列中每个数字都恰好出现1次。,拉丁方存在性问题,20

15、20年9月15日,43,2阶拉丁方是存在的,2020年9月15日,44,n阶拉丁方是存在的 构造方法如下： 第1行为（1,2,3,n） 第2行为 ( 2,3,n,1)， 第k行为 ( k,k+1,n,1, ,k-1)， 第n行为（n, 1 , 2 , 3, , n-1）。,45,例1.5 设计一个药物临床试验以测试五种药物对人体的药效。这五种药物编号1,2,3,4,5。然后选取5个人，并给每人不同的药。为了消除个体对药物的反应偏差，要求在连续5天里进行测试，每人每天吃一种药物。而为了消除服药时间造成药效的偏差，要求2个人不能在同1 天吃相同的药。,46,最后满足要求的实验是要形成由1,2,3,

16、4,5构成的55的方阵，其中每行每列中没有相同的数字，即5阶拉丁方的构造问题。,47,行（人） 列（天）,例 36军官问题 有36名军官来自六个不同的团，具有六种不同的军衔，而且每个团每种军衔的军官各有一名，能否把他们排成一个66方阵，每行和每列上的不同军衔的6名军官还分别来自不同的军团？ 是由Euler首先提出的，实际上是组合设计中的正交拉丁方问题，属于构造问题。 猜想？6、10、。,将这36名军官排成66方阵, 使得 1)每行每列都有任一军团的军官 2)每行每列都有任一军衔的军官. i :军衔, j :军团, 军官对应数偶(i, j), i, j1,6 问题等价于构造数偶(i,j)排成的6

17、阶方阵, 使得 1) 数偶第一个数字构成拉丁方; 2) 数偶第二个数字构成拉丁方; 3) 每个数偶只出现一次.,两个拉丁方称为互相正交，即正交拉丁方. 定义:设A=(aij)nn,B=(bij)nn是两个nn拉丁方. 令C=(aij, bij)nn,若C的n2对数偶互不相同, 则称A与B正交.,上述是两个3阶正交拉丁方。2阶哪？ 36军官问题即不存在6阶正交拉丁方。 欧拉不存在4k+26的猜想不对。,对于只有9个军官的类似问题有解：,52,1.3 涂色问题,在实际应用中，很多计数问题都可抽象成涂色问题。 作为典型的组合计数问题，根据涂色问题难度的不同，将反映出各种不同的计数技术。 四色问题,5

18、3,例1.6 对正三角形的三个顶点涂以红、蓝（r和b）两种颜色，求有多少种不同的涂色方案？,解 由于只有两种颜色，我们可以采用枚举方法分类讨论。,54,涂色方案可分成四类：,（1）三点全涂红色，只有一种方案 rrr （2）三点全涂蓝色，只有一种方案 bbb,（3）两点涂红色，一点涂蓝色，因蓝色可分别涂于三个顶点之一，故有3种方案 brr，rbr，rrb,（4）由对称性可知，两点涂蓝色，一点染红的方案也有3种：,55,红色, 蓝色,56,如果考虑正三角形可以旋转，则(3),(4),(5)显然是同一个涂色方案，(6),(7),(8)也是同一个涂色方案，这样涂色方案数就变成了4种。 如果变成了空间的

19、四面体了，即加上空间的旋转之后，涂色方法的计算将更加复杂。 要涂色的点和可选颜色的数目如再增加的话，枚举方法就不奏效了,需要特殊技巧解决问题 例 有101名选手参加羽毛球比赛，如果采用单循环淘汰制，问产生冠军需要进行多少场比赛？ 方法一：50+25+13+6+3+2+1=100场比赛 方法二：由于每场比赛都要产生一个失败者，而每个失败者只能失败一次，因此比赛的场数与失败者的人数相等，除冠军外其他100人都失败过，因此产生冠军需要100场比赛。 例 有一个边长为3的立方体木块，要把它切割成27个边长为1的小立方体，如果在切割的过程中可以重新排列被切割的木块，问至少需要多少次才能完成任务？,解：

20、首先可以看到，通过6次是可以完成整个切割的，上图就是这样的一种方案。其次，我们证明少于6次是不能完成切割的。由于处于原立方体中心的一个小立方体的每个面都是由切割产生的，每次切割只能产生一个面，所以切割次数不能少于它的面数，因此至少6次才能完成切割。,例:棋盘的完美覆盖 Perfect Covers of Chessboards,mn棋盘: m行n列方格, b-牌:1行b个的方格条 mn棋盘被b-牌的一个完美覆盖是 b-牌在棋盘上的一个排列, 满足: (1)每个格子恰好只被一张牌覆盖; (2) 每条b-牌覆盖b个方格.,64=8*8, 2-牌的覆盖 32 张多米诺牌 12,988,816 = 24 X 172 X 532,34棋盘有2-牌的完美覆盖. 33棋盘有2-牌的完美覆盖？,64个格去掉对角上的两个方格，剩下62个格，存在完美覆盖吗?,将棋盘上的方格交替涂成黑色和白色 32个黑、30个白 31张不重叠的多米诺要盖住31个白方格和31个黑方格 若完美=切过的棋盘必须有相同数目的黑白格。 二分图的匹配,66棋盘有4-牌的完美覆盖吗?,定理: mn棋盘有b-牌的完美覆盖 b|m或b|n.,Nim取子游戏,Nim取子游戏是由两个人面对若干堆硬币（或石子）进行的游戏。设有k=1堆硬币，各堆分