组合数学第一章.ppt

1、组合数学,2,第一章 组合数学基础,3,1.1 绪论,组合数学又叫组合学、组合论,它是一个历史悠久的数学分支.它起源于数学游戏与人们的休闲.它所研究的中心问题是按照一定的规则来安排一些物件有关的数学问题.,4,5,就是一个3阶幻方.它的和是15.,尽管组合数学历史久远,但蓬勃发展的时期只近半个世纪.自20世纪60年代以来,数字通讯理论、规划论、试验设计等新兴学科发展迅速,特别是计算机科学的巨大发展.大大推动了组合数学的发展,使组合数学成为富有生命力的新兴的数学分支.,6,计算机科学中涉及的算法可分为两类： 第一类是计算方法，它主要解决数值计算，如方程求根、解方程组、求积分等问题，其数学基础是高

2、等数学和线性代数. 第二类是组合算法，它解决搜索、排序、组合优化等问题，其数学基础是组合数学.,按所研究问题的类型，组合数学所研究的内容可化分为：组合计数理论、组合设计、组合矩阵论和组合优化.,组合数学问题求解的方法大致可分为两类：一类是从组合数学基本概念、基本原理出发解题的所谓常规法（基本方法）.另一类是一些特殊方法.,7,解决组合问题常需要特殊的方法,即使是在使用组合数学中的基本原理和方法去解决问题时,仍需要巧妙地应用它们.因此,在解决组合问题时,学习组合数学中典型问题的解题经验和方法是非常重要的.常用的方法有：,（1）数学归纳法,（2）迭代法,（3）一一对应法,（4）组合意义法,（5）数

3、论方法,8,例如:“棋盘覆盖”问题.设mn棋盘,假定有一批外形完全一样的骨牌，每块牌恰好覆盖棋盘上两个相邻的方格.若用一些牌覆盖棋盘,使得棋盘上的所有方格都被牌覆盖，牌之间不交叠，这称之为棋盘的完全覆盖.,9,例如 88棋盘存在完全覆盖,但当88棋盘剪去对角线上两个方格后,是否还存在完全覆盖？这个问题的解答似乎很困难,但用组合分析的方法解决起来很简单：,把棋盘上的方格用黑白两色交替着色,由于任一骨牌必须覆盖一黑一白两个方格,而剪角的棋盘中,被剪掉的两个方格同色, 88棋盘上黑白方格各32个,剪去同色两格后,黑白方格数不相等,从而这样的棋盘不存在完全覆盖.,定理 若m或n为偶数时,则mn棋盘存在

4、完全覆盖.,10,11,12,13,1.2 两个基本法则,加法法则：如果完成一件事情有两个方案，第一个方案有m种方法，第二个方案有n种方法可以实现，只要选择任何方案中的任何一种方法，就可以完成这件事情，并且这些方法互不相同，则完成这件事情共有m + n种方法.,用集合语言描述： 设A、B为两个有限集合，若AB，则 | AB |=| A |+| B |.,1.2.1 加法法则,14,乘法法则：如果完成一件事情需两个步骤，第一步有m种方法，第二步有n种方法去实现，则完成该事情共有mn种方法.,用集合语言描述： 设A、B为有限集合，所有有序对构成的集合 AB=(a, b)|aA，bB 称为A和B的积

5、集(笛卡儿乘积).则有 | AB |=| A | B |.,1.2.2 乘法法则,15,例 1 在1000到9999之间有多少个各位数字不同的奇数?,解 首先, 个位数可取1, 3, 5, 7, 9共五种选择;,其次, 千位数不能是0, 也不能取个位已选定的数, 所以有八种选择;,然后, 百位数有八种选择; 最后, 十位数有七种选择.,由乘法法则,所求的数共有5887=2240个.,16,例 3 求小于10000的正整数中含有数字 1 的数的个数.,解 小于10000的正整数可以看成是由0, 1, 2, 3, 4, 5, 6, 7, 8, 9中取四个数构成的. 但0000不在正整数,17,范围

6、内, 故小于10000的正整数个数为,个.,同理, 四位数中不含1的数的个数为,个.,故小于10000并含有1的正整数个数为,个.,18,1.3 排列与组合,排列组合是组合数学的基本内容之一，它提供了培养“组合思维”与“组合技巧”方面的具体而又直观的模型. 对排列组合的计数方法、技巧以及构造的训练，为以后较为复杂的组合问题奠定了基础.,19,一、排列,定义 从n个元素的集合S中有序选取的r个元素叫做S的一个r-排列,不同排列的总数记作P(n, r)或,1.3.1 相异元素不允许重复的排列数和组合数,如果r = n, 则称这个排列为S的全排列,简称为S,的排列.,20,二、组合,21,将 r 个

7、有区别的球放入n个不同的盒子里，每盒不超过一个，则总的放球方案数为P(n,r)； 若球不加区别，则放球方案数为C(n,r)，这就是排列与组合的数学模型.,相异元素不允许重复的排列与组合问题也可以描述为：,22,如果把集合的元素排成一个圆,这种排列叫圆排列,也叫环排列.若两个圆排列由相同的元素所组成，且其中任何两元素的相对位置保持不变,这样的圆排列认为是同一种排列.,定理 从 n元集S 中不重复地取r 个围成圆排列(叫做圆形r -排列)，则不同的排列总数为,1.3.2 相异元素不允许重复的圆排列,特别，当r = n时，S的圆排列数是(n1)！.,23,例 2 由5个不同颜色的珠子可以做成多少种项

8、链？,解 5个珠子组成的圆排列共有(51)！=24种,但这种计数只考虑了项链的旋转,没有考虑翻转,而,项链翻转还是同一项链，即一个项链对应两个圆排,故只能做24/2 =12种项链.,列，,24,一般地,从n个相异珠子中任取r个组成一个项链,共有,种不同的项链.,25,多重集是元素可以多次出现的集合，把含有k种 不同元素的多重集S记作,是不同的元素,表示,出现的次数，,如果每个元素可以出现无穷多次,则这个多重集记为,使用多重集可以处理允许重复的排列和组合问题.,1.3.3 相异元素允许重复的排列(多重集的排列),26,定义 从n个不同元素中允许重复地选r个元素的排列, 叫做r元重复排列, 其排列

9、总数记为RP(, r) .,注：可重排列对应的模型是将r个不同的球放入n个有区别的盒子里，每个盒子中的球数不加限制且同盒的球不分次序.,27,简记为,1.3.4 不尽相异元素的全排列,28,29,1.3.5 相异元素允许重复的组合问题,30,将可重组合转化为 不可重组合,31,注：重复组合的模型是将r个无区别的球放入n个不同的盒子里，每个盒子的球数不受限制.,32,一个r- n可重组合;,反之,对于S的一个r -n可重组合,证 任取S的一个所求的r可重组合, 在这个组合,中拿走元素 各1个,剩下的元素组成 S 的,33,所以 S 中,加入元素,就得到所求组合.,每个元素至少取一个的r可重组合数

10、等于S的r -n可重,组合数, 这个数为：,34,1.3.6 不尽相异元素任取r个的组合问题,35,36,集合的排列与组合问题，根据选取的元素是否有序与是否可重复而将选取方法划分成以下四类：,集合的排列,集合的组合,多重集的排列,多重集的组合,无序的不允许重复的选取,有序的允许重复的选取,有序的不允许重复的选取,无序的允许重复的选取,37,1.4 组合等式及其组合意义,组合等式是指由若干个组合数构成的一类恒等式.,组合等式的证明方法主要有三种：归纳法、母函数法、组合意义法.,本节主要介绍组合意义法.,组合意义法就是对等式两端作组合解释, 即阐明两端的不同表达式实质是同一组合问题的方案数, 只是

11、按照不同途径进行统计而得(殊途同归), 或者是两个不同组合问题的方案数, 但二者的组合方案之间存在一一对应关系.,38,等式1 对称关系式,等式2 加法公式（杨辉恒等式）,等价形式：,39,等价形式：,40,41,42,分析：将n个人分为三组，使得第一组有r个人,第二组有k- r个人, 第三组有n- k个人. 考虑两种分组方案：,(1)将n个人先给第一组分r个,有C(n,r)种分法；,然后从余下的n - r个人中给第二组分k - r个，有,最后将余下的n - k个人全,部分给第三组.,于是，按这种顺序分组共有,等式3 乘法公式（Newton恒等式）,C(n - r,k - r)种分法；,43,(2) 如果按另一种顺序来分组, 先给第三组分n- k个人, 有C(n, n - k) 种分法；然后从余下的k个人中给第一组分r个人,有C(k, r)种分法；最后将余下的k - r个人全部分给第二组.,于是按这种顺序分组共有,种分法，这恰好是等式的左端.,种分法，这恰好是等式的右端.,44,在具体使用组合意义法证明组合等式时,常常把问题中产生r组合的所有方法看作一个集合,然后用某种规定的方式将此集合分解为若干个不相交的子集，并计算各子集的元素个数,最后用加法