《组合数学讲》PPT课件.ppt

前言,组合数学是一个古老而又年轻的数学分支。据传说，大禹在4000多年前就观察到神龟背上的幻方.,幻方可以看作是一个3阶方阵，其元素是1到9的正整数，每行、每列以及两条对角线的和都是15。,5,1,9,3,7,2,4,8,6,前言,1666年莱布尼兹所著组合学论文一书问世，这是组合数学的第一部专著。书中首次使用了组合论（Combinatorics）一词。组合数学的蓬勃发展则是在计算机问世和普遍应用之后。由于组合数学涉及面广，内容庞杂，并且仍在很快地发展着，因而还没有一个统一而有效的理论体系。这与数学分析形成了对照。组合数学研究的中心问题是按一定规则将一些事物安排成各式各样模式的问题。包括安排的存在问题、计数问题、构造问题以及给出了优化标准后如何求出最优安排问题。,前言,组合数学经常使用的方法并不高深复杂。最主要的方法是计数时的合理分类和组合模型的转换。但是，要学好组合数学并非易事，既需要一定的数学修养，也要进行相当的训练。,第一章排列与组合,1.1 加法法则与乘法法则.加法法则 设事件A有m种产生方式，事件B有n种产生方式，则事件A或B之一有m+n种产生方式。,集合论语言：若|A|=m,|B|=n,AB=,则|AB|=m+n。,第一章排列与组合,例 某班选修企业管理的有 18 人，不选的有 10 人，则该班共有 18+10=28 人。,例 北京每天直达上海的客车有 5 次，客机有 3 次，则每天由北京直达上海的旅行方式有 5+3=8 种。,第一章排列与组合,乘法法则 设事件A有m种产生式，事件B有n种产生方式，则事件A与B有 m n种产生方式。,集合论语言：若|A|=m,|B|=n,AB=(a,b)|a A,b B,则|A B|=m n。,第一章排列与组合,例 某种字符串由两个字符组成，第一个字符可选自a，b，c，d，e，第二个字符可选自1，2，3，则这种字符串共有5 3=15 个。,例 从A到B有三条道路，从B到C有两条道路，则从A经B到C有32=6 条道路。,第一章排列与组合,例 某种样式的运动服的着色由底色和装饰条纹的颜色配成。底色可选红、蓝、橙、黄，条纹色可选黑、白，则共有42=8种着色方案。若此例改成底色和条纹都用红、蓝、橙、黄四种颜色的话，则方案数就不是4 4=16，而只有 4 3=12 种。在乘法法则中要注意事件 A 和 事件 B 的相互相容性。,第一章排列与组合,例 1)求小于10000的含1的正整数的个数 2)求小于10000的含0的正整数的个数,1)小于10000的不含1的正整数可看做4位数,但0000除外.故有999916560个.含1的有：99996560=3439个,另:全部4位数有104 个,不含1的四位数有94个,含1的4位数为两个的差:10494=3439个,第一章排列与组合,2)“含0”和“含1”不可直接套用。0019含1但不含0。在组合的习题中有许多类似的隐含的规定，要特别留神。,不含0的1位数有9个，2位数有92个，3位数有93个，4位数有94个,不含0小于10000的正整数有9+92+93+94=(951)/(91)=7380个,含0小于10000的正整数有 99997380=2619个,第一章排列与组合,1.2排列与组合,定义：从n个不同的元素中，取r个不重复的元素，按次序排列，称为从n个中取r个的排列。其排列的个数记为P(n,r)表示。,第一章排列与组合,规定：,从n个不同元中取n个的排列称为n的全排列,第一章排列与组合,我们有下列排列与组合的计数公式：,特别地，对于全排列有P(n,n)=n!。,第一章排列与组合,从n个中取r个的排列的典型例子是从n个不同的球中,取出r个,放入r个不同的盒子里,每盒1个。第1个盒子有n种选择，第2个有n-1种选择，第r个有n-r+1种选择。故有P(n,r)=n(n-1)(n-r+1)有时也用nr记P(n,r),第一章排列与组合,若球不同，盒子相同，则是从n个中取r个的组合的模型。若放入盒子后再将盒子标号区别，则又回到排列模型。每一个组合可有r!个标号方案。,故有 C(n,r)r!=P(n,r),第一章排列与组合,例 有5本不同的日文书，7本不同的英文书，10本不同的中文书。1)取2本不同文字的书；2)取2本相同文字的书；3)任取两本书请问有多少种不同的取法？,解：1)57+510+710=155;2)C(5,2)+C(7,2)+C(10,2)=10+21+45=76;,第一章排列与组合,例 从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)+1003=1485100,第一章排列与组合,定义：从n个不同元素中允许重复地取r个元素作排列，称为n元可重r-排列，其排列数为nr例：由数字1，2，3可组成多少个两位数？并写出这些两位数。解：这是三元可重2-排列问题。其排列数为32=9。这些两位数为11,12,13,21,22,23,31,32,33。,n1个a1,n2个a2,nk个ak的全排列的个数为:,第一章排列与组合,定义：从n 个不同元素中取r个元素围成一圈，称为从n个不同元中取r个元的圆排列，其排列数记为K(n,r)。我们有：,这是因为r个不同的线排列（即一般的排列）对应于一个圆排列。,第一章排列与组合,例：4个女生和4个男生围圆桌相间而坐，试问有多少种不同的入座方式？解：先让女生入座，这是一个4的圆排列问题。有K（4，4）4!=4！/44!=3！4!。例:由四种颜色的珠子各一颗，可以做成多少种不同的项链？解：注意项链可以翻转。,第一章排列与组合,定义：从n个不同元中允许重复地取r个元的组合，称为n元可重r-组合，其组合数记为F(n,r)。用集合描述为：重集a1,a2,an的r-组合数为F(n,r)。,结论：F(n,r)=C(n+r-1,r)，其中n,r均为正整数。,证明要点：设a1,a2,ar是从1,2,n中任取的一个可重r-组合，不妨设：1a1 a2 ar n从而有：1a1 a2+1 a3+2 ar+r-1 n+r-1,第一章排列与组合,例:某车站有6个入口处，每个入口处每次只能进一人，一组9个人进站的方案有多少？,解一进站方案表示成：其中“0”表示人，“1”表示门框，其中“0”是不同元，“1”是相同元。给“1”n个门只用n-1个门框。任意进站方案可表示成上面14个元素的一个排列。,第一章排列与组合,解法1标号可产生5!个14个元的全排列。故若设x为所求方案，则 x5!=14!x=14!/5!=726485760,解法2在14个元的排列中先确定“1”的位置，有C(14,5)种选择，在确定人的位置，有9！种选择。故C(14,5)9!即所求,第一章排列与组合,解法3把全部选择分解成若干步，使每步宜于计算。不妨设9个人编成1至9号。1号有6种选择；2号除可有1号的所有选择外，还可（也必须）选择当与1号同一门时在1号的前面还是后面，故2号有7种选择；3号的选择方法同2号，故共有8种。以此类推，9号有14种选择。故所求方案为67 814种。,第一章排列与组合,1.3模型转换,“一一对应”概念是一个在计数中极为基本的概念。一一对应既是单射又是满射。如我们说A集合有n个元素|A|=n，无非是建立了将A中元与1,n元一一对应的关系.在组合计数时往往借助于一一对应实现模型转换。比如要对A集合计数，但直接计数有困难,于是可设法构造一易于计数的B，使得A与B一一对应。,第一章排列与组合,例 在100名选手之间进行淘汰赛(即一场的比赛结果，失败者退出比赛),最后产生一名冠军，问要举行几场比赛？解 一种常见的思路是按轮计场，费事。另一种思路是淘汰的选手与比赛(按场计)集一一对应。99场比赛。,第一章排列与组合,例,第一章排列与组合,无论怎样走法，在x方向上总共走m步，在y方向上总共走n步。若用一个x表示x方向上的一步，一个字母y表示y方向上的一步。则(0,0)(m,n)的每一条路径可表示为m 个x与n个y的一个有重排列。将每一个有重排列的x与y分别编号，可得m!n!个m+n元的无重全排列。,第一章排列与组合,设所求方案数为P(m+n；m，n)则P(m+n；m，n)m!n!=(m+n)!故P(m+n;m,n)=()=()=C(m+n,m),(m+n)!m!n!,m+n n,m+n m,第一章排列与组合,例：在上例的基础上若设mn，求(0,1)点到(m,n)点不接触对角线x=y的格路的数目(“接触”包括“穿过”)从(0,1)点到(m,n)点的格路，有的接触x=y，有的不接触。对每一条接触x=y的格路，做(0,1)点到第一个接触点部分关于x=y的对称格路，这样得到一条从(1,0)到(m,n)的格路。,第一章排列与组合,容易看出从(0,1)到(m,n)接触x=y的格路与(1,0)到(m,n)的格路(必穿过x=y)一一对应,第一章排列与组合,若条件改为可接触但不可穿过，则限制线要向下或向右移一格，得xy=1，(0,0)关于xy=1的对称点为(1,-1).,格路也是一种常用模型,第一章排列与组合,例 CnH2n+2是碳氢化合物,随着n的不同有下列不同的枝链：,H|H C H|H,H|H C H|H C H|H,H|H C H|H C H|H C H|H,n=1甲烷 n=2 乙烷 n=3 丙烷,第一章排列与组合,H|H C H|H C H|H C H|H C H|H,H|HH C H|H C C H|H C H|H H,n=4 丁烷 n=4异丁烷,这说明对应CnH2n+2的枝链是有3n+2个顶点的一棵树，其中n个顶点与之关联的边数为4；其它2n+2个顶点是叶子。对于这样结构的每一棵树，就对应有一种特定的化,合物。从而可以通过研究具有上述性质的树找到不同的碳氢化合物CnH2n+2.,第一章排列与组合,1.4全排列的生成算法,就是对于给定的字符集，用有效的方法将所有可能的全排列无重复无遗漏地枚举出来。,全排列的生成算法有许多种，我们仅介绍其中一种-序数法,第一章排列与组合,全排列的生成-序数法,任一自然数n都可以唯一确定一个p进制数,反之也然。,类似地，有,第一章排列与组合,同理,所以,即,第一章排列与组合,不难证明，从0到n!-1的任一个整数m都可唯一地表示为：,所以从0到n!-1的n!个整数与满足上式的序列(an-1,an-2,a2,a1)一一对应。然后我们再从(an-1,an-2,a2,a1)建立与全排列的一一对应关系。,第一章排列与组合,例：m4000，即n14000,第一章排列与组合,现从序列(an-1,an-2,a2,a1)得到生成排列，为了方便起见,不妨今n个对象分别是1,2,n.,建立起对应的规则如下：设序列(an-1,an-2,a2,a1)对应某个排列(p)=p1 p2,pn，其中ai可以看作是排列(p)中数i+1所在位置后面比i+1小的数的个数，也就是排列(p)中从数i+1开始向右统计小于或等于i的数的个数。,第一章排列与组合,以排列4213为例，4后面比它小的数的个数(即a3)为3;3后面比它小的数的个数(即a2)等于0;2后面比它小的数的个数(即a1)为1；排列中比1小的数是没有的故得(p)=(4213)(a3a2a1)(301),我们称a3a2a1为中介数。,第一章排列与组合,1.5组合的生成算法,组合的生成不如排列生成困难今以从1、2、3、4、5、6取3个的组合为例:(1)123，(2)124，(3)125，(4)126，(5)134，(6)135，(7)136，(8)145，(9)146，(10)156，(11)234，(12)235，(13)236，(14)245，(15)246，(16)256，(17)345，(18)346，(19)356，(20)456,第一章排列与组合,从中可得规律：（1）最后一位数最大可达n，倒数第2位最大可达n-1，依此类推倒数第k位(k r)不得超过n-k+1若r个元素的组合用c1c2cr来表示，不妨假定c1c2cr 其中 ck n-r+k，k1,2,r。,(2)当存在cjn-r+j时，其中下标的最大者设为i，即imaxj|cj n-r+j，则作cici+1。与之相应地作ci+1ci+1，ci+2ci+1+1，crcr-1+1,第一章排列与组合,于是我们可得到一般的算法：(1)求满足不等式cin-r+i的最大的下标i，即imaxj|cjn-r+j，(2)cici+1。(3)从i+1位开始途径修改：cjcj-1+1，j=i+1,i+2,r,大家可以思考，从n个不同元中选r个的可重组合的生成？,第一章排列与组合,1.6若干等式及其组合意义,组合意义或组合证明:含意强弱的不同。承认组合证明与其他证明有相同的“合法性”。,1.C(n,r)=C(n,n-r)(1.6.1)从1,n去掉一个r子集，剩下一个(n-r)子集。由此建立C(n,r)与C(n,n-r)的一个一一对应。,第一章排列与组合,2.C(n,r)=C(n-1,r)+C(n-1,r-1)(1.6.2)从1,n取a1,a2,ar.设1a1a2arn,对取法分类：a1=1,有C(n-1,r-1)种方案a11,有C(n-1,r)种方案共有C(n-1,r)+C(n-1,r-1)中方案，,第一章排列与组合,3.()+()+()+()=()(1.6.3),n n+1 n+2 n+r n+r+1n n n n r,也可看做按含1不含1，含2不含2,含r不含r的不断分类,1可从(6.2)推论，也可做一下组合证明从1,n+r+1取a1a2an an+1，设a1a2an an+1，可按a1的取值分类：a1=1,2,3,r,r+1.,第一章排列与组合,选政治局,再选常委,n个中央委员选出l名政治局委员,再从其中选出r名常委选常委,再选非常委政治局委员两种选法都无遗漏,无重复地给出可能的方案，应该相等。,第一章排列与组合,组合证 1,m的所有方案.每一元素都可取或不取两种状态，由乘法原理可知所有状态数为2m.而这些可分解为从m个元素中分别取0个,1个，2个，m个组合的总和。,第一章排列与组合,例某保密装置须同时使用若干把不同的钥匙才能打开。现有人，每人持若干钥匙。须人到场，所备钥匙才能开锁。问至少有多少把不同的钥匙？每人至少持几把钥匙？解 每人至少缺把钥匙，且每人所缺钥匙不同。故至少共有()=35把不同的钥匙。,73,任一人对于其他人中的每人，都至少有把钥匙与之相配才能开锁。故每人至少持()20把不同的钥匙。,一般地,某保密装置安装了一个电子锁.须同时使用若干把不同的钥匙才能打开。现有n人，每人有一把钥匙。必须m人(mn)到场，才能用钥匙开锁。问怎么分配锁的特征和每个的钥匙上的特征?,既然锁比任意m-1把钥匙多一个特征，而任意两个m-1把钥匙组合缺少的特征不同，所以锁的特征至少为C(n,m-1)个。,同样道理，对于m把钥匙中的一把a，加入任意m-1把钥匙必能打开锁，也即剩下的n-1把钥匙中任意m-1把钥匙必然缺少a中的某项特征，所以每把钥匙的特征数至少为C(n-1,m-1)个。,每个锁的特征在钥匙中出现的次数,锁的特征数,上式实际说明了一个构造锁及磁卡的方法。,钥匙特征满足最低要求,以n=5,m=3为为例，在MATLAB输入以下指令：,n=5;m=3;v=nchoosek(1:5,n-m+1)v=1 1 1 1 1 1 2 2 2 3 2 2 2 3 3 4 3 3 4 4 3 4 5 4 5 5 4 5 5 5,123,124,125,134,135,145,235,234,245,345,第一章排列与组合,例设n位长能纠r个错的码字的个数为M，则,n位长的0-1字符串共有2n个。但不能每个串都设为码字，否则失去纠错能力。,第一章排列与组合,Hamming距离:设a=a1a2an，b=b1b2bn是 n位串。则a,b的Hamming距离为,即对应位不同的位的个数。它有如下性质：d(a,b)0(当且仅当a=b时，等号成立)；d(a,b)=d(b,a);d(a,b)+d(b,c)d(a,c),第一章排列与组合,右图表示以a为球心,r位半径的球体中的 串都作为a处理。若规定a是码字，收到a有d(a,a)r 即将a当作a发生最多r个错误。此时两个码字a,b应满足 d(a,b)2r+1。当作a处理的串的个数为,故,第一章排列与组合,另一方面任一串与最近的码字的距离不大于2r，否则此串本身可作为一新的码字，即以2r位半径的各码字为球心，应当使任一串落入某球内，故,故所以结论成立。,