全面的计算机组合数学—CHO

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

2、Plya定理二分图的匹配组合设计组合优化组合矩阵计计 数数考试形式：作业+笔试作业：20-40%共10次作业（也许有小考）怎样学好组合数学怎样学好组合数学基本原则、容斥原理、生成函数、递推关系、基本原则、容斥原理、生成函数、递推关系、polya等。等。其他：其他： 数学归纳法数学归纳法 组合模型的转换组合模型的转换（一一对应技术）（一一对应技术） 数论数论 殊途同归法殊途同归法 反证法反证法 要学好组合数学并非易事，既需要一定的要学好组合数学并非易事，既需要一定的数学修养数学修养，也要进行相当的训，也要进行相当的训练。练。计数时的合理分类，计数时的合理分类，可从规模小的模型着手，从中找到规律性

3、的东西，可从规模小的模型着手，从中找到规律性的东西，再推及一般。再推及一般。你解决的问题越多，那么你能够解决下一个问题的可能性也越大你解决的问题越多，那么你能够解决下一个问题的可能性也越大。 8第一章第一章 引言引言组合数学组合数学(简称组合学）是数学的一个分支简称组合学）是数学的一个分支, 它它起源于古代的娱乐和休闲游戏。起源于古代的娱乐和休闲游戏。组合数学中的著名问题组合数学中的著名问题如何构造如何构造幻方幻方，比赛的场次等。，比赛的场次等。 计算一些物品在特定条件下分组的方法数目。这些是关于计算一些物品在特定条件下分组的方法数目。这些是关于排列排列、组合组合和和整数分拆整数分拆的。的。

4、地图着色问题地图着色问题：对世界地图着色，每一个国家使用一种颜色。：对世界地图着色，每一个国家使用一种颜色。如果要求相邻国家的颜色相异，是否总共只需四种颜色？如果要求相邻国家的颜色相异，是否总共只需四种颜色？船夫过河问题船夫过河问题：船夫要把一匹狼、一只羊和一棵白菜运过河。：船夫要把一匹狼、一只羊和一棵白菜运过河。只要船夫不在场，羊就会吃白菜、狼就会吃羊。船夫的船每次只要船夫不在场，羊就会吃白菜、狼就会吃羊。船夫的船每次只能运送一种东西。怎样把所有东西都运过河？。只能运送一种东西。怎样把所有东西都运过河？。 中国邮差问题中国邮差问题：由中国组合数学家由中国组合数学家管梅谷管梅谷教授提出。邮递员

5、要教授提出。邮递员要穿过城市的每一条路至少一次，怎样行走走过的路程最短？穿过城市的每一条路至少一次，怎样行走走过的路程最短？ 1856年，哈密尔顿（年，哈密尔顿（Kirkman）, 旅行商问题。旅行商问题。任务分配问题：任务分配问题：各个员工完成不同任务所花费的时间不同。每个员工只分配一项任务。每项任务只被分配给一个员工。怎样分配员工与任务以使所花费的时间最少？组合数学的起源组合数学的起源幻方最早记载于我国公元前幻方最早记载于我国公元前500年的春秋时期年的春秋时期大戴礼中，这说明我中，这说明我国人民早在国人民早在2500年前就已经知道了幻方的排列规律。而在国外，公元年前就已经知道了幻方的排列

6、规律。而在国外，公元130年，希腊人塞翁才第一次提起幻方年，希腊人塞翁才第一次提起幻方 ；公园公园1275年（宋代），杨辉的著作中出现年（宋代），杨辉的著作中出现10阶幻方问题和杨辉三角的记阶幻方问题和杨辉三角的记载；载；1666年，莱布尼茨发表年，莱布尼茨发表组合的艺术组合的艺术(De Art Combinatoria)，这是组，这是组合数学的第一部专著。书中首次使用了组合论（合数学的第一部专著。书中首次使用了组合论（Combinatorics）一词）一词。标志组合数学的诞生。标志组合数学的诞生。莱布尼茨：莱布尼茨：德国德国最重要的最重要的自然科学自然科学家、家、数学数学家、家、物理学物理学

7、家、历史学家和家、历史学家和哲学哲学家，一个举世罕见的科学家，一个举世罕见的科学天才，和天才，和牛顿牛顿（1643年年1月月4日日1727年年3月月31日）同为日）同为微积分微积分的创建人。的创建人。 杨辉，杨辉，中国中国南宋南宋时期杰出的时期杰出的数学数学家和数学教育家。家和数学教育家。 11 组合数学的组合数学的蓬勃发展蓬勃发展则是在计算机问世和则是在计算机问世和普遍应用之后。普遍应用之后。 一方面，当我们研究的一方面，当我们研究的组合问题规模很大组合问题规模很大的的时候，计算量会很大，计算机为求解这些问题时候，计算量会很大，计算机为求解这些问题提供了有力手段。提供了有力手段。 另一方面，

8、在另一方面，在计算机科学的算法研究中计算机科学的算法研究中 数据结构数据结构+算法算法+编程语言编程语言 时间复杂性和空间复杂性时间复杂性和空间复杂性 计算复杂性理论计算复杂性理论、 算法设计与分析算法设计与分析的基础课。的基础课。组合分析组合分析 组合算法组合算法在其他领域：生物学、化学、心理学及基因工程等的应用。2022年年5月月15日日12什么是组合数学什么是组合数学组合数学就是研究按照一定的规则来安排一些组合数学就是研究按照一定的规则来安排一些离散个体的问题。它涉及面广，内容庞杂（涉离散个体的问题。它涉及面广，内容庞杂（涉及到组合分析、图论、组合算法、近代密码学及到组合分析、图论、组合

9、算法、近代密码学、编码理论等），并且仍在、编码理论等），并且仍在很快地发展很快地发展着，因着，因而还而还没有一个统一而有效的理论体系没有一个统一而有效的理论体系。 研究的对象是离散结构，一般可以用研究的对象是离散结构，一般可以用1，2，、，、，n表示。表示。本书仅限于讨论本书仅限于讨论n是有限的是有限的自然数的情况。自然数的情况。组合数学是研究组合数学是研究离散结构的存在、计数、构造离散结构的存在、计数、构造和优化和优化等问题的一门学科。等问题的一门学科。14 组合数学的主要问题组合数学的主要问题（1）存在性问题）存在性问题 （2）安排的枚举、分类和计数）安排的枚举、分类和计数 （3）构造性问

10、题）构造性问题 与计算机算法密切相关与计算机算法密切相关 典型问题：组合设计典型问题：组合设计 （4）优化问题）优化问题与算法分析密切相关与算法分析密切相关 传统方法：动态规划传统方法：动态规划 现代智能方法现代智能方法本学期涉及到的内容（组合分析）本学期涉及到的内容（组合分析）鸽巢原理和鸽巢原理和Ramsey定理（存在性问题）定理（存在性问题）基本计数方法基本计数方法容斥原理容斥原理生成函数生成函数递推关系递推关系Plya定理计计 数数19幻方问题幻方问题有趣的数学游戏有趣的数学游戏 幻方在娱乐数学中的地位以及它的意义幻方在娱乐数学中的地位以及它的意义非同一般，它是中国人的首创。非同一般，它

11、是中国人的首创。 公元前公元前22002200年年易经易经提到提到洛书洛书与与河图河图 1.1 幻方问题幻方问题816357492一个n阶幻方是由整数1，2，3，n2按下述方式组成的nn方阵：该方阵每行上的整数的和、每列上的整数的和以及两条对角线中每条对角线上的整数的和都等于同一个数s 21 3阶幻方的所有整数和为阶幻方的所有整数和为15；每一行（或列或对角线）数字的和称为每一行（或列或对角线）数字的和称为幻方的和（幻和）：幻方的和（幻和）： S= n (n2+1)/2 。关于幻方的问题归结为关于幻方的问题归结为（一）存在性问题（一）存在性问题 对任意的正整数对任意的正整数n，n阶幻方存在吗？

12、阶幻方存在吗？（二）组合计数问题（二）组合计数问题 如果存在，那么应该有多少个不同的如果存在，那么应该有多少个不同的 n阶幻方。阶幻方。 （三）构造问题（三）构造问题 奇数阶幻方：连续摆数法奇数阶幻方：连续摆数法(de La Loubre法法) 双偶数（双偶数（4k）阶幻方：对称法）阶幻方：对称法 单偶数单偶数(4k+2)阶幻方：斯特雷奇法（阶幻方：斯特雷奇法（1918） 2022年年5月月15日日23（一）幻方的存在性问题（一）幻方的存在性问题 例1.1 证明了不存在2阶幻方。对其余的正整数n，由于n阶幻方都能构造出来，当然就证明了（正整数）阶幻方的存在性。 24例例 1.1 证明不存在证明

13、不存在2阶幻方阶幻方证明：证明：反证法。假定存在2阶幻方，如图所示：a1a2a3a4根据幻方的定义，它的幻和是5，于是a1+ a2= a1+ a3=5，可得a2= a3，因为a1，a2，a3， a4必定彼此不同，所以不可能，矛盾。因此不存在2阶幻方。 2022年年5月月15日日25（二）（二） 幻方的构造性问题幻方的构造性问题（1）奇数阶幻方的构造）奇数阶幻方的构造连续摆放法（连续摆放法（de la Loubre法）。法）。规则为：规则为：假定构造假定构造n阶（阶（n为奇数）幻方为奇数）幻方。 首先首先将将1放在放在(n+1)/2列第列第1行的方格中，行的方格中， 然后然后按照副对角线方向（即

14、行号减按照副对角线方向（即行号减1，列号加列号加1）依次把从小到大的各个数字放）依次把从小到大的各个数字放入相应的方格中。入相应的方格中。2/ ) 1( n2022年年5月月15日日26 如果行号变成如果行号变成0（第（第1行上面一行），行上面一行），则改成第则改成第n行相应列对应的方格。行相应列对应的方格。 如果列号变成如果列号变成n+1（第（第n列右面一列），列右面一列），则改成第则改成第1列相应行对应的方格。列相应行对应的方格。 如果轮到的方格已经填有数字或者到如果轮到的方格已经填有数字或者到了第了第0行第行第n+1列对应的方格，则退到前列对应的方格，则退到前一个方格正下方的方格。一个方

15、格正下方的方格。 27例例1.2 利用连续摆放法构造5阶幻方 17241815235714164613202210121921311182529即行号减即行号减1，列号加，列号加12829302022年年5月月15日日31 214315812592117143106151381211659432 33 3435 192867233342621221712192327101433036 29 13 18242520151611A CD Bm=12k+1=336192867233342621221712192327101433036 29 13 1824252015161137（三）幻方的计数问题

16、（三）幻方的计数问题 3阶幻方阶幻方 基本形式只有一种 若经过旋转和翻转 一共有8种变形 81 6 6 1 835 7 7 5 34 9 2 2 9 4 4阶幻方阶幻方 分类枚举 基本形式有880个 变形有7040个 5 阶幻方阶幻方 基本形式有275305224个 6 阶及以上幻方阶及以上幻方 即使通过大型计算机的计算仍然难以获得精确的数字，目前只能估计出它的取值范围392022年年5月月15日日在3维情形下的推广，n阶幻方体,是由整数1,2,3，。，n3构造成一个n*n*n的立方体阵列，其在下述每一条直线上的n个元素之和都是相同的s：（1）平行于立方体一条边的直线。（2）每个截面上的两条对

17、角线。（3）四条空间对角线。 幻和s 值为（n4+n)/2不存在2阶幻方体、3阶幻方体、4阶幻方体。反证不存在3阶幻方体2022年年5月月15日日411.2 拉丁方问题拉丁方问题2022年年5月月15日日42 拉丁方拉丁方是另一类典型的组合数学是另一类典型的组合数学问题问题 n阶拉丁方阶拉丁方定义为由数字1,2,n构成的nn的方阵，使得在每1行、每1列中每个数字都恰好出现1次。 拉丁方存在性问题拉丁方存在性问题 2022年年5月月15日日43 2阶拉丁方是存在的阶拉丁方是存在的 12212022年年5月月15日日44n阶拉丁方阶拉丁方是存在的是存在的 构造方法如下：第1行为（1,2,3,n）第

18、2行为 ( 2,3,n,1)， 第k行为 ( k,k+1,n,1, ,k-1)， 第n行为（n, 1 , 2 , 3, , n-1）。 45 46最后满足要求的实验是要形成由1,2,3,4,5构成的55的方阵，其中每行每列中没有相同的数字，即5阶拉丁方的构造问题。472345134512451235123412345行（人）行（人） 列（天）列（天）例例 36军官问题军官问题将这将这36名军官排成名军官排成66方阵方阵, 使得使得 1)每行每列都有任一军团的军官每行每列都有任一军团的军官 2)每行每列都有任一军衔的军官每行每列都有任一军衔的军官.i :军衔军衔, j :军团军团, 军官对应数偶

19、军官对应数偶(i, j), i, j 1,6 问题等价于构造数偶问题等价于构造数偶(i,j)排成的排成的6阶方阵阶方阵, 使使得得 1) 数偶第一个数字构成拉丁方数偶第一个数字构成拉丁方; 2) 数偶第二个数字构成拉丁方数偶第二个数字构成拉丁方; 3) 每个数偶只出现一次每个数偶只出现一次.定义定义:设设A=(aij)nn,B=(bij)nn是两个是两个nn拉丁方拉丁方. 令令C=(aij, bij)nn,若若C的的n2对数偶互不相对数偶互不相同同, 则称则称A与与B正交正交. )2 , 1()1 , 3()3 , 2()1 , 2()3 , 1()2 , 3()3 , 3()2 , 2()1

20、 , 1(213132321132213321521.3 涂色问题涂色问题 在实际应用中，很多计数问题都可抽象成涂色问题。作为典型的组合计数问题，根据涂色问题难度的不同，将反映出各种不同的计数技术。四色问题53例例1.6 对正三角形的三个顶点涂以红、蓝（r和b）两种颜色，求有多少种不同的涂色方案？ 解解 由于只有两种颜色，我们可以采用枚举方法分类讨论。54 涂色方案可分成四类：涂色方案可分成四类：（1）三点全涂红色，只有一种方案 rrr（2）三点全涂蓝色，只有一种方案 bbb（3）两点涂红色，一点涂蓝色，因蓝色可分别涂于三个顶点之一，故有3种方案 brr，rbr，rrb（4）由对称性可知，两点

21、涂蓝色，一点染红的方案也有3种： 55红色, 蓝色56 如果考虑正三角形可以旋转，则(3),(4),(5)显然是同一个涂色方案，(6),(7),(8)也是同一个涂色方案，这样涂色方案数就变成了4种。 如果变成了空间的四面体了，即加上空间的旋转之后，涂色方法的计算将更加复杂。 要涂色的点和可选颜色的数目如再增加的话，枚举方法就不奏效了 需要特殊技巧解决问题需要特殊技巧解决问题例例 有有101名选手参加羽毛球比赛，如果采名选手参加羽毛球比赛，如果采用单循环淘汰制，问产生冠军需要进行多用单循环淘汰制，问产生冠军需要进行多少场比赛？少场比赛？ 方法一：方法一：50+25+13+6+3+2+1=100场

22、比赛 方法二：方法二：由于每场比赛都要产生一个失败者，而每个失败者只能失败一次，因此比赛的场数与失败者的人数相等，除冠军外其他100人都失败过，因此产生冠军需要100场比赛。例例 有一个边长为有一个边长为3的立方体木块，要把它切割成的立方体木块，要把它切割成27个边长为个边长为1的小立方体，如果在切割的过程中的小立方体，如果在切割的过程中可以重新排列被切割的木块，问至少需要多少次可以重新排列被切割的木块，问至少需要多少次才能完成任务？才能完成任务？解：解： 首先可以看到，通过首先可以看到，通过6 6次是可以完成整个切割的，次是可以完成整个切割的，上图就是这样的一种方案。其次，我们证明少于上图就

23、是这样的一种方案。其次，我们证明少于6 6次次是不能完成切割的。由于处于原立方体中心的一个是不能完成切割的。由于处于原立方体中心的一个小立方体的每个面都是由切割产生的，每次切割只小立方体的每个面都是由切割产生的，每次切割只能产生一个面，所以切割次数不能少于它的面数，能产生一个面，所以切割次数不能少于它的面数，因此至少因此至少6 6次才能完成切割。次才能完成切割。例例: :棋盘的完美覆盖棋盘的完美覆盖 Perfect Covers of Chessboardsmn棋盘棋盘: m行行n列方格列方格, b-牌牌:1行行b个的方格条个的方格条mn棋盘被棋盘被b-牌的一个牌的一个完美覆盖完美覆盖是是b-牌在棋盘上的一个排列牌在棋盘上的一个排列, 满足满足:(1) 每个格子恰好只被一张牌覆盖每个格子恰好只被一张牌覆盖;(2) 每条每条b-牌覆盖牌覆盖b个方格个方格.64=8*8, 2-牌的覆盖32 张多米诺牌12,988,816 = 24 X 172 X 5323 4棋盘有棋盘有2-牌的完美覆盖牌的完美覆盖.3 3棋盘有棋盘有2-牌的完美覆盖？牌的完美覆盖？64个格去掉对角上的两个方格，剩下62个格，存在完美覆盖吗?将棋盘上的方格交替涂成黑色和白色32个黑、30个白31张不重叠的多米诺要盖住31个白方格和31个黑方格 若完美=切过的棋盘必须有相同数目的黑白格。 二分图的匹