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

组合数学 清华大学计算机 黄连生 1999年7月 前言 组合数学是一个古老而又年轻的数学分支。 据传说，大禹在4000多年前就观察到神龟背上的幻方…... 前言 幻方可以看作是一个3阶方阵，其元素是1到9的正整数，每行、每列以及两条对角线的和都是15。 前言 贾宪 北宋数学家（约11世纪） 著有《黄帝九章细草》、《算法斅古集》斅 音“笑（“古算法导引”）都已失传。杨辉著《详解九章算法》（1261年）中曾引贾宪的“开方作法本源”图（即指数为正整数的二项式展开系数表，现称“杨辉三角形”）和“增乘开方法”（求高次幂的正根法）。前者比帕斯卡三角形早600年，后者比霍纳（William Geoge Horner，1786—1837）的方法（1819年）早770年。 前言 1666年莱布尼兹所著《组合学论文》一书问世，这是组合数学的第一部专著。书中首次使用了组合论（Combinatorics）一词。 前言 组合数学的蓬勃发展则是在计算机问世和普遍应用之后。由于组合数学涉及面广，内容庞杂，并且仍在很快地发展着，因而还没有一个统一而有效的理论体系。这与数学分析形成了对照。 前言 本学期主要讲组合分析（计数和枚举）以及组合优化的一部分（线性规划的单纯形解法）。 组合分析是组合算法的基础。 前言 组合数学经常使用的方法并不高深复杂。最主要的方法是计数时的合理分类和组合模型的转换。 但是，要学好组合数学并非易事，既需要一定的数学修养，也要进行相当的训练。 第一章 排列组合 1.1 加法法则与乘法法则 1.1 加法法则与乘法法则 1.1 加法法则与乘法法则 1.1 加法法则与乘法法则 例 某种样式的运动服的着色由底色和装饰条纹的颜色配成。底色可选红、蓝、橙、黄，条纹色可选黑、白，则共有4?2 = 8种着色方案。 若此例改成底色和条纹都用红、蓝、橙、黄四种颜色的话，则，方案数就不是4 ? 4 = 16， 而只有 4 ? 3 = 12 种。 在乘法法则中要注意事件 A 和 事件 B 的相互独立性。 1.1 加法法则与乘法法则 例 1)求小于10000的含1的正整数的个数 2)求小于10000的含0的正整数的个数 1.2排列与组合 定义 从n个不同的元素中，取r个不重复的元素，按次序排列，称为从n个中取r个的无重排列。排列的全体组成的集合用P(n,r)表示。排列的个数用P(n,r)表示。当r=n时称为全排列。一般不说可重即无重。可重排列的相应记号为 - P(n,r),P(n,r)。 1.2排列与组合 定义从n个不同元素中取r个不重复的元素组成一个子集，而不考虑其元素的顺序，称为从n个中取r个的无重组合。 组合的全体组成的集合用C(n,r)表示，组合的个数用C(n,r)表示，对应于可重组合 - 有记号C(n,r),C(n,r)。 1.2排列与组合 从n个中取r个的排列的典型例子是从n个不同的球中,取出r个,放入r个不同的盒子里,每盒1个。第1个盒子有n种选择，第2个有n-1种选择，······，第r个有n-r+1种选择。 故有 P(n,r)=n(n-1)······(n-r+1) 有时也用[n]r记n(n-1)······(n-r+1) 1.2排列与组合 若球不同，盒子相同，则是从n个中取r个的组合的模型。若放入盒子后再将盒子标号区别，则又回到排列模型。每一个组合可有r!个标号方案。 故有 C(n,r)·r!=P(n,r), C(n,r)=P(n,r)/r!=[n]r/r!=( )= 易见 P(n,r)=n 1.2排列与组合 例 有5本不同的日文书，7本不同的英文书，10本不同的中文书。 1)取2本不同文字的书； 2)取2本相同文字的书； 3)任取两本书 1.2排列与组合 求r1个1，r2个2，…，rt个t的排列数，设r1+r2+…+rt=n,设此排列数为P(n;r1,r2,…,rt),对1，2，…，t分别加下标，得到 P(n；r1,r2,…,rt)·r1!·r2!·…·rt! = n! ∴P(n；r1,r2,…,rt)= ———— =( ) 1.2排列与组合 从n个中取r个的圆排列的排列数为 P(n,r)/r , 2≤r≤n 以4个元素为例 1.2排列与组合 从n个中取r个的项链排列的排列数为 P(n,r)/2r, 3≤r≤n 项链排列就是说排列的方法和项链一样,在圆排列的基础上，正面向上和反面向上两种方式放置各个数是同一个排列。 例 下面两种方式实