组合数学CH01.ppt

组合数学,2023年3月31日,2,参 考 教 材,组合数学，屈婉玲编。北京大学出版社，1989年11月。组合数学（第四版），卢开澄等。清华大学出版社，2006年12月。组合数学(英文版第5版)，(美)布鲁迪(Brualdi,R.A.)著。机械工业出版社，2009年3月。,2023年3月31日,3,第一章 引言,计算机算法,2023年3月31日,4,一、什么是组合数学 二、组合数学的主要内容 三、组合数学的几个例子 四、组合数学的学习方法,四色问题,对世界地图着色，每一个国家使用一种颜色，那么只需要四种颜色就能保证每两个相邻的国家的颜色不同,2023年3月31日,5,装箱问题,当你装一个箱子时，你会发现要使箱子尽可能装满不是一件很容易的事，你往往需要做些调整。从理论上讲，装箱问题是一个很难的组合数学问题，即使用计算机也是不容易解决的。,2023年3月31日,6,过河问题,一个船夫要把一只狼，一只羊和一棵白菜运过河。问题是当人不在场时，狼要吃羊，羊要吃白菜，而他的船每趟只能运其中的一个。他怎样才能把三者都运过河呢？,2023年3月31日,7,2023年3月31日,8,一个邮递员从邮局出发，再返回邮局，如果他必须走过他所管辖的每条街道至少一次，问如何选择路线，使得路程最短？,中国邮路问题,2023年3月31日,9,n阶幻方 把1，2，n2这n2个数字排成nn的方阵，并使得每一行、每一列、每一条对角线上的n个数字之和都相等，称这样的方阵为n阶幻方，又称为纵横图。,棋盘完美覆盖问题,2023年3月31日,10,2023年3月31日,11,组合数学简称 组合学,Combinatorics,组合数学是数学的一个分支,它起源于古代的娱乐和休闲。1666年莱布尼兹所著组合学论文一书问世，这是组合数学第一部专著。,一、什么是组合数学,2023年3月31日,12,组合数学是研究离散结构的存在、计数、分析和优化等问题的一门学科。组合数学是研究事物在给定模式下的配置，研究这种配置的存在性，所有可能配置的计数和分类，以及配置的各种性质。,2023年3月31日,13,二、组合数学的主要内容,(1)组合分析，基础，为后面的讨论作准备。主要研究存在性问题、组合计数问题、构造或枚举问题。(2)组合优化，讨论线性规划及整数规划问题。(3)组合设计，是将集合的元素分成满足某些所述性质的子集的排列方法。(4)组合算法，如：搜索法。动态规划。优先策略与分治策略。分类与查找，重点在于算法的分析。,2023年3月31日,14,本学期涉及到的内容：鸽巢原理和Ramsey定理（存在性问题）排列和组合二项式系数包含排斥原理递推关系生成函数Polya定理,组合计数问题,2023年3月31日,15,组合数学应用领域 1，计算机科学 2，管理科学 3，信息科学 4，电子工程 5，人工智能 6，生命科学,2023年3月31日,16,算法复杂性，算法的时间复杂性和空间复杂性分析,要用到组合数学的知识，组合计数。近代密码学，好的密码，对它的破译等价于某一NPC类困难问题，这样的密码是不可破的。编码理论，研究的是通信中如何纠错与检错。组合设计。图论，较成熟的组合数学的分支，已独立。主要应用于网络流理论，电路网络以及TSP。,2023年3月31日,17,(1)存在性问题对于模式要证明或否定它的存在,计数和分类问题 讨论对不同的方案进行计数，并对它们进行分类问题,2023年3月31日,18,(3)构造性问题 通过程序化的方法把相应的模式枚举或构造出来,(4)优化问题 寻找满足某种标准下“最好”或“最优”的一个模式,2023年3月31日,19,一个3阶方阵，其元素是1到9的正整数，每行、每列以及两条对角线的和都是15。杨辉称其为纵横图，在著详解九章算法（1261年）中曾研究三阶幻方，并给出它的构造方法还给出了4至10阶的幻方。,三、组合数学的几个例子,1.1 幻方问题,九子斜排，上下对易，左右相更，四维挺出，戴九履一，左三右七，二四为肩，六八为足,2023年3月31日,21,一个n阶幻方是由整数1，2，3，n2按下述方式组成的nn方阵：该方阵每行上的整数的和、每列上的整数的和以及两条对角线中每条对角线上的整数的和都等于同一个数s,2023年3月31日,22,3阶幻方的所有整数和为15；2阶幻方的所有整数和为5；,每一行（或列或对角线）数字的和称为幻方的和（幻和）：S=n(n2+1)/2。,2023年3月31日,23,关于幻方的问题归结为：（1）存在性问题 对任意的正整数n，n阶幻方存在吗？（2）组合计数问题 如果存在，那么应该有多少个不同的n阶幻方。（3）构造问题 怎样构造n阶幻方？,2023年3月31日,24,幻方的存在性问题 例1.1 证明不存在2阶幻方。对其余的正整数n，由于n阶幻方都能构造出来，当然就证明了（正整数）阶幻方的存在性。,2023年3月31日,25,例 1.1 证明不存在2阶幻方,证明：反证法。假定存在2阶幻方，如图所示：,根据幻方的定义，它的幻和是5，于是a1+a2=a1+a3=5，可得a2=a3，因为a1，a2，a3，a4必定彼此不同，所以不可能，矛盾。因此不存在2阶幻方。,2023年3月31日,26,幻方的构造性问题（1）奇数阶幻方的构造,连续摆放法（de la Loubre法）。规则为：假定构造n阶（n为奇数）幻方。首先将1放在(n+1)/2列第1行的方格中，然后按照副对角线方向（即行号减1，列号加1）依次把从小到大的各个数字放入相应的方格中。,2023年3月31日,27,如果行号变成0（第1行上面一行），则改成第n行相应列对应的方格。如果列号变成n+1（第n列右面一列），则改成第1列相应行对应的方格。如果轮到的方格已经填有数字或者到了第0行第n+1列对应的方格，则退到前一个方格正下方的方格。,2023年3月31日,28,例1.2 利用连续摆放法构造5阶幻方,2023年3月31日,29,（2）偶数阶幻方的构造 当n=4k的时候，即双偶数的情况，对称法。先把nn的方阵分成上、下、左、右四个2k2k的方阵。然后对于左上的2k2k方阵进行处理，每行每列任意取一半（k个）的方格做标记，如我们把这些方格涂成阴影。,2023年3月31日,30,然后按照对称轴将这种标记方式向下和向右作对称图形。经过处理后使得nn的方阵的每一行和每一列都有一半（n/2）的方格被涂成阴影。接下来，把从1开始的数字依次往方格里面填。第一遍：从第1行第1列的方格开始往右，不是阴影，则填数字，如果是阴影的方格，不填数字，但相应的数字加1。第1行填完后，是第2行第1列的方格，依次，最后是第n行第n列的方格。,2023年3月31日,31,这样填完之后，有一半的方格被填上了数字。第二遍，从第n行第n列的方格开始依次往左，规则同前，从1开始的数字依次往方格里面填。第n行结束之后，是第n-1行第n列的方格。依次，最后是第1行第1列的方格。最后就得到了幻方。,2023年3月31日,32,例1.3 利用对称法构造4阶幻方,2023年3月31日,33,当n=4k+2,所谓的单偶数的情况。首先把nn的方阵分成上、下、左、右四个(2k+1)(2k+1)的方阵,为了表达方便，依次把左上、右下、右上、左下的方阵编号为A,B,C,D。采用连续摆数法，把1(2k+1)2放在A中做成第一个幻方；把(2k+1)212(2k+1)2放在B中成第二个幻方。,2023年3月31日,34,把2(2k+1)213(2k+1)2放在C中成第三个幻方。把3(2k+1)214(2k+1)2放在D中成第四个幻方。然后，在A的各行从第1列开始向右取m个(m=(n-2)/4)方格，但中间一行（k+1行）从第2列开始。,把这些方格中的数字与D中相应位置的数字对换。在C中各行最后一列起向左各取m1个方格，把这些方格中的数字与B中相应位置的数字对换。最后，就得到了幻方。,35,2023年3月31日,2023年3月31日,36,例1.4 构造6阶幻方,2023年3月31日,37,2023年3月31日,38,幻方的计数问题,3阶幻方 基本形式只有一种 经过旋转和翻转可获得8种变形,4阶幻方 分类枚举 基本形式有880个 变形有7040个,5阶幻方 基本形式有275305224个,6阶及以上幻方 即使通过大型计算机的计算仍然难以获得精确的数字，目前只能估计出它的取值范围,39,2023年3月31日,1.2 拉丁方问题,2023年3月31日,40,n阶拉丁方定义为由数字1,2,n构成的nn的方阵，使得在每1行、每1列中每个数字都恰好出现1次。,拉丁方是另一类典型的组合数学问题,拉丁方存在性问题,2023年3月31日,41,2阶拉丁方是存在的,2023年3月31日,42,n阶拉丁方是存在的 构造方法如下：第1行为（1,2,3,n）第2行是(2,3,n,1)，第k行为(k,k+1,n,1,k-1)，第n行为（n,3,2,1）。,2023年3月31日,43,例1.5 设计一个药物临床试验以测试五种药物对人体的药效。这五种药物编号1,2,3,4,5。然后选取5个人，并给每人不同的药。为了消除个体对药物的反应偏差，要求在连续5天里进行测试，每人每天吃一种药物。而为了消除服药时间造成药效的偏差，要求2个人不能在同1 天吃相同的药。,2023年3月31日,44,最后满足要求的实验是要形成由1,2,3,4,5构成的55的方阵，其中每行每列中没有相同的数字，即5阶拉丁方的构造问题。,2023年3月31日,45,正交拉丁方,2023年3月31日,46,将两个n阶拉丁方重叠在一起时，所有t2个组合各出现一次，则称这两个拉丁方是相互正交的。,2023年3月31日,47,3阶正交拉丁方,并置方阵,2023年3月31日,48,36军官问题 有36名军官来自六个不同的军团，具有六种不同的军衔，而且每个团每种军衔的军官各有一名，能否把他们排成一个66方阵，使得对每一个军团与每一种军衔，在每一行或每一列都有一位军官来自这个团，也都有一位军官有此军衔？是由Euler首先提出的，实际上是组合设计中的6阶正交拉丁方问题,2023年3月31日,49,能否编成方阵，使得每行每列的军衔不重复，每行每列的军团不重复,问题简述为：,2023年3月31日,50,（1）一个有序对(i,j)表示一个军官,其中：i表示他的军衔类别(i=1,6),j表示他所在的军团(j=1,6),问题转化为：36个有序对(i,j)(i=1,2,6；j=1,2,6)能否排成一个66阵列，使得每行(或列)中，整数1,2,6以某种次序出现于有序对的第一位置；又以另一种次序（不一定相同）出现于有序对的第二位置。,2023年3月31日,51,（2）分裂成别两个66阵列，一个对应于有序对的第一个位置，即军衔方阵；另一个对应于有序对的第二个位置，即军团方阵,军衔方阵,军团方阵,2023年3月31日,52,问题转化为：是否存在阵列，满足：(1)整数1-6以某种次序出现在阵列的每行(或列)中;且(2)两个阵列并置时,所有36个有序对(i,j)都会出现。满足第一个条件的每个方阵称为拉丁方，满足第二个条件的两个拉丁方称为互相正交，即正交拉丁方.,2023年3月31日,53,上述是两个3阶正交拉丁方。36军官问题即是否存在6阶正交拉丁方。,9个军官问题,军衔方阵,军团方阵,并置方阵,2023年3月31日,54,1.3 涂色问题,在实际应用中，很多计数问题都可抽象成涂色问题。作为典型的组合计数问题，根据涂色问题难度的不同，将反映出各种不同的计数技术。,2023年3月31日,55,例1.6 对正三角形的三个顶点涂以红、蓝（r和b）两种颜色，求有多少种不同的涂色方案？,解 由于只有两种颜色，我们可以采用枚举方法分类讨论。,2023年3月31日,56,涂色方案可分成四类：,（1）三点全涂红色，只有一种方案 rrr（2）三点全涂红色，只有一种方案 bbb,（3）两点涂红色，一点涂蓝色，因蓝色可分别涂于三个顶点之一，故有3种方案 brr，rbr，rrb,（4）由对称性可知，两点涂蓝色，一点染红的方案也有3种：,2023年3月31日,57,红色,蓝色,2023年3月31日,58,如果考虑正三角形可以旋转，则(3),(4),(5)显然是同一个涂色方案，(6),(7),(8)也是同一个涂色方案，这样涂色方案数就变成了4种。如果变成了空间的四面体了，即加上空间的旋转之后，涂色方法的计算将更加复杂。要涂色的点和可选颜色的数目如再增加的话，枚举方法就不奏效了,一笔画问题,2023年3月31日,59,四、组合数学的学习方法,组合数学经常使用的方法并不高深复杂。最主要的方法是计数时的合理分类和组合模型的转换（一一对应）。要学好组合数学并非易事，既需要一定的数学修养，也要进行相当的训练。可从规模小的模型着手，从实际出发分析它，从中找到规律性的东西，再推及一般。你解决的问题越多，那么你能够解决下一个问题的可能性也越大。,2023年3月31日,60,解题方法一类是常规方法 从组合学基本概念、基本定理出发解题 鸽巢原理、相异代表系定理解存在性问题等等。利用容斥原理、二项式定理、Polya定理解计数问题；特征根方法、生成函数方法解递推关系式；这类方法通常比较容易掌握，将在以后各章里分别学到并学会它们，,2023年3月31日,61,另一类方法，通常与问题所涉及的组合学概念无关 1数学归纳法，2.反证法,3一一对应技术。把一个组合问题转化成另一个组合问题。4数论方法，特别是利用整数的奇偶性、整除性等效论性质进行分析推理的方法。5殊途同归方法，即从不同角度讨论计数问题以建立组合等式。,2023年3月31日,62,特殊技巧的例子：一一对应例1 有101名选手参加羽毛球比赛，如果采用单循环淘汰制，问产生冠军需要进行多少场比赛？,解2：因为每场比赛都要产生一个失败者，而每个失败者只能失败一次，所以比赛的场数与失败者的人数相等又因为冠军是唯一的胜利者，其它100个人都失败过，所以要比赛100场。,解1：50+25+13+6+3+2+1=100,2023年3月31日,63,例2 有一个边长为3的立方体木块，要把它切割成27个边长为1的小立方体，如果在切割的过程中可以重新排列被切割的木块，证明至少需要6次才能完成任务？,（分析）设具有最少切割次数的方案是最优，如果我们先列出所有可能的切割方案，然后从中由出最优的方案，这是相当麻烦的，我们采用另一种解法,2023年3月31日,64,解 首先可以看到6次是可以完成整个切割的左图就给出了这样的一种方案；其次，我们来证明少于6次是不能完成整个切割的因为在27个小立方体中有一个处在原来大立方体的中心，它的每一个面都是由切割而产生的又因为每切一次只能产生一个面，所以切割次数不能少于它的面数，因此至少要6次切割才能完成。,