组合数学前言省公开课一等奖全国示范课微课金奖课件

第一章组合数学序言第1页序言组合数学是一个古老而又年轻数学分支据传说，大禹在4000多年前就观察到神龟背上幻方第2页幻方幻方能够看作是一个3阶方阵，其元素是1到9正整数，每行、每列以及两条对角线和都3页中国古代组合数学贾宪北宋数学家（约11世纪）著有《黄帝九章细草》、《算法斅古集》（斅音“笑”）都已失传第4页中国古代组合数学杨辉著《详解九章算法》（1261年）中曾引贾宪“开方作法根源”图（即指数为正整数二项式展开系数表，现称“杨辉三角形”）和“增乘开方法”（求高次幂正根法）第5页中国古代组合数学前者比帕斯卡三角形早600年，后者比霍纳（WilliamGeogeHorner，1786-1837）方法（1819年）早770年第6页国外组合数学1666年莱布尼兹所著《组合学论文》一书问世，这是组合数学第一部专著。书中首次使用了组合论（Combinatorics）一词第7页几个经典组合数学实例棋盘完美覆盖再议幻方中国邮递员问题第8页棋盘完美覆盖8×8棋盘覆盖2格多米诺牌能否完美覆盖？有多少覆盖方式？Fischer在1961年发觉，不一样完美覆盖总数是12,988,816=24×(901)2第9页m×n棋盘完美覆盖….….….….….….

….….m×n棋盘能否完美覆盖？有多少覆盖方式？当且仅当棋盘方格数为偶数时，m×n棋盘存在完美覆盖第10页残缺棋盘完美覆盖覆盖2格多米诺牌能否完美覆盖？有多少覆盖方式？残缺8×8棋盘第11页残缺棋盘完美覆盖黑白黑白黑白黑白白黑白黑白黑白黑黑白黑白黑白黑白白黑白黑白黑白黑黑白黑白黑白黑白白黑白黑白黑白黑黑白黑白黑白黑白白黑白黑白黑白黑黑白黑白黑白黑白黑白黑白黑白黑黑白黑白黑白黑白白黑白黑白黑白黑黑白黑白黑白黑白白黑白黑白黑白黑黑白黑白黑白黑白黑白黑白黑白黑黑白31≠

32+30黑白第12页b-多米诺牌….….….….….….

….….

m×n棋盘b-多米诺牌能否完美覆盖？有多少覆盖方式？第13页b-多米诺牌命题：一张m行n列棋盘有一个b-牌完美覆盖，当且仅当b是m一个因子或者b是n一个因子

命题是否成立？第14页幻方一个n阶幻方是由整数1，2，3，…，n2按下述方式组成n×n方阵：该方阵每行上整数和、每列上整数和以及两条对角线中每条对角线上整数和都等于同一个数ss--幻和第15页幻方81635749216321351011896712415141问题：哪些n存在幻方？假如有，则结构方法怎样？第16页结构幻方结构奇数阶幻方方法：

将1放在最上一行中间，其后整数沿着自左下到右上这条对角线按照自然次序放置，同时作修正：在抵达顶行时，下一个整数要放在底行，所放位置就是把底行看成顶行上边一行时该数应该放置位置当抵达最右边一列时，下一个整数要放在最左边一列上，所放位置就是把最左边一列看成最右边那列右边列时该数应该放置位置当要放位置上已经填好了整数，或上一个整数已经放在了幻方右上角时，则当前要摆放整数将放在紧挨上述位置下方第17页中国邮递员问题邮递员从邮局出发送信，要求对辖区内每条街，都最少经过一次，再回邮局。在此条件下，怎样选择一条最短路线?中国邮递员问题由管梅谷教授在1960年提出，美国国家标准和技术研究院（NIST）首先将此问题命名为中国邮递员问题第18页中国邮递员问题假设有一个镇有14条路及9个路口（路口分别编号为1,2,…,9），怎样找到一条最短路线?

第19页欧拉回路若图中有欧拉回路（图G一个回路，若它恰经过G中每条边一次），则任何一个欧拉回路即为此问题解。若图中不存在欧拉回路，其中必存在有奇数个边端点，且这类端点一定大于2个。所以有些边需要再重复一次，使奇数边端点变为偶数边端点。第20页重复边不存在欧拉回路，其中有4个路口（编号1,3,6及9）有奇数条路经过现在要做：在图中使几个边重复，使图中全部端点都有偶数边经过。

问题：确定重复哪个边能够使原图端点都有偶数边经过，且增加长度最少？第21页选择重复边画出全部奇数边端点完全图K4，边上数字是从一端点到另一端点最短长度。选择边{1,6}及{3,9}，全部端点都经过一次，而总长度4+2=6最短。

第22页问题解原来图中，连接端点1和6,端点3和9边再重复一次，全部端点都有偶数个边经过任一个欧拉路径即为此问题解答，如以下端点次序{1,2,3,4,9,3,1,8,7,3,9,7,6,9,5,6,7,8,1}即为一解。图中红色部份即为重复边第23页组合数学发展组合数学源于消遣和游戏计算机促进了组合数学快速发展（组合爆炸）：大规模计算、程序设计处理组合问题、算法复杂性、优化和近似不过，因为组合数学包括面广，内容庞杂，而且仍在很快地发展着，因而还没有一个统一而有效理论体系第24页组合数学研究内容包括将一个集合物体排列成满足一些指定规则格式排列存在性：满足一些条件安排是否存在；安排存在充要条件排列计数和分类：安排存在方式和数量研究已知排列性质和结构：优化第25页组合数学研究内容组合数学:研究离散结构存在、计数、分析和优化等问题一门学科第26页组合数学研究工具数学归纳法：证实当n等于任意一个自然数时某命题成立。证实分下面两步：证实当n=1时命题成立。证实假如在n=m时命题成立，那么能够推导出在n=m+1时命题也成立。（m代表任意自然数）

原理：首先证实在某个起点值时命题成立，然后证实从一个值到下一个值过程有效。当这两点都已经证实，那么任意值都能够经过重复使用这个方法推导出来。第27页小结组合数学经常使用方法并不高深复杂。最主要方法是计数时合理分类和组合模型转换不过，要学好组合数学并非易事，既需要一定数学涵养，也要进行相当训练第28页教材及参考书《组合数学》RichardA.Brualdi著，机械工业出版社《组合数学》卢开澄，卢华明编著，清华大学出版社第29页学习内容鸽巢原理：掌握利用鸽巢基本原理分析和处理实际问题排列与组合：了解排列与组合基本