习题2与答案.docx

《习题2与答案.docx》由会员分享，可在线阅读，更多相关《习题2与答案.docx（14页珍藏版）》请在第壹文秘上搜索。

1、习题二（母函数及其应用）I.求卜列数列的母函数（=0,2）2)3)4)+5):j(-1)J：“+2):解：（1）母函数为：G（K）=Z（T）*1-0(211=qs母函数为：G(X)=(5*=*+52八万士不+V7=怒rt-oAf.-OUr)I-AU-A)触二，G(X)=(+5)x=(t+l)4.ru-1-0HI_45-4a(l-x)2+i=(I-X)23)母函数为：G(X)OiTw吃5+1*-2夕*=言-言=言7:-:G(x)=Z(-1)q=O+O+./(-1)n-2-0*-2=(11+2)(n+l)x=(xo*1)-IIlHO2Y04）母函数为:exXfyYY4*-*2G(X)=En(n+2

2、)(I-X)(-*)(1-4)疲二：G(X)=S(+2)=(+1)(+2)x-(+1)x-xn0-0Hn-0=(2f-(,)-r三(2)-(,j-=田【口3一，u-vjU-rJI-V(l-x)s(I-X)-l-r3x-x22.证明序列。(.).(+1.).。(+2.”)的母函数为-(1-)证明:因为C(n+k,n)C(n+k-,n)+C(n+k-,n-i)令G,(x)=Z。(+A.)/=C(.)+C(+1,)x+C(+2,)/+C(+3,)./+JkTl则xGn(x)=C(n.n)+C(i+1,n)x2+C(z+2.11)x1+.G“_G)=C(-l,-D+C(.-Dx+C(+1.-l)x2+

3、C(+2.-l)x+而(IT)G)-GBTa)=O故GlI(X)=JG11(x)=-GT(X)=1G0(x)I(I)(I)G0(x)=C(O1O)+C(1.0)x+C(2,O)x2+C(3,O).+又=1+x+2+,+.=E旋二：已知S=gq,e2f8ej的k-组合数为C(n+k-l),其母函数为：A(X)=(I+x+x2+f+)=:二=(“+：1(I-X)AfIk序列C(n,n),C(+l,n),C(n+2,n),的母函数为G(X)=(?(.)+(?(+1.j)-v+C(j+2.”x?+C(“+3,n)x,+=c(+&,)x=c(+A,A)fJk=OA=O0=Zq+u*-I二(I严3.设5=

4、8巧，8%,84,84,求序列0)的母函数“其中.4是S的满足下列条件的n组合数。1)S的每个元素都HI观奇数次；(2) S的每个元素都出现3的倍数次；3)弓不出现，叫至多出现一次：4)弓只出现I、3或Il次，e?只出现2、4或5次；+Cf.?f(2)G(M=(C*+2)2(CX+C2)：(第二版第6题把n个相同的小球放入编号为123.的m个盒了中，使得每个盒子内的球数不小于它的编号数。已知”12,求不同的放球方法数黑几.解：对应母函数为:K,EG(x)=(x+x1+)(x2+xy+xi+).(.vw+-,h+.v,u2+-)=-(1-x)mugjJm+l)Jn(m+l)(m+2),1!2!3

5、!+制加+1)，”+一一(川+1)-1|1-+11-n(11+1)!1(，+1%.(一加-1)(n-m(w+l)J!+1)j+一阳(川+1)-11t-w(n+l)j!6.红、黄、蓝三色的球各8个，从中取出9个，要求每种颜色的球至少一个，间有多少种不同的取法？解：对应的母函数为：G(X)=(x+x1+x4+x5+Xi+X*)3=(I+X+X2+X5+X6+x,)=(l+2,v+3.r+4+5.+6r+7.r6+8F+7,/+6/+5.”+4x+3。2+2产+x*)(1+x+x+.+XS+1+M)从中取9个对应的组合数为r的系数，即ll+2l+3l+4l+5l+6l+7l=28(种)厩二，原问题等

6、价于从集合S=8a8仇8。中取出9个元素,I1每个元素至少取一个。现在先把元素a、b、C各取一个，然后再随意选出6个，则问题转变为从集合S=77.7c中取出6个元素，且每个元素个数不限，求重复组合的方案数。又由于每个元素的个数大于6,故从$中取6个元素与从集合Sl.a,b,8c中取出6个元案的组合数一样多，因此不I可的取法为Ms=C=28(种)7 .将币值为2角的人民币，兑换成硬币(壹分、贰分和伍分)可有多少种兑换方法？解：该题用1分、2分、5分的硬币组成20分。是可重兔的无序拆分：G(X)=(I+x+2+)(1+2+x4+)(1+xi+a10+)其母函数为：=1.-1.+1.-1.+1一!_

7、(+x+.)=,(-)ivQDl41.41/1-1=-(l+(-l),+2(+l)x,.(l+.+x,+)4MO则不同的兑换方法为Xxl的系数,即l+(-l)a,+2(20+1).1+(-l),s+2(15+1).1+l+(-l),o+2(IO+l).l+l+(-l)s+2(5+l).l+l+(-l)n+2(O+l).lJ=29即有29种兑换方法.8 .有1克重硅码2枚，2克重硅码3枚，5克重跌码3枚，要求这8个硅码只许放在天平的一端，能称几种1R量的物品？有多少种不同的称法？解：该题属于有限克夏的无序拆分问即。对应的母函数为：G（八）=(l+x+)(l+xi+.V4+X6)(1+Xs+产+产

8、)=l+x+2xj+24+2f+3.d+3x7+2+2xq+2”+3x”+3x1+2xli+2xm+2x,i+3产+3/+2d+2/+-+2/+产+户所以能称123克等23种重量的物品.总共的称法为母函数的各项系数之和，再减去常数项，即总共有G(1)-i=344-l=47(种)不同的称法。其中，称1、3、20、22、23克重量各有1种称法：称2、4、5、8,9、10、13、14、15、18、19、21克重量各有2种称法；称6、7、II、12、16、17克重量各有3种乘法；若耍枚举出各种方案，则可作母函数：G(My,)=(l+.r+x2)(l+y2+/)(1+i+a+z,s项x5尸产ZyZM,q

9、=i或0)即为称M1+n2+nj,+%-+%+%+ns=克重量的一种方案。9 .证明不定方程+七+.+&=/的正整数解组的个数为C(r-1.-1)解：该问题即，求正整数r的n有序分拆。问题可转换为：将r个无区别的球，放入n个不同的盒子中，每盒至少I个的组合问题。可以先在每个盒子中放1球，再将r-个无区别的球，放入n个不同的盒子中，每盒球数不限，则其方案数为：C(十(r-)T.m)=C(,l.zt-l)故该不定方程的正整数解组的个数为C-1.l1)o厩二：问题可以视为聘r个相同的I放入n个盒子。由于将天之间的值互换，对应不同的解，所以盒子不同。设共有明个解，则,的母函数为G(X)=(X+/+F+

10、.)=(j-)=/力C=力-3尸=力=cr,r-0r-A-OC-O所以z=C(r-l.j-l)10 .求方程x+y+z=24的大于I的整数解的个数。解：该题相当于将24的3有序分拆,并II要求每个分项大于1。其母函数为：G(XM+/=居)=H居卜;啥W所求的整数解的个数即为小的系数：.19.(19+1)=190.11 .设见=SC5+32A)，1=XC(w+.2+l),其中怎=1,%=0。试证:A=O1.0(I)a.a“n，bn,l=all+bnt(2)求出%、也的母函数A(x),B(x),jV*Iaatl=C(n+k.2k)=C(+1.0)+C(,j+I+A.2)-l.hh.=C(n,0)+C(f+k,2k)C(n-k,2k-)ilk91J)A=I-MC=ZC(+A2A)+ZC(n+E2+l)(.C(n+n+1.2+2)=O)=11+ZC(+A+l,2A+l)(.C(+1+m+1,2+3)=0)-0=fln+lrAan+i=ZC(+A2k)+ZCS+,22+1)c=o=1=yC(n+1.2+1)A-Ol=ZC5+1+入2A+1)(.C(211+2.2n+3)=0)A=O=如(2)因为A(X)=%+K*=