组合数学习题解答ex2

1.=++++nnnnnnn2...210222287m=n,r=nnnnxxx2)1()1()1(+=++nx==−∑∑==nnknknnknxnknkn2:020nnxx)11()1(++2.(1+x4+x8)100x20.4x+8y=20x+2y=5x=5,y=0;x=1,y=2x=3,y=1()()!5!95!100085495:1xx()()!1!3!96!100183496:1xx()()!2!1!97!100281497:1xx91457520.3.310(1+x+x2)4(1+x+x2+x3)3x10(1-x3)4(1-x4)3/(1-x)7x3:00011223x4:01201010x:106273401+−++−+++−+++−+11634446241324336131477614226236661310106=6784.A,B,C,DABanbnABan+bn=4n,bn=4bn-1-bn-2,an=4an-1+bn-2,b1=4,b2=15,b0=1,b3=56.x2-4x+1=0x=32±bn=S(2+3)n+t(2-3)n()()=−++=+432321tStSS=3232+,t=3232−−()()−−+=++113213232nnnb()()−−+−=++1132132324nnnna()()−++−=++1132132324nnnna5.n23()()()1222...!4!21...!212441222412224222++=++=+=++++++=−−xxxxxxxxeeeeeeeeexxxxxG()114124224:!−−+=⋅+nnnnnnx0,222211243)24()24(−−−−−−+×=+−+nnnnnn.6.a,b,cnaaaaanna,n-1bcabc.an=2an-1+2an-2a1=3a2=8a0=1.x2-2x-2=0,x=31±an=A(1+3)n+B(1-3)n()()=−++=+331311BABAA=()34312+,B=()34312−−()()−++−=++223413131nnnaaka1nkC(n-k+1,k)-27knnkkkn−=∑+−2120knnkkkn−=∑+−2120=6)31)(323()31)(323(nn−−+++7.C(n,n),C(n+1,n),C(n+2,n),...()111+−nxnn=0,n-1()nkxxnkn−=−+−∑1111()()()nnkkknxxxGxnknxnknxnknxG−+=−+−++−=+=∑∑∑11111()()nknxxxnknxG−⋅−=+=∑1111121...)1(.)1(1+++++=−nnxxxxrar(n+1)rxr(n+1)+=−++=nrnnrnar118.C(n,n)+C(n+1,n)++C(n+m,n)=C(n+m+1,n+1).mm=0m-1,C(n,n)+C(n+1,n)++C(n+m-1,n)+C(n+m,n)=C(n+m,n+1)+C(n+m,n)=C(n+m,m-1)+C(n+m,m)=C(n+m+1,n+1).7n+2n+1n+2n+2mn+101mmm-1m-20n+m+1n+1n+m+1:n+11C(n+m,n);2C(n+m-1,n)mC(n,n)C(n,n)+C(n+1,n)++C(n+m,n)=C(n+m+1,n+1)9.63121112222π=+++L4(2)pnxxxG−16)(ln2πxxnxxxnxxPn)1(161ln16ln22−+−+−ππ)1,0(∈∀x,ππ32)1(162ln2nxxnxxPn=−−π32nneP10.83132435)1)(1)(1(543243232xxxxxxxxxxxx++++++++++++x81411.nFibonacci1,0,0,12===+≥∑iiiiiiaaaFan.F1=F2=1Fibonacci:(n).1n=12nn+1kn+1=Fkk,Fkn+1Fk+1n+1-FkF,iik-1.(Fk-1=n+1-FkFk+1-Fk=Fk-1,)n+1FF2m=F2m-1+F2n-3++F3+F112.n34nnannn-1n-1nnan=an-1+n++=2210nAnAAana0=1,a1=2,a2=4,A0=A1=A2=1++=21nnanbn=bn-1+an-1,+++=323210nBnBnBBbnb0=1,b1=2,b2=4,b3=8,B0=B1=B2=B3=1+++=321nnnbndnd-1nadna,=∑=dkkn0nd≤dna,=∑=dkkn0=d21+=nd,dna,=∑=dkkn0=d2-1.13.0n200n2hnan0n1,nhn-101nhn-221−−+=nnnhhhh1=2,h2=3,h0=1.hnFab2n=2an14.HanoiAn1nBCn1n-1CB2nC3n-3CA4n-2BnBCk(1)=1,k(2)=2,k(3)=5h(k)Hanota−=73275)(nnk15.mnmkm-kk=0∑=−+mkmnkmnkkDDnDkm2)!(16.ABCD,C1B1AB1C1DB1C1CDABCD...AD1AB17.nnnannn-1n-1nnan=an-1+n++=2210nAnAAana0=1,a1=2,a2=4,A0=A1=A2=1++=21nnanbn=bn-1+an-1,+++=323210nBnBnBBbnb0=1,b1=2,b2=4,b3=8,B0=B1=B2=B3=1+++=321nnnbn18.nn-1an-1nn-133nnnn-11n-1nn19.n11an,n010an-11n-10,an-2.5,3,2,1,321021====+=−−aaaaaaannn012=−−xx,251,25121−=+=∴xxnnnBxAxa21+==−++=[phone]BABA−⋅−=+⋅=222515125151BA−++⋅=++22)251()251(51nnna20.nkakAB21.14+24+34+...+n4n422.1002013−−=−==−−−−−−−111111203201320132032032013nnnnnnnnnnaaa,-3n-1+2an-1=3an-1-2n-1,an-1=2n-1-3n-1,an=2n-3n−=−10010010010010020323201323....24.nr1rr-1rrr-13nr1r+++=∴nnnnnnan4)6(4)3)(1(25.anna()−++=+−−nnanaannnn41,2133b{an}Inar-31arabc(a+b)-c=2a+b-2c-1ar1ar-3IInIarar-3a+b-c=122(2)322−=kkaa4)1(1212212+−+−+++=kkkkaa∑+∞==022)(kkkxaxf12012)(++∞=+∑=kkkxaxg)()(3232323220022xgxxaxxaaxaxfkkkkkk=++==∑∑+∞=−−+∞=()()()()424320123111222222312112211201211)(11144)(41244)1(12)(xxxxfxxxxxxxfxxxxkxxaxxkaxaxaxgkkkkkkkkkkkkkkkk−−+=−+−′−+=−−++=−++++==∑∑∑∑∑∑∞+=+∞+=∞+=∞+=−−++∞=+−++∞=+()()()6427111)(xxxxxf−−−=()()()6424111)(xxxxxg−−−={}na()()()4324111)()(xxxxxgxf−−−=+26.albfn2ngn2n+1fngn...al=131l=21222223xyzl=2k+1x+y=2k+2k+112k+122k...k+1k+1x+y=2k+3k22k+132k...k+1k+2x+y=2k+4k32k+142k...k+2k+2x+y=4k+112k2k+1x+y=4k+212k+12k+1l=2kx+y=2k+1k12k22k-1...kk+1x+y=2k+2k22k32k-1...k+1k+1x+y=2k+3k32k42k...k+2k+2x+y=4k-112k-12kx+y=4k12k2kb27.aan+1=an+bn+1,bn+1=an+bnb{an}{bn}cFibonaccianbn...ab)+=++=)()()()()(1)(xxgxxfxgxgxxfxf2311)(xxxxf+−−=231)(xxxxg+−=c28.F1=F2=1,Fn=Fn-1+Fn-2a1,11+=−−+−knFFFFFknkknknbFm|Fnm|nc2,...211062≥≥++++=−+−+−+−+−+nmnFnFFFFFFnmnmnmnmmnnmd(Fm,Fn)=F(m,n),(m,n)m,nakk=2Fn=F2Fn-2+1+F1Fn-2kk+1Fn=FkFn-k+1+Fk-1Fn-k=Fk(Fn-k+Fn-k-1)+Fk-1Fn-k=(Fk+Fk-1)Fn-k+FkFn-k-1=Fk+1Fn-k+FkFn-k-1bmm=0mmn,nmnnmnmFFFFF−−+−+=11nmnnmnFFFFF−−↔1Fn,Fn-1=1,nmnnmnnFFFFF−−−↔1,mnnmnFFnmn↔−↔−c)n.n=2n=3FmF3=Fm+3-2+Fm-3+1=Fm+1+Fm-2=Fm+Fm-1+Fm-Fm-1=2Fm,n+++=+−−−+−−−−−+−−−+−−−n,n2)2(21)2(262222222nmnmnmnmnmFFFFFFLFmFn=Fm+n-1-Fm-1Fn-1=Fm+n-1–(Fm-1+n-1-1–Fm-2Fn-2)=Fm+n-2+Fm-2Fn-2+++=+−+−−+−+n,n2162nmnmnmnmnmFFFFFFLdmax{m,n}m=nmnmax{m,n}nmnnmnmFFFFF−−+−+=11()()()()()nmFnnmFFFFFFFFnnmnnmnnm,,,,,1=−===−−−29.1nkf(n,k)af(n,k)bf(n,k)c1n1nkkg(n,k)f(n,k)g(n,k)abc30.S2(n,k)Stirling()()1,,1212−=+∑−=mkSknmnSnmk.n+1n-kkm-1k=m-1,m,,nnkm-13