组合数学ch01资料

《组合数学ch01资料》由会员分享，可在线阅读，更多相关《组合数学ch01资料（64页珍藏版）》请在金锄头文库上搜索。

1、组合数学,吉林大学 计算机科学与技术学院 2012年9月,2019年9月22日,2,参 考 教 材,组合数学，屈婉玲编。北京大学出版社，1989年11月。 组合数学（第四版），卢开澄等。清华大学出版社， 2006年12月。 组合数学(英文版第5版) ，(美)布鲁迪(Brualdi,R.A.)著。机械工业出版社，2009年3月。,2019年9月22日,3,第一章 引言,计算机算法,2019年9月22日,4,一、什么是组合数学 二、组合数学的主要内容 三、组合数学的几个例子 四、组合数学的学习方法,四色问题,对世界地图着色，每一个国家使用一种颜色，那么只需要四种颜色就能保证每两个相邻的国家的颜色不

2、同,2019年9月22日,5,装箱问题,当你装一个箱子时，你会发现要使箱子尽可能装满不是一件很容易的事，你往往需要做些调整。从理论上讲，装箱问题是一个很难的组合数学问题，即使用计算机也是不容易解决的。,2019年9月22日,6,过河问题,一个船夫要把一只狼，一只羊和一棵白菜运过河。问题是当人不在场时，狼要吃羊，羊要吃白菜，而他的船每趟只能运其中的一个。他怎样才能把三者都运过河呢？,2019年9月22日,7,2019年9月22日,8,一个邮递员从邮局出发 ，再返回邮局，如果他必须走过他所管辖的每条街道至少一次，问如何选择路线，使得路程最短？,中国邮路问题,2019年9月22日,9,n阶幻方 把1

3、，2，n2这n2个数字排成nn的方阵，并使得每一行、每一列、每一条对角线上的n个数字之和都相等，称这样的方阵为n阶幻方，又称为纵横图。,棋盘完美覆盖问题,2019年9月22日,10,2019年9月22日,11,组合数学简称 组合学, Combinatorics,组合数学是数学的一个分支, 它起源于古代的娱乐和休闲。 1666年莱布尼兹所著组合学论文一书问世，这是组合数学第一部专著。,一、什么是组合数学,2019年9月22日,12,组合数学是研究离散结构的存在、计数、分析和优化等问题的一门学科。 组合数学是研究事物在给定模式下的配置，研究这种配置的存在性，所有可能配置的计数和分类，以及配置的各种

4、性质。,2019年9月22日,13,二、组合数学的主要内容,(1)组合分析，基础，为后面的讨论作准备。主要研究存在性问题、组合计数问题、构造或枚举问题。 (2)组合优化，讨论线性规划及整数规划问题。 (3)组合设计， 是将集合的元素分成满足某些所述性质的子集的排列方法。 (4)组合算法，如：搜索法。动态规划。优先策略与分治策略。分类与查找，重点在于算法的分析。,2019年9月22日,14,本学期涉及到的内容： 鸽巢原理和Ramsey定理（存在性问题） 排列和组合 二项式系数 包含排斥原理 递推关系 生成函数 Polya定理,组合计数问题,2019年9月22日,15,组合数学应用领域 1，计算机

5、科学 2，管理科学 3，信息科学 4，电子工程 5，人工智能 6，生命科学,2019年9月22日,16,算法复杂性，算法的时间复杂性和空间复杂性分析, 要用到组合数学的知识，组合计数。 近代密码学，好的密码，对它的破译等价于某一NPC类困难问题，这样的密码是不可破的。 编码理论，研究的是通信中如何纠错与检错。组合设计。 图论，较成熟的组合数学的分支，已独立。 主要应用于网络流理论，电路网络以及TSP。,2019年9月22日,17,(1) 存在性问题 对于模式要证明或否定它的存在,计数和分类问题 讨论对不同的方案进行计数，并对它们进行分类问题,2019年9月22日,18,(3) 构造性问题 通过

6、程序化的方法把相应的模式枚举或构造出来,(4) 优化问题 寻找满足某种标准下“最好”或“最优”的一个模式,2019年9月22日,19,一个3阶方阵，其元素是1到9的正整数，每行、每列以及两条对角线的和都是15。 杨辉称其为纵横图，在著详解九章算法（1261年）中曾研究三阶幻方，并给出它的构造方法还给出了4至10阶的幻方。,三、组合数学的几个例子,1.1 幻方问题,九子斜排，上下对易， 左右相更，四维挺出， 戴九履一，左三右七， 二四为肩，六八为足,2019年9月22日,21,一个n阶幻方是由整数1，2，3，n2按下述方式组成的nn方阵：该方阵每行上的整数的和、每列上的整数的和以及两条对角线中每

7、条对角线上的整数的和都等于同一个数s,2019年9月22日,22,3阶幻方的所有整数和为15； 2阶幻方的所有整数和为5；,每一行（或列或对角线）数字的和称为幻方的和（幻和）： S= n (n2+1)/2 。,2019年9月22日,23,关于幻方的问题归结为： （1）存在性问题 对任意的正整数n，n阶幻方存在吗？ （2）组合计数问题 如果存在，那么应该有多少个不同的n阶幻方。 （3）构造问题 怎样构造n阶幻方？,2019年9月22日,24,幻方的存在性问题 例1.1 证明不存在2阶幻方。 对其余的正整数n，由于n阶幻方都能构造出来，当然就证明了（正整数）阶幻方的存在性。,2019年9月22日,

8、25,例 1.1 证明不存在2阶幻方,证明：反证法。假定存在2阶幻方，如图所示：,根据幻方的定义，它的幻和是5，于是a1+ a2= a1+ a3=5，可得a2= a3，因为a1，a2，a3， a4必定彼此不同，所以不可能，矛盾。因此不存在2阶幻方。,2019年9月22日,26,幻方的构造性问题 （1）奇数阶幻方的构造,连续摆放法（de la Loubre法）。 规则为：假定构造n阶（n为奇数）幻方。 首先将1放在 (n+1)/2列第1行的方格中， 然后按照副对角线方向（即行号减1，列号加1）依次把从小到大的各个数字放入相应的方格中。,2019年9月22日,27,如果行号变成0（第1行上面一行）

9、，则改成第n行相应列对应的方格。 如果列号变成n+1（第n列右面一列），则改成第1列相应行对应的方格。 如果轮到的方格已经填有数字或者到了第0行第n+1列对应的方格，则退到前一个方格正下方的方格。,2019年9月22日,28,例1.2 利用连续摆放法构造5阶幻方,2019年9月22日,29,（2）偶数阶幻方的构造 当n=4k的时候，即双偶数的情况， 对称法。 先把nn的方阵分成上、下、左、右四个2k2k的方阵。 然后对于左上的2k2k方阵进行处理，每行每列任意取一半（k个）的方格做标记，如我们把这些方格涂成阴影。,2019年9月22日,30,然后按照对称轴将这种标记方式向下和向右作对称图形。经

10、过处理后使得nn的方阵的每一行和每一列都有一半（n/2）的方格被涂成阴影。 接下来，把从1开始的数字依次往方格里面填。第一遍：从第1行第1列的方格开始往右，不是阴影，则填数字，如果是阴影的方格，不填数字，但相应的数字加1。第1行填完后，是第2行第1列的方格，依次，最后是第n行第n列的方格。,2019年9月22日,31,这样填完之后，有一半的方格被填上了数字。 第二遍，从第n行第n列的方格开始依次往左，规则同前，从1开始的数字依次往方格里面填。第n行结束之后，是第n-1行第n列的方格。依次，最后是第1行第1列的方格。 最后就得到了幻方。,2019年9月22日,32,例1.3 利用对称法构造4阶幻

11、方,2019年9月22日,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中成第二个幻方。,2019年9月22日,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列开始。,把这些方格中的数字与

12、D中相应位置的数字对换。 在C中各行最后一列起向左各取m1个方格，把这些方格中的数字与B中相应位置的数字对换。最后，就得到了幻方。,35,2019年9月22日,2019年9月22日,36,例1.4 构造6阶幻方,2019年9月22日,37,2019年9月22日,38,幻方的计数问题,3阶幻方 基本形式只有一种 经过旋转和翻转可获得8种变形,4阶幻方 分类枚举 基本形式有880个 变形有7040个,5阶幻方 基本形式有275305224个,6阶及以上幻方 即使通过大型计算机的计算仍然难以获得精确的数字，目前只能估计出它的取值范围,39,2019年9月22日,1.2 拉丁方问题,2019年9月22

13、日,40,n阶拉丁方定义为由数字1,2,n构成的nn的方阵，使得在每1行、每1列中每个数字都恰好出现1次。,拉丁方是另一类典型的组合数学问题,拉丁方存在性问题,2019年9月22日,41,2阶拉丁方是存在的,2019年9月22日,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）。,2019年9月22日,43,例1.5 设计一个药物临床试验以测试五种药物对人体的药效。这五种药物编号1,2,3,4,5。然后选取5个人，并给每人不同的药。为了消除个体对药物的反应偏差，要求在

14、连续5天里进行测试，每人每天吃一种药物。而为了消除服药时间造成药效的偏差，要求2个人不能在同1 天吃相同的药。,2019年9月22日,44,最后满足要求的实验是要形成由1,2,3,4,5构成的55的方阵，其中每行每列中没有相同的数字，即5阶拉丁方的构造问题。,2019年9月22日,45,正交拉丁方,2019年9月22日,46,将两个n阶拉丁方重叠在一起时，所有t2个组合各出现一次，则称这两个拉丁方是相互正交的。,2019年9月22日,47,3阶正交拉丁方,并置方阵,2019年9月22日,48,36军官问题 有36名军官来自六个不同的军团，具有六种不同的军衔，而且每个团每种军衔的军官各有一名，能

15、否把他们排成一个66方阵，使得对每一个军团与每一种军衔，在每一行或每一列都有一位军官来自这个团，也都有一位军官有此军衔？ 是由Euler首先提出的，实际上是组合设计中的6阶正交拉丁方问题,2019年9月22日,49,能否编成方阵，使得每行每列的军衔不重复，每行每列的军团不重复,问题简述为：,2019年9月22日,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以某种次序出现于有序对

16、的第一位置；又以另一种次序（不一定相同）出现于有序对的第二位置。,2019年9月22日,51,（2）分裂成别两个66阵列，一个对应于有序对的第一个位置，即军衔方阵；另一个对应于有序对的第二个位置，即军团方阵,军衔方阵,军团方阵,2019年9月22日,52,问题转化为： 是否存在阵列，满足： (1) 整数1-6以某种次序出现在阵列的每行(或列)中; 且(2) 两个阵列并置时, 所有36个有序对(i,j) 都会出现。 满足第一个条件的每个方阵称为拉丁方，满足第二个条件的两个拉丁方称为互相正交，即正交拉丁方.,2019年9月22日,53,上述是两个3阶正交拉丁方。 36军官问题即是否存在6阶正交拉丁方。,9个军官问题,军衔方阵,军团方阵,并置方阵,2019年9月22日,54,1.3 涂色问题,在实际应用中，很多计数问题都可抽象成涂色问题。 作为典型的组合计数问题，根据涂色问题难度的不同，将反映出各种不同的计