上海交通大学：《组合数学 Combinatorics》课程教学资源（讲义）第一章 概论（主讲：陈克非）

上海交通大学 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元和相等： „ 平行于立方体一条边的直线 „ 每个截面的两条对角线 „ 四条空间对角线

举例:四色问题 问题( Francis Guthrie,1850):地图上的国 家是连通区域,对每个国家着色,以便于区分 具有共同边界的国家着不同颜色(角点除外) 至少需要几种颜色 些地图需要4种颜色 Heawood(1890)证明 至多五种颜色就够了 Appe和 Haken(1976) 100亿个判定 A 1200个机时 200399 Dept of computer Science and Engineering, Shanghai fiaotong University 11 举例:36军官问题 来自6个不同军团,共有6个不同的军阶的36名军 官,能否排成6x6方阵 每行的军官来自不同的军团「(1)(2,2)(3,3) 每行的军官的军阶不同 3×3的例子 (3,2)(1,3)(2,1) ■正交拉丁方 (2,3)(3,1)(1,2) Euer猜想n=2(mod4)时,不存在正交拉丁方(18世纪) Tarry证明n=6时,不存在正交拉丁方(1910) Bose、 Parker、 Shrikhande证明:n≡2(mod4),m>6时 必存在一对正交拉丁方(1960) ■应用:实验设计 200399 Dept of computer Science and Engineering, Shanghai fiaotong Univrsity

6 2003-9-9 Dept of Computer Science and Engineering， Shanghai Jiaotong University 11 举例：四色问题 „ 问题（Francis Gurthrie, 1850）：地图上的国 家是连通区域，对每个国家着色，以便于区分。 „ 具有共同边界的国家着不同颜色（角点除外) „ 至少需要几种颜色？ „ 一些地图需要4种颜色 „ Heawood（1890）证明 „ 至多五种颜色就够了 „ Appel和Haken（1976） „ 100亿个判定 „ 1200个机时 2003-9-9 Dept of Computer Science and Engineering， Shanghai Jiaotong University 12 举例： 36军官问题 „ 来自6个不同军团，共有6个不同的军阶的36名军 官，能否排成6x6方阵 „ 每行的军官来自不同的军团 „ 每行的军官的军阶不同 „ 3x3的例子 „ 正交拉丁方 „ Euler猜想n≡2(mod4)时，不存在正交拉丁方（18世纪） „ Tarry证明n=6时，不存在正交拉丁方（1910） „ Bose、Parker、Shrikhande证明：n≡2(mod4), n>6时 必存在一对正交拉丁方（1960） „ 应用：实验设计           (2,3) (3,1) (1,2) (3,2) (1,3) (2,1) (1,1) (2,2) (3,3)

举例:最短路径问题 ■在多条路径可选的情况下,选最短的 组合优化问题 寻径算法 ■从起点出发,尝试各种可能的路径到终点 是否存在一种有效的算法? 工作量随系统规模扩大成指数增长 算法复杂度问题 P类,NP类,NP- Complete,NP-hard 200399 Dept of computer Science and Engineering, Shanghai fiaotong Uniperaity13 举例:七桥问题 ■普鲁士的 Konigsberg(今俄国 Kaliningrad) 被 Pregel河分成4部分 GURE 1 The Seven Bridges FIGURE 2 Multigraph Model the Town of Konigsberg

7 2003-9-9 Dept of Computer Science and Engineering， Shanghai Jiaotong University 13 举例：最短路径问题 „ 在多条路径可选的情况下，选最短的 „ 组合优化问题 „ 寻径算法 „ 从起点出发，尝试各种可能的路径到终点 „ 是否存在一种有效的算法？ „ 工作量随系统规模扩大成指数增长 „ 算法复杂度问题 „ P类，NP类，NP-Complete，NP-hard 2003-9-9 Dept of Computer Science and Engineering， Shanghai Jiaotong University 14 举例：七桥问题 „ 普鲁士的Gönigsberg（今俄国Kaliningrad） 被Pregel河分成4部分

Euler回路问题 ■能否从某点出发,经过每座桥不重复, 最终返回起点。 笔画问题,一笔画出给定的图,如何一条 边不重复画 ■瑞士数学家 Euler证明(1736),问题无 解 ■顶点次数必须是偶数 更一般地, Euler回路问题 200399 Dept of computer Scienc and Engineering, Shanghai fiaotong Uhniperity15 计算机算法问题 ■运筹学中涉及大量的搜索算法(遍历算法) 穷举搜索算法 顺路返回算法 四色问题的解决,得益于 Heesch的工作 用计算机得出大量可约结构(一个点数最少的反例图中不 可能出现的一类图形) 证明每个平面图至少包含一个可约结构,即四色定理 ■分枝界定算法 分类问题的气泡算法 ■算法的优劣在很多情况下往往是决定性的 200399 Dept of computer Science and Engineering, Shanghai fiaotong Univrsity

8 2003-9-9 Dept of Computer Science and Engineering， Shanghai Jiaotong University 15 Euler回路问题 „ 能否从某点出发，经过每座桥不重复， 最终返回起点。 „ 一笔画问题，一笔画出给定的图，如何一条 边不重复画 „ 瑞士数学家Euler证明（1736），问题无 解！ „ 顶点次数必须是偶数 „ 更一般地，Euler回路问题 2003-9-9 Dept of Computer Science and Engineering， Shanghai Jiaotong University 16 计算机算法问题 计算机算法问题 „ 运筹学中涉及大量的搜索算法（遍历算法）： „ 穷举搜索算法 „ 顺路返回算法 „ 四色问题的解决，得益于Heesch的工作： „ 用计算机得出大量可约结构（一个点数最少的反例图中不 可能出现的一类图形） „ 证明每个平面图至少包含一个可约结构，即四色定理 „ 分枝界定算法 „ 分类问题的气泡算法 „ 算法的优劣在很多情况下往往是决定性的

纠错码问题 在有扰信道传输信号c→v=c+e 如何确定噪声e的存在(检错) ■如果可能,如何除去e(纠错) ■纠错编码对信号进行编码,使其具有纠错能力 若要能纠十个错误,码间距离d>2+t 最大似然译码 [nkd]码:满足特定条件的线性空间CcF d<=n-k+1 Hamming码,BCH码,完全码,最佳码(?) 重量分布,覆盖半径, 译码问题(一般来说是NPC问题) 200399 Dept of computer Scienc and ngineering, Shanghai iaotong Univerity 密码算法设计 ■密码算法是一种变换 具有快速扩散、置乱的作用 密码变换需要具有一定的性质,以确保安全性 ■随机性、相关免疫性、非线性性、无碰撞性、长周 期(状态图的圈长) ■涉及计数、穷举、设计构造等 ■安全分析 攻击方法 规模大小估计,如ECC中群的大小 200399 Dept of computer Science and Engineering, Shanghai fiaotong Univrsity

9 2003-9-9 Dept of Computer Science and Engineering， Shanghai Jiaotong University 17 纠错编码问题 „ 在有扰信道传输信号cÆv=c+e „ 如何确定噪声e的存在（检错） „ 如果可能，如何除去e（纠错） „ 纠错编码对信号进行编码，使其具有纠错能力 „ 若要能纠t个错误，码间距离d>2+t „ 最大似然译码 „ [n,k,d]码：满足特定条件的线性空间 „ d<=n-k+1 „ Hamming码，BCH码，完全码，最佳码（？）； „ 重量分布，覆盖半径，… „ 译码问题（一般来说是NPC问题） n C ⊂ F 2003-9-9 Dept of Computer Science and Engineering， Shanghai Jiaotong University 18 密码算法设计 „ 密码算法是一种变换 „ 具有快速扩散、置乱的作用 „ 密码变换需要具有一定的性质，以确保安全性 „ 随机性、相关免疫性、非线性性、无碰撞性、长周 期（状态图的圈长）、… „ 涉及计数、穷举、设计构造等 „ 安全分析 „ 攻击方法 „ 规模大小估计，如ECC中群的大小

租合学历史与发展 组合数学是门非常古老的学科 ■传说禹公元前2200年前在神龟背上发现幻方 公元前1100年中国就有了排列的概念 ■公元1140年, Rabbi Ben ezra发现n个事务中取r 个的组合公式 ■ Bache砝码问题、 Kirkman女生问题、Euer36军 官问题 ■求解问题:机智+精巧 17~18世纪,随数论、概率论发展而发展 ■1950年代后,受计算机的影响发展迅速 ■不仅是数学,同时成为计算机科学的理论基础 200399 Dept of computer Science and Engineering, Shanghai fiaotong University 本课程内容安排 ■排列与组合 ■母函数与递推关系 容斥原理和鸽巢原理 Poya定理 ■区组设计与编码 ■线性规划 200399 Dept of computer Science and Engineering, Shanghai fiaotong Univrsity

10 2003-9-9 Dept of Computer Science and Engineering， Shanghai Jiaotong University 19 组合数学历史与发展 组合数学历史与发展 „ 组合数学是门非常古老的学科 „ 传说禹公元前2200年前在神龟背上发现幻方 „ 公元前1100年中国就有了排列的概念 „ 公元1140年，Rabbi Ben Ezra发现n个事务中取r 个的组合公式 „ Bachet砝码问题、Kirkman女生问题、Euler36军 官问题 „ 求解问题：机智＋精巧 „ 17～18世纪，随数论、概率论发展而发展 „ 1950年代后，受计算机的影响发展迅速 „ 不仅是数学，同时成为计算机科学的理论基础 2003-9-9 Dept of Computer Science and Engineering， Shanghai Jiaotong University 20 本课程内容安排 本课程内容安排 „ 排列与组合 „ 母函数与递推关系 „ 容斥原理和鸽巢原理 „ Polya定理 „ 区组设计与编码 „ 线性规划