组合数学参考答案及解析卢开澄第四版修改版.doc

《组合数学参考答案及解析卢开澄第四版修改版.doc》由会员分享，可在线阅读，更多相关《组合数学参考答案及解析卢开澄第四版修改版.doc（44页珍藏版）》请在三一文库上搜索。

1、 .wd.1.1 题从1，2，50中找两个数a，b，使其满足1|a-b|=5；2|a-b|5；解：1：由|a-b|=5a-b=5或者a-b=-5，由列举法得出，当a-b=5时，两数的序列为6，17，250，45，共有45对。当a-b=-5时，两数的序列为1，6，2，745，50也有45对。所以这样的序列有90对。2：由题意知，|a-b|5|a-b|=1或|a-b|=2或|a-b|=3或|a-b|=4或|a-b|=5或|a-b|=0；由上题知当|a-b|=5时有90对序列。当|a-b|=1时两数的序列有1，2，3，4，2，11，249，50，50，49这样的序列有49*2=98对。当此类推当|a

2、b|=2，序列有48*2=96对，当|a-b|=3时，序列有47*2=94对，当|a-b|=4时，序列有46*2=92对，当|a-b|=0时有50对所以总的序列数=90+98+96+94+92+50=5201.2题5个女生，7个男生进展排列，(a) 假设女生在一起有多少种不同的排列(b) 女生两两不相邻有多少种不同的排列(c) 两男生A和B之间正好有3个女生的排列是多少解：a可将5个女生看作一个单位，共八个单位进展全排列得到排列数为：8！5！，b用x表示男生，y表示空缺，先将男生放置好，共有8个空缺， Y X Y X Y X Y X Y X Y X Y X Y在其中任取5个得到女生两两不相邻

3、的排列数： C8，57！5！c先取两个男生和3个女生做排列，情况如下： 6. 假设A，B之间存在0个男生，A，B之间共有3个人，所有的排列应为 P6=C(5,3)*3!*8!*2 1假设A，B之间存在1个男生，A，B之间共有4个人，所有的排列应为 P1= C(5,1)*C(5,3)*4!*7!*2 2假设A，B之间存在2个男生，A，B之间共有5个人，所有的排列应为 P2=C(5,2)*C(5,3)*5!*6!*2 3假设A，B之间存在3个男生，A，B之间共有6个人，所有的排列应为 P3=C(5,3)*C(5,3)*6!*5!*2 4假设A，B之间存在4个男生，A，B之间共有7个人，所有的排列应

4、为 P4=C(5,4)*C(5,3)*7!*4!*2 5假设A，B之间存在5个男生，A，B之间共有8个人，所有的排列应为 P5=C(5,5)*C(5,3)*8!*3!*2所以总的排列数为上述6种情况之和。1.3题 m个男生，n个女生，排成一行，其中m,n都是正整数，假设(a)男生不相邻; (b)n个女生形成一个整体； (c)男生A和女生B排在一起；分别讨论有多少种方案。解：(a) 可以考虑插空的方法。n个女生先排成一排，形成n+1个空。因为正好m个男生可以插在n+1个空中，形成不相邻的关系。则男生不相邻的排列个数为(b) n个女生形成一个整体有n！种可能，把它看作一个整体和m个男生排在一起，则

5、排列数有(m+1)!种可能。因此，共有种可能。(c)男生A和女生B排在一起，因为男生和女生可以交换位置，因此有2！种可能，A、B组合在一起和剩下的学生组成排列有(m+n-1)！(这里实际上是m+n-2个学生和AB的组合形成的)种可能。共有组合数为1.4题26个英文字母进展排列，求x和y之间有5个字母的排列数解：C24，5*13！1.5题求3000到8000之间的奇整数的数目，而且没有一样的数字。解：根据题意，千位可以从3，4，5，7，6中选取，个位可以从1，3，5，7，9中选取；因此 2*5*8*7+3*4*8*7=12321.6 题计算，11！+22！+33！+。+nn！解：由序数法公式可知

6、1!+1=2!22!+11!+1=3!33！+22！+11！+1=4！nn!+(n-1)(n-1)!+。+22!+11!+1= (n+1)!所以11！+22！+33！+。+nn！=(n+1)!1.7题试证：被2n除尽。证明：因因为(2n-1)!是整数所以能被2n除尽。18题求和的公因数数目。解：因为它们最大公因子为转化为求最大公因子能除尽的整数个数，能除尽它的整数是根据乘法法则，能除尽它的数个数为 41*31=12711.9题试证的正除数的数目是奇数。证明：设有, 则一定有表达式，则可知符合范围的和必成对出现，所以为偶数。又当a=b=n时，表达式=ab仍然成立。所以的正除数的数目是“偶数为奇数

7、1.10题证任一正整数n可唯一地表成如下形式:,0aii,i1,2,。证：对n用归纳法。先证可表示性：当n=0,1时，命题成立。假设对小于n的非负整数，命题成立。对于n,设k!n(k+1)!,即0n-k!kk! 由假设对n-k!,命题成立，设，其中akk-1,，命题成立。再证表示的唯一性：设, 不妨设ajbj,令j=maxi|aibiajj!+aj-1(j-1)!+a11! =bjj!+bj-1(j-1)!+b11!, 矛盾，命题成立。1.11题证明nC(n-1,r)= (r+1)C(n,r+1),并给予组合解释.证：所以左边等于右边组合意义：等式左边：n个不同的球，先任取出1个，再从余下的

8、n-1个中取r个；等式右边：n个不同球中任意取出r+1个，并指定其中任意一个为第一个。所以两种方案数一样。1.12题证明等式：证明：1.13题有N个不同的整数，从中间取出两组来，要求第1组的最小数大于另一组的最大数。解题思路：取法由大到小第1步：从N个数由大到小取一个数做为第一组，其它N-1个数为第二组，组合数为：cn,1*c(n-1,1)+c(n-1,2)-+c(n-1,n-1)第2步：从N个数由大到小取两个数做为第一组，其它N-2个数为第二组，组合数为：cn,2*c(n-2,1)+c(n-2,2)-+c(n-2,n-2)第n-2步：从N个数由大到小取n-2个数做为第一组，其它2个数为第二组

9、组合数为：cn,n-2*c(2,1)第n-1步：从N个数由大到小取n-1个数做为第一组，其它1个数为第二组，组合数为：cn,n-1*c(1,1总的组合数为：1.14 题6个引擎分列两排，要求引擎的点火顺序两排交织开来，试求从特定一引擎开场有多少种方案解：第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种方案。1.15题求1至1000000中0出现的次数。解：当第一位为0时，后面6位组成的数可以从1-1

10、00000，共100000个0；当第二位为0时，当第一位取0-9时，后面5位可以取1-9999，此外当第一位取0时，后面5位还可以取为10000，这样共有9999*10+1=99991个0；同理第三位为0时，共有99901个0；第四位为0时，共有99001个0；第五位为0时，共有90001个0；第六位为0时，只有1个0；这样总共的0数为：100000+99991+99901+99001+90001+1=488895。1.16题n个一样的球放到r个不同的盒子里，且每个盒子里不空的放法。解：如果用“O表示球，用“|表示分界限，就相当于用r-1个“|把n个“O分成r份，要求是每份至少有一个球。如以以

11、以下图所示： 00|00000000|00000000|00000|000000对于第一个分界限，它有n-1种选择，对于第二个分界限只有n-2个选择，(因为分界限不能相临，如果相临它们之间就没有了球，这不合要求)，依次第r-1个分界限只有n-(r-1)种选择。但是这样的分法中存在重复，重复度为(r-1)!,所以总得放法为：(n-1)*(n-2)*(n-r+1)/(r-1)!=C(n-1,r-1)。1.18题8个盒子排成一列，5个有标志的球放到盒子中，每盒最多放一个球，要求空盒不相邻，问有多少种排列方案解：要求空盒不相邻，这样球的位置共有8种。而不同标志的球的排列有。所以共有8*5！种排列。8种

12、排列如下两类。因为要求空盒不相邻，途中1代表球a) 1 1 1 1b) 1 1 1 1在a)中剩下的一个球有四种位置，b)中剩下的一个球也有四种位置，两者合起来一共有8种1.17题和都是正整数，而且，试证以下等式：解：(a) 等式成立。(b) 等式成立。(c) 等式成立。(d) (e)利用(d)的结论可证明此题。1.19题n+m位由m个0，n个1组成的符号串，其中nm+1,试问不存在两个1相邻的符号串的数目。解：m个0进展排列，留出m+1个空挡，任选n 个空挡放1，共有C(m+1,n)种方案. 1.21题一个盒子里有7个无区别的白球，5个无区别的黑球，每次从中随机取走一个球，前面取走6个，其中

13、3个是白的，试问取第6个球是白球的概率。解：C6,2*C(5,2)*C(5,3)/C(5,3)C(7,3)C(6,3)=3/141.20 题甲单位有10个男同志，4个女同志，乙单位有15个男同志，10个女同志，由他们产生一个7人的代表团，要求其中甲单位占4人，而且7人中男同志占5人，试问有多少中方案解：1.甲单位出4个男同志，乙单位出1个男同志，从乙单位出2个女同志 C(10,4)*C(15,1)*C(10,2)=1417502. .甲单位出3个男同志，乙单位出2个男同志，从甲单位出1个女同志,从乙单位出1个女同志。C(10,3)*C(15,2)*C(4.1)*C(10,1)=5040003.

14、 .甲单位出2个男同志，乙单位出3个男同志，从甲单位出2个女同志. C(10,2)*C(15,3)*C(4,2)=1228501+2+3即为所求，总的方案数为768600PCAB1.22题求图1-22中从O到P的路经数:(a) 路径必须经过A点; (b) 路径必须过道路AB;(c) 路径必须过A和C (d) 道路AB封锁(但A,B两点开放)解: (a)分两步走O(0,0)A(3,2)A(3,2)P(8,5)，根据乘法法则:(b)分两步走O(0,0)A(3,2),B(4,2)P(8,5)，根据乘法法则:(c)分三步走: O(0,0)A(3,2),A(3,2)C(6,3), C(6,3)P(8,5

15、), 根据乘法法则: dAB封锁路径数加必经AB路径数即O(0,0)P(8,5)的所有路径数有加法法则可得：1.23题令s=1,2,n+1,n2,T=(x,y,z)|x,y,zs, xz, yz,试证:证明：要确定x,y,z的取值，有两种方法，(1)可先确定z,由题意可得当z=2时，x可取1，y可取1，根据乘法法则，x,y取值共有11=12种可能；当z=3时，x可取1,2，y可取1,2，根据乘法法则，x,y取值共有22=22种可能；当z=4时，x可取1,2,3，y可取1,2,3,根据乘法法则，x,y取值共有33=32种可能；当z=n+1时，x可取1,2,n,y可取1,2,n,根据乘法法则，x,

16、y取值共有nn=n2种可能。根据加法法则，当z取2,3,n+1时，x,y取值共有种可能。故。(2)由xz, yz，可以分为三种情况：x=yz,x,y可看作一个元素，这种情况等价于从1,2,n+1中取2个进展组合，然后对比大小，小者为x(y),大者为z,其组合数为；xyz,等价于从1,2,n+1中取3个进展组合，然后对比大小可得x,y,z,其组合数为；yxz,等价于从1,2,n+1中取3个进展组合，然后对比大小可得x,y,z,其组合数为。所以满足题意的x,y,z的组合数为+。由于这两种方法是等价的，故可得。证毕。1.24题A=(a, b)|a, bZ, 0a9,0b5 (a) 求x-y平面上以A

17、作顶点的长方形的数目.(b) 求x-y平面上以A作顶点的正方形数目.解(a)：如图(a)，从图中可以看出，对于x-y平面上满足题意的任一顶点A(a,b),除它本身以外，横坐标取值有9种可能，纵坐标取值有5种可能。顶点A(a,b)与和它不在同一水平线或垂直线上的任一点(x,y)均可构成一个长方形。故满足要求的长方形的数目为95=45个。解(b)：如以以以下图(b)，网格左边是b的取值，下面是a的取值。网格里是x-y平面上对应每个顶点A(a,b)所得的正方形的数目。1.26题 S=1,2,，1000，a,bS,使ab0 mod 5,求数偶a,b的数目解：根据题意，ab可以整除5，2*C200，1*

18、1000=4000001.25题平面上有15个点P1,P2。15，其中P1P2P3P4P5共线，此外不存在3点共线的。 (1)求至少过15个点中两点的直线的数目(2)求由15个点中3点组成的三角形的数目解：1)由题意知：P1P2P3P4P5共线，此外不存在3点共线的，所以与这五点分别相连的其他的十点的直线数目为：5*10=50。另外十个点两两相连得直线数目为：C102=45又因为P1P2P3P4P5共线，所以可算作一条至少2点相连的直线所以至少过15个点中两点的直线的数目=50+45+1=962)有三种情况a：没有P1P2P3P4P5这五个点的三角个数：C103=120b：有这五个点的其中一个

19、点：5*C102 225c：有着五个点的两个点：10*C52=100由15个点中3点组成的三角形的数目=425故数目为C(15,2)-C(5,2)+1(b) C(5,0)C(10,3)+C(5,1)C(10,2)+C(5,2)C(10,1)1.27 题 6位男宾，5位女宾围一圆桌而坐，1女宾不相邻有多少种方案2所有女宾在一起有多少种方案3一女宾A和两位男宾相邻又有多少种方案解：1假设5位女宾不相邻，先考虑6位男宾围圆桌而做的方案数，然后女宾插入Q6，6*6*5*4*3*2=864002把5位女宾看成一个整体，然后插入Q6，6P(6,5)=864003P6，2*Q9，9=1940001.28题k

20、和n都是正整数，kn位来宾围着k张圆桌而坐，试求其方案数。解：假设每个圆桌的的人数相等，则每个桌子有n个人。因为圆周排列的个数为因此此题的结果为。1.29 题从n个对象中取个r做圆排列，求其方案数目。1=r=n解：c(n,r)*Qr,r =c(n,r)*(r-1)!1.31题试证任意r个相邻数的连乘： 被r！除尽.证明：由 Pn ,r=n*(n-1)n-r+1可知：n+1n+2n+r= pn+r,r=cn+r,r* r!所以 n+1n+2n+r/r!= pn+r,r/ r! = cn+r,r故任意个相邻数连乘可被r！除尽。130题1=n/r， 1rn；2=n-r+1/r, 1rn；(3) =n

21、/(n-r) , 0rn；解：1：n!/(r!(n-r)!) n/r=n/r*(n-1)!/(r-1)!(n-r)!)= n!/(r!(n-r)!)=上式所以两式相等2：n!/(r!(n-r)!)(n-r+1)/r=n-r+1/r*(n!)/(r-1)!(n-r+1)!)= n!/(r!(n-r)!)=上式所以两式相等3：n!/(r!(n-r)!)n/n-r=n-1!/(r!(n-r-1)!)= n!/(r!(n-r)!)=上式所以两式相等1.32题在a, b, c, d, e, f, x, x, x, y, y的排列中，要求y必须夹在两个x之间，问这样的排列数等于多少解：满足y必须加在两个x

22、之间应为 x y x y x 然后再把a ，b ，c ，d ，e ，f插入，a插入时有6种选择，b插入时有7种选择，c插入时有8种选择，d插入时有9种选择，e插入时有10种选择，f插入时有11种选择，由此可得排列数N=11*10*9*8*7*6=11!/5!1.33题r，n，k都是正整数，将r个无区别的球放在n个有标志的盒子里，每盒至少k个球，试问有多少种方案解：首先从r个球中取出nk个球放入n个盒中，因为球是无区别的。因此只有一种排列方案。剩下的球，每个球放的时候都有n中可能。因此方案数为.1.34 题在r,s,t,u,v,w,x,y,z的排列中求y居于x和z中间的排列数解： 2*5+4+3

23、2+1*6！=24301.35题凸十边形的任意三条对角线不共点。试求这凸十边形的对角线相交于多少个点解：根据题意，1个顶点有7条对角线，与它相邻的顶点有7条对角线，这样的点2个；与它不相邻的顶点有6条对角线有1条与它重复的，这样的点8个；因此2* C7，1* C7，1+8* C6，1* C7，1*9+1 =43401.36题试证一整数是另外一整数的平方的必要条件是除尽他的数的数目是整数证明：设N=P1a1 P2a2。Pnan，P1，P2，。Pn是n个不同的素数，每个能整除尽数n的正整数都可以选取每个素数Pi从0到ai次，即每个素数都有ai+1种选择，所以能整除n的正整数的数目为(a1+1)(

24、a2+1)。(ai+1)个。而设M=N2=P12a1 P22a2。Pn2an，能被(2a1+1)(2a2+1)。2(ai+1)个整除。所以一整数是另外一整数的平方的必要条件是除尽他的数的数目是整数。1.37题.给出+=的组合意义。解： Y Bm,n+r+1-m P P(k,r) 0 k m X如上图所示，表示0，0点到P点的路径数；P点到P点只有一步；=表示P点到B点的路径数;表示0，0点到B点的路径数。所以0点到B点的路径由0点到P点再从P点到P点，最后从P点到达B点。*1*=+=1.41 题分别写出按照字典序，有给定排列计算其对应序号的算法及有给定序号计算其对应排列的算法。解：利用“字典序

25、法生成下一排列的算法，计算该排列的对应序号，生成排列序号算法：设 int M为每一排列的对应序号初始时：P1_P2_.Pi-1_Pi_Pi+1_.Pn_ (其中P1_ P2_.Pi-1_ Pi_ Pi+1_Pn_)M =1初始化I. 满足关系式Pj-1Pj 的j的最大值，设为i , 即i=max j | Pj-1Pj II. 满足关系式Pi-1Pk 的k的最大值，设为j, 即j=max j | Pi-1PkIII. 使Pi-1与 Pj 互换得(p_)= P1_P2_.Pi-1_Pi_Pi+1_.Pn_IV. (p_)= P1_P2_.Pi-1_Pi_Pi+1_.Pn_ 中的Pi_Pi+1_.P

26、n_局部的顺序逆转，得下一排列。V. 判断(p_)排列是否与给定排列一样，一样则输出M， ELSE M=M+1 GOTO 2给定序列号计算排列算法：设 Int M为每一排列的对应序号，M=N N为给定序号设 Int K为循环次数FOR K=1；K+；K =N 满足关系式Pj-1Pj 的j的最大值，设为i , 即i=max j | Pj-1Pj 满足关系式Pi-1Pk 的k的最大值，设为j, 即j=max j | Pi-1=r 得： C(m,0)C(m,n)=C(m,n)C(n,0)同理： C(m,1)C(m-1,n-1)=C(m,n)C(n,1) C(m,n)C(m-n,0)=C(m,n)C(

27、n,n)由上知：左边=C(n,0)+C(n,1)+ +C(n,n)C(m,n) 由=C(n,0) +C(n,1)+C(n,2)+C(n,n)令x=y=1 可得 C(n,0) +C(n,1) +C(n,2) +C(n,n)=左边=2nC(m,n)=右边命题得证。1.40题从n个人中选r个围成一圆圈，问有多少种不同的方案解：圆排列:共有P(n,r)/r种不同的方案。1.48题在由n个0及n个1构成的字符串中，在任意前k个字符中，0的个数不少于1的个数的字符串有多少解：转化为格路问题(弱领先条件),即从(0,0)到(n,n),只能从对角线上方走,可以碰到对角线,故方案数为C(2n,n)-C(2n,n

28、1。1.42题(a) 按照1.41的要求，写出邻位对换法排列的生成算法之二的相应算法.(b) 写出按照邻位对换法由给定排列生成其下一个排列的算法.解：1：给定排列求相应序号：设 Int I为每一排列的对应序号 I=1 初始化假定A1：n和E2：n；D2：n；B1：n都是整数数组，其中B1：n为给定序列2：给定序号求相应排列：设 Int I为每一排列的对应序号 I=1 初始化 M为给定序列号 M=N假定A1：n和E2：n；D2：n；都是整数数组(a) 由给定排列生成其下一个排列的算法1.43题对于给定的正整数N，证明，当时，C(N,K)是最大值。证明：要证明CN，K是最大值，只需证明CN，K大

29、于CN，K-1即可根据以往证明大小值的经历，可以用相减或是相除的方法来证明，就此题，相减不适宜，采用相除可以消除等式中的一些项CN，K/ CN，K-1=N！/K！N-K！*K-1！N-K+1！/N！ =N-K+1/K当n为偶数，k=n/2时N-K+1/K=n+2/n*2/n=n+2/n 1当n为奇数,k=(n-1)/2时N-K+1/K=(n+3)/2) * (2/(n-1)=1+4/(n-1) 1当n为奇数, k=(n+1)/2时N-K+1/K=(n+1)2) * (2/(n+1) =1综上所述,当n取以上三种情况, CN，K取最大值1.46题证明在由字母表0,1,2生成的长度为n的字符串中.

30、a)0出现偶数次的字符串有个；(b) ，其中. 证：(a)归纳法：当n=1时,0出现偶数次的字符串有(31+1)/2=2个(即1,2),成立。假设当n=k时,0出现偶数次的字符串有(3k+1)/2种。总的字符串有3种。0出现奇数次的字符串有(3k-1)/2种。当n=k+1时，0出现偶数次的字符串包括两局部：n=k时,0出现偶数次再增加一位不是0的，共有2(3k+1)/2种，0出现奇数次再增加一位0,共有(3k-1)/2种。所以共有2(3k+1)/2+(3k-1)/2=(3k+1+1)/2种，证毕。(b) 等式左边第m项是0出现m次的字符串数，总和就是0出现偶数次的字符串数，右边由(a)得是0

31、出现偶数次的字符串数，两边显然相等。1.44题a用组合方法证明和都是整数。b证明是整数。解：(a)方法一：因为：所以是整数，因此是整数。方法二：设有2n个不同球放入n个不同的盒子里，每盒两个，这个方案数应该是整数。对2n个球进展排列得到方案数为(2n)!。而把2个球放入同一个盒子里不计顺序，应该把全排列数除掉这些重复计算的次数，n个盒子内部的排列共重复计算了2 次。得到2n个不同球放入n个不同的盒子里，每盒两个的方案数假设有3n个不同的球,放入n个不同盒子,每个盒子放三个，这个方案应该是整数。对这3n个球进展排列得到方案数为(3n)!。而把3个球放入同一个盒子里不计顺序，应该把全排列数除掉这些

32、重复计算的次数，n个盒子内部的排列共重复计算了3！次。得到3n个不同的球放入n个不同的盒子里，每盒三个的方案数(b) 有个不同的球，放入n个一样的盒子里，每盒n个，求方案数，方案数应该是一个整数。按前面(a)的方法，应该得到(n2)!/(n!)n是整数。另外由于n个盒子一样，放入不同的盒子是没有区别的，应该把n个盒子的排列数n!除去。因此得到(n2)!/(n!)n+1是整数。1.49 题在1到n的自然数中选取不同且互不相邻的k个数,有多少种选取方案解:设从1-n中选取互不相邻的k个数的方案为g(n,k)。假设选n，则方案为g(n-2,k-1),假设不选n,则方案数位g(n-1,k).显然g(n

33、k)=g(n-2,k-1)+g(n-1,k)，且只有当n2k-1时,g(n,k)0,否则g(n,k)=0,可给定初始值g(2k-1,k)=1,g(2k-2,k)=0.1.45题(a) 在2n个球中，有n个一样. 求从这2n个球中选取n个的方案数.(b) 在3n+1个球中，有n个一样. 求从这3n+1个球中选取n个的方案数.解(a：有n个一样就有n个不一样取n个不一样和0个一样的为C(n,n), 取n-1个不一样的球和1个一样的球为C(n,n-1)，等等。所以总的方案数为解(b：方法同上，方案数为由于C(2n+1,0)=C(2n+1,2n+1), ,C(2n+1,n)=C(2n+1,n+1)则

34、1.47题5台教学机器m个学生使用，使用第一台和第二台的人数相等，有多少种分配方案解：当使用第1台机器的学生为n个时，使用第2台机器的学生也为n,从m个学生中选出2n个使用这两台机器，剩余的学生可以任意使用剩下的机器的组合数为C(m,2n)C(2n,n)3(m-2n)。所以总的方案数为1.50题(1)在有5个0，4个1组成的字符串中，出现01或10的总次数为4的字符串，有多少个(2)在有m个0，n个1组成的字符串中，出现01或10的总次数为k的字符串，有多少个解：(1)、先将5个00000排成一排，1假设插在两个0中间，即：“010则出现2个“01或“10；假设插在两端，则出现1个“01或“1

35、0；要使出现“01，“10总次数为4，有两种方法：1、把两个1插入0的空当内，剩下的1插入1的后面类似010111000。2、把1个1插入0的空当，再取两个1分别插入两端，剩下的1插入1的前面。类似10100011。由1和2得：(2)、m个0产生m-1个空当。假设k为偶数时：要得到出现“01与“10总次数为k，可以先按上题中1的情况讨论，则在m-1个空当中分别插入个1即可，也就是。剩下的1若何插入的问题与书P20页的定理1.2类似(在n个不同元素中取r个允许重复的组合，其组合数为Cn+r-1,r)，在这里无区别的球的个数也就是剩下的1的个数即n-，盒子的个数也就是插入到m-1个空当中的1的个数

36、即)，则得出剩下的1的插入方法有。即第一种情况的总的插入方法为：。同理可得，按2的情况讨论后的第二种情况的总的插入方法为：。1和2得总的插入方法为：。假设k为奇数时：则必有且只有一个1插入字符串的头或尾,剩下的1按照1的方法插入,只有这样才能使k为奇数。所以插入的总方法为：。1.51 题从N=1,2,20中选出3个数，使得没有两个数相邻，问有多少种方案解：相当于从N=1,2,20个数中取3个作不相邻的组合，故方案数为C(20-3+1,3)=C(18,3)种1.52题从s=1,2,n中连取k个数，使之没有两个数相邻，求不同方案数。解：在n个数中选k个数，使之没有两个数相邻，相当于在n-k+1位

37、置中插入k个数，k个数中没有俩个数相邻。有种方案。有定理1.4直接可得。1.53题把n个无区别的球放进有标志1，2，n的n个盒子中，每个盒子可放多于一个球，求有多少种方案解：把n个无标志的球放进n个有标志的盒子中，每个盒子允许多于一个球是允许重复的组合所以是=1.54题.m个1，n个0进展排列，求1不相邻的排列数.设nm.解：相当于n个0排列后,使m个1做不相邻的插入，共产生n+1个位置.第一个1插入有n+1种情况，第二个是n种情况第m个1插入就有n-m+1种情况。所以是n+1nn-1n-m+1，即此题解为pn+1 m。1.55题偶数位的对称数，即从左向右读法与从优向左的读法一样，如3223。

38、试证这样的数可被11整除。证明：根据所有偶数位置上的数字及所有奇数位置上的数字分别相加，再求出两个和的差，如果所得的差能被11整除，那么这个整数必能被11整除。例如12344321，偶数位上是：2，4，3，1。奇数位上是：1，3，4，2因为对称数是偶数个，所以偶数为相加与奇数为相加的和是相等的，他们的差是零，而零能能被任何数整除，所以原题成立。证毕。1.56 题 n个男人与n个女人沿一圆桌坐下，问两个女人之间坐1个男人的方案数。又m个女人n个男人，且mn，沿一圆桌坐下，求无两个女人并坐的方案数。解：根据题意，两个女人之间坐1个男人的方案数Q (n,n)* P(n,n)无两个女人并坐的方案数Q

39、n,n)* P (n,m)1.57 题 n个人分别沿着两张圆坐下，一张r人，另一张个n-r人，试问有多少种不同的方案数解： Cn,r*(r-1)!(n-r-1)!1.58题一圆周上n个点标以。每一点与其它n-1个点连以直线，试问这些直线交于圆内有多少点解：这些直线交于圆内有Cn,4个点每4个点形成矩形，其对角线有一个交点，故圆内交点有：因为四个点连在一起构成一个四边形，这个四边形的对角线相交于一个点，求这些直线交于圆内多少点就是求这些点能构成几个四边形，即转化为从n个点取出四个进展组合2.1题求序列 0，1，8，27，的母函数。解：由序列可得到因为设设由以上推理可知=所以可通过求得得到序列的

40、母函数：2.2题序列，求母函数解： =因为所以所以就是所求序列母函数2.3题母函数，求序列。解：=由得所以由两式相加得：对应序列=11，39，2.4题母函数，求序列。解：=则=2.5题设，其中是Fibonacci数。证明：，n=2.3.4.求的母函数。解：(1).则=则则(2) = = = =2.6题求序列1，0，2，0，3，0，的母函数。解：序列=2.7题设=1/(1-x2)2 求解：设所以 122.8题求以下序列的母函数：(1)1,0,1,0,1,0， (2)0,-1,0,-1,0,-1, (3)1,-1,1,-1,1,-1,解：(1) (2) (3)2.9题设证明：(1)(2) (3)因

41、为，所以有证明12展开(1-x2)G= (1+x)/(1-2x+x2) 当时有(3)=12.10题证明(1) (2) 求H的表达式。证明(1) 设H的第K+1项为h，则h=，设G的前K+1项的和为G，则G=+而+=1+ + + =1+3*2+4*3+(k+2)(k+1) =1+(1+ 2+ 3+k+3+6+3k+2+2+2)注释：均为k项，分别为平方数列，等差数列，常数列=1+k(k+1)(2k+1)+ +2k =1+k = = = hH=(2) 由H=1+4x+10x+20 x+() x+=1+x+对其3次积分得=，对此积分式3次求导得H=( )。求解完毕。2.11题 a=(n+1),G=1+4x+(n+1)x+,证明(1-3x+3x-x)G是一个多项式,并求母函数G。解: G=G =+ G =xG+G(1x)= G=即为所求(13x3xx)=(1x)(13x3xx)G =(1x)G =(1x)=x+1求解完毕。说明：可以由=2.12题a=, =,求序列