《组合数学0章引言.ppt》由会员分享，可在线阅读，更多相关《组合数学0章引言.ppt（36页珍藏版）》请在三一文库上搜索。
1、组合数学,(Combinatorial Mathematics),http:/ 卢开澄、卢华明编著,组合数学(第4版),清华大学出版社。 参考书： 殷剑宏.组合数学.北京:机械工业出版社,2006. (荷)范林特(vanLint, J.H.)，(美)威尔森(R.M.Wilon)著，刘振宏，赵振江译.组合数学教程.北京:机械工业出版社,2007. 屈婉玲.组合数学.北京:北京大学出版社,2002. 作业：每周交一次。 成绩考评： 平时(课堂参与、作业)20%，期末80%； 平时(课堂参与、作业)10%，期中30%，期末60%。,引言(Introduction),组合数学是一个古老而又年轻的数学分
2、支，起源于古老的数学娱乐和游戏。 相传，公元前2100年的大禹时代，人们发现了洛水神龟背上的神奇图案-洛书。,洛书,河图,引言(Introduction),河图 黄河中跃出一匹神马，马背上驮着一幅图，人称“河图” 。,幻方起源,洛书 洛水河中浮出一只神龟，龟背上有一张象征吉祥的图案，称为“洛书”。,幻方(Magic Square)：每一行每一列和每一对角线相加起来的数值都是相同的。,引言(Introduction),幻方最早记载于我国公元前500年的春秋时期大戴礼中。而在国外，公元130年，希腊人塞翁才第一次提起幻方。 在欧洲，直到1514年，德国著名画家丢勒才绘制出了完整的4阶幻方，而且将年
3、号也嵌进去了。 印度太苏神庙石碑上的幻方刻于十一世纪，有85组四数和为34的组合，而且将幻方边上的行或列挪到另一边去，所得的仍是幻方。,引言(Introduction),下图是1956年冬在我国陕西元代安西王府旧址发掘出的铁板面样。据考证，可能是“西域人”扎马鲁丁带来的。,引言(Introduction),下图为欧洲某博览会大厅的地砖上的数字，这里任一55的正方形都构成一个五阶幻方 。,引言(Introduction),数学上已经证明，对于n2，n阶幻方都存在。 幻方类型,引言(Introduction),三阶幻方,九子斜排，上下对易，左右相更，四维挺出，载九履一，左三右七，二四为肩，六八为足
4、。,引言(Introduction),奇阶幻方,1,2,3,4,5,6,7,8,9,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,方法 把1(或最小的数)放在第一行正中；按以下规律排列剩下的nn-1个数： (1)每一个数放在前一个数的右上一格； (2)如果这个数所要放的格已经超出了顶行那么就把它放在底行，仍然要放在右一列； (3)如果这个数所要放的格已经超出了最右列那么就把它放在最左列，仍然要放在上一行； (4)如果这个数所要放的格已经超出了顶行且超出了最右列，那么就把它放在前一个数的下一行同一列的格内； (
5、5)如果这个数所要放的格已经有数填入，处理方法同(4)。 这种写法总是先向“右上”的方向，象是在爬楼梯。,引言(Introduction),双偶阶幻方,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,引言(Introduction),双偶阶幻方,Spring方法：顺序填数，以中心点对称互换数字。,法一：第一步，顺序填数；第二步，以中心点对称互换数字； 对称互换的方法有两种： 方法一；将左上区域i+j（i行、j列）为偶数的与幻方内以中心点为对称点的右下角对角数字进行交换；将右上区域i+j为奇数的与幻方内以中心点为对称点的左下角对角数字进行交换。（保证不同时为奇或偶即
6、可。）,法二；将幻方等分成mm个4阶幻方，将各4阶幻方中对角线上（或非对角线上）的方格内数字与n阶幻方内以中心点为对称点的对角数字进行交换。,引言(Introduction),双偶阶幻方,A,B,引言(Introduction),双偶阶幻方,Strachey法生成双偶幻方: 第一步，将n阶双偶幻方表示为4m阶幻方。将其等分为四分，成为如下图所示A、B、C、D四个2m阶偶数幻方。 第二步， A用1至(2m)2填写成2m阶幻方；B用(2m)2+1至2*(2m)2填写成2m阶幻方；C用2*(2m)2+1至3*(2m)2填写成2m阶幻方；D用3*(2m)2+1至4*(2m)2填写成2m阶幻方；将8阶双
7、偶幻方表示为42阶幻方。将其等分为四个22阶偶数幻方，即4阶偶数幻方。 第三步，在A每行取m个小格（一侧对角线格为必换格，其余m-1格只要不是另一侧对角线格即可），将其与D相应方格内交换；B与C以相同方法进行。 对于8阶幻方，A每行取2个小格（一侧对角线格为必换格，其余1格只要不是另一侧对角线格即可），要与D相应方格内交换；C与B以相同方法进行。最简单的方法就是：A任意2列，与D相对应的2列互换，C任意2列，与B相对应的2列互换即可。,引言(Introduction),双偶阶幻方,A,B,C,D,引言(Introduction),单偶阶幻方,Strachey法：将n阶单偶幻方表示为4m+2阶幻
8、方。将其等分为四份，成为如下图所示A、B、C、D四个2m+1阶奇数幻方。 A C D B A用1至(2m+1)2填写成2m+1阶幻方；B用(2m+1)2+1至2*(2m+1)2填写成2m+1阶幻方；C用2*(2m+1)2+1至3*(2m+1)2填写成2m+1阶幻方；D用3*(2m+1)2+1至4*(2m+1)2填写成2m+1阶幻方； 在A每行取m个小格（中心格及一侧对角线格为必换格，其余m-1格只要不是另一侧对角线格即可），也就是说在A中间一行取包括中心格在内的m个小格，其他行左侧边缘取m个小格，将其与D相应方格内交换；B与C任取m-1列相互交换。 6阶幻方就是4*1+2，那么m就是1。在A中
9、间一行取中心格1个小格，其他行左侧边缘取1个小格，将其与D相应方格内交换；B与C接近右侧m-1列相互交换（6阶幻方m-1=0，则不用互换）。,引言(Introduction),单偶阶幻方,A,B,C,D,http:/ 幻方中最为奥妙，最为壮观的大约要数“双料幻方”，它有8行8列，不仅每行每列及对角线的和为定数840，而且每行每列及对角线的积也为定数，等于2058068231856000.,引言(Introduction),平方幻方 平方幻方就是把幻方里的每一个数平方后所组成的幻方，如果本身是幻方，每个数平方后也是幻方，那就是“双重平方幻方”了。,引言(Introduction),完全幻方（4阶
10、） 任一2*2的正方形，四数加起来都是34。 任一3*3的正方形，四个角上的数字加起来也刚好等于34。 只要用任何一点用象飞(斜上两格)的方式，那两个数加起来正好是34的一半17。 幻方四角数之和和幻方中任一2*4的矩形的四角上的数，加起来也是34。 如果把这个幻方横裁或直裁，在做上下交换或左右交换，都可以符合以上性质。,引言(Introduction),马步幻方 神奇的欧拉幻方他的特点是可以用象棋马步走完全部，又叫“马步幻方” 。,引言(Introduction),反幻方 幻方专家马丁加德纳博士找到了反幻方。,引言(Introduction),圆形幻方 幻方冲破方阵限制至少可追溯到700年前
11、，公元1275年出版的我国古代著作续古摘奇算法中就有“攒九图”(杨辉)。,这个由三十三个数组成的幻方，每条直径和每个圆周上的数加起来都是一样的。,引言(Introduction),六角形幻方 龟文聚六图，是中国清朝一个平民张潮制作出来的，图中的二十四个数使出了四十个数的力量，使每个六角形上的六个数加起来都等于75。,引言(Introduction),六角形幻方,引言(Introduction),原方阵,90度,180度,270度,铅直翻转,水平翻转,左下右上,左上右下,引言(Introduction),幻方个数,引言(Introduction),立体幻方 它的每一行，每一列，和每一对角线的数加
12、起来都是一样的，就连立体的斜线的和都是一样的。,引言(Introduction),特征线图、幻直线 日本人阿部乐方:凡是幻方中的两个格子里的数，加起来都是半和（意思是指幻和的一半，幻和就是指幻方每一条线上面所有数的和）17，把每一对连成一条线，当每一条线都连完后，就会出现了很美妙的对半模式，称为:特征线图。,引言(Introduction),有一些幻方，你只要从1连到2，2连到3，一直连到最后一个数，就会发现幻方变成了一个非常丽的图案，称：幻直线 。,引言(Introduction),1666年莱布尼兹所著组合学论文一书问世，这是组合数学的第一部专著。书中首次使用了组合论（Combinator
13、ics）一词。 组合数学的蓬勃发展则是在计算机问世和普遍应用之后。由于组合数学涉及面广，内容庞杂，并且仍在很快地发展着，因而还没有一个统一而有效的理论体系。这与数学分析形成了对照。 组合数学研究的中心问题是按一定规则将一些事物安排成各式各样模式的问题。包括安排的存在问题、计数问题、构造问题以及给出了优化标准后如何求出最优安排问题。,引言(Introduction),例1 在100名选手之间进行单循环淘汰赛（即一场比赛后，失败者退出比赛），最后产生一名冠军，需举行多少场比赛？ 99场。 例2 有一个边长为3的立方体木块，要把它切割成27个边长为1的小立方体。如果在切割过程中可以重新排列被切割木块的位置，问至少需要多少次才能完成整个切割？ 6次。,引言(Introduction),组合分析是组合算法的基础。组合数学有着极其广泛的应用,大致可以包含以下几个方面的内容,引言(Introduction),作业： 1.在下图的九个空格内,填入不大于12且互不相等的九个自然数,使每一横行,竖行,对角线上的3个数之和都等于21. 2.将18中的 8个自然数填入上图方格内,构成一个不完整的三阶幻方,使得每行,每列,对角线上的数的和都相等(不完整幻方就是指幻方中有一个空格不填数) . 3.作出10阶幻方。,Thank You !,http:/