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

一.组合数学简介,组合数学是一个古老而又年轻的数学分支。据传说，大禹在4000多年前就观察到神龟背上的幻方.,幻方可以看作是一个3阶方阵，其元素是1到9的正整数，每行、每列以及两条对角线的和都是15。,5,1,9,3,7,2,4,8,6,1666年莱布尼兹所著组合学论文一书问世，这是组合数学的第一部专著。书中首次使用了组合论（Combinatorics）一词。,组合数学的蓬勃发展则是在计算机问世和普遍应用之后，也是计算机科学的重要理论基础之一。对从事计算机科学技术的人员来讲，若无组合数学的基础，就难以深入地研究与分析计算机中的有关算法。,由于组合数学涉及面广，内容庞杂，并且仍在很快地发展着，因而还没有一个统一而有效的理论体系。这与数学分析形成了对照。,组合数学经常使用的方法并不高深复杂。最主要的方法是计数时的合理分类和组合模型的转换。但是，要学好组合数学并非易事，既需要一定的数学修养，也要进行相当的训练。,参考书,卢开澄、卢华明编著，组合数学，清华大学出版社第4版。田秋成等编著，组合数学，电子工业出版社。,讲解内容,本学期主要讲组合分析（计数和枚举）。组合分析是组合算法的基础。,第一章排列组合,1.1 加法法则与乘法法则,1.1 加法法则与乘法法则,加法法则 设事件A有m种产生方式，事件B有n种产生方式，则事件A或B之一有m+n种产生方式。,集合论语言：若|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，则这种字符串共有,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符号串的数目为多少?,一一对应原理,“一一对应”概念是一个在计数中极为基本的概念。一一对应既是单射又是满射。如我们说A集合有n个元素|A|=n，无非是建立了将A中元与1,n元一一对应的关系。在组合计数时往往借助于一一对应实现模型转换。比如要对A集合计数，但直接计数有困难，于是可设法构造一易于计数的B，使得A与B一一对应。,例 在100名选手之间进行淘汰赛(即一场的比赛结果，失败者退出比赛),最后产生一名冠军，问要举行几场比赛？,一一对应,例 含有n个元素的集合的所有子集个数,解 一种常见的思路是按轮计场，费事。另一种思路是淘汰的选手与比赛(按场计)集一一对应。99场比赛。,1.2排列与组合,定义 从n个不同的元素中，取r个不重复的元素，按次序排列，称为从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!个标号方案。故有 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 2,1.2排列与组合,例 从1,300中取3个不同的数，使这3个数的和能被3整除，有多少种方案？,解 将1,300分成3类：A=i|i1(mod 3)=1,4,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=1485100,3,1.2排列与组合,例 某车站有6个入口处，每个入口处每次只能进一人，一组9个人进站的方案有多少？,解一进站方案表示成：00011001010100其中“0”表示人，“1”表示门框，其中“0”是不同元，“1”是相同元。给“1”n个门只用n-1个门框。任意进站方案可表示成上面14个元素的一个排列。,1.2排列与组合,标号可产生5!个14个元的全排列。故若设x为所求方案，则 x5!=14!x=14!/5!=726485760,1.3 圆周排列,将一排列排到一圆周上，称为圆周排列，记为Q(n,r)=P(n,r)/r.,1.3 圆周排列,例：n对夫妻围一圆桌而坐，求每对夫妻相邻而坐的方案数。,1.4 全排列的生成算法,就是对于给定的字符集，用有效的方法将所有可能的全排列无重复无遗漏地枚举出来。,全排列的生成算法,1.4 全排列的生成算法,(A)序数法(B)字典序法(C)换位法,1.4.1 字典序法,顾名思义就是按照字典的顺序（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项开始，之后的所有项的顺序逆转便得下一个排列。,1.4.1 字典序法,求839647521的下一个排列,7 5 2 1,7,5,2,1,5,8396 7 21,5,4,12 4 7,例,1.4.2 换位法,1,2,n的r-组合的第一个是1,2,r，最后一个是n-r+1,n-r+2,n.只要一个组合c1c2cr中存在cjn-r+j，说明此组合还有下一个组合。求其下一个组合的步骤如下：1）求2）3）,1.5 组合生成算法（r-组合）,1.6 可重组合,允许重复的组合是指从A=1,2,n中取r个元素a1,a2,ar,而且允许ai=aj,ij,1.6 可重组合,可重组合的计数问题相当于r个相同的球放入n个互异的盒子，每盒球的数目允许多于一个的计数。此问题又可转换为r个相同的球与n-1个相同的盒壁的排列的问题。易知所求计数为=C(n+r-1,r),(n-1+r)!r!(n-1)!,r个相同的球/001001100/n-1个相同的盒壁,1.6.1线性方程的整数解的个数问题,线性方程x1+x2+xn=b（n和b都是整数，n1）的非负整数解的个数是（）C(n+b-1,b),1.7 若干等式及其组合意义,1.C(n,r)=C(n,n-r)从1,n去掉一个r子集，剩下一个(n-r)子集。由此建立C(n,r)与C(n,n-r)的一个一一对应。故C(n,r)=C(n,n-r),1.7 若干等式及其组合意义,2.C(n,r)=C(n-1,r)+C(n-1,r-1)从1,n取a1,a2,ar.设1a1a2arn,对取法分类：a1=1,有C(n-1,r-1)种方案 a11,有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 若干等式及其组合意义,杨辉三角除了(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+1,a1=r+1,a2an+1取自r+2,n+r+1 有()种取法,nn,也可看做按含1不含1，含2不含2,含r不含r的不断分类,1.7 若干等式及其组合意义,4.()()=()()选政治局,再选常委,n个中央委员选出l名政治局委员,再从其中选出r名常委选常委,再选非常委政治局委员两种选法都无遗漏,无重复地给出可能的方案，应该相等。,n l n n-rl r r l-r,1.7 若干等式及其组合意义,1.7 若干等式及其组合意义,1.7 若干等式及其组合意义,证2 从n个元素中取偶数个数的组合数（包含0）,等于取奇数个数的组合数。r为偶数的组合和r为级数的组合之间建立一一对应即可。举例说明,1.7 若干等式及其组合意义,1.7 若干等式及其组合意义,8.在7中令r=mn,再将()换成()得()=()()+()()+()(),m mk m-k,m+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=1,a,r,上图表示以a为球心,r位半径的球体中的串都作为a处理,1.8 应用举例,