《习题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)+
11、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*=I+(a,.i+bn)xv11=0R=I*=l=+%+#-*-l=l+n,+V(v=0)E11=0=I+.r(x)i(x)所以(x-l)A(x)+B(x)=-18(X)=bv.e=
12、+=(4T+-1)-vn0n-ln-1同理,=,xJV-II-O=(.V)+(.V)所以，XA(X)+(x-l)8(,r)=O，解联立方程组，即可得(X-I)A(X)+B(x)=-I.4(.r)+(x-l)(.r)=0A(X)=I-A-l-3,v+B(X)=Xl-3x+(1)(2)(3)(4)解:母函数为：G(X)=I+*+1JJ(2)母函数为：G(6=j+二I4!5!(3)母函数为：GrCv)=112!O-OU,(4)母函数为:-11)-11(12 .设S=l8.q,8.,8e*),求序列的母函数,其中PI)是S的满足下列条件的n排列数：S的每个元素都出现奇数次：S的每个元素至少出现4次；e
13、,至少出现i次=l,2,幻;至多出现i次(i=l,2,；13 .把23本书分给甲乙丙丁四人，要求这四个人得到的书的数批分别不超过9本、8本、7本、6本，问：(1)若23本书相同，有多少种不I司的分法？(2)若23本书都不相同，乂有多少种不同的分法？解：(1)对应的母函数为：G（八）=(1+x+x2+x9)(l+.r+t,)(l+x+x2+,)(I+x+2+x)=(1+2+3+4.v,+5+6a5+7xft+Ix1+7.，+7xi+6产+5x+4x,2+3/+24+,)(l+2.r+3x2+4+5xi+6+7.+8a；+8.ri+7.d+6.vl+5x+4xi+3产+2产+x”)所求的分法数就是
14、F的系数，即7.1+7.2+6.3+5.4+4.5+36+2.7+.8=ll9(种)(2)对应的母函数为:tQ，KYVrt1G,()=(1+-+-+-)(1+-+)1!2!9!1!2!8!所求的分法数就是总的系数，即+_1.+_1.(-_1.(1!9!2!8!3!7!4!6!5!5!6!4!j(5!8!6!7!7!6!jI11I1II(1I2!+3!+4!7!+5!6!+6!5!j4!8!+5!7!+6!6!+7!5!j=2628193998058214.8台计算机分给3个单位,第个单位的分配里不超过3台,第二个单位不超过4台，第三个单位不超过5台，问共有几种分配方案？解：对应的母函数为：G(
15、x)=(I+x+a2+x,)(+x+.v2+x+4X1+x+x2+x+4+x5)=(1+2a+3.v2+4x+4x4+3父+2+FXl+.r+x2+f+x4+H)所求的分配方案数即/的系数，即分配方案数为：4.1+4.1+3.1+2.1+1.1=14(种)15.用母函数证明下列等式成立：/CM2:)证明：(I)方法一：根据范德蒙恒等式方法二：因为+产=+)0+)*两边展开得(o1(KH(犹K比较/次方的系数，即得(2)：令allt=C(t.r)+C(+1.”)+C(j+w./1).则“g=%+C(+m+1，)=am+C(w+m+I,m+I),IIaI)=C(.”)=1，令4(,r)=Z,VM=
16、alt+axxa2x2-0则A(x)=I+x4(x)+C(+11rl,n+I)xm*110即(I-X)A(X)=l+C(M+l.l).v+C(w+2,2)+C(rt+3,3)xs+因为1+C5+1J)x+C(+2,2)x2+C(j+3,3)/+=(DYM,所以(IT)Aa)=(l尸F,A(X)=(1-a-2=l+C(11+2,l).v+C(m+3.2).v2+C(+4.3)x+C(m+m+1.n)xm+所以an=C(n+m+,ni)=C(n+m+.n+),证毕。(l+x)+(l+x)v,+.+(l+x)”=0t)4l-(+x)Tr-4.”,1.hWll113(t+l(n+m(/1+(11+1比
17、较两边的系数，即可得：|+卜+fiI=I“+1.方法三(组合意义法)等式右端：相当于从+m+l个不同的球中取“+I个球的组合，其组合方案数为cm+j+.”+i);等式左端:把这+5+1个球编号为1,2,m+n+l,按取出的球中最小的编号，可分为如下的m+l类：如果取出的+1个球中最小编号是1.其余n个球要从去掉I号球后剩F的+】个球中选取，此类组合方案数为C(+跟”)；如果取出的+1个球中最小编号是2,则1不能被选取，其余n个球要从去擦I.2号球后剩下的+?-1个球中选取，此类组合方案数为C(n+m-l,11):依次类推,如果取出的+1个球中最小编号是m,则1,2.不能被选取，其余n个球要从去
18、掉1,2,.川-1”号球后剩下的”+1个球中选取,此类组合方案数为C5+1.”)；如果取出的“+I个球中最小编号是机+1,则12M不能被选取,其余n个球要从去掉1.2.,利加+1号球后剩卜的n个球中选取，此类组合方案数为；因此，按加法原理，从+?+1个不同的球中取“+1个球的组合方案lC(11,w)+C(w+l,w)+C(11+tn,n)故等式两边相等。16 .证明自然数n分拆为互异的正整数之和的分拆数等于n分拆为奇数之和的分拆数。i正明：将n分拆为互异的正整数之和的分拆数的母函数为：Gl()=(l+.v)(l+x2)(l+x1)(l,t4)(l+x5)(l+x,i)I-X2l-xITiiI-
19、.FJXn)I-X12I-*I-2*l-*l-x4*l-*I-X6*I-A-l-.vl-将分拆为奇数之和的分拆数的母函数为:GG)=(ISD八M)r-/=TT=GG)所以，两种分拆的方.案数相同。17 .求自然数50的分拆总数，要求分拆的每个分项不超过3。解：其母函数为：G(X)=(I+x+./+)(l+.v4+)(l+.)=(I+x+x2+)(1+X2+X4+)(1+.V+X6+)=-(1+(-1),+2(/+I),.(1+-+x6+)(r+2)i为偶数=(l+x6+-.)2-(/+1)i为奇数则所求的分拆数为十的系数，即-(2+3.0+2)+(2+3.1+1)+(2+3.2+2)+(2+3.3+1)+(2+3.15+1)+(2+3.16+2)=2.17+3,1-12*9+1.8=234注：本站资料全部免由！如果您对资料有任何疑问,欢迎咨询QQlI207789S9!本站资料大部分都是自己将理所得.请勿用作商业用途！同时也JE常炊迎迩从这个网站上传您所感兴趣的资料给我，本人不胜感激！不管什么资料，只要伤感兴理就可以！最后推荐您注册千脑网站httpomos1,uircgistcr.h(mVrcmuscrlD342596l19
