组合数学CH01.ppt

《组合数学CH01.ppt》由会员分享，可在线阅读，更多相关《组合数学CH01.ppt（64页珍藏版）》请在优知文库上搜索。

1、组合数学组合数学2023年3月7日2参参 考考 教教 材材组合数学，屈婉玲编。北京大学出版组合数学，屈婉玲编。北京大学出版社，社，1989年年11月。月。组合数学（第四版），卢开澄等。清组合数学（第四版），卢开澄等。清华大学出版社，华大学出版社， 2006年年12月。月。组合数学组合数学(英文版英文版第第5版版) ，(美美)布鲁迪布鲁迪(Brualdi,R.A.)著。机械工业出版社，著。机械工业出版社，2009年年3月。月。2023年3月7日3第一章第一章 引言引言计算机算法计算机算法数值计算数值计算如如： 解方程组，解方程组， 求积分等求积分等非数值计算非数值计算 如：如：搜索，排序，搜索，

2、排序， 组合优化等组合优化等高等数学高等数学组合数学组合数学2023年3月7日4 一、什么是组合数学一、什么是组合数学 二、组合数学的主要内容二、组合数学的主要内容 三、组合数学的几个例子三、组合数学的几个例子 四、组合数学的学习方法四、组合数学的学习方法四色问题四色问题对世界地图对世界地图着色着色，每一个国家使每一个国家使用一种颜色，那么用一种颜色，那么只需要四种颜只需要四种颜色就能保证每两个相邻的国家的色就能保证每两个相邻的国家的颜色不同颜色不同2023年3月7日5装箱问题装箱问题当你装一个箱子时，你会发现要使当你装一个箱子时，你会发现要使箱子尽可能装满不是一件很容易的箱子尽可能装满不是一

3、件很容易的事，你往往需要做些调整。从理论事，你往往需要做些调整。从理论上讲，装箱问题是一个很难的组合上讲，装箱问题是一个很难的组合数学问题，即使用计算机也是不容数学问题，即使用计算机也是不容易解决的。易解决的。 2023年3月7日6过河问题过河问题一个船夫要把一只狼，一只羊和一一个船夫要把一只狼，一只羊和一棵白菜运过河。问题是当人不在棵白菜运过河。问题是当人不在场时，狼要吃羊，羊要吃白菜，场时，狼要吃羊，羊要吃白菜，而他的船每趟只能运其中的一个。而他的船每趟只能运其中的一个。他怎样才能把三者都运过河呢？他怎样才能把三者都运过河呢？2023年3月7日72023年3月7日8一个邮递员从邮局出发一个

4、邮递员从邮局出发 ，再返回邮局，再返回邮局，如果他必须走过他所管辖的每条街道至如果他必须走过他所管辖的每条街道至少一次，问如何选择路线，使得路程最少一次，问如何选择路线，使得路程最短？短？中国邮路问题中国邮路问题2023年3月7日9 n阶幻方阶幻方 把把1，2，n2这这n2个数字排个数字排成成nn的方阵，并使得每一行、的方阵，并使得每一行、每一列、每一条对角线上的每一列、每一条对角线上的n个数字之和都相等，称这样的个数字之和都相等，称这样的方阵为方阵为n阶幻方阶幻方，又称为，又称为纵横纵横图图。棋盘完美覆盖问题2023年3月7日102023年3月7日11Combinatorics 1666年年

5、莱布尼兹莱布尼兹所著所著组合学论文组合学论文一书问世，这是组合数学第一部专著。一书问世，这是组合数学第一部专著。一、什么是组合数学一、什么是组合数学2023年3月7日12 组合数学是研究事物在给定模式下的配置，研究这种配置的存在性，所有可能配置的计数和分类，以及配置的各种性质。2023年3月7日13二、组合数学的主要内容 (1)组合分析组合分析，基础，为后面的讨论作准备。主要研究存在性问题、组合计数问题、构造或枚举问题。(2)组合优化组合优化，讨论线性规划及整数规划问题。(3)组合设计组合设计， 是将集合的元素分成满足某些所述性质的子集的排列方法。 (4)组合算法组合算法，如：搜索法。动态规划

6、。优先策略与分治策略。分类与查找，重点在于算法的分析。2023年3月7日14本学期涉及到的内容：鸽巢原理和鸽巢原理和Ramsey定理（存在性问题）定理（存在性问题）排列和组合排列和组合二项式系数二项式系数包含排斥原理包含排斥原理递推关系递推关系生成函数生成函数Polya定理定理组合计数问题组合计数问题2023年3月7日15 组合数学应用领域组合数学应用领域 1，计算机科学，计算机科学 2，管理科学，管理科学 3，信息科学，信息科学 4，电子工程，电子工程 5，人工智能，人工智能 6，生命科学，生命科学2023年3月7日162023年3月7日17 (1) 存在性问题存在性问题对于模式要证明或否定

7、它的存在(2)计数和分类问题计数和分类问题 讨论对不同的方案进行计数，并对它们进行分类问题2023年3月7日18(3) 构造性问题构造性问题 通过程序化的方法把相应的模式枚举或构造出来(4) 优化问题优化问题 寻找满足某种标准下寻找满足某种标准下“最好最好”或或“最优最优”的一个模式的一个模式 2023年3月7日19 一个一个3阶方阵，其元阶方阵，其元素是素是1到到9的正整数，每的正整数，每行、每列以及两条对角行、每列以及两条对角线的和都是线的和都是15。 杨辉称称其为纵横图，在其为纵横图，在著详解九章算法（1261年）中曾研究三阶幻方，并给出它的构造方法还给出了还给出了4 4至至1010阶的

8、幻方。阶的幻方。519372486三、组合数学的几个例子三、组合数学的几个例子l1.1 幻方问题幻方问题123564789927564381927564381927564381九子斜排，上下对易，九子斜排，上下对易，左右相更，四维挺出，左右相更，四维挺出，戴九履一，左三右七，戴九履一，左三右七，二四为肩，六八为足二四为肩，六八为足2023年3月7日21一个n阶幻方阶幻方是由整数1，2，3，n2按下述方式组成的nn方阵：该方阵每行上的整数的和、每列上的整数的和以及两条对角线中每条对角线上的整数的和都等于同一个数s 2023年3月7日22 3阶幻方的所有整数和为阶幻方的所有整数和为15； 2阶幻方

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

10、其余的正整数n，由于n阶幻方都能构造出来，当然就证明了（正整数）阶幻方的存在性。 2023年3月7日25例例 1.1 证明不存在证明不存在2阶幻方阶幻方证明：证明：反证法。假定存在2阶幻方，如图所示：a1a2a3a4根据幻方的定义，它的幻和是5，于是a1+ a2= a1+ a3=5，可得a2= a3，因为a1，a2，a3， a4必定彼此不同，所以不可能，矛盾。因此不存在2阶幻方。 2023年3月7日26 幻方的构造性问题幻方的构造性问题（1）奇数阶幻方的构造）奇数阶幻方的构造连续摆放法（连续摆放法（de la Loubre法）。法）。规则为：规则为：假定构造假定构造n阶（阶（n为奇数）幻方为奇

11、数）幻方。首先首先将将1放在放在 (n+1)/2列第列第1行的方格中，行的方格中，然后然后按照副对角线方向（即行号减按照副对角线方向（即行号减1，列，列号加号加1）依次把从小到大的各个数字放入）依次把从小到大的各个数字放入相应的方格中。相应的方格中。2023年3月7日27如果行号变成如果行号变成0（第（第1行上面一行），则行上面一行），则改成第改成第n行相应列对应的方格。行相应列对应的方格。如果列号变成如果列号变成n+1（第（第n列右面一列），列右面一列），则改成第则改成第1列相应行对应的方格。列相应行对应的方格。如果轮到的方格已经填有数字或者到了如果轮到的方格已经填有数字或者到了第第0行第行

12、第n+1列对应的方格，则退到前一列对应的方格，则退到前一个方格正下方的方格。个方格正下方的方格。 2023年3月7日28例例1.2 利用连续摆放法构造5阶幻方 172418152357141646132022101219213111825292023年3月7日292023年3月7日302023年3月7日312023年3月7日32 21431581259211714310615138121165942023年3月7日332023年3月7日34352023年3月7日2023年3月7日36 1928326723334262122171219232710143353036 29 13 18312425

13、201516112023年3月7日37132928567233342621221712192327101435331383036 29 13 1842425201516112023年3月7日38 幻方的计数问题幻方的计数问题 3阶幻方阶幻方 基本形式只有一种 经过旋转和翻转可获得8种变形 4阶幻方阶幻方 分类枚举 基本形式有880个 变形有7040个 5阶幻方阶幻方 基本形式有275305224个 6阶及以上幻方阶及以上幻方 即使通过大型计算机的计算仍然难以获得精确的数字，目前只能估计出它的取值范围392023年3月7日1.2 拉丁方问题拉丁方问题2023年3月7日40 n阶拉丁方阶拉丁方定义

14、为由数字1,2,n构成的nn的方阵，使得在每1行、每1列中每个数字都恰好出现1次。 拉丁方拉丁方是另一类典型的组合数学问题是另一类典型的组合数学问题 拉丁方存在性问题拉丁方存在性问题 2023年3月7日41 2阶拉丁方是存在的阶拉丁方是存在的 12212023年3月7日42n阶拉丁方阶拉丁方是存在的是存在的 构造方法如下：第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月7日43 2023年3月7日44最后满足要求的实验是要形成由1,2,3,4,5构成的55的方阵，其中每行每列中没有相同的数字，即5

15、阶拉丁方的构造问题。2023年3月7日452345134512451235123412345 正交拉丁方正交拉丁方2023年3月7日46 将两个将两个n阶拉丁方重叠在一起时，阶拉丁方重叠在一起时，所有所有t2个组合各出现一次，则称个组合各出现一次，则称这两这两个拉丁方是相互正交的个拉丁方是相互正交的。2023年3月7日47)2 , 1 () 1 , 3()3 , 2() 1 , 2()3 , 1 ()2 , 3()3 , 3()2 , 2() 1 , 1 (2131323211322133212023年3月7日48 36军官问题军官问题2023年3月7日496个军团6种军衔36名军官能否能否编

16、成方阵，使得每行每列的军衔不重复，每行每列的军团不重复2023年3月7日502023年3月7日51)2 , 1 () 1 , 3()3 , 2() 1 , 2()3 , 1 ()2 , 3()3 , 3()2 , 2() 1 , 1 (2131323211322133212023年3月7日522023年3月7日53 )2 , 1()1 , 3()3 , 2()1 , 2()3 , 1()2 , 3()3 , 3()2 , 2()1 , 1(2131323211322133212023年3月7日541.3 涂色问题涂色问题 在实际应用中，很多计数问题都可抽象成涂色问题。作为典型的组合计数问题，根据涂色问题难度的不同，将反映出各种不同的计数技术。2023年3月7日55例例1.6 对正三角形的三个顶点涂以红、蓝（r和b）两种颜色，求有多少种不同的涂色方案？ 解解 由于只有两种颜色，我们可以采用枚举方法分类讨论。2023年3月7日56 涂色方案可分成四类：涂色方案可分成四类：（1）三点全涂红色，只有一种方案 rrr（2）三点全涂红色，只有一种方案 bbb（3）两点涂红色，一点涂蓝色，因蓝色可分