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

组合数学 清华大学计算机黄连生 999年F7月

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

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

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

前言 幻方可以看 作是一个3阶方492 阵,其元素是1 到9的正整数 357 每行、每列以 及两条对角线 16 的和都是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