第一周-漫谈组合数学

1组合数学Combinatorics1漫谈组合数学1-0什么是组合数学？清华大学马昱春3离散数学(目录)离散数学（第五版）作者：耿素云，张立昂编著第1章命题逻辑第2章一阶逻辑第3章集合的基本概念和运算第4章二元关系和函数第5章图的基本概念第6章特殊的图第7章树第8章组合分析初步8.1加法法则和乘法法则8.2基本排列组合的计数方法8.3递推方程的求解与应用8.4题例分析第9章代数系统简介第10章形式语言和自动机初步本课程内容大纲第一部分排列与组合第二部分递推关系与母函数第三部分容斥原理第四部分鸽巢原理第五部分Burnside引理与Polya定理组合数学:有人认为广义的组合数学就是离散数学，也有人认为离散数学是狭义的组合数学和图论、代数结构、数理逻辑等的总称。但这只是不同学者在叫法上的区别。总之，组合数学是一门研究离散对象计数的科学。数学发展史数学起源于计数奇普，印加帝国时所使用的计数工具。算术初等代数几何学16世纪初等数学高等数学线性代数概率学分析数学17世纪出现变量WilhelmLeibniz(1646-1716)LeonhardEuler(1707-1783)FriedrichGauss(1777-1855)数学发展史数学起源于计数奇普，印加帝国时所使用的计数工具。算术初等代数几何学16世纪初等数学高等数学线性代数概率学分析数学17世纪出现变量拓扑学抽象代数现代数学群论集合论数论组合数学…幼儿园小学，中学大学研究生组合数学•组合数学研究的是事物按照某种规则的安排，主要有：存在性问题、计数性问题和对已知安排的研究——RichardA.Brualdi所著《IntroductoryCombinatorics》•研究离散结构的存在、计数、分析和优化等问题的一门学科——高洁《浅谈组合数学的应用与教学》67组合数学中的三大问题•存在（existenceproblem）–是否存在合理的解？•计数（countingproblem）–有多少种解的可能？•优化（optimizationproblem）–依照某种标准，所有解中那个是最优的？8组合数学Combinatorics1-1组合数学的渊源1-1-a最精巧的排列----幻方清华大学马昱春9组合数学的历史组合数学是一个古老而又年轻的数学分支。据传说，大禹在4000多年前(2200B.C.)就观察到神龟背上的幻方…...Amagicsquare:asquarearrayofnumbersinwhichthesumofallrows,allcolumnsandbothdiagonalsisthesame.大禹(2205BC-2105BC)492357816南宋数学家杨辉(1238-1298)永乐大典中一页《续古摘奇算法》纵横图：洛书，河图，四四图，五五图，六六图，六十四图，九九图，百子图，聚五图，聚六图，聚八图，攒九图，八阵图，连环图。幻方的神秘力量11AlbrechtDürer《忧伤》（1514年）幻方蕴含着宇宙的法则12例:幻方•一个n阶幻方是由整数1,2,3….n2按下述方式组成的n×n方阵：该方阵每行上的整数的和、每列上的整数的和以及两条对角线中每条对角线上的整数和都等于同一数。•定义行/列的整数和为该幻方的幻和。–{1,2,3….n2}整数和为•1+2+3+….+n2=n2×(n2+1)/2–n阶幻方共有n行，每行的和为s•ns=n2×(n2+1)/2s=n×(n2+1)/213存在性问题•是不是所有1到n2的数字都可以构成幻方呢？•是否存在2阶幻方？–假设存在2阶幻方–2阶幻方的幻和为5abcd[]b-d=0;与假设矛盾。a,b,c,d是[1，4]的各不相同的整数不存在2阶幻方！a+b=5c+d=5a+d=5c+b=5大约30年前德国数学家L.Bieberbach证明了：「对于任意大于等于3的数n，都存在一个n阶的幻方。」n*(n2+1)/2=2×5/2=514幻方的构造•17世纪delaLoubere提出了n阶幻方构造方法，其中n为奇数–将1放在最上一行的中间，然后按照自左下到右上的对角线顺序来放置，同时遵循如下规则：•到达顶行，则下一个数放在底行，位置相应错过去•到达最右边一列，下一个整数放在最左边，位置相应错位•如果要放的位置上已经填好了整数，或者已经放到了右上角，则放在紧挨着该位置的下方。杨辉构造法九子斜排，上下对易，左右相更，四维挺出，戴九履一，左三右七，二四为肩，六八为足15幻方的构造•将1放在最上一行的中间，然后按照自左下到右上的对角线顺序来放置，同时遵循如下规则：–到达顶行，则下一个数放在底行，位置相应错过去–到达最右边一列，下一个整数放在最左边，位置相应错位–如果要放的位置上已经填好了整数，或者已经放到了右上角，则放在紧挨着该位置的下方。834165972根据构造方法的不同，幻方可以分三类：奇数阶幻方、4M阶幻方和4M+2阶幻方16834165972三阶幻方的个数17n阶普通幻方有多少个呢？幻方的计数•弗兰尼克尔（BernardFrenicledeBessy）在1693年得出结论，认为4阶幻方总共有880个基本形式，通过旋转与镜面反射，总共有7040个幻方。•对于5阶幻方总数的估计，理查德•许洛泼尔（RichardSchroeppel）利用计算机编程运算得出结论，•认为5阶幻方的基本形式有275305224个，即2亿7千5百多万个。•对6阶幻方，皮恩（K.Pinn）和维茨考夫斯基（C.Wieczerkowski）利用蒙特卡洛模拟和统计学方法，得出一个大概的数值估计，其数量在1.774310×1019至1.776610×1019之间。由此可见，其他阶幻方•的多少将是一个多么难以置信的庞大数字•Thenumbersofdifferentn×nmagicsquaresfornfrom1to5,notcountingrotationsandreflectionsare:1,0,1,880,275305224(sequenceA006052inOEIS).Thenumberforn=6hasbeenestimatedtobe(0.17745±0.00016)×1020.[22][23]19例:幻方•一个n阶幻方是由整数1,2,3….n2按下述方式组成的n×n方阵：该方阵每行上的整数的和、每列上的整数的和以及两条对角线中每条对角线上的整数和都等于同一数。20例:幻方•一个n阶幻方是由整数1,2,3….n2按下述方式组成的n×n方阵：该方阵每行上的整数的和、每列上的整数的和以及两条对角线中每条对角线上的整数和都等于同一数。任意数列平方数素数幻积，幻差，幻商平方幻和1472+12+25622=14799400929822+15332+18862=1479940091472+15332+21632=14799400921幻方问题•组合数学中有许多象幻方这样精巧的结构。•1977年美国旅行者1号、2号宇宙飞船就带上了幻方以作为人类智慧的信号。2008幻方东阳78岁老人包中祥设计出的正六面体“完美幻方”。它的每个田字格中的四个数的和是2008，每个等腰梯形，长方形，菱形上四个格中的四个数的和是2008，8条对角线和8条直线的四个数的和是2008，这里也告诉人们一个数字系列：2008.8.8。还有，奥运五环上的五个数字和与另一颗“心”上的数字的差是2008，如（232+962+532+352+402）-472＝2008。个性的幻方也是表达心意不错的选择23组合数学Combinatorics1组合数学概论1-1组合数学的渊源1-1-b苦难的羊皮纸卷----西方组合学的发展清华大学马昱春25阿基米德手稿•用希腊文写在羊皮纸上的阿基米德手稿副本，距今约1000年•2003科学家借助现代科技手段初步破译了古希腊数学家阿基米德的这篇论文,结论是这篇论文解决的是组合数学问题《十四巧板》(stomachion)。•在论文中阿基米德是在计算把14条不规则的纸带拼成正方形一共能有多少种不同的拼法。这在现在被称为tiling问题。•斯坦福数学系的教授研究了这个问题，设立了一个小小的奖项来征集答案，100美金，•数学家和计算机学者都来参与了，你猜谁赢了呢？•伊利诺大学计算机系的比尔.卡特勒借助计算机得出的答案是17152种拼法•数学家用纸和笔对排列进行分类，共24个基本族，基本解法是536种，考虑旋转32种，答案也是17152种。公元前287年—公元前212年26组合数学的历史1666年莱布尼兹所著《论组合的艺术》一书问世，这是组合数学的第一部专著。书中首次使用了组合论（Combinatorics）一词。一切推理和发现，不管是否用语言描述，都能归结为如数，字，声，色这些元素经过某种组合的有序集合。戈特弗里德·威廉·莱布尼茨GottfriedWilhelmLeibniz(1646年－1716年），德国哲学家、数学家。涉及的领域及法学、力学、光学、语言学等40多个范畴，被誉为十七世纪的亚里士多德。和牛顿先后独立发明了微积分。27组合数学Combinatorics1组合数学概论1-1组合数学的渊源1-1-c密码安全不安全算了才知道清华大学马昱春28组合数学的应用•著名的组合数学家ThomasTutte(1917-2002)在组合数学界是泰斗级的大师。直到最近人们才知道，原来他对提前结束“二战”有着突出贡献。•Tutte从德军的两条情报密码出发，用组合数学的方法，重建了敌人的密码机，确定了德军密码的内部结构，从而获得了极为重要的情报。•加拿大政府2011年成立TheTutteInstituteforMathematicsandComputing(TIMC)以纪念他。手机密码安全吗？•10×10×10×10=1000029？手机屏幕开锁•3×3的点阵中的一条路径，这条路径最少连接四个点，最多连接九个点。•C(9,4)+C(9,5)+C(9,6)+C(9,7)+C(9,8)+C(9,9)=985824总体方案：389112方案数31如果连接的点数不到6个的话，密码可能个数：1624+7152=8776个4位：16245位：71526位：260167位：729128位：1407049位：140704•10×10×10×10=1000032前言•组合数学的历史渊源扎根于数学娱乐和游戏之中，过去的研究往往出于消遣或者美学的考虑。•组合数学的蓬勃发展则是在计算机问世和普遍应用之后。–程序的基础往往是求解问题的组合数学算法–算法的运行时间效率和存储需求分析都需要组合数学的思想。–过去研究过的许多问题如今在研究和应用中具有高度的重要性。–广泛应用在社会科学，生物科学，信息论等。•由于组合数学涉及面广，内容庞杂，并且仍在很快地发展着，因而还没有一个统一而有效的理论体系。这与数学分析形成了对照。–计数：无重复无遗漏33组合数学Combinatorics1漫谈组合数学1-1组合数学的渊源1-1-d暴力枚举和抽象转换清华大学马昱春34抽象转换•例世界杯复赛中十六支球队进行单场淘汰赛，直至决出冠军，请问一共需要踢多少场比赛？•如果全世界224个国家和地区都参加，一共要踢多少场比赛呢？•解一种常见的思路是按轮计场，费事。–淘汰的选手与比赛(按场计)集一一对应。•模型转换：世界杯复赛和决赛共15场比赛。•全世界都来参加的话需要223场比赛。n-1哥尼斯堡七桥问题•18世纪，哥尼斯堡是东普鲁士的一座景色迷人的城市，普莱格尔河横贯城区，并且这条河在城区形成了两条支流，把城市分成了4块，因此人们建造了7座各具特色的桥，每到傍晚，人们都会来此散步。•而这座美丽的城市人杰地灵，数学家哥德巴赫，哲学家康德都出生在这里，这里的人民长期漫步在这座桥之间，久而久之，萌发了这样一个问题，能不能不重复的走遍所有的桥，最终回到出发点？•欧拉的拓扑抽象桥的连接图一笔画？充要条件1736年欧拉发表的有关图论的第一篇论文《哥尼斯堡七桥问题》36节点要联通奇数点的个数为0或者2奇数点