资源描述
,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第一章习题,1.证任一正整数,n,可唯一地表成如下形式：,n=,a,i,i!,0,a,i,i,i1,2,。,解,2.,证,nC(n-1,r)=(r+1)C(n,r+1).,并给出组合意义。,解,3.证,kC(n,k)=n2 。,解,4.有,n,个不同的整数，从中取出两组来，,要求第一组数里的最小数大于第二组的最大数。问有多少种方案？,解,i1,i1,k,n-1,5.六个引擎分列两排，要求引擎的点火的次序两排交错开来，试求从一特定引擎开始点火有多少种方案。,解,6.,试求从1到1000000的整数中，0出现了多少次？,解,7.,n,个男,n,个女排成一男女相间的队伍，试问有多少种不同的方案？若围成一圆桌坐下，又有多少种不同的方案？,解,8.,n,个完全一样的球，放到,r,个有标志的盒子,nr,要求无一空盒，试证其方案数为,().,解,n-1,r-1,9.设,n=p,1,p,2,p,l,p,1,、p,2,、p,l,是,l,个不同的素数，试求能整除尽数,n,的正整数数目.,解,10.试求,n,个完全一样的骰子掷出多少种不同的方案？,解,11.凸10边形的任意三个对角线不共点，试求这凸10边形的对角线交于多少个点？又把所有对角线分割成多少段？,解,12.试证一整数是另一个整数的平方的必要条件是除尽它的数目为奇数。,解,a,1,a,2,a,l,13.统计力学需要计算,r,个质点放到,n,个盒子里去,并服从下列假定之一，问有多少种不同的图象。假设盒子始终是不同的。(,a),Maxwell-Boltzmann,假定：,r,个质点是不同的，任何盒子可以放任意数个.(,b),Bose-Einstein,假定：,r,个质点完全相同，每一个盒子可以放任意数个.,(,c),Fermi-Dirac,假定：,r,个质点都完全相同，每盒不超过一个.,解,14.从26个英文字母中取出6个字母组成一字，若其中有2或3个母音，问分别可构成多少个字(不允许重复,)？,解,15.,给出,()(),+,()(),+,()(),+,()(),=,(),的组合意义。,解,16.给出,(),+,(),+,(),+,(),=,(),的组合意义。,解,n,m,r,0,n-1,m-1,n-2,m-2,n-m,0,n+r+1,m,r+1,1,r+2,2,r+m,m,r,r,r+1,r,r+2,r,n,r,n+1,r+1,17.证明：,解,()(),+,()(),+,()(),+,()(),=2,(),18.从,n,个人中选,r,个围成一圆圈，问有多少种不同的方案？,解,19.分别写出按照字典序由给定排列计算其对应序号的算法及由给定序号计算其对应排列的算法。,(解略),20.(,a),按照第19题的要求，写出邻位对换法(排列的生成算法之二)的相应算法。(,b),写出按照邻位对换法由给定排列生成其下一个排列的算法。,(解略),m,0,m,n,m,1,m,2,m,n,m,n,m-1,n-1,m-2,n-2,m-n,0,n,21.对于给定的正整数,n,证明当,22.(,a),用组合方法证明 和 都是整数,.,(,b),证明 是整数.,解,23.(a),在2,n,个球中,有,n,个相同,求从这2,n,个 球中选取,n,个的方案数。(,b),在3,n+1,个球中，有,n,个相同，求从这3,n+1,个球中选取,n,个的方案数。,解,k=,n-1,2,n,2,n+1,2,时，,C(n,k),是最大值。,解,若,n,是奇数,若,n,是偶数,(2n)!(3n)!,2 2 3,n n n,(n)!,(n!),n+1,2,24.证明在由字母表0,1,2生成的长度为,n,的字符串中.(,a)0,出现偶数次的字符串有个；(,b),(),2,+,(),2,+,(),2 =，其中,q=2 .,解,25.5,台教学机器,m,个学生使用，使用第1台和第2台的人数相等，有多少种分配方案？,解,n,0,n,2,n,q,3+1,2,3+1,2,n,n-1,n-q,n,n,n,2,26.在由,n,个0及,n,个1构成的字符串中，任意前,k,个字符中，0的个数不少于1的个数的字符串有多少？,解,27.在1到,n,的自然数中选取不同且互不相邻的,k,个数，有多少种选取方案？,解,28.(,a),在5个0，4个1组成的字符串中，出现01或10的总次数为4的，有多少个？(,b),在,m,个0，,n,个1组成的字符串中,出现01或10的总次数为,k,的，有多少个？,解,习题解答,1.,证：,对,n,用归纳法。,题,先证可表示性：,当,n=0,1,时，命题成立。,假设对小于,n,的非负整数，命题成立。,对于,n,设,k!n(k+1)!,即0,n-k!kk!,由假设对,n-k!,命题成立，,设,n-k!=,a,i,i!，,其中,a,k,k-1,n=,a,i,i!+k!，,命题成立。,i=1,k,i=1,k,再证表示的唯一性：,设,n=,a,i,i!=,b,i,i!,不妨设,a,j,b,j,令,j=maxi|a,i,b,i,a,j,j!+a,j-1,(j-1)!+a,1,1!,=b,j,j!+b,j-1,(j-1)!+b,1,1!,(a,j,-b,j,)j!=,(,b,i,-,a,i,)i!j!,ii!,|,b,i,-,a,i,|i!,(,b,i,-,a,i,)i!,另一种证法：令,j=mini|a,i,b,i,a,i,i!=,b,i,i!,两边被(,j+1)!,除,得余数,a,j,j!=b,j,j!,矛盾.,i=1,k,i=1,k,i=1,j-1,i=1,j-1,i=1,j-1,i=1,j-1,ij,ij,2.,证：,题,组合意义：,等式左边：,n,个不同的球，先任取出1个，再从余下的,n-1,个中取,r,个；,等式右边：,n,个不同球中任意取出,r+1,个，并指定其中任意一个为第一个。显然两种方案数相同。,nC(n-1,r)=n =,(n-1)!(r+1)n!,r!(n-r-1)!(r+1)r!(n-r-1)!,=(r+1)C(n,r+1).,(r+1)n!,(r+1)!(n-r-1)!,3.,证：,题,设有,n,个不同的小球，,A、B,两个盒子,A,盒中恰好放1个球,B,盒中可放任意个球。有两种方法放球：先从,n,个球中取,k,个球(,k1),再从中挑一个放入,A,盒,方案数共为,kC(n,k),其余球放入,B,盒。先从,n,个球中任取一球放入,A,盒，剩下,n-1,个球每个有两种可能，要么放入,B,盒，要么不放，故方案数为,n2 .,显然两种方法方案数应该一样。,k=1,n,n-1,4.,解：,设取的第一组数有,a,个,第二组有,b,个,而要求第一组数中最小数大于第二组中最大的，即只要取出一组,m,个数(设,m=a+b,),从大到小取,a,个作为第一组,剩余的为第二组。此时方案数为,C(n,m)。,从,m,个数中取第一组数共有,m-1,中取法。总的方案数为(,m-1)C(n,m)=n,2 +1,.,题,5.,解：,第1步从特定引擎对面的3个中取1个有,C(3,1),种取法，第2步从特定引擎一边的2个中取1个有,C(2,1),种取法，第3步从特定引擎对面的2个中取1个有,C(2,1),中取法，剩下的每边1个取法固定。,题,所以共有,C(3,1)C(2,1)C(2,1)=12,种方案。,m=2,n,n-1,6.,解：,首先所有数都用6位表示，从000000到999999中在每位上0出现了10 次,所以0共出现了6,10,次,0出现在最前面的次数应该从中去掉，000000到999999中最左1位的0出现了10 次，000000到,099999,中左数第2位的0出现了10 次，000000到009999左数第3位的0出现了10 次,000000到000999左数第4位的0出现了10 次,000000到000099左数第5位的0出现了10 次,000000到000009左数第6位的0出现了10 次。另外1000000的6个0应该被加上。所以0共出现了 6,10 10 10 10 10 10 10+6=488895次。,5,5,5,4,3,2,1,0,5,5,4,3,2,1,0,题,7.,解：,把,n,个男、,n,个女分别进行全排列，然后按乘法法则放到一起，而男女分别在前面,应该再乘2,即方案数为2,(n!),个.围成一个圆桌坐下，根据圆排列法则，方案数为2,(n!),/,(2n),个.,题,8.,证：,每个盒子不空，即每个盒子里至少放一个球，因为球完全一样，问题转化为将,n-r,个小球放入,r,个不同的盒子，每个盒子可以放任意个球，可以有空盒，根据可重组合定理可得共有,C(n-r+r-1,n-r)=C(n-1,n-r),中方案。根据,C(n,r)=C(n,n-r),可得,C(n-1,n-r)=C(n-1,n-1-(n-r)=C(n-1,r-1),个方案。证毕。,题,2,2,9.,解：,每个能整除尽数,n,的正整数都可以选取每个素数,p,i,从0到,a,i,次，即每个素数有,a,i,+1,种选择，所以能整除,n,的正整数数目为(,a,1,+1),(,a,2,+1),(,a,l,+1),个。,题,10.,解：,相当于把,n,个小球放入6个不同的盒子里，为可重组合，即共有,C(n+6-1,n),中方案，即,C(n+5,n),中方案。,题,11.,解：,根据题意,每4个点可得到两条对角线,1个对角线交点,从10个顶点任取4个的方案有,C(10,4),中,即交于210个点。,11.(续前页)根据图论知识，每个对角线交点有4个度，每个顶点去掉与相邻两个顶点的连线还有7个度，可以得到210,4+10 7 2,12.,证：,根据第9题的结论，,n=p,1,p,2,p,l,能被(,a,1,+1),(,a,2,+1),(,a,l,+1),个数整除，而,n=p,1,p,2,p,l,能被(2,a,1,+1),(2,a,2,+1),(2,a,l,+1),个数整除，2,a,i,+1,为奇数(,0,il)，,所以乘积为奇数。证毕。,题,=455条边,题,a,1,a,2,a,l,2,2,a,1,2,a,2,2,a,l,13.,解,：,题,(,a),每个质点放入盒子都有,n,种选择，,r,个质点共有,r,种不同的图案。(,b),可重组合，共有,C(n+r-1,r),种图案。(,c),一般组合问题，共有,C(n,r),种图案。,14.,解：,题,其中有2个母音可构成,C(21,4)C(5,2)6!,个字。其中有2个母音可构成,C(21,3)C(5,3)6!,个字。,n,15.解：,题,如图：,-r-1 -1 0 m-n x,y,m,A(-1,m),B(m-n,m),可看作是格路问题：左边第,i,项为从点,C,到点(-1,i),直接经过(0,i),的路径,再到点,B,的所有路径数。左边所有项的和就是从,点,C,到,B,的所有路径数即为右边的意义。,C(-r-1,0),16.,解：,C(n+1,r+1),是指从,n+1,个元素,a,1,a,2,a,n+1,中任取,r+1,个进行组合的方案数。左边：若一定要选,a,n+1,则方案数为,C(n,r).,若不选,a,n+1,一定要选,a,n,则方案数为,C(n-1,r).,若不选,a,n+1,a,n,a,r+2,则方案数为,C(r,r).,题,所有这些可能性相加就得到了总方案数。,17.,证：,组合意义,右边：,m,个球,从中取,n,个,放入两个盒子,n,个球中每个球都有两种放法,得到可能的方案数。左边：第,i,项的意义是一个盒子中放,i,个,另一个盒子放,n-i,个,所有的方案数相加应该等于右边。,17.(续前页)数学证明：左边=,C(m,k)C(m-k,n-k),=,=,=,C(m,n),=2 C(m,n)=,右边 证毕。,题,k=0,n,m!(m-k)!,k!(m-k)!(n-k)!(m-n)!,k=0,n,k=0,n,m!n
展开阅读全文