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

组合数学 清华大学计算机黄连生 1999年7月

组合数学 清华大学计算机 黄连生 1999年7月

言 组合数学是一个古老而又年轻的 数学分支。 据传说,大禹在4000多年前就观 察到神龟背上的幻方 ●●●●·●

前言 组合数学是一个古老而又年轻的 数学分支。 据传说，大禹在4000多年前就观 察到神龟背上的幻方…

前言 幻方可以看 作是一个3阶方492 阵,其元素是1 到9的正整数 357 每行、每列以 及两条对角线 816 的和都是15

前言 幻方可以看 作是一个 3阶方 阵，其元素是 1 到 9的正整数， 每行、每列以 及两条对角线 的和都是15 。 519 3 7 4 2 8 6

前 贾宪北宋数学家(约11世纪)著有《黄帝 九章细草》、《算法斅古集》斅音“笑(“古 算法导引”)都已失传。杨辉著《详解九章算 法》(1261年)中曾引贾宪的“开方作法本源” 图(即指数为正整数的二项式展开系数表,现 称“杨辉三角形”)和“增乘开方法”(求高 次幂的正根法)。前者比帕斯卡三角形早600 年,后者比霍纳( William Geoge Horner, 1786-1837)的方法(1819年)早770年

前言 贾宪 北宋数学家（约11世纪） 著有《黄帝 九章细草》、《算法斅古集》斅 音“笑（“古 算法导引”）都已失传。杨辉著《详解九章算 法》（1261年）中曾引贾宪的“开方作法本源” 图（即指数为正整数的二项式展开系数表，现 称“杨辉三角形”）和“增乘开方法”（求高 次幂的正根法）。前者比帕斯卡三角形早600 年，后者比霍纳（William Geoge Horner， 1786—1837）的方法（1819年）早770年

1666年莱布尼兹所著《组合学论文》 书问世,这是组合数学的第一部专著 书中首次使用了组合论( Combinatorics)

前言 1666年莱布尼兹所著《组合学论文》 一书问世，这是组合数学的第一部专著。 书中首次使用了组合论（Combinatorics） 一词

前言 组合数学的蓬勃发展则是在计算机 回世和普遍应用之后。由于组合数学涉 及面广,内容庞杂,并且仍在很快地发 展着,因而还没有一个统一而有效的理 论体系。这与数学分析形成了对照

前言 组合数学的蓬勃发展则是在计算机 问世和普遍应用之后。由于组合数学涉 及面广，内容庞杂，并且仍在很快地发 展着，因而还没有一个统一而有效的理 论体系。这与数学分析形成了对照

前言 本学期主要讲组合分析(计数和枚举) 以及组合优化的一部分(线性规划的单 纯形解法) 组合分析是组合算法的基础

前言 • 本学期主要讲组合分析（计数和枚举） 以及组合优化的一部分（线性规划的单 纯形解法）。 • 组合分析是组合算法的基础

前 组合数学经常使用的方法并不高深 复杂。最主要的方法是计数时的合理分 类和组合模型的转换 但是,要学好组合数学并非易事, 既需要一定的数学修养,也要进行相当 的训练

前言 组合数学经常使用的方法并不高深 复杂。最主要的方法是计数时的合理分 类和组合模型的转换。 但是，要学好组合数学并非易事， 既需要一定的数学修养，也要进行相当 的训练

第一章排列组合 1.1加法法则与乘法法则

第一章 排列组合 1.1 加法法则与乘法法则

1.1加法法则与乘法法贝 加法法则]设事件A有m种产生方式 事件B有n种产生方式,则事件A或B之 有m+n种产生方式 集合论语言: 若|A|=m,B|=n,A⌒B=⑧,则 A∪B|=m+n

1.1 加法法则与乘法法则 [ 加法法则 ] 设事件A有m种产生方式， 事件B有n种产生方式，则事件A或B之一 有m+n种产生方式。 集合论语言： 若 |A| = m , |B| = n , AB =  , 则 |AB| = m + n