组合数学组合数学第一章.ppt

《组合数学组合数学第一章.ppt》由会员分享，可在线阅读，更多相关《组合数学组合数学第一章.ppt（53页珍藏版）》请在第壹文秘上搜索。

1、一. 组合数学简介 组合数学是一个古老而又年轻的数学分支。 据传说，大禹在4000多年前就观察到神龟背上的幻方. 幻方可以看作是一个3阶方阵，其元素是1到9的正整数，每行、每列以及两条对角线的和都是15。519372486 1666年莱布尼兹所著组合学论文一书问世，这是组合数学的第一部专著。书中首次使用了组合论（Combinatorics）一词。 组合数学的蓬勃发展则是在计算机问世和普遍应用之后，也是计算机科学的重要理论基础之一。 对从事计算机科学技术的人员来讲，若无组合数学的基础，就难以深入地研究与分析计算机中的有关算法。 由于组合数学涉及面广，内容庞杂，并且仍在很快地发展着，因而还没有一个

2、统一而有效的理论体系。这与数学分析形成了对照。 组合数学经常使用的方法并不高深复杂。最主要的方法是计数时的合理分计数时的合理分类类和组合模型的转换。组合模型的转换。 但是，要学好组合数学并非易事，既需要一定的数学修养，也要进行相当的训练。参考书 卢开澄、卢华明编著，组合数学，清华大学出版社第4版。 田秋成等编著，组合数学，电子工业出版社。讲解内容 本学期主要讲组合分析（计数和枚举）。 组合分析是组合算法的基础。第一章排列组合1.1 加法法则与乘法法则1.1 加法法则与乘法法则 加法法则加法法则 设事件A有m种产生方式，事件B有n种产生方式，则事件A或B之一有m+n种产生方式。集合论语言：若 |

3、A| = m , |B| = n , AB = , 则 |AB| = m + n 。1.1 加法法则与乘法法则 例 北京每天直达上海的客车有 5 次，客机有 3 次， 则每天由北京直达上海的旅行方式有5 + 3 = 8 种。1.1 加法法则与乘法法则 乘法法则乘法法则 设事件A有m种产生式，事件B有n种产生方式，则事件A与B有 m n种产生方式。集合论语言：若 |A| = m , |B| = n , AB = (a,b) | a A,b B, 则 |A B| = m n 。1.1 加法法则与乘法法则例 某种字符串由两个字符组成，第一个字符可选自a，b，c，d，e，第二个字符可选自1，2，3，则

4、这种字符串共有5 3 = 15 个。1.1 加法法则与乘法法则 例例 某种样式的运动服的着色由底色和装饰条纹的颜色配成。底色可选红、蓝、橙、黄，条纹色可选黑、白，则共有42 = 8种着色方案。 若此例改成底色和条纹都用红、蓝、橙、黄四种颜色的话，则，方案数就不是4 4 = 16， 而只有 4 3 = 12 种。在乘法法则中要注意事件 A 和 事件 B 的相互独立性。1.1 加法法则与乘法法则例：设某BASIC语言限制标识符，最多由三个字符组成，要求第1个字符必须是26个英文字母中的一个，第2、3个字符可以是英文字母，也可以是阿拉伯数字0,1,2,3,4,9.求标识符的数目。例：长度为n的0，1

5、符号串的数目为多少? 一一对应原理一一对应原理 “一一对应一一对应”概念是一个在计数中极为概念是一个在计数中极为基本的概念。一一对应既是单射又是满基本的概念。一一对应既是单射又是满射。射。 如我们说如我们说A A集合有集合有n n个元素个元素 |A|=n|A|=n，无非，无非是建立了将是建立了将A A中元与中元与1,n1,n元一一对应的元一一对应的关系。关系。 在组合计数时往往借助于一一对应实现在组合计数时往往借助于一一对应实现模型转换。模型转换。 比如要对比如要对A A集合计数，但直接计数有困难，集合计数，但直接计数有困难，于是可设法构造一易于计数的于是可设法构造一易于计数的B B，使得，使

6、得A A与与B B一一对应。一一对应。 例例 在在100100名选手之间进行淘汰赛名选手之间进行淘汰赛( (即一即一场的比赛结果，失败者退出比赛场的比赛结果，失败者退出比赛),),最后最后产生一名冠军，问要举行几场比赛？产生一名冠军，问要举行几场比赛？ 一一对应一一对应例例 含有含有n n个元素的集合的所有子集个数个元素的集合的所有子集个数解解 一种常见的思路是按轮计场，费事。一种常见的思路是按轮计场，费事。 另一种思路是另一种思路是淘汰的选手淘汰的选手与与比赛比赛( (按场计按场计) )集集一一对应一一对应。9999场比赛。场比赛。1.2排列与组合定义定义 从n个不同的元素中，取r个不重复的

7、元素，按次序排列，称为从n个中取r个的无重排列。无重排列的方案数用 P(n,r)表示。1.2排列与组合定义：从n个不同元素中取r个不重复的元素组成一个子集，而不考虑其元素的顺序，称为从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)1.2排列与组合若球不同，盒子相同，则是从n个中取r个的组合的模型。若放入盒子后再将盒子标号区别，则又回到排列模型。每一个组合可有r!个标

8、号方案。故有 C(n,r)r!=P(n,r),C(n,r)=P(n,r)/r!=( )=nr n!r!(n-r)!1.2排列与组合例例 有5本不同的日文书，7本不同的英文书，10本不同的中文书。1)取2本不同文字的书；2)取2本相同文字的书；3)任取两本书1.2排列与组合解解 1) 57+510+710=155; 2) C(5,2)+C(7,2)+C(10,2) =10+21+45=76; 3) 155+76=231=( )5+7+10 21.2排列与组合例例 从1,300中取3个不同的数，使这3个数的和能被3整除，有多少种方案？解解 将1,300分成3类： A=i|i1(mod 3)=1,4

9、,7,298, B=i|i2(mod 3)=2,5,8,299, C=i|i3(mod 3)=3,6,9,300. 要满足条件，有四种解法： 1)3个数同属于A;2)3个数同属于B 3)3个数同属于C;4)A,B,C各取一数.故共有3C(100,3)+100 =485100+1000000=148510031.2排列与组合例例 某车站有某车站有6 6个入口处，每个入口处每个入口处，每个入口处每次只能进一人，一组次只能进一人，一组9 9个人进站的方案有多个人进站的方案有多少？少？解一进站方案表示成：00011001010100其中“0”表示人，“1”表示门框，其中“0”是不同元，“1”是相同元。

10、给“1”n个门只用n-1个门框。任意进站方案可表示成上面14个元素的一个排列。1.2排列与组合标号可产生5!个14个元的全排列。故若设x为所求方案，则 x5!=14! x=14!/5!=7264857601.3 圆周排列将一排列排到一圆周上，称为圆周排列，记为Q(n, r)=P(n,r)/r.1.3 圆周排列例：n对夫妻围一圆桌而坐，求每对夫妻相邻而坐的方案数。1.4 全排列的生成算法 就是对于给定的字符集，用有效的方法将所有可能的全排列无重复无遗漏地枚举出来。 全排列的生成算法全排列的生成算法1.4 全排列的生成算法(A)序数法(B)字典序法(C)换位法1.4.1 字典序法顾名思义就是按照字

11、典的顺序（a-z, 1-9）。以字典序为基础，我们可以得出任意两个数字串的大小。比如 1 1213。 就是按每个数字位逐个比较的结果。对于一个数字串，“123456789”， 可以知道最小的串是 从小到大的有序串“123456789”，而最大的串是从大到小的有序串“*987654321”。这样对于“123456789”的所有排列，将他们排序，即可以得到按照字典序排序的所有排列的有序集合。 由前一个排列到下一个排列的生成算法：设p是1n的一个全排列:p=p1p2.pnS1：求 i=maxj|pjpj+1S2: 找到h=maxk|pipkS3: 对换pi，ph得新排列S4：将新排列从第i+1项开始

12、，之后的所有项的顺序逆转便得下一个排列。1.4.1 字典序法求83964 47521的下一个排列7 5 2 1 7 5 2 1 5 8396 7 215412 4 7例1.4.2 换位法1,2,1,2,n,n的的r-r-组合的第一个是组合的第一个是1,2,1,2,r,r，最后一个是最后一个是n-r+1,n-r+2,n-r+1,n-r+2,n.,n.只要一个组合只要一个组合c c1 1c c2 2c cr r中存在中存在c cj jn-r+j1,有C(n-1,r-1)种方案 共有C(n-1,r)+C(n-1,r-1)中方案，故C(n,r)=C(n-1,r)+C(n-1,r-1)1.7 若干等式及

13、其组合意义 杨辉三角除了(0,0)点，都满足此递推式1.7 若干等式及其组合意义 3.( )+( )+( )+( )=( ) 可从上一等式推论，也可做一下组合证明从1,n+r+1取a1a2anan+1，设a1a2an an+1，可按a1的取值分类：a1=1,2,3,r,r+1.n n+1 n+2 n+r n+r+1n n n n n+1a1=r+1, a2an+1取自r+2,n+r+1 有( )种取法nn也可看做按含1不含1，含2不含2,含r不含r的不断分类1.7 若干等式及其组合意义 4. ( )( )=( )( ) 选政治局,再选常委,n个中央委员选出l名政治局委员,再从其中选出r名常委

14、选常委,再选非常委政治局委员 两种选法都无遗漏,无重复地给出可能的方案，应该相等。n l n n-rl r r l-r1.7 若干等式及其组合意义1.7 若干等式及其组合意义1.7 若干等式及其组合意义 证证2 2 从从n n个元素中取偶数个数的组合数个元素中取偶数个数的组合数（包含（包含0 0）, ,等于取奇数个数的组合数。等于取奇数个数的组合数。 r r为偶数的组合和为偶数的组合和r r为级数的组合之间建为级数的组合之间建立一一对应即可。立一一对应即可。 举例说明1.7 若干等式及其组合意义1.7 若干等式及其组合意义 8. 在7中令r=mn,再将( )换成() 得()=( )( )+( )( )+( )( )m mk m-km+n m n m n m n m 0 0 1 1 m m 1.8 应用举例Hamming距离 设a=a1a2an，b=b1b2bn是n位串，ai,bi=0,1。则a,b的Hamming距离为 d(a,b)=|ai-bi|即对应位不同的位的个数。d(a,b)+d(b,c)d(a,c)d(a,b)=|ai-bi|,d(b,c)=|bi-ci|d(a,b)+d(b,c)=|ai-bi|+|bi-ci|(ai-bi)+(bi-ci)|=d(a,c) ni=1ar上图表示以a为球心,r位半径的球体中的串都作为a处理1.8 应用举例