组合数学课件第一章 排列组合

组合数学课件

组

合

数

学

组合数学课件

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

组合数学课件

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

4

9

2

38

51

76

组合数学课件

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

组合数学课件

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

组合数学课件

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

组合数学课件

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

组合数学课件

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

组合数学课件

第一章

排列组合

1.1 加法法则与乘法法则

组合数学课件

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

组合数学课件

1.1 加法法则与乘法法则[ 例 ] 某班选修企业管理的有 18 人，不选 的有 10 人，则该班共有 18 + 10 = 28 人。 [ 例 ] 北京每天直达上海的客车有 5 次，客 机有 3 次， 则每天由北京直达上海的旅行 方式有 5 + 3 = 8 种。

组合数学课件

1.1 加法法则与乘法法则[ 乘法法则 ] 设事件A有m种产生式， 事件B有n种产生方式，则事件A与B有 m· n种产生方式。集合论语言： 若 |A| = m , |B| = n , A B = {(a,b) | a A,b B}, 则 |A B| = m · 。 n

组合数学课件

1.1 加法法则与乘法法则[例] 某种字符串由两个字符组成，第一个 字符可选自{a,b,c,d,e},第二个字符 可选自{1,2,3},则这种字符串共有5 3 = 15 个。 [例] 从A到B有三条道路，从B到C有两条 道路，则从A经B到C有3 2=6 条道路。

组合数学课件

1.1 加法法则与乘法法则 例 某种样式的运动服的着色由底色和装 饰条纹的颜色配成。底色可选红、蓝、

橙、黄，条纹色可选黑、白，则共有4 2 = 8种着色方案。 若此例改成底色和条纹都用红、蓝、橙、 黄四种颜色的话，则，方案数就不是4 4 = 16, 而只有 4 3 = 12 种。 在乘法法则中要注意事件 A 和 事件 B 的 相互独立性。

组合数学课件

1.1 加法法则与乘法法则例 1)求小于10000的含1的正整数的个数 2)求小于10000的含0的正整数的个数 1)小于10000的不含1的正整数可看做4位数, 但0000除外. 故有9×9×9×9-1=6560个. 含1的有：9999-6560=3439个另: 全部4位数有10 个,不含1的四位数有9 个, 含1的4位数为两个的差: 104-94= 3439个4 4

组合数学课件

2)“含0”和“含1”不可直接套用。0019含1但不含0。 在组合的习题中有许多类似的隐含的 规定，要特别留神。 不含0的1位数有9个，2位数有9 2 个， 3 4 3位数有9 个，4位数有9 个 不含0小于10000的正整数有 2 3 4 5 9+9 +9 +9 =(9 -1)/(9-1)=7380个 含0小于10000的正整数有 9999-7380=2619个