组合数学一课件.ppt

1,组合数学的应用范畴,第一章:排列与组合 第二章:递推关系与母函数 第三章:容斥原理与鸽巢原理 第四章:Burnside引理与Polya定理 第五章:区组设计 第六章:线性规划 第七章:编码简介 第八章:组合算法简介,2,第一章：排列与组合,1.1 基本计数法则1.2 一一对应:1.3 排列与组合1.4 圆周排列1.5 排列的生成算法1.6 允许重复的组合与不相邻的组合1.7 组合意义的解释1.8 应用举例1.9 *Stirling公式,3,1.1基本计数法则,1、加法法则:如果具有性质A的事件有m个，性质B的事件有n个，则具有性质A或B的事件有m+n个。,A和B是性质无关的两个事件。,4,2、乘法法则:若具有性质A的事件有m个，具有性质B的事件有n个，则具有性质A及B的事件有mn个,1.1基本计数法则,5,例1.1 若从合肥到南京有2条路可走，从南京到上海有3条路可走，从上海到杭州有2条路可走，问从合肥经南京、上海到杭州有多少路可走？,1.1基本计数法则,6,例1.2：用乘法法则解释8卦及64卦。,解：1、太极生两仪,3、四象生八卦 000，001，010, 011 100，101，110, 111,2、两仪生四象 00，01，10，11；,1.1基本计数法则,7,例1.3：长度为n的0,1符号串的数目?,例1.4 人类DNA链的长度为2.11010,链上每一位由T,C,A,G四种化合物组成,求人类DNA链的可组成数目。,1.1基本计数法则,8,例1.5：求布尔函数f(x1,x2,xn)的数目,以n=2为例：,f(x1,x2)有四种方式：f(0,0),f(0,1),f(1,0),f(1,1)。,1、f(0,0)=0,f(0,1)=0,f(1,0)=0,f(1,1)=0。,2、f(0,0)=0,f(0,1)=0,f(1,0)=0,f(1,1)=1。,对应着长度为22的字符串，每一位都可以取0或1;,乘法：222,自变量数为n个时：22n,1.1基本计数法则,*,9,1、从n个数中找出最大值问题 2、n个人参加单淘汰赛，最后产生冠军的过程。,1.2 一一对应,10,例1.6：求n2个人站成一排和站成n排（方阵）的方案数，并比较两种方案数的大小？,解：9个人站成一排的方案数是9!，,设a1a2a3a4a5a6a7a8a9是9个人的一排，,可构成一个方阵a1a2a3a4a5a6a7a8a9,给定一个方阵b1b2b3b4b5b6b7b8b9,也唯一确定一排b1b2b3b4b5b6b7b8b9,因此这两种站位方式的方案数一样多，都是9!,1.2 一一对应,11,例1.6：求n2个人站成一排和站成n排（方阵）的方案数，并比较两种方案数的大小？,9个人站成方阵的方案数为：,C(9,3)3!C(6,3)3!C(3,3)3!,1.2 一一对应,12,定理1.1 n个有标号1,2,n的顶点的树的数目等于nn-2。（n=2）,1,2,5,3,4,设一棵树的顶点集为A 1、从中找到编号最小的叶子结点，去掉该叶子结点a1及其邻接边(a1,b1)。 2、重复以上过程。只到剩一条边为止。,(1,2),(4,3),(3,2),这棵树对应序列（2，3，2）,一个棵对应序列B=b1b2b3bn-2而且是唯一的,1.2 一一对应,13,1,2,5,3,4,树的顶点集合为12345,这棵树对应序列（2，3，2）,任给一个序列Bb1,b2,b3,bn-2 1、从A找到最小的不属于B的元素,设为a1,与b1连接，从A中去掉a1，从B中去掉b1. 2、重复以上过程只到B为空，A中剩余两个 3、连接剩余的两个顶点。,1.2 一一对应,*,14,1.3：排列与组合,1、排列的定义：设A=a1,a2,an是n个不同的元素的集合，任取A中r个元素按顺序排成一列，称为从A中取r个的一个排列，r满足0rn。,从n个不同的球中取一个球放在第一个盒子中， 从余下的n-1个球中取一个球放在第二个盒子中， 从余下的n-(r-1)个球中取一个放在第r个盒子中。,根据乘法法则： P(n,r)=n(n-1)(n-r+1)=n!(n-r)!,15,全排列:P(n,n)=n(n-1)21=n!,1.3：排列与组合,2、组合的定义：当从n个不同元素中取出r个而不考虑它的顺序时,称为从n中取r个的组合,其数目记为C(n,r)。,公式：从n中取r的组合数记作C(n,r) 从n中取r的排列数是P(n,r)。,C(n,r)=P(n,r)/r! =n!/r!(n-r)!,二者之间的关系:,16,第一章：排列与组合,排列可以看作n个不同的元素放进r个不同的盒子的放法.,组合可以看作n个不同的元素放进r个相同的盒子的放法.,公式1：C(n,r)=C(n,n-r),17,从5个元素中取3个进行排列的算法： int a5=1,2,3,4,5,b3； for(i=0;i5;i+) b0=ai; for(j=0;j5;j+) if (j=i) j+; else b1=aj; for(k=0;k5;k+) if(k=i|k=j) k+; else b2=ak; 打印b,1.3：排列与组合,18,例1.7:由5种颜色的星状物,20种不同的花共25个元素中任取5个排成如下图案：两边是星状物,中间是3朵花，问共有多少种这样的图案？,解1：52019184=136800,20种不同的花取3种排列的排列数为：P(20,3)=20!/17!=20*19*18=6840,根据乘法法则，共有图案数为：6840*20=136800,解2：5种颜色的星状物取两个排列的排列数为 P(5,2)=5!/3!=5*4=20,1.3：排列与组合,19,1.8 随机地选择n个人，求n个人至少有两人生日相同的概率(不考虑润年),解:,n个人生日不同的方案数是:,365*364*(365-n+1)=P(365,n),n个人生日的总方案数是:,365n,至少有两人生日相同的概率: 1-P(365,n)/365n,1.3：排列与组合,*,20,1.4：圆周排列,定义：在排列中，如果我们不横排而是将各元素排列在一个圆周上，那么我们称这种排列方式为圆周排列。,在排列中1234,2341,3412,4123为四个不同的排列，而在圆排列中这些排列是一个.,规定相对位置不变算一个排列。,21,将从n中取r个作圆排列的排列数记作Q(n,r)。,从n中取r个作排列，与圆排列相比，重复了r倍；,公式：Q(n,r)=P(n,r)/r，,Q(n,n)=P(n,n)/n=n!/n=(n-1)!,1.4：圆周排列,Q(n,r)=P(n,r)/r=n!/r(n-r)!,22,例1.19：5颗不同的红色珠子，3颗不同的蓝色珠子装在圆板的四周,试问有多少种方案？若蓝色珠子不相邻又有多少种排列方案？蓝色珠子在一起又如何？,解：(1)Q(8,8)=P(8,8)/8=7!。,(3)蓝色珠子在一起 Q(6,6)3!=5!3!。,(2) 蓝色珠子不在一起。,首先5颗不同的红色珠子作圆排列，共有 Q(5,5)=4!，,3颗不同的蓝色珠子排在红色珠子中间,4!543,1.4：圆周排列,*,23,例1.20：5对夫妇出席一宴会，围一圆桌而坐，试问有几种不同的方案？若要求每对夫妻相邻又有多少种方案?,解： 1）座位无限制 Q(10,10)=P(10,10)/10=10!/10=9!=362880 共有362880种方式。,2）夫妇相邻而坐 首先可以将一对夫妇作为一个元素来看待，共有Q(5,5)=P(5,5)/5=24。,但夫妇可以交换坐位，5对夫妇共有25种方式。,根据乘法法则：若夫妻相邻而坐，共有 2425=2432=768种方式。,1.4：圆周排列,*,24,第一章：排列与组合,多重集的排列,设S是一个多重集，有K个不同类型的元素，各元素的重复分别为n1,n2,nk,n=n1+n2+nk,则S的排列数为:,25,第一章：排列与组合,证明：给定多重集S，有k种类型的元素，比如说a1,a2,a3,ak,且分别有重数n1,n2,nk,元素的总个数n=n1+n2+nk,现在存在n个位置,我们要在n个位置放S的一个元素,首先要确定哪些位置放a1的元素,共有,剩下n-n1个位置, a2的元素,共有,.,剩下n-n1-nk-1个位置, ak的元素,共有,26,第一章：排列与组合,根据剩法法则:,S的排列的总数,27,练习题,1、求1040和2030的公因数的数目。,解：1040=240540，2030=260530,C(41,1)*C(31,1),28,2、试证n2的整除数的数目是奇数。,练习题,29,1.13、有n个不同的整数，从中取出两组来，要求第1组的最小数大于另一组的最大数。,设取的第一组数有a个,第二组有b个,要求第一组数中最小数大于第二组中最大的，,即只要取出一组m个数(设m=a+b),从大到小取a个作为第一组,剩余的为第二组。,此时方案数为C(n,m)。,从m个数中取第一组数共有m-1中取法。,(m-1)C(n,m),练习题,30,练习题,31,第一章：排列与组合,1.1 基本计数法则1.2 一一对应:1.3 排列与组合1.4 圆周排列1.5 排列的生成算法1.6 允许重复的组合与不相邻的组合1.7 组合意义的解释1.8 应用举例1.9 *Stirling公式,32,1.5 排列的生成算法：,排列的生成算法: 对于给定的字符集，用有效的方法将所有可能的排列无重复无遗漏地枚举出来。,3阶幻方九宫图,33,从5个元素中取3个进行排列的算法： int a5=1,2,3,4,5,b3； for(i=0;i5;i+) b0=ai; for(j=0;j5;j+) if (j=i) continue; else b1=aj; for(k=0;k5;k+) if(k=i|k=j) continue; else b2=ak; 打印b,1.3：排列与组合,34,n个元素的全排列有n!个,从0到n!-1共n!个数。,序数法的思想：,n个元素的全排列与n!个数一一对应。,序数法找到了一种n!个数直接计算出n!个排列的算法：,1、0到n!-1这n!个数与如下序列一一对应：,（an-1，an-2，a1） 0aii；,2、从每一个这样的序列我们可以生成一个排列。,一、序数法,35,公式：n!-1=(n-1)(n-1)!+(n-2)(n-2)!+22!+ 11!,等同于：n!=(n-1)(n-1)!+(n-2)(n-2)!+22!+ 11!+1,一般: (k-1)(k-1)!+(k-1)!=k! (n-2)(n-2)!+(n-2)!=(n-1)! (n-1)(n-1)!+(n-1)!=n!,一、序数法,36,定理3：令n0,0mn!-1，则m可以唯一地表示为：m=an-1(n-1)!+an-2(n-2)!+a11! 其中：0aii, i=1, 2, , n-1。（一） ai由m唯一确定。 （二） 反过来，任何满足上式的数m都是一个大于或等于0，小于或等于n!-1的数。 （三）,最大值是：,最小值是：,0(n-1)!+0(n-2)!+ 01!=0,因此：（三）成立,(n-1)(n-1)!+(n-2)(n-2)!+22!+ 11!=n!-1,一、序数法,37,证明：（二）唯一表示性,设m=an-1(n-1)!+an-2(n-2)!+a11! m=bn-1(n-1)!+bn-2(n-2)!+b11!,显然a1=b1,如果一直到an-1 =bn-1，定理得证：,否则令k=mini,aibi ,那么: ai=bi ,当ik时,如果两边同时除以(k+1)!,我们可以看到等式左边余数为akk!,等式右边余数为bkk!,由akbk,与假设予盾，因此表示法是唯一的。,一、序数法,38,证明：（一）可表示性,怎样求序列an-1, an-2, a1,m=an-1(n-1)!+an-2(n-2)!+a2 2!+ a1 1!,数m除以2的整数部分与余数是什么？,整数部分是：an-1(n-1)!/2+ +a3 3!/2 +a2,余数是a1,如果用m除以2的整数部分再除以3，余数就是a2,其它项以此类推。,一、序数法,39,例 1: 将m=4000展开。40007!=5040解： b=4000,a1=b%2=0; b=b/2=2000;,a2=b%3=2; b=b/3=666;,a3=b%4=2; b=b/4=166; a4=b%5=1; b=b/5=33; a5=b%6=3; b=b/6=5; a6=b%7=5; b=b/7=0;,4000=5*6!+3*5!+1*4!+2*3!+2*2! +0*1!,40005,3,1,2,2,0,一、序数法,40,int a=0;int m,n;/ 0=m=n!-1int b=m；int index =1; do aindex=b%(index+1); b = b/(index+1); index+; while(b);,推论 从0到n!-1的n!个整数与序列an-1, an-2, a1一一对应。这里 0a1 1,0 a2 2, , 0 an-1 n-1,算法:,一、序数法,41,例2:对于0 m 23=4!-1,m可以展开为： m=a33!+a2 2!+a1 1!。 求所有的序列a3, a2,a1 ；,解： 0000, 1001, 2010, 3011, 4020, 5021, 6100, 7101, 8110, 9111, 10120, 11121, 12101, 13201, 14210, 15211 16220, 17221, 18300, 19301, 20301, 21311, 22320, 23321,一、序数法,42,怎样建立a(3)a(2)a(1)p(1)p(2)p(3)p(4)a(3) 确定4的位置,a(2)确定3的位置a(1)确定2的位置,剩余的位置就是1的位置,例3:021,3,2,1,4,一、序数法,例3: 201,4,3,2,1,43,求n个不同的数的全排列，主要有以下两步：,1、求出0到n!-1之间各数对应的序列an-1, an-2, a1 m=an-1(n-1)!+an-2(n-2)!+a2 * 2!+a1*1!,2、由an-1, an-2, a1确定排列序列p1p2pn,an-1,确定n的位置， an-2确定n-1的位置， a1确定2的位置， 剩下的是1的位置。,一、序数法,44,int result17 = 0 ; /记录排序int a17 = 0 ; /记录序列void permute( int n) int fact = 1,i; for( i = 1; i = n; i+ ) fact *= i;/求n的阶乘,1、求阶乘,一、序数法,2022/12/5,45,可编辑,46,for( i = 0; i fact; i+ ) int b=i, index =1; do aindex=b%(index+1); b = b/(index+1); index+; while(b);,2、对于0,1,2,n!-1共n!个数求序列ai,一、序数法,47,int j=0;for(j=n-1;j0;j-)index=n; int spacecount=0; while(ajspacecount|resultindex!=0) if( resultindex=0) spacecount+; index-; resultindex=j+1; ,3、aj确定j+1的位置,一、序数法,48,/最后一个位置是1的位置 index = n; while( resultindex!= 0) index-; result index = 1; / 输出结果 for( j = 1; j = n; j+ ) cout result j endl; result j = 0; ,一、序数法,49,void main() int n;cout n;permute(n);,一、序数法,*,50,字典序法的思想：,对于n个字符的任何二个排列，我们都可以比较它的大小。,1、初始排列我们可以给出来， 1,2,3,n-1,n,二、字典序法,2、设计算法找到比上一个排序大的排列中最小的一个。 1,2,3,n,n-1,3、重复以上过程直到最大。 n,n-1,3,2,1,51,例4：求839647521的下一个排列。,此时5右边为7421，倒置为1247，即得下一个排列:839651247。,只要后边的大数与前面的小数交换，都比原数大，那个是最小的一个。 这一个与下一个有尽可能长的共同前缀，也即变化限制在尽可能短的后缀上。,找到前面数小于后边数的最后一个，4,4与后面比它大最接近他的数交换，5,二、字典序法,52,例4：求839647521的下一个排列。,1：从排列的末尾开始,逐步向前搜索,直到找到比其后面相邻的数小的数:如果未找到,表明不再有下一个排列,程序终止;2：从该数后面的序列中寻找比该数大的最小的数来替换它(使用交换);3：将余下的数反转。,二、字典序法,53,1、求满足关系式pjpj+1的下标j的最大值，设为i , i=maxjpjpj+1 例如： 839647521中i=5 注:该位置值为4,2、求出i后，再求满足关系式pipk的k的最大值，设为h, h=maxkpipk 例如： 839647521中h=7 注:该位置值为5,3、 pi与ph 互换。得新排列P1P2Pi-1PiPi+1Pn 例如： 839647521换成839657421,4、 将新排列P1P2Pi-1PiPi+1Pn中的Pi+1Pn顺序逆转，得到P1P2PiPn Pi+1,二、字典序法,54,void main ()int i,j,k,h,t,n,p100,select; select=1; /*select用于控制是否循环执行程序*/ while (select) printf(“please input an Integer n:”); scanf(%d, ,二、字典序法,55,/求i=maxj|pji) i=j; ,二、字典序法,56,/求h=maxk|pipk*/ k=i+1; h=k; for (;k=n;k+) if (pipk) h=k; ,二、字典序法,57,/pi与ph互换 t=pi; pi=ph; ph=t; /将pi+1pn部分逆转 for (j=i+1;j=(i+1+n)/2;j+) t= pj; pj=pn+i+1-j; pn+i+1-j=t; ,二、字典序法,*,58,1.6.4 组合的生成算法,观察从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,59,1、最后一位数最大是6,倒数第二位最大是5,倒数第三位最大是4。,若r个元素组合用c1c2 cr表示，假定c1c2cr那么crn, cr-1n-1, c1n-r+1,2、若要确定145的下一个组合，,就是要找比145大而又最接近145的数，,那么256的下一个组合是什么呢？,是345。,显然是146；,1.6.4 组合的生成算法,60,3、当存在cjn-r+j时，,例如：456,例如：256，,ci=2,2修改为3，后边两位改为4,5得345；,例如：345， ci=5,5改为6，得346。,其中下标最大者设为i,用ci+1替换ci ,如果ir,再作ci+1= ci+1, ci+2= ci+1+1, cr= cr-1+1；,最后一个；,*,1.6.4 组合的生成算法,61,1.41、分别写出按照字典序,由给定排列计算其对应序号的算法及由给定序号计算其对应排 列的算法。,1234，1243，1324，1342， 1 2 3 4,练习题,62,第一章：排列与组合,1.1 基本计数法则1.2 一一对应:1.3 排列与组合1.4 圆周排列1.5 排列的生成算法1.6 允许重复的组合与不相邻的组合1.7 组合意义的解释1.8 应用举例1.9 *Stirling公式,63,例如：从1,2,3中取两个数的组合，原来是 1，2，1，3， 2，3，,如果允许重复，多了 1，1， 2，2， 3，3。,1.6.1 允许重复的组合,1.6 允许重复的组合与不相邻的组合,组合模型: 是两个无标志的球放进三个有区别的盒子的情况，一个盒子中可放一个，也可以放多个。,组合模型是r个无标志的球放进n个有区别的盒子的情况:一个盒子中可放一个，也可以放多个。,64,定理1.2 在n个不同的元素中取r个进行组合，若允许重复，则组合数为C(n+r-1,r)。,证明：只要证明n取r可重复组合，与从n+r-1中取r个的不允许重复的组合一一对应即可。,设n个元素分别为1,2,3,n。从中取r个作允许重复的组合a1,a2,ar。(假设这r个我们按顺序给出),由于允许重复，因此有a1a2 ar。,首先证明每个n取r可重复组合，都对应着不同的从n+r-1中取r个的不允许重复的组合。,从a1,a2,ar构造序列a1,a2+1, a3+2 ,ar+(r-1),1.6 允许重复的组合与不相邻的组合,65,(ai+i-1)- (ai-1+i-2)= (ai - ai-1)+10，,从n个不同元素中取r个作允许重复的组合,C(n+r-1,r),并且ar+(r-1)n+r-1,因此ak+(k-1)是1到n+r-1中的元素。,1.6 允许重复的组合与不相邻的组合,66,显然br-r+1n, bk-k+1是1到n中的元素，而且(bk-k+1)- bk-1-(k-1)+1= bk- bk-1 -10b1b2-1br-r+1,因此，又得到从n+r-1中取r个作不重复的组合对应于从n个元素中取r个作允许重复的组合。,构造序列b1,b2-1,br-r+1,反过来，要证明从(1,2,n+r-1)中取r个作不允许重复的组合(b1,b2,br),不妨设b1b2 brn+r-1。,对应于从n个元素中取r个作允许重复的组合,1.6 允许重复的组合与不相邻的组合,67,1.6.2 不相邻的组合,例如：从1,2,3,4中取2个的组合如下：1,3,1,4,2,4,1,2,2,3,3,4。,从1,2,3,4中取2个不相邻的组合如下：1,3,1,4,2,4。,1.6 允许重复的组合与不相邻的组合,定理1.4 从1,2,n中取r个作不相邻的组合，其组合数为C(n-r+1,r)。,68,1.6.3 线性方程的整数解的个数问题:,x1+x2+xn=b,n和b都是非负整数;求方程的非负整数的解的个数.,允许重复的组合模型是r个无标志的球放进n个有区别的盒子的情况:,方程的非负整数的个数与b个无标志的球放进n个有区别的盒子的情况一一对应.,C(n+b-1,b),69,1.7 组合的解释,1、路径数问题：如图从(0,0)点出发沿x轴或y轴的正方向每步走一个单位，最终走到(m,n)点，问有多少条路径；,无论怎样走法，在x方向上总共走m步，在y方向上总共走n步，若用一个字母x表示x方向上的一步，一个字母y表示y方向上的一步；,则(0,0)(m,n)的每一条路径可表示为m个x与n个y的一个多重排列；,70,(m+n)!,/(m!n!),=C(m+n,m)=C(m+n,n),1.7 组合的解释,71,1.22(P64) 求图1.22中从O到P的路径数,(a)必须经过A点；(b)必须过道路AB(c)必须过A和C(d)道路AB封锁,解：(a),C(3+2,2),C(5+3,3),(b),C(3+2,2),C(4+3,3),(c),C(3+2,2),C(3+1,1),C(2+2,2),(d),C(8+5,5),-C(3+2,2) C(4+3,3),1,2,3,4,5,1.7 组合的解释,72,1.32 C(n,r)=C(n-1,r)+C(n-1,r-1),(0,0),(n-r,r),(n-r-1,r),(n-r,r-1),1.7 组合的解释,73,1.33 C(n+r+1,r)=C(n+r,r)+C(n+r-1,r-1)+C(n+1,1)+C(n,0),(0,0),(n+1,r),(n,r),(n,0),1.7 组合的解释,74,1.35 C(m,0)+C(m,1)+C(m,2)+C(m,m)=2m,1 2 3 m-2 m-1 m,没有0，C（m,0）,只有一个0，C（m,1）,只有二个0，C（m,2）,.,M个全是0，C（m,m）,1.7 组合的解释,75,1.35 C(m,0)+C(m,1)+C(m,2)+C(m,m)=2m,(m,0),(0,m),从(0,0)点到(m,0)和(0,m)上点的路径总数是2m,(1,m-1),1.7 组合的解释,76,1.35 C(m,0)+C(m,1)+C(m,2)+C(m,m)=2m,二项式定理：设m是一个正整数，则对于所有的x和y, 有： (x+y)m =C(m,0)xm+x(m,1)xm-1y+ C(m,2)xm-2y2+C(m,m-1)xym-1+C(m,m)xym,1.7 组合的解释,*,77,1.8：应用举例,等同于：某保密装置须同时使用若干把不同的钥匙才能打开。现有人，每人持若干把钥匙。当且仅当人到场，所备钥匙才能开锁。,例1-41: 7位科学工作者从事一项机密的研究技术，他们的实验室装有“电子锁”，每位参加该项工作的人都有一把打开“电子锁”用的钥匙，为了安全起见，当且仅当有4人到场方可打开实验室的门，试问该“电子锁”必须具备多少特征？每位科学工作者的“钥匙”应具有多少这些特征？,问至少有多少把不同的钥匙？ 每人至少持几把钥匙？,78,解：,设有A,B,C,D,E,F,G共7人;,如果有两个3人小组所缺钥匙相同，例如A,B,C与A,B,D所缺钥匙相同,每人至少缺把钥匙，,故至少共有C(7,3)=35把不同的钥匙。,每人所缺钥匙是否相同？,将这两组合并A,B,C与A,B,D合并，产生一个至少四个人的小组A,B,C,D，仍然缺一把钥匙，这与假设相矛盾;,至少有多少把不同的钥匙？,1.8：应用举例,79,任一人对于其他人中的每人，都至少有把钥匙与之相配才能开锁；,存不存在有一人对于其他6人中的两组，都用一把钥匙这种情况呢？,每人至少持几把钥匙？,任一人对于其他人中的每人，都至少有把钥匙与之相配才能开锁。故每人至少持C(6,3)20把不同的钥匙。,例如A对于B,C,D与E,F,G都用一把钥匙；,不能是同一把钥匙；,1.8：应用举例,80,为加深理解，举一个较简单的例子:人中须人到场，所求如上；,解：每2人至少缺把钥匙，且每2人所缺钥匙不同。故至少共有C(4,2)=6把不同的钥匙；,任一人对于其他3人中的每2人，都至少有把钥匙与之相配才能开锁。 故每人至少持C(3,2)3把不同的钥匙。,1.8：应用举例,81,例3 若a和b是两个用n位二进制表达的码，设 a=a1a2an，b=b1b2bn其中ai,bi=0,1,i=1,2,n，若aibi的数目为l,则用 d(a,b)=d(b,a)=l称l为a,b码的汉明(Hamming)距离。,1、令c=c1c2cn,ci=0,1,i=1,2,n.证明三角不等式 d(a,b)+d(b,c)d(a,c),证明：,d(a,b)= |ai-bi|,d(a,b)+d(b,c)= |ai-bi|+|bi-ci| =(|ai-bi|+|bi-ci|) (|ai-bi+bi-ci|)=d(a,c),d(b,c)=|bi-ci|,1.8：应用举例,82,(2)编码中的纠错功能,编码中的纠错功能是这样处理的，如果收到 a=a 1a 2a n假设a 与a的汉明距离小于或等于r,则认为a是由a的错误引起的，将它作为a处理。,可能存在a与a和b的汉明距离都小于或等于r,怎么才能避免这种情况呢？对编码有什么要求呢？,码b与码a之间的汉明距离要大于或等于2r+1.,b与a的汉明距离大于或等于2r+1，如果存在a与a的距离小于r,那么a与b的距离大于r。,1.8：应用举例,83,码b与码a之间的汉明距离要大于或等于2r+1.,如果存在a与a的距离小于r,那么a与b的距离大于r。,证明： d(a,a)+d(a,b)d(a,b) d(a,b)d(a,b)- d(a,a) 2r+1-r因此： d(a,b)r+1,这说明：要保证能纠正r个错，码字间的距离必须至少为2r+1.,1.8：应用举例,84,(3)两个n位码字a,b满足d(a,b)2r+1,与码字a的汉明距离小于或等于r的数，也就是当成a处理的字符串；,为了保证码字间的距离不小于2r+1,码字的数目m与码长n之间必须满足不等式；,C(n,0),+C(n,1),+C(n,2),+,+C(n,r),当成a处理的字符串有多少？,mC(n,0)+C(n,1)+C(n,r)2n,1.8：应用举例,*,85,1.9 司特林（Stirling公式）,*,86,例1.15：求小于10000的正整数中含有数字1的数的个数。,解：小于10000的正整数是1到9999，如果我们把不到4位的数前面补零，,例如：2看作0002，22看作0022，222看作0222，,那么小于10000的正整数的个数为104-1=9999个,不包含1的个数为94-1=6560,小于10000的正整数中含有数字1的数的个数为 9999-6560=3449。,1.9 例题,87,1.9 例题,1.15试求从1到1000000的整数中，0出现的次数。,解：先将1到999999的整数都看作6位数,例如2就看作是000002，这样从000000到999999。0出现了多少次呢？,6105，某一位取0，其它各位任取。,0出现在最前面的次数应该从中去掉,000000到999999中最左1位的0出现了105次，000000到099999中左数第2位的0出现了104次，000000到009999左数第3位的0出现了103次,000000到000999左数第4位的0出现了102次,000000到000099左数第5位的0出现了10次,000000到000009左数第6位的0出现了1次。,88,1.9 例题,因此不合法的0的个数为105+104+103+102+101+1=111111，不合法的应该去掉，再加整数1000000中的6个0，这样，从1到1000000的整数中0出现的次数为6105-111111+6=488895。,89,7*,1.9 例题,1.31 试证任意r个相邻数的连乘 (n+1)(n+2).(n+r)=(n+r)!/n!被r!除尽。,从n+r个元素中取r个的组合数，C(n+r,r)=(n+r)!/n!r!,2022/12/5,90,可编辑,