组合数学（张永刚）吉林大学 第一章 绪论.pptxVIP

组合数学Combinatorics;关于我;关于这门课;参考书(1);参考书(2);计算一些物品在特定条件下分组的方法数目。这些是关于排列、组合和整数分拆的。 地图着色问题：对世界地图着色，每一个国家使用一种颜色。如果要求相邻国家的颜色相异，是否总共只需四种颜色？这是图论问题。 中国邮差问题：由中国组合数学家管梅谷教授提出。邮递员要穿过城市的每一条路至少一次，怎样行走走过的路程最短？这不是一个NP完全问题，存在多项式复杂度算法：先求出度为奇数的点，用匹配算法算出这些点间的连接方式，然后再用欧拉路径算法求解。这也是图论问题。 如何构造幻方。 ;组合数学的起源;8;9;组合数学是研究离散结构的存在、计数、分析和优化等问题的一门学科。 组合数学就是研究按照一定的规则来安排一些离散个体的问题。它涉及面广，内容庞杂（涉及到组合分析、图论、组合算法、近代密码学、编码理论等），并且仍在很快地发展着，因而还没有一个统一而有效的理论体系。 研究的对象是离散结构，一般可以用{1，2，…，n}表示。本书仅限于讨论n是有限的自然数的情况。;组合数学经常使用的方法并不高深复杂。最主要的方法是计数时的合理分类和组合模型的转换（一一对应）。 学好组合数学既需要一定的数学修养，也要进行相当的训练。 可从规模小的模型着手，从中找到规律性的东西，再推及一般。 你解决的问题越多，那么你能够解决下一个问题的可能性也越大。 ;12; （2）安排的枚举、分类和计数 如果所要求的安排存在，则可能有多种不同的安排。此时，需要计数不同的方案数，并将它们进行枚举和分类。 当实际问题比较复杂的时候，必须有好的方法来解决. ; （3）构造性问题 一个组合问题，如果已经判定解是存在的，那么将所有可能的安排构造出来是一个关键问题。 与计算机算法密切相关，典型问题：组合设计; （4）优化问题 在给定的优化条件下从所有的安排方案中找出最优的安排方案。 如最短路径问题、数学规划问题，与算法分析密切相关 ;本课程涉及的内容： (不含图论和组合设计) 鸽巢原理和Ramsey定理???存在性问题） 基本计数方法 容斥原理 生成函数 递推关系 Pólya定理 ;17;18;关于幻方的问题归结为: （一）存在性问题 对任意的正整数n，n阶幻方存在吗？ （二）组合计数问题 如果存在，那么应该有多少个不同的 n阶幻方。 （三）构造问题 奇数阶幻方：连续摆数法(de La Loubère法) 双偶数（4k）阶幻方：对称法 单偶数(4k+2)阶幻方：斯特雷奇法（1918） ;20;21;22;23;例1.2 利用连续摆放法构造5阶幻方 ;25;26;27;28;29;30;31;32;33;34;35;36;37;38;39;40;41;例 36军官问题 有36名军官来自六个不同的团，具有六种不同的军衔，而且每个团每种军衔的军官各有一名，能否把他们排成一个6?6方阵，使得对每一个团与每一种军衔，在每一行或每一列都有一位军官来自这个团，也都有一位军官有此军衔？ 是由Euler首先提出的，实际上是组合设计中的正交拉丁方问题，属于构造问题。;如果每一个军官用一个有序对(i,j)来表示,其中i表示它们的军衔类别(i=1,?,6),而j表示他所在的团(j=1,2,?, 6),于是问题即要求将有序对(i, j) (i=1,2,?,6；j=1,2,?,6)排成一个6?6数组，使得每一行或每一列中整数1,2,?,6中任一数以某种次序出现于有序对的第一位置，又以另一种次序（不一定相同）出???于有序对的第二位置.;分别考虑军衔方阵与团队方阵, 于是问题就是是否存在两个6?6数组满足： (1) 每个数组中每一行或每一列中整数 1,2,?,6以某种次序出现; (2) 两个数组并置时, 所有的36个有序对 (i,j) (i=1,2,?,6; j=1,2,?,6)都将出现. 满足第一个条件的每个方阵称为拉丁方，满足第二个条件的两个拉丁方称为互相正交，即正交拉丁方. ;45;46;47;48;49;50;需要特殊技巧解决问题 例 有101名选手参加羽毛球比赛，如果采用单循环淘汰制，问产生冠军需要进行多少场比赛？ 方法一：50+25+13+6+3+2+1=100场比赛 方法二：由于每场比赛都要产生一个失败者，而每个失败者只能失败一次，因此比赛的场数与失败者的人数相等，除冠军外其他100人都失败过，因此产生冠军需要100场比赛。 例 有一个边长为3的立方体木块，要把它切割成27个边长为1的小