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