清华大学：《组合数学》课程教学资源（PPT课件讲稿）讲义一

上海交通大学 Combinatorics 组合数学 陈克 上海通大学计算机科学与工程系 situ.edu.cn ht:/202.1201546 第一章:欐论 什么是组合数学 举例 ■涉及内容 典型应用 教学安排 参考文献 200399 Dept of computer Science and Engineering, Shanghai fiaotong Univrsity

1 Combinatorics Combinatorics 组合数学 陈克非 上海交通大学计算机科学与工程系 Kfchen@mail.sjtu.edu.cn http://202.120.15.46/ 2003-9-9 Dept of Computer Science and Engineering， Shanghai Jiaotong University 2 第一章：概论 „ 什么是组合数学 „ 举例 „ 涉及内容 „ 典型应用 „ 教学安排 „ 参考文献

租合学无处不在 组合数学的问题无处不在 ■排课表(教师、学生、时间、教室) akademische viertel(课间预留时间),列车时刻表 体育比赛 ■淘汰赛、循环赛、混合赛制(世界杯32s.36) ■访问路径 ■巡回售货员(邮递员)、网络路由、 实验设计 新药(减少人为因素)、计量(降低仪器误差) 200399 Dept of computer Scienc and ngineering, Shanghai fiaotong Univeraity 租合数学的问题 ■组合数学涉及到将一个集合的对象排列成满足 些指定规则的形式 排列的存在性 什么情况下存在(必要与充分条件) 排列的计数和分类 如果存在,有多少种? 研究一个已知的排列 涉及到排列的性质、结构 涉及到排列的分类,可能某些应用 ■构造一个最优的排列 在多于一种排列的情况下,寻找每种最好的解 200399 Dept of computer Science and Engineering, Shanghai fiaotong Univrsity

2 2003-9-9 Dept of Computer Science and Engineering， Shanghai Jiaotong University 3 组合数学无处不在 组合数学无处不在 „ 组合数学的问题无处不在： „ 排课表（教师、学生、时间、教室） „ akademische Viertel（课间预留时间），列车时刻表 „ 体育比赛 „ 淘汰赛、循环赛、混合赛制（世界杯 32 vs. 36） „ 访问路径 „ 巡回售货员（邮递员）、网络路由、… „ 实验设计 „ 新药（减少人为因素）、计量（降低仪器误差）、… 2003-9-9 Dept of Computer Science and Engineering， Shanghai Jiaotong University 4 组合数学的问题 组合数学的问题 „ 组合数学涉及到将一个集合的对象排列成满足 一些指定规则的形式 „ 排列的存在性 „ 什么情况下存在（必要与充分条件）？ „ 排列的计数和分类 „ 如果存在，有多少种？ „ 研究一个已知的排列 „ 涉及到排列的性质、结构 „ 涉及到排列的分类，可能某些应用 „ 构造一个最优的排列 „ 在多于一种排列的情况下，寻找每种最好的解

租合学分类 ■组合数学是研究离散结构的存在、计数、分析 和优化问题的学科 组合分析:研究计数和枚举 基本方法,数学归纳法,母函数法 组合设计:构造特殊的离散结构 幻方,区组设计,实验设计,编码 ■组合算法:组合问题涉及的算法 搜索法、算法复杂度、NPC 图论:顶点和边的连接关系 同构,路径,流量,连通,着色, 200399 Dept of computer Scienc and Engineering, Shanghai fiaotong Univerity 5 租合数学的名称 组合数学 Combinatoria/ mathematics ■组合学 Combinatorics ■组合理论 Combinatoria/theory 组合分析 Combinatorial analysis 慝之,研究一类有限(也可是无限的)离散集合中元 素排列、组合、选掸、配置等对应当计嶽和构造问题 200399 Dept of computer Science and Engineering, Shanghai fiaotong Univrsity

3 2003-9-9 Dept of Computer Science and Engineering， Shanghai Jiaotong University 5 组合数学分类 „ 组合数学是研究离散结构的存在、计数、分析 和优化问题的学科 „ 组合分析：研究计数和枚举 „ 基本方法，数学归纳法，母函数法，… „ 组合设计：构造特殊的离散结构 „ 幻方，区组设计，实验设计，编码，… „ 组合算法：组合问题涉及的算法 „ 搜索法、算法复杂度、NPC、… „ 图论：顶点和边的连接关系 „ 同构，路径，流量，连通，着色，… 2003-9-9 Dept of Computer Science and Engineering， Shanghai Jiaotong University 6 组合数学的名称 组合数学的名称 „ 组合数学 „ Combinatorial mathematics „ 组合学 „ Combinatorics „ 组合理论 „ Combinatorial theory „ 组合分析 „ Combinatorial analysis „ 总之，研究一类有限（也可是无限的）离散集合中元 素排列、组合、选择、配置等对应当计数和构造问题

举例:棋盘的覆盖问题 国际象棋棋盘8×8方格 ■多米诺骨牌可覆盖相邻的两个方格 ■问题:32张牌能否恰好覆盖整个棋盘? 构造一些"完美覆盖"容易 计算出有多少"完美覆盖"不易(24×9012=12988816) 若考虑mxm的棋盘 是否存在完美覆盖?(对应于分子物理的二聚物问 题) ■若棋盘去掉两个对角(剩62个方格 ■是否存在完美覆盖? ■证明:31 Black white not=32Back+30whte 200399 Dept of couputer ciena and ngineering, Shanghai iaotong University 举例:幻方问题 ■最古老、最流行的游戏 ■1,2,3灬n2个数排成nxn方阵 每行、每列、以及对角线上元素和为定数s 是否存在? nn=3,n=4「816 163213 510118 357 96712 492 415141 200399 Dept of computer Science and Engineering, Shanghai fiaotong Univrsity

4 2003-9-9 Dept of Computer Science and Engineering， Shanghai Jiaotong University 7 举例：棋盘的覆盖问题 „ 国际象棋棋盘8x8方格 „ 多米诺骨牌可覆盖相邻的两个方格 „ 问题：32张牌能否恰好覆盖整个棋盘？ „ 构造一些“完美覆盖”容易 „ 计算出有多少“完美覆盖”不易（24x9012=12988816） „ 若考虑m x n的棋盘 „ 是否存在完美覆盖？（对应于分子物理的二聚物问 题） „ 若棋盘去掉两个对角（剩62个方格） „ 是否存在完美覆盖? „ 证明：31Black|white not= 32Black + 30white 2003-9-9 Dept of Computer Science and Engineering， Shanghai Jiaotong University 8 举例：幻方问题 „ 最古老、最流行的游戏 „ 1,2,3,…,n2个数排成nxn方阵 „ 每行、每列、以及对角线上元素和为定数s „ 是否存在？ „ n=3, n=4

幻方问题的一般解 问题:对任意n,是否有解? 分析:若有解,则每行和相等,即 (1+n2)/2 5是其1/n,n(n2+1)/2 ■解的构造 只要n不是2 ■多种不同的构造方法 200399 Dept of computer Scienc and ngineering, Shanghai fiaotong Univeraity 勾方的构造方法 n奇数: de la loubere方法(17世纪) 1放在顶上一行的中央 其后的数沿斜线自左下至右上顺序排列,如该位置 已被占用,放在其正下方,直到n2为止 其中行循环移位向上扩展,如定行的上面是第n行;对于 列也是类似,循环移位向右扩展 n偶禺数: Rouse方法(1962) 3维幻方( nxnxn阵列),下面的n元和相等 平行于立方体一条边的直线 每个截面的两条对角线 四条空间对角线 200399 Dept of computer Science and Engineering, Shanghai fiaotong Univrsity

5 2003-9-9 Dept of Computer Science and Engineering， Shanghai Jiaotong University 9 幻方问题的一般解 „ 问题：对任意n，是否有解？ „ 分析：若有解，则每行和相等，即 „ S是其1/n，n(n2+1)/2 „ 解的构造 „ 只要n不是2 „ 多种不同的构造方法 (1 )/ 2 2 2 1 2 s i n n n i = ∑ = + = 2003-9-9 Dept of Computer Science and Engineering， Shanghai Jiaotong University 10 幻方的构造方法 幻方的构造方法 „ n奇数：de la Loubere方法（17世纪） „ 1放在顶上一行的中央 „ 其后的数沿斜线自左下至右上顺序排列，如该位置 已被占用，放在其正下方，直到n2为止。 „ 其中行循环移位向上扩展，如定行的上面是第n行；对于 列也是类似，循环移位向右扩展 „ n偶数：Rouse方法（1962） „ 3维幻方（nxnxn阵列），下面的n元和相等： „ 平行于立方体一条边的直线 „ 每个截面的两条对角线 „ 四条空间对角线