第四组合数学.ppt

组合数学 组合数学是一门研究离散对象的科学，是计算机的核心课程之一，在众多的计算机系统软件和信息安全软件中都要用到本课程的内容。它是近代密码学和算法的理论基础，在计算机科学的理论体系中占有极其重要的位置。对计算机专业本科的学生进行组合数学教学和训练，为进一步学习计算机算法（组合算法）打下坚实基础。 组合数学是为学习”算法与复杂性分析”作理论的准备。 本课程的学习目的 通过本课程的学习，理解组合理论的基本概念，掌握组合理论的基本方法和技巧，了解一些简单算法，为深入研究、应用组合数学打好基础。 前言 组合数学是一个古老而又年轻的数学分支。 据传说，大禹在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的正整数的个数 排列 排列 排列研究事物的有序安排或有序选择数。 例如：125和251虽然都由1，2，5三个数字构成，但这是两个不同的排列。 分为： 线排列（简单排列，我们高中所学的排列） 圆排列（排列的首尾元素相连） 重排列（排列中的元素可以重复） 组合 组合 组合研究事物的无序安排或无序选择数。 例如：125和251都由1，2，5三个数字构成，被看成是同一个组合。 1.1排列与组合 排列计数定理 P(n,r)=n(n-1)······(n-r+1) = 1.1排列与组合 若球不同，盒子相同，则是从n个中取r个的组合的模型。若放入盒子后再将盒子标号区别，则又回到排列模型。每一个组合可有r!个标号方案。 故有 C(n,r)·r!=P(n,r), C(n,r)=P(n,r)/r!=[n]r/r!=( )= 易见 P(n,r)=n 排列与组合 排列与组合 从n个中取r个的圆排列的排列数为 P(n,r)/r , 2≤r≤n 以4个元素为例 排列与组合 从n个中取r个的项链排列的排列数为 P(n,r)/2r, 3≤r≤n 项链排列就是说排列的方法和项链一样,在圆排列的基础上，正面向上和反面向上两种方式放置各个数是同一个排列。 例 下面两种方式实际上表示的都是3个元素的同一种排列。 排列与组合 1.2一一对应 “一一对应”概念是一个在计数中极为基本的概念。一一对应既是单射又是满射。 如我们说A集合有n个元素 |A|=n，无非是建立了将A中元与[1,n]元一一对应的关系。 在组合计数时往往借助于一一对应实现模型转换。 比如要对A集合计数，但直接计数有困难，于是可设法构造一易于计数的B，使得A与B一一对应。 1.2模型转换 例 1.2 模型转换 无论怎样走法，在x方向上总共走m步，在y方向上总共走n