組合數(shù)學第四版盧開澄標準答案-第三章解析

1、第三章3.12.一年級有100名學生參加中文，英語和數(shù)學的考試，其中92人通過中文考試，75人通過英語考試，65人通過數(shù)學考試；其中65人通過中，英文考試，54人通過中文和數(shù)學考試，45人通過英語和數(shù)學考試，試求通過3門學科考試的學生數(shù)。解令：舛=通過中文考試的學生A2=通過英語考試的學生A3=通過數(shù)學考試的學生于是|Z|=100，|A1|=92，|A2|=75，|A3|=65IAHA|=65,IAHA|=54,IAHA=451 21323此題沒有給出： 有多少人通過三門中至少一門； 有多少人一門都沒通過。但是由max|A1|,|A2|,|A3|=max92,75,65=92故可以認為： 至少

2、有92人通過三門中至少一門考試，即100|A1UA2UA3|92 至多有8人沒通過一門考試，即0|AnAnA|8123于是，根據(jù)容斥原理，有|A1UA2UA3|=(|A1|+|A2|+|A3|)-(|A1nA2|+|A1nA3|+|A2nA3|)+|A1nA2nA3|即|A1nA2nA3|=|A1UA2UA3|-(|A1|+|A2|+|A3|)+(|A1nA2|+|A1nA3|+|A2nA3|)=|A1UA2UA3|-(92+75+65)+(65+54+45)=|AUAUA|-232+164123=|AUAUA|-68123從而由92-68|A1UA2UA3|-68100-68即24|AUAU

3、A|-6832123可得24|A1nA2nA3|32故此，通過3門學科考試的學生數(shù)在24到32人之間。也可用容斥原理，即|AnAnAi=izi-(iai+iai+iai)+(ianAi+ianAi+ianAi)-ianAnAi123123121323123=100-(92+75+65)+(65+54+45)-iA1nA2nA3i=100-232+164-iAnAnAi123=32lAfAfAJ123從而有iaaanA1=32-1AnAnAi123123由已知owlAnAnAi8,可得12324|A1nA2nA3|32故此，通過3門學科考試的學生數(shù)在24到32之間。313試證：（a）lAnB|=

4、|B|-|AnB|（b）iAnBnc|=|C|-|Anc|-|Bnc|+i（AABnc）i證（a）B=BAZ（因為BcZ）=BA（AUa）（零壹律:且有互補律Z=AUA）=（baa）u（baa）（分配律）=（AAB）u（AAB）（交換律）另夕卜（AAB）A（AAB）=（AAA）AB（結(jié)合律，交換律，幕等律）=0nB（互補律AAA=0）=0（零壹律）所以|B|=|AAB|+|AAB|因此lAAB|=|B|-|AAB|（b）lAABAC|=|AUBAC|（deMorgan律）=lCl-l（AUB）AC|（根據(jù)（a），令A1=AUB）=iCi-i（AnC）U（BnC）i（分配律）第3頁共42頁】IA

5、nA3nA4I=120/(2x5x7)=1IA2nA3nAF=I.120/(3x5x7)=1=ici-|Anc|-|Bnc|+i（Anc）n（Bnc）i=ici-|Anc|-|Bnc|+i（AnBnc）i（結(jié)合律，交換律，幕等律）3.14.N=l,2,.,1000，求其中不被5和7除盡，但被3除盡的數(shù)的數(shù)目。解.定義：P1(x):3ixA1=xLxgNaP1(x)P2(x):5ixA2=xLxgNaP2(x)P3(x):7ixiA1i=L1000/3=333A3=xLxgNaP3(x)iA1nA2i=L1000/(3x5)=66iAinA3i=Ll000/(3x7)=47iAinA2nA3i=

6、L1000/(3x5x7)=9因此iA1nA2nA3i=iA1i-iA1nA2i-iA1nA3i+iA1nA2nA3iJL7JJLJL乙1丄JJL乙1J=333-66-47+9=229因此，在11000中能被3整除，同時不能被5和7整除的數(shù)有229個。315N=1,2,-,120，的素數(shù)的數(shù)目。求其中被2,3,5,7,m個數(shù)除盡的數(shù)的數(shù)目，m=0,1,2,3,4。求不超過120解.定義P1(x):2ixA1=xixeNnP1(x)P2(x):3ixA2=xixeNnP2(x)P3(x):5ixA3=xixeNnP3(x)P4(x):7ixA4=xixeNnP4(x)iA1i=L120/2J=6

7、0iA2i=L120/3J=40iA3i=L120/5J=24iA4i=L120/7J=17iA1HA4i=L120/(2x7)J=8iA3nA4i=L120/(5x7)J=3iA1nA2i=L120/(2x3)J=20iA1nA3I=120/(2x5)=12iA2nA3i=L120/(5x7)J=8AnA4i=120/(3x7)J=5iA1nA2nA3i=L120/(2x3x5)J=4iA1nA2nA4i=L120/(2x3x7)J=2IAnA2nA3nA4I=L120/(2x3x5x7)J=0INI=120p0=INI=120p=IAI+IAI+IAI+IAI=60+40+24+17=14

8、11 1234p=IAnAI+IAnAI+IAnAI+IAnAI+IAnAI+IAnAI=20+12+8+8+5+3=562 121314232434p=IAnAnAI+IAnAnAI+IAnAnAI+IAnAnAI=4+2+1+1=83 123124134234p4=IA1nA2nA3nA4I=0當m=0時，q0=p0-p1+p2-p3+p4=120-141+56-8+0=27當m=1時，r2)qi=piiJp2+r3)p3-r4)cp=141-2x56+3x8-4x0=534J第4頁共42頁】當m=2時，r3)q2=PjlJp3+r4)_P4=56-3x8+6x0=322J4r4)當m=3

9、時，q3=p3-1p4=8-4x0=81J當m=4時，q4=p4=0由于v-1212?=11,所以不超過120的合數(shù)一定有不超過10的因子，因而一定有2,3,5,7的素因子(因為10以內(nèi)的素數(shù)只用2,3,5,7)，所以不超過120的素數(shù)一定是那些不能被2,3,5,7除盡的數(shù)(當然還要去掉非素數(shù)的數(shù)1)，故此不超過120的素數(shù)的數(shù)目=q0-1=27-1=26個。316求正整數(shù)n的數(shù)目，n除盡1040,2030中的至少一個數(shù)。解定義：P(x):xI1040A1=xIxeNnPi(x)P2(x):xI2O3oA2=xIxgNnP2(x)由于1040=(2x5)40=240x5402030=(22x5

10、)30=260x530故此IA1I=(40+1)(40+1)=1681IA2I=(60+1)(30+1)=1891(參見第一章第九題)IAnA2l=(40+l)(30+l)=1271于是IA1UA2I=IA1I+IA2I-|A1UA2I=1681+1891T271=2301因此，能至少除盡1040和2030之一的正整數(shù)的數(shù)目是2301。3.17.n是除盡1060,2050,3040中至少一個數(shù)的除數(shù)，求n的數(shù)目。解.定義：P1(x):xI1060A1=xIxeNHP1(x)第8頁共42頁】P2(x):xI2050A2=xlxwNnP2(x)P3(x):xI3040A3=xIxeNnP3(x)由

11、于1060=(2x5)60=260x5602050=(22x5)50=2100x5503040=(2x3x5)40=240x340x540故此：IA1I=(60+1)(60+1)=3721IA2I=(100+1)(50+1)=5151IA3I=(40+1)(40+1)(40+1)=68921IA1nA2I=(60+1)(50+1)=3111IA1nA3I=(40+1)(40+1)=1681IA2nA3I=(40+1)(40+1)=1681IA1nA2nA3I=(40+1)(40+1)=1681根據(jù)容斥原理，有IA1UA2UA3I=(IA1I+IA2I+IA3I)-(IA1nA2I+IA1nA3

12、I+IA2nA3I)+IA1nA2nA3I=(3721+5151+68921)-(3111+1681+1681)+1681=73001所以，至少能整除1060,2050,3040之一的正整數(shù)n有73001個。3.18求下列集合中不是n2，n3形式的數(shù)的數(shù)目，nN。(a) 1,2,104(=N1)(b) 103,103+1,104(=N2)A1=x|xGN1GP1(x)【解】(a)定義：Pl(x):x=n2(nN)P2(x):x=n3(nN)A1=x|xGN2GP2(x)A1=I2,22,(102)2匸N1故|A1|二102=100A2=13,23,213匸N1故|A2|=21(因為213=92

13、61V10410648=223)A1GA2=16,26,36,46匸N1，故IA1GA2I=4(因為46=409610415625=56)因此，根據(jù)容斥原理，有|AnA2|=|N1|-(|A1|+|A2|)+|A1GA2|=104(100+21)+4=9883(b)定義：Pl(x):x=n2(nN)A1=x|xN1nPl(x)P2(x):x=n3(nN)A1=x|x$N2nP2(x)A1=312,(102)2匸N2故|A1|=100-30=70(因為312=9611031024=322)A2=103,213匸N2故|A2|=21-9=12AlnA2=46匸N2故IA1nA2I=1(因為36=7

14、29V103V46=4096=因此，根據(jù)容斥原理，有|AnA2|=|N1|-(|A1|+|A2|)+|A1GA2|=9001(70+12)+1=89203191000,1001,3000，求其中是4的倍數(shù)但不是100的倍數(shù)的數(shù)的數(shù)目?！窘狻苛頝1=1000,1001,3000，則IN1l=2001P1(x):4|xA1=x|x$N1nP1(x)P1(x):100|xA1=x|xeN2nP2(x)于是由A1=4250,4251,4750oN1,故|A1|=750250+1=501，A1nA2=10010,10011,10030oN1,故|A1nA2|=3010+1=21因此lAinA2l=IA1

15、|AinA2l=50121=480所以，10003000中只能被4整除，但不能被100整除的數(shù)有480個。3.20在由a,a,a,b,b,b,c,c,c組成的排列中，求滿足下列條件的排列數(shù)，(a) 不存在相鄰3元素相同(b) 相鄰兩元素不相同9！【解】(a)定義：Z=9個元素的全排列,IZI=亠=16803！3！3！P1(x):排列x中有相鄰三元素相同，且是aP2(x):排列xP3(x):排列xAl=x|xGZGPl(x)A2=x|xGZGP2(x)A3=x|xGZGP3(x)5!|A1GA2I=203!5!IA2GA3I=203!于是，根據(jù)容斥原理，有中有相鄰三元素相同，且是b中有相鄰三元素

16、相同，且是cIA1|=工=1403!3!IA2|=工=1403!3!IA3I=Z=1403!3!IA1GA3I=203!IA1GA2GA3I=3!=6|A1nA2nA3|=IZ|-(IA1I+IA2I+IA3I)+(IA1GA2I+IA1GA3I+IA2GA3I)IA1GA2GA3I=16803X140+3X206=13149!(b)定義:Z=9個元素的全排列,IZI9-=16803!3!3!P1(x)：排列x中有相鄰兩個元素相同，且是aP2(x):排列x中有相鄰兩個元素相同，且是bP3(x)：排列x中有相鄰兩個元素相同，且是cA=xIxeznP(x)(1WiW3)ii8!7!IA1I=112

17、0140=9803!3!3!3!(因為將aa與a看做為不同的兩個元素參與排列，在它們相遇之時會產(chǎn)生重復其重復因子剛好是將aaa看作一個整體參與排列的個數(shù))8!7!同理可得：IA2I=1120140=9803!3!3!3!IA3I=8!7!=1120140=9803!3!3!3!因為A1AA2為aa,bb圖象都出現(xiàn)的排列集合，當我們將aa與a,bb與b看作不同的兩對元素進行排列時，在aa與a相遇而成aaa圖象及bb與b相遇而成bbb圖象時會產(chǎn)生重復計數(shù)。當aaa圖象與bbb圖象恰出現(xiàn)一個時，重復因子為2；當圖象aaa與圖象bbb同時出現(xiàn)時，重復因子為4。設q1(x):排列x中aa與a相遇而有aa

18、a圖象q2(x):排列x中bb與b相遇而有bbb圖象故B1=xIxGA1GA2Gq1(x)B2=x|xA1AA2Aq2(x)于是IB1I=IB2I=6!=1203!IB1AB2I=5!=203!P1=IB1I+IB2I=2X120=240P2=IB1AB2I=20q1=P12P2=2402X20=200q2=P2=207!從而初廠彷心小840-心叭580同理，IA1AA3I=580IA2AA3I=580第11頁共42頁】因為A1AA2AA3為aa,bb,cc圖象出現(xiàn)的排列集合，當我們將aa與a,bb與b，cc與c看作不同的三對元素進行排列時，在aa與a相遇而成aaa圖象,bb與b相遇而成bbb

19、圖象，cc與c相遇而成ccc圖象時會產(chǎn)生重復計數(shù)。當aaa，bbb，ccc圖象恰出現(xiàn)一個時，重復因子為2當aaa，bbb，ccc圖象恰出現(xiàn)兩個時，重復因子為4當aaa，bbb，ccc圖象恰同時出現(xiàn)時，重復因子為8設q1(x)；排列x中有aaa圖象q2(x)；排列x中有bbb圖象q3(x)；排列x中有ccc圖象B=xIxeA1AA2AA3Aq(x)(1WiW3)iiIB1I=IB2I=IB3I=5!IB1AB2I=IB1AB3I=IB2AB3I=4!=24IB1GB2GB3I=3!=6P1=IB1I+IB2I+IB3I=3X120=360P2=IB1nB21+IB1nB3|+IB2nB3I=3X

20、24=72P3=IB1AB2nB3I=6q1=P12P2+3P3=3602X723X6=234q2=P23P3=723X6=54q3=P3=6因此IA1nA2nA3I=6！(q13q27q3)=720(234+3X54+7X6)=282所以IA1nA2nA3I=IZ|-(IA1I+IA21+IA3I)+(IA1nA2I+IA1nA3I+IA2nA3I)IA1nA2nA3I=16803X9803X580282=198即相鄰兩元素不相同的排列數(shù)為1983-21求出O(0,0)點到(8,4)點的路徑數(shù)，已知(2,1)至【(4,1)的線路，(3，1)到(3，2)的線路被封鎖?！窘狻浚毫頟(8,4),A

21、(2,1),B(4,1),C(3,1),D(3,2)P1(x)：線段AB在從O到P的路徑X上Z=從O到P的路徑P2(x)：線段CD在從O到P的路徑X上A二xIxZnq(x)(1WiW2)iiIZI=12x11x10x94x3x2x1=495=105=4=84第13頁共42頁】(8-4)+(4-1)、_(3)(7)4-1丿-1丿3丿(2+1)IA1I=11丿=3XIA2I=（3+1）1丿(4)(7)1丿2丿IA1GA2I=0+0=306故此IA1nA2I=IZ|(IA1I+IA2I)+IA1GA2I=495(105+84)因此，從O到P的路，不過線段AB和CD的有306條。322求滿足條件：X+

22、x2+x3=2O1233x,9，0乳小8，7x。17123的整數(shù)解的數(shù)目。解方法一：利用容斥原理二不定方程與如下的不定方程等價：X1+X2+X3=10、0x,6，0乳小8，0x。0，xo0，xo01 23設：X=xIx=(x,x,x)是不定方程6的解;123A=xIx=(x,x,x)是不定方程的解且x6+1=7;1 1231A=xX=(x,x,x)是不定方程的解且x8+1=9;2 1232A=xIx=(x,x,x)是不定方程的解且x10+1=11;3 1233因此，根據(jù)定理3.6.4.可知，不定方程的解的數(shù)目：p0=IXI=(3+101)仃2)仃2)12x1110丿=(10丿=(2丿=2x1=

23、66A1對應的不定方程是:x.+x“+x=10123x,7，xo0，xo0123第19頁共42頁】令：筠二X-711g二x22g=xJ33（評,評,鏟0）。利用我們得到:g+g+g=(x1-7)+x2+x3=(x1+x2+x3)-7=10-7=3123123123所以不定方程的解與下列不定方程：g1+g2+g3=3Ig0,g0,g0123的解一一對應。故根據(jù)定理3.6.4可知，不定方程的解的數(shù)目為:|A|=(3+3-1)(5)(5)5x4=10同理可得:=3|A|=A對應的不定方程是:3廠x,+Xc+Xc=101 23Ix,0，乳小0，x。11123由于解若滿足條件x10,x20,x311，貝

24、y有x+x+x0+0+11=1110123故不定方程沒有解，即|A|=02因此p=|A|+|A|+|A|=10+3+0=131123AcA對應的不定方程是：12廠x,+x“+xo=10J123Ix7，x9，x,0123由于解若滿足條件x17,x29,x30，則有x+x+x7+9+0=1610123故不定方程沒有解，即|AcA|=012同理可得：|AcA|=0，|AcA|=01323因此p=|AcA|+|AcA|+|AcA|=0+0+0=02 121323AcAcA對應的不定方程是：123廠Jx1+x2+x3=10x7，x9，x11123由于解若滿足條件x17,x29,x311，貝9有x+x+x

25、7+9+ll=2710123故不定方程沒有解，即p=1AcAcA1=03 123所以，不定方程、也即不定方程的解的數(shù)目為：q=|AcAcA|=p-p+p-p=66-13+0-0=53。01230123方法二：利用母函數(shù)方法不定方程對應的母函數(shù)是：(1+x+x2+x3+x4+x5+x6)(1+x+x2+x3+x4+x5+x6+x7+x8)(1+x+x2+x3+x4+x5+x6+x7+x8+x9+x10)=(1+2x+3x2+4x3+5x4+6x5+7x6+7x7+7x8+6x9+5x10+4x11+3x12+2x13+x14)(1+x+x2+x3+x4+x5+x6+x7+x8+x9+x10)不定

26、方程的解的數(shù)目為上述母函數(shù)中X10的系數(shù)：1x1+2x1+3x1+4x1+5x1+6x1+7x1+7x1+7x1+6x1+5x1=1+2+3+4+5+6+7+7+7+6+5=53。3.23.求滿足下列條件：x1+x2+x3=40I6X15，5X20，10X25123的整數(shù)解的數(shù)目。解(仿3.22題)方法一利用容斥原理二，不定方程與如下的不定方程等價：；X1+X2+X3=190x,9，0Xc15，0X。0，Xc0，x。0123設：X=xlx=(x,x,x)是不定方程的解;123A=xX=(x,x,x)是不定方程的解且x9+1=10;11231A=xlx=(x,x,x)是不定方程的解且x15+1=

27、16;21232A=xlx=(x,x,x)是不定方程的解且x15+1=16;31233因此，根據(jù)定理3.6.4.可知，不定方程的解的數(shù)目：p0=|X|=(3+19-1)(21)(21)21x2019丿=(19)=(2)=2x1=210A對應的不定方程是：1廠10,xo0,x。0123g二x1011令:隹廣x2(g0,g0,g0)。利用我們得到:22123g=xJ33g+g+g=(x1-10)+x2+x=(x1+x2+x)-10=19-10=9121212所以不定方程的解與下列不定方程：g+g+g=9V123Lg0,g0,g0123的解一一對應。故根據(jù)定理3.6.4可知，不定方程的解的數(shù)目為:|

28、A|=(3+91)(11)(11)11x109丿(9丿(2丿2x1=55同理可得：(3+(1916)1)(5)(5)(19-16J10，x16，x0123由于解若滿足條件x110,x216,x30，貝y有x+x+x10+16+0=2619123故不定方程沒有解，即IAnAI=012同理可得：IAnAI=0，IAnAI=01323因此p=IAnAI+|AnAI+IAnAI=0+0+0=02 1213231+x2+x3=19AcAcA對應的不定方程是：12310,xo16,xo16123由于解若滿足條件X10,x216,x316，則有x+x+x10+16+16=4219123故不定方程沒有解，即p

29、=|AcAcA|=03 123所以，不定方程、也即不定方程的解的數(shù)目為：q=|AcAcA|=p-p+p-p=210-75+0-0=135。01230123方法二：利用母函數(shù)方法不定方程對應的母函數(shù)是(1+x+x2+x3+x4+x5+x6+x7+x8+x9)(1+x+x2+x3+x4+x5+x6+x7+x8+x9+x10+x11+x12+x13+x14+x15)2(1x10)(12x16+x32)=(1-x10-2x16+2x26+x32-x42)3、(4(n+2+2x+2x2+2xn+J乙丿J乙丿J乙丿(1x)322丿(參見第三版習題2.16(P99)或第二版第二章習題7(P131)不定方程的

30、解的數(shù)目為上述母函數(shù)中x19的系數(shù):1X仃1)(5)1x-2x1221x2011x105x42x1-2x1-2x1X1=210-55-20=135。3.24.求滿足下列條件的整數(shù)解的數(shù)目： x1+x2+x3+x4=201x,5，0xo7，4xo8，2xA6O1234解(仿題3.22)方法一：利用容斥原理二，不定方程與如下的不定方程等價: x1+x2+x3+x4=13I0x4，0x7，0x4，0x0，xo0，xo0，x”01234設：X=xlx=(x,x,x,x)是不定方程的解;1234A=xlx=(x,x,x,x)是不定方程的解且x4+1=5;1 12341A=xlx=(x,x,x,x)是不定

31、方程的解且x7+1=8;2 12342A=xlx=(x,x,x,x)是不定方程的解且x4+1=5;3 12343A=xlx=(x,x,x,x)是不定方程的解且x4+1=5;4 12344因此，根據(jù)定理3.6.4.可知，不定方程的解的數(shù)目：第23頁共42頁】(4+13p0=lXl=13(16、J3(16x15xl43x2x1=560A對應的不定方程是：15，x0，x0，x01234g=x511g=x令：仁22(g0,g0,g0,g0)。利用我們得到：g=x1234331g4=x444g+g+g+g=(x_-5)+x_+x_+x.=(x_+x_+x_+x.)-5=13-5=812341234123

32、4所以不定方程的解與下列不定方程：g+g+g+g=81234g0,g0,g0,g01234的解一一對應。故根據(jù)定理3.6.4可知，不定方程的解的數(shù)目為:lAl=1(4+81(11)(11)11x10x93x2x1=1658丿同理可得：(4+(138)1、(8)(8)13-8丿=5丿=3丿lAl=28x7x63x2x1=56(4+(13-5)-1、(11)(11)13-5丿=8J3丿|A|=311x10x93x2x1=165(4+(13-5)-1、(11)(11)13-5丿=8J5,x28,x30,営0x1+x2+x3+x4=13g=x511(g0,g0,g0,g0)。利用我們得到:1234g=

33、x822g=x33g=X*44g+g+g+g=(x1-5)+(x2-8)+x3+x4=(x1+x2+x3+x4)-(5+8)=13-13=0123412341234所以不定方程的解與下列不定方程:g+g+g+g=01234g0,g0,g0,g0的解1234對應。故根據(jù)定理3.6.4可知，不定方程的解的數(shù)目為:|A1nA2|=同理可得:|A1nA3|=|A1nA4|=|A2nA3|=|A2nA4|=0丿=1(4+(13-5-5)-1)(66x5x4I3丿13-5-5丿3x2x1=20(4+(13-5-5)-1(66x5x4I3丿13-5-5丿(4+(13-8-5)-1)(3、10丿13-8-5丿

34、(4+(13-8-5)-1)(3、10丿13-8-5丿3x2x1=20=1=1IA3nA4l6x5x43x2x1=20因此(4+(13-5-5)-1、13-5-5丿p2=|A1nA2|+|A1nA3|+|A1nA4|+|A2nA3|+|A2nA4|+|A3nA4|=1+20+20+1+1+20=63AnA2nA3對應的不定方程是:x+x+x+x=1312345,乳小8,x。5,x”01234由于解若滿足條件X5,x28,x35,x40，貝9有x+x+x+x5+8+5+0=18131234故不定方程沒有解，即iAinA2nA3i=0同理可得:iAinA2nA4i=0,iAinA3nA4i=o,i

35、A2nA3nA4i=op=|AnAnA|+|AnAnA|+|AnAnA|+|AnAnA|=0+0+0+0=03 i23i24i34234AinA2nA3nA4對應的不定方程是：x.+Xc+Xc+x_=13i234x5,x8,x5,x5i234由于解若滿足條件x15,x28,x35,x40，貝9有x+x+x+x5+8+5+5=23i3i234故不定方程沒有解，即p=iAnAnAnAi=04 i234所以，不定方程、也即不定方程的解的數(shù)目為：q0=lA1nA2nA3nA41=p。-p1+p2p3+p4=560551+630+0=72。方法二利用母函數(shù)方法，不定方程對應的母函數(shù)是:(i+x+x2+x

36、3+x4+x5+x6+x7)(i+x+x2+x3+x4)33_(1-x8)(1-3x5+3x10-x15)(1-x)4=(i-3x5-x8+3xi0+3xi3-xi5-3xi8+x23)X2+xn+V第24頁共42頁】(參見第三版習題2.16(P99)或第二版第二章習題7(P131)不定方程的解的數(shù)目為上述母函數(shù)中x13的系數(shù):1X-3x仃1)-1x(8+3xr6+3x16x15x1411x10x93x2x1-3x3x2x16x5x4+3X3x2x1+3x1=560-495-56+60+3=72。325試證滿足下列條件:fx1+x2+x=r12n0xik+1(i=l,2,.,n)i12niA.

37、=xIxgXaP.(x)(i=1,2,.,n)因此，根據(jù)定理3.6.4可知，不定方程的解的數(shù)目為：(r+n1、(n、(r+n1、p0=|X|=n1丿并且，參考第三版P238第3.9節(jié)的方法一，做相應的變換，可得:(n+(r(k+1)1、(r(k+1)+n1、r-(k+1)丿P1=ILIA.I=i=11AinAi1=p2=iin1(1in)(n+(r2(k+1)1、(r2(k+1)+n1、r2(k+1)丿n1(1ijn)1AinAi(n、(r2(k+1)+n1、2丿In-1|AinAinAk|=(r3(k+1)+n1、n1(1ijkn)(n、(r3(k+1)+n1、3丿In-1(rn(k+1)+

38、n1、(n、(rn(k+1)+n1、p=ianAnnAi=n1丿=n1丿n12nn丿丿P3=E1AinAinAkl=iik于是，根據(jù)容斥原理二，可知q0=|A1nA2nnan|=p0-p1+p2p3+(1)npn(n、(r+n1)(n、(r(k+1)+n1、(n、(r2(k+1)+n1、0丿n1丿1丿n1丿+2丿n1丿第45頁共42頁】nn1丿1)+(1)n=工(-1)ii=0r(k+1)i+n1、=rn)k0丿rn)k1xk+1+)rn)k2丿x2(k+1)+.+(-1)nrn)kn丿xn(k+1).rn1)rn)x+rn+1)x2+.+r2n1)kn1)kn1)kn1)kn1)xn+.(參

39、見第三版習題2.16(P99)或第二版第二章習題7(P131)rn)rr+n1)rn)rrr(k+1)+n1)rn)rrr2(k+1)+n1)k0丿kn1)rk1)kn1)+rk2)kn1)不定方程的解的數(shù)目為上述母函數(shù)中xr的系數(shù):rn)+rn)rr3(k+1)+n1)k3丿kn1)+(1)nkn)rrn(k+1)+n1)kn1)=工(1)irn)rr(k+1)i+n1)i=0ki)kn1326試證滿足下列條件：x+x+.+x=r12nV上xik，i=l,2,.,n的整數(shù)解的數(shù)目為：rn)rrrki1)rki)kn1)工(T)ii=0證方法一利用習題3.25的結(jié)論，對不定方程做變換:比=X-

40、111g=X一122”X=g+111X=g+1(于是122)g=X一1nnX=g+1nn則不定方程轉(zhuǎn)化為題3.25型的不定方程:g+g+.+g=rn12n0gk1,0gk1,.,0gk112n不定方程與不定方程的解是一一對應的，故不定方程的整數(shù)解的數(shù)目就是不定方程的整數(shù)解的數(shù)目。因此,不定方程的整數(shù)解的數(shù)目，也即不定方程的整數(shù)解的數(shù)目按題3.25為：(n)(r-n)-(k-1)+1)i+n-1、(-1)i.i=0丿i=0方法二.利用母函數(shù)方法，不定方程對應的母函數(shù)是:(1+X+X2+.+Xk-1)n1-Xk丫1-X丿rnrnX2k+.+(-1)nrn)XnkIn丿rn-1、rnrn+1r2n-

41、1、-+X+X2+.+Xn+.ln-1Jln一1丿ln一1丿in一1丿-1=工(-1)i=0rnrr-ki-1、li丿ln一1丿(參見第三版習題2.16(P99)或第二版第二章習題7(P131)不定方程的解的數(shù)目為上述母函數(shù)中Xr-n的系數(shù)：rnrr-n+n-1、rnrr-n-k+n-1、rnrr-n-2k+n-1、l0丿in一1丿l1丿in一1丿+l2丿in一1丿rnrr-n-3k+n-1)rn)rr-n-nk+n-1、+.+(-1)nl3丿ln-1丿lnJln-1丿rnrr-1)rnrr-k-1、rn)rr-2k-1、l0丿ln一1丿l1丿ln-1丿+l2丿ln-1丿rnrr-3k-1+.

42、+(-1)nrn)rr-nk-1、l3丿ln一1丿ln丿ln-1丿327求n對夫妻排成一列，夫妻不相鄰的排列數(shù)。解n對夫妻有n個男人，n個女人，總計2n個人。設Z=x：x是2n個人的一個排列于是顯然有IZI=(2n)!。定義：P0):在排列x中第i對夫妻相鄰(1in)A.=xIxgZAPi(x)(1in)于是IA.I=2(2n-l)!1(第i對夫妻看作一個整體參加排列，排列數(shù)為(2n-l)!,但這對夫妻內(nèi)部有男女，女男兩種排列)IA.AA.I=22.(2n-2)!(第i對，第j對夫妻看作2個人參加排列，排列數(shù)(2n-2)！ij但ij每對夫妻內(nèi)部有2種排列)IA.AA.nAkl=23.(2n-3

43、)!(第j對夫妻看作3個人參加排列，排列數(shù)(2n-3)！，ijk但i,j,k每對夫妻內(nèi)部有2種排列)IA,nA2n-nAl=2n.n!(n對夫妻看作n個人參加排列，有n!種排列,12n而每對夫妻內(nèi)部有2種排列)于是根據(jù)容斥原理二，有n對夫妻排成一列，夫妻不相鄰的排列數(shù)為：iAnA12nnaI=izi-ni=iIai+工IanA1-工ianAnAi+-+(-i)nianAn-nA1iijijk12nijij1,1in)12ni的整數(shù)解的個數(shù)。做變換g.=x.1(1i0(1in)（rn）+n1、方程的整數(shù)解有r1n-J個故不定方程以及題目的方案有r1n一1丿個。nn+ri1、r1i丿r丿n。證（組合模型法）考慮不定方程:X+