第四章生成函数.docx

第四章 生成函数组合数学 第四章 生成函数 1. 求下列数列的生成函数： 0,1,16,81,n4, 解：Gk=4x(1+11x+11x2+x3)5ìæ3öæ4öæn+3öüíç÷,ç÷,L,ç÷ý 333èøþîèøèøìæn+3öü1解：Gíç= ý÷4îènøþ(1-x)1,0,2,0,3,0,4,0, 解：A(x)=1+2x2+3x4+4x6+=1,k,k2,k3, 解：A(x)=1+kx+k2x2+k3x3+=1. 1-kx1. 21-x2. 求下列和式： 14+24+n4 解：由上面第一题可知，n4生成函数为 x(1+11x+11x2+x3)¥kA(x)=， axåk5k=0此处ak=k.令bn=1+2+n，则bn=åak，由性质3即得数列bn的生4444k=0næi+5öi成函数为 B(x)= åbnx=(x+11x+11x+x)åçx. ÷1-xn=0i=1èiø¥nA(x)234¥比较等式两边xn的系数，便得 æn-1+5öæn-2+5öæn-3+5öæn-4+5ö4441+2+n=bn=ç +11ç+11ç+ç÷÷÷÷èn-1øèn-2øèn-3øèn-4ø301·2+2·3+n(n+1) =1n(n+1)(6n3+9n2+n-1) 解： n(n+1)的生成函数为A(x)= 2x(1-x)3n=åakxk，此处ak= n(n+1). k=0¥令bn=1·2+2·3+n(n+1)，则bn=åak.由性质3即得数列bn的生成k=0函数为B(x)= 1-x(1-x)4比较等式两边xn的系数，便得 n=0åbnx=n¥A(x)=2x=2xåçæk+3ökx. ÷køk=0èn24 组合数学 æn+2ön(n+1)(n+2)1·2+2·3+n(n+1)= bn=2ç. =÷3èn-1ø3. 利用生成函数求解下列递推关系： ìf(n)=7f(n-1)-12f(n-2)í îf(0)=2,f(1)=7解：令A(x)=åf(n)xn n=0¥则有A(x)-f(0)-f(1)x= åf(n)x=å(7f(n-1)-12f(n-2)xnn=2¥n=2¥¥n=7xåf(n)x-12xnn=12åf(n)xn=0¥n=7x(A(x)-f(0)-12xA(x). 将f(0)=2，f(1)=7代入上式并整理，得 ¥2-7x11nnA(x)=+=(3+4). å21-7x+12x1-3x1-4xn=0ìf(n)=3f(n-1)+5×3ní îf(0)=0解：令A(x)=åf(n)xn，则有 n=0¥2A(x)-f(0)= å(3f(n-1)+5×3)xnn=1¥n=3xåf(n)x+15xå3nxn nn=0n=0¥¥=3xA(x)+15x·11-3x. A(x)= í15x2(1-3x)ìf(n)=2f(n-1)+f(n-2)îf(0)=0,f(1)=1¥n=0; 解：令A(x)=åf(n)xn，则有 A(x)-f(0)-f(1)x=å(2f(n-1)+f(n-2)x=2xåf(n)x+xnnn=2¥¥2=2x(A(x)-f(0)+xA(x). 将f(0)=0，f(1)=1代入上式并整理，得A(x)=4. 设序列an的生成函数为：2n=1åf(n)xn=0¥nx1-2x-x2. 4-3x,但b0=a0,b1=a1-a0, 3(1-x)(1+x-x),bn=an-an-1,求序列bn的生成函数. n解：由b0=a0,b1=a1-a0,bn=an-an-1,得åbk=an，所以A(x)= k=0B(x)1-x. 25 组合数学 4-3x，亦即序列bn的生成函数。 31+x-x3-9x5. 已知生成函数,求对应的序列an. 21-x-56x由此得B(x)=(1-x)A(x)= 解：3-9x21-8x1+7x1-x-56x8x-17x+1nn 所以an=-5·8-2·(-7). 6. 有红,黄,蓝,白球各两个,绿,紫,黑球各3个,从中取出10个球,试问有多少种不同的取法？ 解：Mr=My=Mb=Mw=0,1,2，Mg=Mp=Mh=0,1,2,3，所以该取法的个数为 (1+x+x2)4(1+x+x2+x3)3中x10的系数，为678. 7. 口袋中有白球5个,红球3个,黑球2个,每次从中取5个,问有多少种取法？ 解：Mw=0,1,2,3,4,5，Mr=0,1,2,3，Mb=0,1,2，所以从中取5个的取法个 数为(1+x+x2)(1+x+x2+x3) (1+x+x2+x3+x4+x5)中x5的系数，为12。 8. 求1,3,5,7,9这5个数字组成的n位数个数,要求其中3和7出现的次数位偶数,其它数字出现的次数无限制. 解：M1=M5 =M9=0,1,2,3,，M3 =M7=0,2,4, 该排列的生成函数为 x2x4x2112(1+.)(1+x+.)3=(ex+e-x)2e3x=(e5x+e3x+ex) 442!4!2!1¥nxnn=å(5+2×3+1) 4n=0n!=5-2=-5×1-2×1所以an=14(5n+2×3n+1). 9. 用3个1,2个2,5个3这十个数字能构成多少个偶的四位数？ 解：因要组成偶的四位数，所以个位必为2，然后确定其它三位的排列即可. M1=0,1,2,3，M2 =0,1，M3=0,1,2,3,4,5，故生成函数为 x2x3x2x5(1+x)(1+x+)(1+x+L+). 2!3!2!5!x3其中的系数为20，即可以组成20个偶的四位数。 3!10. 求由A,B,C,D组成的允许重复的排列中AB至少出现一次的排列数目. 解：可把AB看作一个整体，用E表示，则 MA=MB=MC=MD=0,1,2,，ME=1,2, x2x24故有(1+x+L)(x+L)=e(4x)(e(x)-1)=e(5x)-e(4x)=5n-4n. 2!2!11. 从n×a,n×b,n×c中取出n个字母,要求a的个数为3的倍数,b的个数是偶数,问有多少种取法? 解：由题意可知，Ma=0,3,6,，Mb=Mc=0,1,2,，该取法的生成函数为 1-x42136232(1+x+x+)(1+x+x+x)=· 31-x1-x12. 把正整数8写成三个非负整数之和，要求n13,n23,n36.问有多少种26 组合数学 不同的方案？ 解：由题意可知，M1=M2 =0,1,2,3，M3=0,1,2,3,6，则生成函数为 (1+x+x2+x3)2(1+x+x2+x3+x6) 1-x421-x71= (=(1-2x4-x7+x8+2x11-x15) · )·31-x1-x(1-x) æ8+2öæ4+2öæ1+2ö 符合题意的方案数为x的系数，为ç÷-2ç2÷-ç2÷+1=13. 2èøèøèø13. 在一个程序设计课程里,每个学生的每个任务最多可以运行10次.教员发现某个任务共运行了38次.设有15名学生,每个学生对这一任务至少做一次.求观察到的总次数的组合数. 解：M1=M2 =M15=1,2,3,10，生成函数为 81-x1015(x+x+x+x)=x， 1-xæ37öæ15öæ27öæ15öæ17ö其中x38的系数为ç÷-ç÷ç÷+ç÷ç÷。 è14øè1øè14øè2øè14ø2310151514. 用1角、2角、3角的邮票可贴出多少种不同数值的邮资？ 解：生成函数为G(x)=(1+x+x2+)(1+x2+x4+)(1+x3+x6+) = 111·· =1+x+2x2+3x3+4x4+ 231-x1-x1-x15. 设多重集合S=¥×e1,¥×e2,¥×e3,¥×e4,an表示集合S满足下列条件的n组合数,分别求数列an生成函数. 每个ei出现奇数次； 每个ei出现4的倍数次i1,2,3,4）； e1出现3或7次,e3出现2,6或8次； 每个ei至少出现6次； 解：由题意知，M1=M2=M3=M4=1,3,5,，故该组合数序列的生成函 ¥æn+3ön¥æn+3ö4+n123444x. 数为(x+x+x+)=x·= x·çx=ç÷4÷(1-x)n=0ènøn=0ènøååXn的系数为çæn-1ö. ÷è3ø由题意知，M1=M2=M3=M4=0,4,8,，故该组合数序列的生成函 1数为(1+x4+x8+)4= . 44(1-x)由题意知，M1=3,7，M2= M4=0,1,2,，M3=2,6,8 故该组合数序列的生成函数为 ¥æn+1ön372682259111315x. (x+x)(x+x+x)(1+x+x+)=(x+2x+x+x+x) ·ç÷n=0è1øåXn的系数为 æn-5+1öæn-9+1öæn-11+1öæn-13+1öæn-15+1öçè1÷+2çøè1÷+çøè1÷+çøè1÷+çøè1÷6n-56. ø27 组合数学 由题意知，M1=M2=M3=M4=6,7,8,，故该组合数序列的生成函 ¥1æn+3ön¥æn+3ö24+n67842424x. 数为(x+x+x+)=x·= x·çx=ç÷÷4(1-x)n=0ènøn=0ènøååæn-21öX的系数为ç÷. 3èøn16. 设多重集合S=¥×e1,¥×e2,¥×e3,L,¥×ek,an表示集合S满足下列条件的n排列 S的每个元素出现偶数次； S的每个元素至少出现4次； S的每个元素至多出现i次； S的每个元素至少出现i次； 解：由题意知，M1=M2=M3=Mk=0,2,4,，故该组合数序列的生成 函数为(1+x222!4!è由题意知，M1=M2=M3=Mk=4,5,6,，故该组合数序列的生成 函数为 23x4x5xxkk(+.)=(e(x)-1-) 4!5!2!3!kkæöiiå e(k-i)x)e(1)+e(2)+e(3)çi÷=(-1)i=0+x4+.)k=çæe(x)+e(-x)ök÷. øèøkiæöin(-1)n1+e(2)+e(3)x/n! ååçi÷=n=0i=0èø¥kæköan=å(-1)ç÷(k-i)n1+e(2)+e(3)i i=0èiøkn由题意知，M1=M2=M3=Mk=0,1,2,i，故该组合数序列的生 x2xik成函数为(1+x+.+). 2!i!由题意知，M1=M2=M3=Mk=i,i+1,i+2,，故该组合数序列的 xixi+1生成函数为 (+.)k. i!(i+1)!17. 用生成函数法证明下列等式： æn+2öæn+1öænöænöç÷-2ç÷+ç÷=ç÷ èrøèrøèrøèr-2ø证明：(1+x)n+2=(1+x)n·(1+x)2=(1+2x+x2) (1+x)n=x2(1+x)n+2(1+x)n+1-(1+x)n ænöæn+1öænöæn+2ö+2-ç÷，对比左右两边xr的系数，左边=ç，右边= ç÷ç÷÷èrøèr-2øèrøèrøæn+2öæn+1öænöænö整理得：ç÷-2ç÷+ç÷=ç÷. èrøèrøèrøèr-2ø等式得证. 28 组合数学 ænöjæqöæn+q-jö(-1)=åç÷ç÷ç÷ rj=0èjøèøèr-qøq证明：(1+x)n(1+x)-1q=xq(1+x)n， 对比左右两边xr的系数， qqöæn+q-jöænöæqöq-jqæ左边=(1+x)åç÷(1+x)=å(-1)ç÷ç，右边=ç， ÷÷jj=0èjøj=0èr-qøèrøèøqn因此等式得证. 18. 设有砝码重为1g的3个,重为2g的4个,重为4g的2个,问能称出多少种重量？各有多少种方案？ 解：由题意知，M1=0,1,2,3，M2=0,1,2,3,4，M4=0,1,2，故生成函数为 (1+x+x2+x3)(1 +x2+x4+x6+x8)(1+x4+x8) =1+x+2x2+2x3+3x4+3x5+4x6+4x7+5x8+5x9+5x10+5x11+4x12+4x13+3x14+3x15+2x16+2x17+x18+x19 故共能称出20种重量，指数即为重量类型，系数为方案数. 19. 求方程x1+2x2+4x3=21的正整数解的个数. 解：由题目可以看出，x1为奇数，故生成函数为 ¥æk+2ö4k3524648127911(x+x+x+)(x+x+x+)(x+x+x+)=(x+2x+x)åç÷x， 2k=0èø展开式中x21的系数为20，亦即该方程正整数解的个数。 æn+3ön2320. H=1+4x+10x+20x+L+çx+L ÷è3ø¥æn+2önx 证明：(1-x)H=åç÷2øn=0è求H的表达式. 解：H的生成函数为Gíçìæn+3öü1=，所以 ý÷4îènøþ(1-x)¥1æn+2ön(1-x)H=x. åç÷32ø(1-x)n=0è21. 数1,2,3, ,9的全排列中,求偶数在原来位置上,其余都不在原来位置上的错排数目. 解：实际上是1，3，5，7，9这5个数的错排问题，总数为 5！-C(5,1)4!+C(5,2)3!-C(5,3)2!+C(5,4)1!-C(5,5)=44. 22. 求整数n拆分成1,2,m的和,并允许重复的拆分数.如若其中m至少出现1次,试求它的方案数和生成函数. 解：因为n拆分成1，2，m的和允许重复，故其生成函数为 G(x)=(1+x+x2+)(1+x2+x4+)(1+xm+x2m+) = 111··· 2m1-x1-x1-x若要m至少出现1次，则生成函数为 G1(x)=(1+x+x2+)(1+x2+x4+)(xm+x2m+) 29 组合数学 xm11= ··· 2m1-x1-x1-x即：整数n拆分成1到m的拆分数，减去n拆分成1到m1的拆分数，即为拆分成1到m，至少出现一个m的拆分数。 23. n个完全相同的球放到m个有标志的盒子,不允许有空盒,问共有多少种不同的方案？其中mn. 解：令n个球放到m个有标志的盒子的方案数为an，由于不允许有空盒，因 此序列an的生成函数为 xmG(x)=(x+x+)(x+x+)(x+x+)= . m(1-x)222(1-x)-m=1+mx+m(m+1)2!x2+ 故其中xn-m的系数为 m(m+1).(m+n-m-1)(n-m)!(n-m)!(m-1)!(n-m)! 即an=C(n-1,m-1) 24. 求在8个字母A,B,C,D,E,F,G,H的全排列中,只有4个元素不在原来的位置上的排列数. 解：8个字母中只有4个不在原来的位置上，其余4个字母保持不动，相当 于4个元素的错排，其数目为4!ç1-=m(m+1).(n-1)=(n-1)!=C(n-1,m-1)æè11!+12!3!+1+1ö÷=9. 4!ø故8个字母的全排列中有4个不在原来位置上的排列数应为C(8,4)·9=630. 30