组合数学引论

组合数学,（引论）,教材：,目录,第1章排列与组合第2章递推关系与母函数第3章容斥原理与鸽巢原理第4章Burnside引理与Polya定理第5章区组设计第6章线性规划第7章编码简介第8章组合算法简介,目录.,第1章排列与组合1.1加法法则与乘法法则1.2一一对应1.3排列与组合1.4圆周排列1.5排列的生成算法1.6允许重复的组合与不相邻的组合1.7组合意义的解释1.8应用举例1.9Stir1ing公式第2章递推关系与母函数2.1递推关系2.2母函数2.3Fibonacci序列2.4优选法与Fibonacci序列的应用2.5母函数的性质2.6线性常系数齐次递推关系2.7关于线性常系数非齐次递推关系2.8整数的拆分2.9Ferrers图像2.10拆分数估计2.11指数型母函数2.12广义二项式定理2.13应用举例2.14非线性递推关系举例2.15递推关系解法的补充,第3章容斥原理与鸽巢原理3.1DeMorgan定理3.2容斥定理3.3容斥原理举例3.4棋盘多项式与有限制条件的排列3.5有禁区的排列3.6广义的容斥原理3.7广义容斥原理的应用3.8第二类Stir1ing数的展开式3.9欧拉函数3.10n对夫妻问题3.11Mobius反演定理3.12鸽巢原理3.13鸽巢原理举例3.14鸽巢原理的推广3.15Ramsey数第4章Burnside引理与Polya定理4.1群的概念4.2置换群4.3循环、奇循环与偶循环4.4Burnside引理4.5Polya定理4.6鸽巢原理4.7鸽巢原理举例4.8鸽巢原理的推广4.9Ramsey数,一、组合数学简介,更直观的问题：1.四个人围绕圆桌就坐，有多少种坐法？2.五个人分十七元钱，有多少种分法？3.用3种颜色涂立方体的六个面，每个面涂一种颜色，有多少种涂法？4.从10个人中选出一个总统、一个副总统、一个财务大臣、一个秘书，可兼任，有几种选法？,一、组合数学简介,组合数学分类,计数是组合分析中的中心问题。计数有多少个对象符合给定的描述，或者说有多少种方式使确定的事件发生。例如：四个人围绕圆桌就坐的方法有多少种？,排列与组合，母函数与递推关系，容斥原理和鸽巢原理，Plya定理，,组合数学历史与发展,神龟背上的幻方,行、列、对角线的和均为15,组合数学历史与发展,组合数学与计算机科学吴文俊院士：每个时代都有它特殊的要求，使得数学出现一个新的面貌，产生一些新的数学分支，组合数学这个新的分支也是在时代的要求下产生的。信息技术很可能会给数学本身带来一场根本性的变革，而组合数学则将显示出它的重要作用。Gian-CarloRota教授曾提出要向中国领导人呼吁：组合数学是计算机软件产业的基础，中国最终一定能成为一个软件大国，但是要实现这个目标的一个突破点就是发展组合数学。,二、学习方法,二、学习方法,组合数学经常使用的方法并不高深复杂。最主要的方法是计数时的合理分类和组合模型的转换。但是，要学好组合数学并非易事，既需要一定的数学修养，也要进行相当的训练。也就是：机智+精巧。组合数学中有二个常用的技巧：1.一一对应2.奇偶性,1.、一一对应,1.一一对应,二个事件之间如果存在一一对应关系，则可用解易解的来替代难解的。应用举例例1.有101个选手参加象棋淘汰赛，问要决出冠军共要进行多少场比赛？,注意：每场比赛必淘汰一人，反之，要淘汰一人也必须进行一场比赛。,淘汰人数比赛场数,一一对应,因为要淘汰100个人，所以要进行100场比赛！,例2.从10个人中选出一个总统、一个副总统、一个财务大臣、一个秘书，可兼任，有几种选法？,解答：用数字09代表10个人。然后将选中的号码放在下表中的职位下面。,总统副总统财务大臣秘书,0,1,2,2,一种选法一个四位数,一一对应,4321,答案：有1万种选法。,2.奇偶性,2.奇偶性,在某些情况下，利用计数问题的奇偶性，很容易得到结论。,例如，若某事件的发生总是奇数，那么就能够断定该事件至少会发生一次(存在性确定)。当然，也可以用奇偶性来证明某些对象是根本不可能存在的。例如图论中的七桥问题。,三、典型问题举例,三、典型问题举例(7个),下面列举一些组合数学中很经典的问题和它们的解法。可以看到，一些解题方法非常巧妙,而其常用的一个技术就是运用“一一对应”，很能启发人。,1.棋盘的覆盖,1.棋盘的覆盖,1.棋盘的覆盖,1.棋盘的覆盖,1.,1.棋盘的覆盖,2.切割立方体,2.切割立方体,2.切割立方体,一个边长为3的立方体，要切割成27个边长为1的小立方体，问至少要切割几次？,？,3.幻方,3.幻方,3.幻方,n阶幻方把数1n2排列成n阶方阵，使得行、列、对角线的和均相同。,例.三阶四阶,3.幻方,3.幻方,问题：1.n取哪些值幻方存在？2.对给定的n，有多少种不同的n阶幻方？3.如何构造幻方？,n2时幻方存在！当n为奇数时，幻方很容易构造！下面介绍几种n为奇数时的构造方法。,3.幻方,3.幻方,1）德拉鲁布方法将1置于顶行中间，然后按向右上方的方向依次放后继数；到顶行后翻到底行，到达最右列后转最左列；其余情况放正下方。,3.幻方,3.幻方,1）德拉鲁布方法将1置于顶行中间，然后按向右上方的方向依次放后继数；到顶行后翻到底行，到达最右列后转最左列；其余情况放正下方。,例.构造5阶幻方。,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,3.幻方,3.幻方,2）麦哲里克方法（与德拉鲁布方法类似）将1置正中央上方，然后按向右上方的方向依次放后继数；到顶行后翻到底行，到达最右列后转最左列；其余情况放正上方2格。,3.幻方,3.幻方,2）麦哲里克方法（与德拉鲁布方法类似）将1置正中央上方，然后按向右上方的方向依次放后继数；到顶行后翻到底行，到达最右列后转最左列；其余情况放正上方2格。,例.构造5阶幻方。,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,3.幻方,3.幻方,3）折角法,4.四色问题,4.四色问题,4.四色问题,5.欧拉回路问题,5.欧拉回路问题,5.欧拉回路问题,6.最短路径问题,6.最短路径问题,6.最短路径问题,7.纠错编码问题,7.纠错编码问题,7.纠错编码问题,结束,第1章排列与组合,1.1加法法则与乘法法则1.2一一对应1.