组合数学第三节

1,第一章：排列与组合,1.1基本计数法则1.2一一对应:1.3排列与组合1.4圆周排列1.5排列的生成算法1.6允许重复的组合与不相邻的组合1.7组合意义的解释1.8应用举例1.9*Stirling公式,2,例如：从1,2,3中取两个数的组合，原来是1，2，1，3，2，3，,如果允许重复，多了1，1，2，2，3，3。,1.6.1允许重复的组合,1.6允许重复的组合与不相邻的组合,组合模型:是两个无标志的球放进三个有区别的盒子的情况，一个盒子中可放一个，也可以放多个。,组合模型是r个无标志的球放进n个有区别的盒子的情况:一个盒子中可放一个，也可以放多个。,3,定理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个我们按顺序给出),由于允许重复，因此有a1a2ar。,首先证明每个n取r可重复组合，都对应着不同的从n+r-1中取r个的不允许重复的组合。,从a1,a2,ar构造序列a1,a2+1,a3+2,ar+(r-1),1.6允许重复的组合与不相邻的组合,4,(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允许重复的组合与不相邻的组合,5,显然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),不妨设b1b2brn+r-1。,对应于从n个元素中取r个作允许重复的组合,1.6允许重复的组合与不相邻的组合,6,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)。,7,1.6.3线性方程的整数解的个数问题:,x1+x2+xn=b,n和b都是非负整数;求方程的非负整数的解的个数.,允许重复的组合模型是r个无标志的球放进n个有区别的盒子的情况:,方程的非负整数的个数与b个无标志的球放进n个有区别的盒子的情况一一对应.,C(n+b-1,b),8,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的一个多重排列；,9,(m+n)!,/(m!n!),=C(m+n,m)=C(m+n,n),1.7组合的解释,10,1.22(P64)求图1.22中从O到P的路径数,(a)必须经过A点；(b)必须过道路AB(c)必须过A和C(d)道路AB封锁,O,P,解：(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组合的解释,11,1.32C(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组合的解释,12,1.33C(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组合的解释,13,1.35C(m,0)+C(m,1)+C(m,2)+C(m,m)=2m,123m-2m-1m,没有0，C（m,0）,只有一个0，C（m,1）,只有二个0，C（m,2）,.,M个全是0，C（m,m）,1.7组合的解释,14,1.35C(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组合的解释,15,1.35C(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组合的解释,*,16,1.8：应用举例,等同于：某保密装置须同时使用若干把不同的钥匙才能打开。现有人，每人持若干把钥匙。当且仅当人到场，所备钥匙才能开锁。,例1-41:7位科学工作者从事一项机密的研究技术，他们的实验室装有“电子锁”，每位参加该项工作的人都有一把打开“电子锁”用的钥匙，为了安全起见，当且仅当有4人到场方可打开实验室的门，试问该“电子锁”必须具备多少特征？每位科学工作者的“钥匙”应具有多少这些特征？,问至少有多少把不同的钥匙？每人至少持几把钥匙？,17,解：,设有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：应用举例,18,任一人对于其他人中的每人，都至少有把钥匙与之相配才能开锁；,存不存在有一人对于其他6人中的两组，都用一把钥匙这种情况呢？,每人至少持几把钥匙？,任一人对于其他人中的每人，都至少有把钥匙与之相配才能开锁。故每人至少持C(6,3)20把不同的钥匙。,例如A对于B,C,D与E,F,G都用一把钥匙；,不能是同一把钥匙；,1.8：应用举例,19,为加深理解，举一个较简单的例子:人中须人到场，所求如上；,解：每2人至少缺把钥匙，且每2人所缺钥匙不同。故至少共有C(4,2)=6把不同的钥匙；,任一人对于其他3人中的每2人，都至少有把钥匙与之相配才能开锁。故每人至少持C(3,2)3把不同的钥匙。,1.8：应用举例,20,例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：应用举例,21,(2)编码中的纠错功能,编码中的纠错功能是这样处理的，如果收到a=a1a2an假设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：应用举例,22,码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：应用举例,23,(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：应用举例,*,24,1.9司特林（Stirling公式）,*,25,例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例题,26,1.9例题,1.15试求从1到1000的整数中，0出现的次数。,解：先将1到999的整数都看作3位数,例如2就看作是002，这样从000到999。0出现了多少次呢？,3102，某一位取0，其它各位任取。,0出现在最前面的次数应该从中去掉,000到999中最左1位的0出现了102次，000到099中左数第2