习题2与答案.docx

习题二（母函数及其应用）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.r"u-<>»1-0HI_45-4a(l-x)2+i=(I-X)2<3)母函数为：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)-<IIlHO2Y0<4）母函数为:exXfyYY4*-*2G(X)=En(n+2)<=£"(+£H=-7+1-r=。Ii.Ilv.l>(I-X)(-*)(1-4)疲二：G(X)=S(+2)"=£(+1)(+2)x-£(+1)x"-£x"n>0-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+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,e2f>8ej的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=8巧，8%,84,84,求序列0)的母函数“其中.4是S的满足下列条件的n组合数。<1)S的每个元素都HI观奇数次；(2) S的每个元素都出现3的倍数次；<3)弓不出现，叫至多出现一次：<4)弓只出现I、3或Il次，e?只出现2、4或5次；<5)S的每个元素至少出现10次.解：(1)GCr)=(X+./+,u+)4=(p-I(2) G()=(I+x6+,+.)4=p-rj1t(3) G(x)=(1+x)(l+x+x2+xy+)1=H-(-x)G(x)=(x+x3+xiiX2+4+,X+x+.v+x,+)2(4) _(+')(1+f+卜)_P+25+x,+./+/+XIS+产(I-X)2=(IT-(5) G()=(x,"+/+)*=(三)4 .投掷两个骰子，点数之和为r(2Sr=Sl2),其组合数是多少？解：用/表示骰子的点数为i,(1)若两个微了不同,则问题等价于r的特殊有序2-分拆r=4+G16.i=1,2故相应的母函数为G(x)=(X+X4+X6)2=+2x+3f+4xs+51+6.v7+5k+4*+3x'n+2x''+x't则点数之和为r的方案总数就是父的系数(2rl2)°(2)若两个骰子相1可，则问题等价Fr的特殊无序2-分拆r=r+r26a1而此问题又可转化为求r的最大分项等F2,且项数不超过6的分拆数，即求方程J1鹏：2q=的非负整数解的个数.10,X21,xl+26相应的母函数为G(.v)=(l+.v+A2+.+F)X2+(1+x+.V+)(.r)：+(1+X2+x,)(x2)+(1+x2)(x2)4+(I+x)(*)'+(.rj=X2+2x*+2s+3+3.v7+3+2,+3/+x"+.vl3其中点数之和为r的方案数就是x'的系数。5 .投掷4个骰子，其点数之和为12的组合数是多少？解：参考第4题。(第二版第5题居民小区组织义务活动，号召每家出一到两个人参加。设该小区共有n个家庭，现从中选出r人，问：(I)设每个家庭都是3口之家,有多少种不同的选法？当n=50时，选法有多少种？(2)设n个家庭中两家有4l人，其余家庭都是3口人，有多少种选法？解：(1G(X)=(C>+Cf.?f(2)G(M=(C*+2)2(CX+C>2)：(第二版第6题把n个相同的小球放入编号为123.的m个盒了中，使得每个盒子内的球数不小于它的编号数。已知”12,求不同的放球方法数黑几.解：对应母函数为:K,EG(x)=(x+x1+)(x2+xy+xi+).(.vw+-,h+.v,u2+-)=-(1-x)mug>"jJ"m"+l)Jn(m+l)(m+2),1!2!3!+制加+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的系数，即l×l+2×l+3×l+4×l+5×l+6×l+7×l=28(种)厩二，原问题等价于从集合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一!_(+x"+.)=',÷(->)iv÷QDl41.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+产+产)=l+x+2xj+24+2f+3.d+3x7+2+2xq+2”+3x”+3x'1+2xli+2xm+2x,i+3产+3/+2d+2/+-+2/+产+户所以能称123克等23种重量的物品.总共的称法为母函数的各项系数之和，再减去常数项，即总共有G(1)-i=3×4×4-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"=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+.)"=(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*=