组合数学习题答案卢开澄

111.1题 从中找两个数{a，b}，使其满足 （1）|a-b|=5； （2）|a-b|解（：|a-b|=5a-b=5或者a-b=-，由列举法得出，当a-b=5时，两数的序列为6，（7，）54，共有45当a-b=-5时，两数的序列为，，（4550）也有45对。所以这样的序列有90对。（2|a-b|5|a-b|=1或|a-b|=2或|a-b|=3或|a-b|=4或|a-b|=5或由上题知当|a-b|=590对序列。当|a-b|=1时两数的序列有1，32（，）（4，554）这样的序列有49*2=98对。当此类推当|a-b|=248*2=96|a-b|=347*2=94|a-b|=446*2=92对，当|a-b|=0时有50对所以总的序列数=90+98+96+94+92+50=520题 5个女生个男生进行排列若女生在一起有多少种不同的排列？(b)女生两两不相邻有多少种不同的列？(c)两男生A和B之间正好有3个女生的排列是多少？（）可将58×5x8个空缺，Y X Y X Y X Y X YX YX Y X Y在其中任取5个得到女生两两不相邻的排列数： C（8，5）×7！×5！3个女生做排列，情况如下：6.若A，B之间存在0个男生， A，B之间共有3个人，所有的排列应为 P6=C(5,3)*3!*8!*2若A，B之间存在1个男生， 之间共有4个人，所有的排列应为 P1=C(5,1)*C(5,3)*4!*7!*2若A，B之间存在2个男生之间共有5个人，所有的排列应为 P2=C(5,2)*C(5,3)*5!*6!*2若A，B之间存在3个男生之间共有6个人，所有的排列应为 P3=C(5,3)*C(5,3)*6!*5!*2若A，B之间存在4个男生之间共有7个人，所有的排列应为 P4=C(5,4)*C(5,3)*7!*4!*2若A，B之间存在5个男生之间共有8个人，所有的排列应为 P5=C(5,5)*C(5,3)*8!*3!*2所以总的排列数为上述6种情况之和。题 m个男生，n个女生，排成一行，其中m,n都是正整数，若男生不相邻(mn; (b)n个女生形成一个整体； (c)男生A和女生B排在一起分别讨论有多少种方案。解：(a)可以考虑插空的方法。nn+1个空。因为mn1mn+1个空中，形成不相邻的关系。则男生不相邻的排列个数为pnpn1n mnnm(m+1)!因此，共有n!(m1)!种可能。AB排在一起，因为男生和女生可以交换位置，因此有2A、B(m+n-1)！(这里实际上是m+n-2个学生和AB的组合形成的)种可能。共有组合数为2!(mn1)!题 26个英文字母进行排列，求x和y之间有5个字母的排列解：C（24，5）*13！题 求3000到8000之间的奇整数的数目，而且没有相同的数字。解根据题意千位可以从中选取个位可以从中选取因此 2*5*8*7+3*4*8*7=12321.6题 计算，1·1！+2·2！+3·3！+。。+n·n！解：由序数法公式可知1!+1=2! 2·2!+1·1!+1=3! 3·3！+2·2！+1·1！+1=4！n·n!+(n-1)(n-1)!+。。+2·2!+1·1!+1=(n+1)!所以1·1！+2·2！+3·3！+。。+n·n！=(n+1)!－１1.7(n2)(2n2n除尽。证明：因(2n)!2nn!(2n(n1)(n2)(2n)n!(n1)(n2)(2n)(2n)!(2n1)!!2n 因为(2n-1)!!是整数所以(n1)(n2)(2n)能被2n除尽。题 求1040和2030的公因数数目。解：因为1040240*540240*530*510

2030260*530240*220*530它们最大公因子为240*530转化为求最大公因子能除尽的整数个数，能除尽它的整数是2a*5b,0a40,0b30根据乘法法则，能除尽它的数个数为 41*31=1271题 试证n2的正除数的数目是奇数。证明：设有0annbn2,则一定有表达式n2ab，则可知符合范围的a和b必成对出现，所以为偶数。又当a=b=n时，表达式n2=ab仍然成立。 所以n2的正除数的数目偶数1”为奇数。题 证任一正整数n可唯一地表成如下形式:证：对n用归纳法。n=0,1n的非负整数，命题成立。n,k!≤n＜(k+1)!,0≤n-k!＜k·k!

,0≤ai≤i,i＝1,2,…。由假设对n-k!,命题成立，设 ，其中ak≤k-1, ，命题成立。再证表示的唯一性：设 ,不妨设a＞b令j=max{i|a≠b}j j i iaj·j!+aj-1·(j-1)!+…+a1·1!=bj·j!+bj-1·(j-1)!+…+b1·1!,(ab

)j!(b

a)ib

(b

a矛盾，命题成立。j j i i i i i i题 证明nC(n-1,r)=(r+1)C(n,r+1),并给予组合解释.(n1)! (r1)n! (r1)n!nC(n1,r)

(r1)C(n,r1)r(nr1)! (r1)r(nr1)! (r1)!(nr1)!所以左边等于右边1n-1r个；r+1所以两种方案数相同。题 证明等式：k1

kC(n,k)n2n1等式左

nn

1n

n1证明：

k

n n k k1

n s0

nnns

右边N1（取法由大到小）1N个数由大到小取一个数做为第一组，其它N-1组合数为：c（n,1）*{c(n-1,1)+c(n-1,2)-…+c(n-1,n-1)}2N个数由大到小取两个数做为第一组，其它N-2组合数为：c（n,2）*{c(n-2,1)+c(n-2,2)-…+c(n-2,n-2)}…n-2Nn-22n-1Nn-11个数为第二组，组合数为：c（n,n-1）*{c(1,1}总的组合数为：C(n,1){C(n1,1)C(n1,2) C(n1,n1)}C(n,2){C(n2,1)C(n2,2) C(n,n2){C(2,1)C(n,n1)C(1,1)}2

C(n2,n2)}PAGEPAGE5题 6个引擎分列两排，要求引擎的点火顺序两排交错开来，试求从特定一引擎开始有多少种方案解：第1步从特定引擎对面的3个中取1个有C(3,1)种取法，第2步从特定引擎一边的2个中取1个有C(2,1)种取法，321个有C(2,1)1C(3,1)•C(2,1)•C(2,1)=12种方案。题求110000000出现的次数。解：当第一位为0时，后面6位组成的数可以从1-100000，共100000个0；00-951-999905位还可以取为10000，这样共有9999*10+1=99991个0；同理第三位为0时，共有99901个0； 第四位为0时，共有99001个0；第五位为0时，共有90001个第六位为0时，只有1个0；这样总共的0数为：100000+99991+99901+99001+90001+1=488895。题nr个不同的盒子里，且每个盒子里不空的放法。“O”r-1个“|”n个“O”r份，要求是每份至少有一个球。00|00000000|00000000|00000|000000……n-1n-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解：要求空盒不相邻，这样球的位置共有8种。而不同标志的球的排列有p55

5!。所以共有8*5！种排列。8种排列如下两类。因为要求空盒不相邻，途中1代表球a) 1 1 1 1b) 1 1 1 1在a)中剩下的一个球有四种位置，b)中剩下的一个球也有四种位置，两者合起来一共有8种1.17题 n和r都是正整数，而且rn，试证下列等式：pnnpn1

pn(nr1)pn

pn n

pn1

,rnr r

r r

r nr rpr))pn1pnpr)

pn1rr(p

pn1r r r

r r

r

r1解(a) npn1n(n)! ! pn等式成立。r1(b)(nr)

(nr)! (nr)! (nr

pn等式成立。r1

(nr(nr)! r(c)

n pn1

n (n1)!

! pn等式成立。nr r nr (nr1)! (nr)! rpnr

n!

r n!

r1)r n!

(nrn!

(n1)!

pn1r

(nr)! (nr1)! (nr1)! (nr1)! (nr1)! (n1r)! r利用(d)的结论可证明本题。rr(pnr1

pn1r1

prpr)prrpnrpn1rpr

r rr

r1prrpr

rpr1rpr2 rpn1rpnr r

r1

r1

r1

r1pr1rpr1rpr2

rpn1rp

pn1r r

r1

r1

rr1.19题 n+m位由m个0，n个1组成的符号串，其中试问不存在两个1相邻的符号串的数目解：m个0进行排列，留出m+1个空挡，任选n个空挡放1，共有C(m+1,n)种方.1.21题 一个盒子里有7个无区别的白球个无区别的黑球，每次从中随机取走一个球，已知前面取走6个，其中3个是白的，试问取第6个球是白球的概率。解：C（6,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..甲单位出2个男同志，乙单位出3个男同志，从甲单位出2个女同. C(10,2)*C(15,3)*C(4,2)=122850PCABPCAB1.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)，根据乘法法:2 N322 (b)分两步走O(0,0)→A(3,2), 根据乘法法:

N32433502 2 (c)分三步走:O(0,0)→A(3,2), A(3,2)→C(6,3), C(6,3)→P(8,5), 根据乘法法

N3231222402 2 2ABABO(0,0)→P(8,5)的所有路径数有加法法则可得：5 3N58325 3 n1 n11.23题 令s={1,2,…,n+1},n≥2,T={(x,y,),y<z},试证:|T证明：要确定x,y,z的取值，有两种方法，

k2k

2 2 3z,z=2时，x1，y11×1=12种可能；z=3时，x1,2，y1,22×2=22种可能；z=4时，x1,2,3，y1,2,3,3×3=32种可能；……z=n+11,2,…,n,y1,2,…,n,n×n=n2种可能。z2,3,…,n+1时，x,y取值共有22n2k1

k2种可能。故|Tk

k2。x<z,y<z，可以分为三种情况：①x=y<z,x,y可看作一个元素，这种情况等价于从1,2,…,n+1中取2个进行组合，然后比较大小，小者为x(y),大者n1为z,其组合数为 ；2②x<y<z,等价于从1,2,…,n+1中取3个进行组合，然后比较大小可得x,y,z,其组合数为n1；3 3 ③y<x<z,等价于从1,2,…,n+1中取3个进行组合，然后比较大小可得x,y,z,其组合数为n1。3 3 所以满足题意的x,y,z的组合数为n1+n1+n1＝n12n1。 3

3 2

32

由于这两种方法是等价的，故可得|T

k2n12n1。证毕。2 3k1

题A={(a,b)|a,b∈Z,0≤a≤9,0≤b≤5} (a)求x-y平面上以A作顶点的长方形的数目.(b)x-yA作顶点的正方形数目.解(a)(a)，从图中可以看出，对于x-y平面上满足题意的任一顶点A(a,b),95A(a,b)(x,y)9×5=45个。解(b)(b)bax-yA(a,b)形的数目。1.26题 S={1,2,……，1000}，a,b∈S,使ab≡0mod求数偶{a,b}的数目解：根据题意可以整除5，2*C（200，1）*1000=40000021512345题 平面上有15个点P1,P。。Ｐ，其中PPPPP共线，此外不存在3点共线的。21512345求至少过15个点中两点的直线的数目 (2)求由15个点中3点组成的三角形的数目解：1)由题意知：P1P2P3P4P5共线，此外不存在3点共线的，所以与这五点分别相连的其他的十点的直线数目为：105*10=50。另外十个点两两相连得直线数目为：C2=4510又因为P1P2P3P4P5共线，所以可算作一条至少2点相连的直线所以至少过15个点中两点的直线的数目=50+45+1=96102)有三种情况 a：没有P1P2P3P4P5这五个点的三角个数3=12010b：有这五个点的其中一个点2225 c：有着五个点的两个点2=10010 5由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)题 6位男宾5位女宾围一圆桌而坐（女宾不相邻有多少种方案（所有女宾在一起有多少种方案（）一女宾A和两位男宾相邻又有多少种方案？解（若5位女宾不相邻先考虑6位男宾围圆桌而做的方案数然后女宾插入 （*6*5*4*3*2=86400（2）把5位女宾看成一个整体，然后插入 Q（6，6）*6*P(5,5)=86400（3）C（5，1）*C（6，2）*Q（8，8）=194000C(5,1)*C(6,2)*C(5,2)*P(4,2)*7！题 k和n都是正整数，kn位来宾围着k张圆桌而坐，试求其方案数。pn解：若每个圆桌的的人数相等，则每个桌子有n个人。因为圆周排列的个数为 rr因此本题的结果为

(kn)!

(kn)!。nn n nk题 从n个对象中取个r做圆排列，求其方案数目1<=r<=n解：c(n,r)*Q（r,r） =c(n,r)*(r-1)!题 试证任意r个相邻数的连乘：(n1)(n2) (nr) 被除.证明：由P（n,=n*(n1)…（n-r+） 可知n+（n+…n+）=（n+r,）=（n+r,）*r!所以（n+（n+…（n+]/r!=n+r,）/r!=（n+r,）故任意个相邻数连乘可被r！除尽。5PAGEPAGE35n

n1 n n

n

n1130题（1r=n/rr1，1rn（r（n-r+/rr

,1r

=n/(n-r)

,0rn；

r

r n n1解（：rn!/(r!(n-r)!) n/rr1=n/r*((n-1)!/((r-1)!(n-r)!))=n!/(r!(n-r)!)上式 所以两式相等n

n （2：rn!/(r!(n-r)!) (n-r+1)/rr=（n-r+）/r*((n!)/((r-1)!(n-r+1)!))=n!/(r!(n-r)!)上式 所以两式相等 1n n1（3：rn!/(r!(n-r)!) nn-）r （n-）!/(r!(n-r-1)!))=n!/(r!(n-r)!)上式 所以两式相等 题 在a,b,c,d,e,f,x,x,x,y,y的排列中，要求y必须夹在两个x之间，问这样的排列数等于多少？解：满足y必须加在两个x之间应为 xyxyx 然后再把a，b，c，d，e，f插入，a插入时有6种选择，b插入时有7种选择插入时有8种选择插入时有9种选择插入时有10种选择，f插入时有11种选择，由此可得排列数N=11*10*9*8*7*6=11!/5!题 已知都是正整数，rnk，将r个无区别的球放在n个有标志的盒子里，每盒至少k个球，试问有多少种方案？rnknn中可能。因此方案数为n(r-nk). 题 在r,s,t,u,v,w,x,y,z的排列中求y居于x和z中间的排列解：2*（5+4+3+2+1）*6！=2430题 凸十边形的任意三条对角线不共点。试求这凸十边形的对角线相交于多少个点？772与它不相邻的顶点有6条对角线（有1条与它重复的，这样的点8个；因此 （2*C（7，1）*C（7，1）+8*C（6，1）*C（7，1）*（9+1） =4340题 试证一整数是另外一整数的平方的必要条件是除尽他的数的数目是整数N=Pa1Pa2Pan，PPn个不同的素数，每个能整除尽数n的正整数都可以选取每个素数1 2 n 1 2 n1Pi从0到aiai+1n(a1+1)(a2+1)。(ai+1)M=N2=P2a11P2a2P2an，能被(2a+1)(2a+1)。2(a+1)个整除。所以一整数是另外一整数的平方的必要条件是除尽他的数的2 n 1 2 i数目是整数。nrn1r1n2r2 nmrmnr11.37题 给出m0+m

的组合意义。

11 m22 0 m m 解： YB（m,n+r+1-m）P’P(k,r)0 k m Xk 如上图所示，rk表示（0，0）点到k nmmk nr1P点到P’点只有一步；mk =表示P’点到B点的路径; 表示点到B点的路径数。

m 所以0点到B点的路径由0点到P点再从P点到P’点，最后从P’点到达B点。M rk nk

nrn1r1n2r2 nmrmnr1k m *1* k m0

+m 0 m m 0 m

+11 11

+…+ = m2 0 m m2 0 m 1.41题 分别写出按照字典序，有给定排列计算其对应序号的算法及有给定序号计算其对应排列的算法解：利用字典序生成下一排列的算法，计算该排列的对应序号，生成已知排列序号算法：设int M为每一排列的对应序号初始时PP

_P

_...P_(P_<P

_<P_

_<P_)M=1（初始化）12 i-1i

i+1

1 2 i-1

i+1 nI. Pj-1<Pjji,i=max{j|Pj-1<Pj}II. 满足关系式Pi-<Pk 的k的最大值，设为j,即j=max{j|i-<Pk}12i-1ii+1nIII. Pi-1Pj(p_P_P_...P_P_P_...P_12i-1ii+1nIV.(p_)=P_P

_P

_...P_P

_...P_部分的顺序逆转，得下一排列。12 i-1

i+1

ii+1 nV. 判断(p_)排列是否与给定排列相同，相同则输出M，ELSE M=M+1GOTOΙ（2）给定序列号计算排列算法：设IntM为每一排列的对应序号（N为给定序号设Int K为循环次数FOR（K=1；K++；K<=N）{Pj-1<Pjji,i=max{j|Pj-1<Pj}满足关系式Pi-<Pk 的k的最大值，设为j,即j=max{j|i-<Pk}12i-1ii+1nPi-1Pj互换得(p_P_P12i-1ii+1n

_P

_...P_(p_)=P_P

_P

_...P_P

_...P_部分的顺序逆转，得下一排列}(p_)

12 i-1

i+1

ii+1 nr r r r11.38题 给出rr1r r r r1 A={aa1

,….,

nr

,……,

n1

},从A中取r+1个元素组合成C，考虑以下n-r+1种情况：na∈CAA\{a}rC，共种可能1 1 r

c，

cA\ar-1个，加上

构成C，共n1中可能 ……1 2 1 2

2 (n-r)a,a1 2

,...,

nr

nr

C则需从A\{a,a1 2

,...,

nr

r}r个组合，再加上r

nr

r1r构成C，共 种可能。r (nr,a1 2

,...,

nr

C,这时只有r=1种可能。rrnn1n2 r1rn1r 故+ +r

+…+ += r r r r1 r r r r1（法二）C(n+1,r+1)n+1a1a2,…,an+1r+1个进行组合的方案数。an+1,C(n,r).an+1,an,C(n-1,r).an+1,an,…ar+2,C(r,r).所有这些可能性相加就得到了总方案数。1.39题 证明(m,0)C(m,n)+C(m,1)C(m-1,n-1)+…+C(m,n)C(m-n,0)=2nC(m,n)证明：由公式C(n,l)C(l,r)=C(n,r)C(n-r,l-r)其中：l>=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(n,n)由上知：左边=[C(n,0)+C(n,1)+…+C(n,n)]C(m,n)由(xy)n=C(n,0)xn+C(n,1)xn1y+C(n,2)xn2y2+…+C(n,n)yn令x=y=1 可得 C(n,0)+C(n,1)+C(n,2)+…+C(n,n)=2n1.40题 从n个人中选r个围成一圆圈，问有多少种不同的方案解：圆排列共有P(n,r)/r种不同的方案。

左=2nC(m,n)=右边 命题得证。1.48题 在由n个0及n个1构成的字符串中，在任意前k个字符中，0的个数不少于1的个数的字符串有多少？解：转化为格路问题(弱领先条件),即从(0,0)到(n,n),只能从对角线上方走,可以碰到对角线,故方案数为C(2n,n)-C(2n,n-1。题 (a)按照1.41的要求，写出邻位对换法（排列的生成算法之二）的相应算.(b)写出按照邻位对换法由给定排列生成其下一个排列的算法.解：1：给定排列求相应序号：设Int I为每一排列的对应序号 I=1（初始化）假定A[1：n]和E[2：n]；D[2：n]；B[1：n]都是整数数组，其中B[1：n]为给定序列S： 11i从2到n作始 i，E[i]1 终；S： q0；2判断A[1：n]是否与B[1：n]相等若相等则输出I值否则II1；S： k从n降到2作3始 D[k]D[k]E[k]; pD[k];若pk 则作E[k]-1;否则作始若p0则作始E[k]1,qq1否则作始ppq;rA[p];A[p]A[p1];A[p1]r;转S 终2终终2：给定序号求相应排列：设Int I为每一排列的对应序号 I=1（初始化） M为给定序列假定A[1：n]和E[2：n]；D[2：n]；都是整数数组S： A[1]11

M=Ni从2到n作始 A[i]i，D[i]i，E[i]1 终；S： q0；2判断I是否与M相等若相等则 i1到n输出A[i]；否则II1；S： k从n降到2作3始 D[k]D[k]E[k]; pD[k];若pk 则作E[k]-1;否则作始若p0则作始E[k]1,qq1终否则作始ppq;rA[p];A[p]A[p1];A[p1]r;转S 终2终终由给定排列生成其下一个排列的算法从排列ppp12

p生成下一个排列nS：若在pppp1 12

中无一处于活动状态则停止。S：求处于活动状态各数中的数值最大者，2设为m和它箭头所指一侧相邻数互换位置。S：比m大的数一律改变箭头的指向S。3 1N1或N若N是奇数题 对于给定的正整数N，证明，当K2 2

时，C(N,K)是最大值。N 若N证明：要证明C（N，K）是最大值，只需证明C（N，K）大于C（N，K-1）即可根据以往证明大小值的经验，可以用相减或是相除的方法来证明，就此题，相减不合适，采用相除可以消除等式中的一些项CN，/（，K-）=N/（N-）（K-（N-K+！/）（N-K+）/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取以上三种情况,C（N，K）取最大值3n11.46题 证明在由字母表{0,1,2}生成的长度为n的字符串中. (a)0出现偶数次的字符串有 个；2(b)

n

n

n

3n1，其中q2n.02n22n1...q2nq 2

2 证：(a)归纳法：当n=1时,0出现偶数次的字符串有(31+1)/2=2个(即1,2),成立。假设当n=k时,0(3k+1)/230(3k-1)/2种。n=k+1时，0出现偶数次的字符串包括两部分：n=k时,002(3k+1)/2种，00,共有(3k-1)/22(3k+1)/2+(3k-1)/2=(3k+1+1)/2种，证毕。等式左边第m0m0右边由(a)0出现偶数次的字符串数，两边显然相等。1.44题 （a）用组合方法证

(2n)! 和

（b）

(2)!

是整数。2n 2n3n

n1解：(a) ①方法一：因为：(2n)!2nn所

(2n)!2nn

n!(2n1)!!n

(2n)!2n

是整数。

2n 2n方法二：设有2n个不同球放入n个不同的盒子里，每盒两个，这个方案数应该是整数。对2n个球进行排列得到方案数为(2n)!。而把2个球放入同一个盒子里不计顺序，应该把全排列数除掉这些重复计算的次数，n个盒子内部的排列共重复计算了2次。(2n)!2得到2n个不同球放入n个不同的盒子里，每盒两个的方案数2n3n,放入n,3n(3n)!。3n3！次。3n个不同的球放入n个不同的盒子里，每盒三个的方案数(3n

(3n)!3n2n有n2个不同的球，放入n个相同的盒子里，每盒n个，求方案数，方案数应该是一个整数。按前面(a)的方法，应该得到(n2)!/(n!)n是整数。另外由于n个盒子相同，放入不同的盒子是没有区别的，应该把n个盒子的排列数n!除去。因此得到(n2)!/(n!)n+1是整数。1.49题 在1到n的自然数中选取不同且互不相邻的k个数有多少种选取方案？解:1-n中选取互不相邻的k个数的方案为g(n,k)g(n-2,k-1),若不选n,则方案数位g(n-1,k).显然g(n,k)=g(n-2,k-1)+g(n-1,k，且只有当n≥2-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个的方案数.3n+1n个相同.3n+1n个的方案数.解(：有n个相同就有n个不相同n0n-11个相同的球为C(n,n-1)，等等。所以总的方案数为 C

,

2n 解(：方法同上，方案数为C2n

C2n1,1C2n1,n由 …,C(n+1,n)=C(2n+,n+1)CC2nC2nC2n12C2则C2n1,0C2n1,1 1,n122n122n21.47题 5台教学机器m个学生使用，使用第一台和第二台的人数相等，有多少种分配方案？1台机器的学生为n2台机器的学生也为n,m2n剩余的学生可以任意使用剩下的机器的组合数为C(m,2n)C(2n,n)(m-2)所以总的方案数为

C(m,2n)C(2n,n)3(m2n)n0

qm 2 题 (1)在有5个0，4个1组成的字符串中，出现01或10的总次数为4的字符串，有多少个？(2)在有m个0，n个1组成的字符串中，出现01或10的总次数为k的字符串，有多少个解：(1)5000000中间，即：“010”2个“01”或“10”；1“01”或“10”“01”，“10”4，有两种办法：1、把两个1插入0的空当内，剩下的1插入1的后面（类似01011100。2、把1个1插入0的空当，再取两个1分别插入两端，剩下的1插入1（类似1010001123*C23*C1304 4(2)、m个0产生m-1个空当。2k“01”与“10”1m-1k2k个1即可，也就是C2m1

。剩下的1如何插入的问题与书P20页的定理1.2类似(在n个不同元素中取r个允许重复的组2合，其组合数为C（n+r-1,r，在这里无区别的球的个数也就是剩下的1的个数（即n-k，盒子的个数也就是插入2k nk

k nk到m-1个空当中的1即21的插入方法有C

2即第一种情况的总的插入方法为C2*C 2。n1

m1

n12

k22

*Cn

k22

2。k12C2

*CnkC

k22

*Cn

k222

m1

n12m12

n1

m1

n1k为奇数时：1,11只有这样才能使k为奇数。2*

k2m1

k1*Cn2。n1题 从N={1,2,…,20}中选出3个数，使得没有两个数相邻，问有多少种方案？解：相当于从N={1,2,…,20}个数中取3个作不相邻的组合，故方案数为C(20-3+1,3)=C(18,3)种题 从s={1,2,n}中连取k个数，使之没有两个数相邻，求不同方案数。解：在n个数中选k个数，使之没有两个数相邻，相当于在n-k+1位置中插入k个数，k个数中没有俩个数相邻。(nk1)!有Cknk1

1.4直接可得。k!题 把n个无区别的球放进有标志1，2，…，n的n个盒子中，每个盒子可放多于一个球，求有多少种方案解：把n个无标志的球放进 n个有标志的盒子中，每个盒子允许多于一个球是允许重复的组合所以是nn12n1n = n 题 .m个1，n个0进行排列，求1不相邻的排列设n>m.解：相当于n0m1做不相邻的插入，共产生n+1.1插入有n+1种情况，第二个是nm1插入就有n-m+1种情况。所以是n+（n（n-…（n-m+，即此题解为n+1。m题 偶数位的对称数，即从左向右读法与从优向左的读法相同，如3223。试证这样的数可被11整除。证明：根据所有偶数位置上的数字及所有奇数位置上的数字分别相加，再求出两个和的差，如果所得的差能被11整除，那么这个整数必能被11整除。例如12344321，偶数位上是：2，4，3，1。奇数位上是：1，3，4，2因为对称数是偶数个，所以偶数为相加与奇数为相加的和是相等的，他们的差是零，而零能能被任何数整除，所以原题成立。证毕。题 n个男人与n个女人沿一圆桌坐下，问两个女人之间坐1个男人的方案数。又m个女人n个男人，且沿一圆桌坐下，求无两个女人并坐的方案数。解：根据题意，两个女人之间坐1个男人的方案数Q(n,n)*P(n,n)无两个女人并坐的方案数Q(n,n)*P(n,m) 题 n个人分别沿着两张圆坐下，一张r人，另一张个n-r人，试问有多少种不同的方案数解：C（n,r）*(r-1)!(n-r-1)!题 一圆周上n个点标以,n。每一点与其它n-1个点连以直线，试问这些直线交于圆内有多少点？解：这些直线交于圆内有C（n,4）个点每4个点形成矩形，其对角线有一个交点，故圆内交点有：n(n2)(n1C(n,4)

n(n2)(n4321 24因为四个点连在一起构成一个四边形，这个四边形的对角线相交于一个点，求这些直线交于圆内多少点就是求这些点能构成几个四边形，即转化为从n个点取出四个进行组合2.1题 求序列{0，1，8，27， n3 }的母函数。n3xn解：由序列可得到G(x)x23x2n3xnxnxn因为1xnxnnxn1

1xx2x3( )'12x3x24x31x(n1)xn1nxn1设p(x)x( )'x(n1)xn1nxn11x(n1)2xn2n2xn1[p(x)]'(n1)2xn2n2xn1(n1)2xn1n2xn设q(x)x[p(x)]'(n1)2xn1n2xn(n1)3xn2n3xn1[q(n1)3xn2n3xn1(n1)3xn1n3xnx[q(x(n1)3xn1n3xn,[7*9n4*(6)n],,[7*9n4*(6)n],所以可通过求得x[q(x)]'得到序列的母函数：G(x)4x3x2x1H(x)F(x)dx [3x24x36

(n3)xn2]3,4, ,n3, 2.2题 已知序列33 3 ，求母函数 解：G(x)

3*2*14*3*2 xn(n(n3)*(n2)*(n1)3*2*11= [3.2.14.3.2x (n3)(n2)(n1)xn]6F(x)G(x)dx1[3.2x4.3x2 (n3)(n2)xn1]6H(x)F(x)dx1[3x24x3 (n3)xn2]6xn3]I(x)H(x)dx1[x3xn3]6xn3I(x)1因为 xn3I(x)11x

( 1xx2)所以G(x1 61x1

1x361

]'''就是所求序列母函数题 已知母函数G(x)

378x ，求序列a}13x54x2 n}G(x

378x A B=

7 413x54x2 19x 16x 19x 16xxxn3得719x(9x)n )由 1xx21x4

7(19x(9x)216x

4(1(6)x(6x)2(6x)n )(6x)n ),[7*9n4*(6)n], }n题 已知母函数G(x) 39x ，求序列{a}。1x56x2 nG(x

39x A B=

1 21x56x2则a=8n2*(1)n*7n

18x 17x 18x 17x题 设G

，其中FFibonacciG

0n=2.3.4….{G,G,G,

}的母函数。n 2n n

n

n2

0 1 2解：(1).已知GFn 2n

则G3Gn

G =Fn2 2

3F2n2

F2n4F F2n 2n1

F2n2

F2n1

F2n2

F2n3

F2n2

F2n3

F2n4则F 3F2n 2n2

F2n4

则G3Gn

G 0n2(2)．G(x)G0

Gx1n2

(Gn1

Gn2

)xn

=GGxx0 1n2

Gn1

xn1x2n2

Gn2

xn2=GGxxGxnG)x2G

xn2 =GGxxG(x)

x2G(x)0 1 n0

0n2

n2

0 1 01x=1xG(x)x2G(x)x G(x)

1xx22.6题 求序列{1，0，2，0，3，0， }的母函数。解：序列a

=

(n1)x2n=

nx2n

x2n=1

(2n1)x2n1

1x2n=

x )'1 1 = 1nn0

n0 n0

2 2n0 n0

21x2

21x2

(1x2)22.7题 设G12x23x44x6(n1)x2n=1/(1-x^2)^2 求x2)G,(1x2)2G(n1)x2n 11x1x(n1)x2n 11x1x1x x 1xx 1G 1x x)2 x)2所以 1）(1x2)G

x2) 1 1x2x4x2n

x2)2Gx2)2

1 1x2)2 1x2 x2)22.8题 求下列序列的母函数：(1)1,0,1,0,1,0，… (2)0,-1,0,-1,0,-1,… (3)1,-1,1,-1,1,-1,…1解：(1)G1x2x4x2n

1x2xx2n )x11x2(2)Gxx3x5x2n1x(1x2x4)x2x4 )111x2 1xx(3)1xx2)x2x4 )111x2 1xxn2

x21

1xx21x222.9题 设G13x6x210x3 xn证明：(1)x)G12x3x24x3(n1)xn2 (2)x2)G1xx2xn (3)因为x)3G1，所以有G

1(1x)3证明（1）1时有1x1x（2）展1时有1x1x)(3)(1x)3G(13x23xx3)(13x6x2)

11=13x6x23x29x330x5 9x218x330x4 6x5=1G 1(1n32 3

n22.10题 H14x10x20x3xn

证明(1)

(1x)HG

2xn

(2)求H的表达式。 n0 n3 (k3)(k2)(kk36k26 证明(1)设H的第K+1项为hk，则hk=3

3*2*1 = 6 ，GG13x6x2 xnn221112x3x2 (n1)xn设G的前K+1项的和为G，则G=k k

kk0

23 k2k 2 2 2g=++…+ k 2 2 2 23 k2 3*2 4*3 (k2)*(k12 2而++…+ 2 2

2

2 =1+2[3*2+4*3+…+(k+2)(k+1)]1=1+2(1+22+32+…+k2+3+6+…+3k+2+2+…+2) ①{k}11 3kk) (2k2k)(k(k=1+ [ k(k+1)(2k+1)+ +2k] =1+ 12 + +k26 2 4(2k2k)(k9k(k12k12=

k36k211k6= =

GH=12 6

1xn 4*3*2 5*4*3 (n3)(n2)(n(2)由H=1+4x+10x2+20x3+…+(n3)x+…=1+ x+ x2+…+

xn+…3 3*2*1 3*2*1 3*2*1x3 x3对其3次积分得 H=x)，对此积分式3次求导得H=(((x)

)))’’’。求解完毕。2.11题 a=(n+1)2,G=nn0

axn=1+4x+…(n+1)2xn+…,证明(1-3x+3x2-x2)G是一个多项式,并求母函数G。n解: G=

axn=n

(n)2xn=

(n22n1)xn

G=x

n2xn1+2x

nxn1+

xn ①n0 n

n0 n

n0

n0 G=xG+ 2x + 1

G(1－x)=

x1

G=

x1

即为所求x)2 1x x)2 x)3(1－3x＋3x2—x2)=(1－x)3 (1－3x＋3x2—x2)G=(1－x)3G=(1－x)

x1(1x)3

=x+1求解完毕。①说明：可以由n1

n2xn1=n0x1

(n1)2xn题 已知an

k

k2, (1x)3

n

(n1)2xn,求序列{an

}的母函数。解：设序列{a}的母函数为G(x), 则G(x)=a+ax+ax+…+axn+a xn1+…n 0 1 2 n n1n1 an

k

k2=1+22+32+…+n2+(n+1)2G(x)=1+(1+22)x+(1+22+32)x2+…+(1+22+32+…+n2+(n+1)2)xn+…=1+x+x2+…xn+… +22x(1+x+x2+…xn+…) +32x2(1+x+x2+…xn+…)+…+(n+1)2xn(1+x+x2+…xn+…)+….=(1+x+x2+…xn+…)(1+22x+32x2+…+n2xn1+(n+1)2xn+…)

11

n

(n1)2xn x

=

(nxn

G=

x

G=

x

即为序列{a

}的母函数。求解完毕。

n0

1x x)3

x)4 n题 已知an

n

14xx2 k 3, k (1x)4

(n1)3xn,求序列{an

}的母函数。k1 n0解：B(x)=13+23x+33x2+……1:

=13 0

=130x: a1

=13+23 b1

=23x2: a2……

=13+23+33 b2

=33a=b0 0a=b+b1 0 1a=b2

+b+b0 1 ……A(x)=b(1+x+x2+……)+bx(1+x+x2+……)+bx2(1+x+x2+……)+……0 1 2B(x)14xx2=(1+x+x2+……)(

+bx+b0 1 x

x2+……)= =1x x)5题 已知{P的母函数为 , (a)求P和P;(b)求序{P的递推关系n 12xx2 0 1 n解:特征多项式K(x)=x2-2x-1 x2-2x-1=0 解得：r1

r=1-22222A B11(1 2)x1(1 2)xA+B=02-A(1-2

)-B(1+

2 22)=1 得：A= ,B=-24 4P(x)=

211(111(1 211(1 2)x

2[14k0

2)k 2)k]xk2Pn=2

[(1+

2)n2

2)n] 2

=0, P=10 1题 已知}的母函数为 1 ,求序列}的递推关系a,a。n 1xx2 n 0 1解：特征多项式K(x)=x2-x+1331 i 133

ix2-x+1=0解得：r= + i=cos +isin =e3, r= - i=cos -isin =e31 2 2 3 3 2 2 2 3 3A BA(x)=

1rx1

+1rx2313A+A1

=1, Ar+A12

r=0 31 3

=1，A=2na=Acos

sinn=cosn+1sinn a=1, a=1n 1 3

2 3 3 3 0 1m m1 m2 mnm mmm题 证明序列mm

，

，

，…，

的母函数为（1-x）m1mm=0时，命题成立。

m1km-1，命题成立，即k0

m1

Xk=（1-x）m，则G

mk mk

mk X X

mk X

=XG

(X)+（1-x）mm k0 m

k0 m

k0

m1 m(1-X)Gm1

(X)=（1-x）m，1G(X)=m

1

X

=（1-x）m1

n32.17题 已知G12x3x2...(n1)xn...

证明(a)G2(1x)4

n

( )xn3(bG2

axn,其中an

(k1)(n1k)

an

(n3

),n{0,1,2,...}n0 k0 (a) G2(1x)4n3 3(n(n1)xn (1x)2证明：由已知 G12x3x2所以有 G2(1x)4又根据牛顿二项式展开定理 1nnxkkk0n4则有14k41kk3k x x3 3G2(1x)4n33

k0 k0 （b）G2

axnn

n0,其中an

(k1k)n0 k0证明：已知 G12x3x2(n1)xn(1x)2由性质：若bk1

kaii0

则 B(x)A(x)1xA1x

1xx2G 1 (1x)2

A(x)1x

即gi

ai1nn0 n0C 1

G(x)

即ci

in

n1(1x)3 1x

i n hn0 n0h0 n0DG2

1 (1x)4

C(x)1x

即di

cin

(h1)n0 n0h0可将d表示成如下形式：ic：a0 0

a(1)0c：aa1 0 1

(a2)12 0 1 22c：aa2 0 1 22c：aaan 0 1 2an(an1)n

(a3)dnni0

c(i1)(n1i)i其中i）表示每列上的数值，n1）表示k）an

nk

(k1)(n1k)成立an

n3 3

n0,1,2,证明：题目即证 nk0

1n1kn3 3

n0,1,2,当n0时 nk0

1n1k1

n3 3

1 等式成立nm-1时等式成立，即m1nkn1km1kmk1m2(m-1)3m1k0 k0(m2)(m1)m

m13

m23！ 3 3nm

kn1k

k1m1kk0 k01m2m3(m1)1m112(m1)21

(m1)1m1(m1)1m1kmk12 (m1)k0m1kmk(m2)(m1)2k0m3(m3)(m2)(m1)m23(m2)(m1)m2(m2)(m1) 3！ 3！ 23 3 3当nm-1时等式成立即 m1kmkk0

m2 3所以 m1kmk(m2)(m1)m2(m2)(m1)k即 mk0

k1m1k

2m3 3

3 2等式成立综合an

n3 得证 3 题 用母函数法求下列递推函数关系的解.an

6an1

8a 0n2

an

14an1

49a 0n2an(e) a

9an212a

036a 0

(d) an(f) a

6an125a

7a 0n20n

n2

n n22(a)x2a23x3:ax4:3

6a

8a000)...4..3. 20(A(x)aax)6x(A(x)a)8x2A(x)0 1 0(16x8x2)A(x)aax6axa(a6a)x0 1 0 0 1 0a(a6a)x A B A(14x)B(12x) (AB)(4A2B)所以A(x)n 1 0 16x8x2 12x 14x (12x)(14x) (12x)(14x)a 10 ABa

6aa 2

a)

4a 1所以有

0 解之得:A= 0 1

0 1

0

a)(4A2B)a6a1 0

1 1 24 2 2 0 14 21 a04 6aa

(6a

a)

2aa 1B 0 1 0 1 0 0 1 (a2a)A1(4aa)

1 1 24 2 2 1 04 2因此 2 0 1B

1(a2a) 2 1 01故此A(x1(4aa1

1 1

2a) 1 1(4aa)

(2x)n (a2a)

(4x)n2 0 112x 2

0 14x 2 0 1

2 1 01 1

n0 n0 [(4aa)2n

2a)4n (n2)2 0 1n0

2 1 0解(b)：x2:a3x3:a23

14a141

49a00x4:a14a2

49a10) :.4..

..2(A(x)aax)14x(A(x)a)49x2A(x)00 1 0(1(4x49x2)A(x)aax14axa

14a)xa(a

A0 0 B

7x)B (AB)7Ax所以A(x)0 1 0 114x49x2 (17x) (17x)2 (17x)2 (17x)ABa7所以有71

Aa1

014aAa1(a14a)1(a7a0071071 0故此A (a14a) Ba )7 1 0Ax)1(a14

) 1 1(a7a) 17 1 1

17x 7 1 1

0(17x)2 n1 (a14a) (7)nxn (a7a) ( 7)2.16)7 1 0 7 1 0 1n0 n0

1[

14a)1(a7a)(n1)](1)n7nxn7 1 0 7 1 0n0 1

[a(a a)n](1)n7nn 0 0 71解x2a9a03x3:a29a003x4:a0) :.4..2...(A(x)aax)9x2A(x)0所以有(109x1)A(x)0aax A B A(13x)B(13x) (AB)(3A3B)x于A(x)0 119x2ABa

13x 13x (13x)(13x) (13x)(13x)①故此有03A3Ba ②③3x① 有6Aa③于是有A1

1a0 120 61将③代入①有B

Aa1a1

1a1a ④0A1a1a

0 20 6

20 61即 20 61B

1a1a20 611故此A(x)(1a1a) 1

(1

1a) 1 (1a1a)

nxn(a1a)

(1)n3nxn20 6113x 2

6113x 20 6

20 61 1 1 1 1

n0

n0 [(a a)(a a)(1)n]3nxn20 61 20 611n0

1 1 1所以a[(a a)(1)n(a a)]3n (n2)n 20 61 20 61解(d)：x2:a3x3:a23

6a

7a00x4:a6a27a10) :.4..3..2.(A(x)aax)6x(A(x)a)7x2A(x)00 1 0(16x7x2A(xaax6axa(a6a1A 0 B A(1x)B(17x) (AB)(A7B)x因而A(x)0 1 0 16x7x2 (17x) 1x (17x)(1x) (17x)(1x)ABa故此有A7B

①6a ② a②7①得 1于是有A1aa

8A0aa1 0( ) ③8 0 1B

A

1

a)1

a) ④A1

0a)

0 8

1 8 0 1从而 8 0 1B1(7aa) 8 0 1故此A(x1(aa

1 1

a)1

1

a

7nxn1

a)

(1)nxn8 0 1

17x 8

0 11x 8 0 1

8 0 1

[18

a)7n1

a)(1)n]xn

n0 n080 1 0 181n0 1所以a8(aa)7n8(7aa)(1)n (n2)n 0 1 0 1x2a2x3:a3x4:a4

12a112a212a3

36a0036a0136a02) :. .....(A(x)aax)12x(A(x)a)36x2A(x)00 1 0于是 (112x36x2)A(x)a0

a12ax1 0a(a12a)x A B A(16x)B (AB)6Ax从A(x)0 1 0 (112x36x2) (16x) (16x)2 (16x)2

(16x)2ABa ①故有 6A

0a12a ②1 0由②A2a1a ③0 61B

Aa(2a1a)

1a ④0A2a1

0 0 6

0 61即 0 61即 1Ba a 0 611 1 1 1 1

1 n1从而A(x)(2a a) (a a) (2a

6nxn(a

a) ( )6nxn0 61

16x

0 6

(16x)2

0 6n0

0 6

1n0121

1a)(a

1a)(n1)6nxn

a)n]6nxn0 61

0 6

0 0 61n0 n01所以 a[a(a a)n]6n (n2)n 0 0 61fx2a2x3:a3x4:a4

25a0025a0125a02) :. .....(A(x)a0

ax)25x2A(x)0125x2A(xa0

ax1aax A B A(15x)B(15x) (AB)(5A5B)x从而 A(x) 0 1 125x2

15x 15x 125x2A1a1a

125x2ABa

20 101故此5A

05Ba1

于是有

B1a202

1a1101从而A(x1

a) 1

(1

1a) 1

(1

1a

5nxn(

1a

(1)n5nxn1120 10115x 211

10115x 20 10

n0

20

1n0[(1a 1a)5n (1

a)(1)n5nxn]xn (n2)20n0

10

20 101题 用特征值法求习题2.18的解。(a) 特征方程为2680

2特征值为1

A2nB4nA1(4a

4 n2a)从而有a0A

解之得

2 0 1a

2A

B

1

2a)1 2 1 0于是a1(4aa)2n1(a2a)4n (n2)n 2 0 1 2 1 0(b) 特征方程为:214490 特征根为:Aa 1 2

通解为an

(ABn)(1)n7naA 0从而有0 解之得1a7(AB) B(a a)1 0 711故a[a(a a)n](1)n7n (n2)n 0 0 71(c) 特征方程为:290 特征根为: 1 11

3,2

3 an

A3nB(1)n3naAB A2a6a从而有03

0 1解之得 1 11a A B B1

a a20 611 1 1 1 1 1故a[(a a)(1)n(a a)]3n[a(1(1)n) a(1(1)n]3n (n2)n 20 61 20 61 20 61(d) 特征方程为:270 特征根为:1,7 通解为a 1 1 2

A(1)nB7naAB

A (7aa) 8 0 1 1 1从而有0

解之得 故a (7aa)(1)n

a)7n (n2)1aA7B B1

1(aa8 0 1

n 8 0 1

8 0 1(e) 特征方程为:212360 特征根为:Aa

6,2

6 通解为an

(ABn)6naA 0 1从而有0

解之得 1

故a