第四章生成函数.docx

《第四章生成函数.docx》由会员分享，可在线阅读，更多相关《第四章生成函数.docx（23页珍藏版）》请在三一办公上搜索。

1、第四章 生成函数组合数学 第四章 生成函数 1. 求下列数列的生成函数： 0,1,16,81,n4, 解：Gk=4x(1+11x+11x2+x3)534n+3,L, 333n+31解：G= 4n(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)=， axk5k=0此处ak=k.令bn=1+2+n，则bn=ak，由性质3即得数列bn的生4444k=

2、0ni+5i成函数为 B(x)= bnx=(x+11x+11x+x)x. 1-xn=0i=1inA(x)234比较等式两边xn的系数，便得 n-1+5n-2+5n-3+5n-4+54441+2+n=bn= +11+11+n-1n-2n-3n-43012+23+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=12+23+n(n+1)，则bn=ak.由性质3即得数列bn的生成k=0函数为B(x)= 1-x(1-x)4比较等式两边xn的系数，便得 n=0bnx=nA(x)=2x

3、=2xk+3kx. kk=0n24 组合数学 n+2n(n+1)(n+2)12+23+n(n+1)= bn=2. =3n-13. 利用生成函数求解下列递推关系： 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=2n=2n=7xf(n)x-12xnn=12f(n)xn=0n=7x(A(x)-f(0)-12xA(x). 将f(0)=2，f(1)=7代入上式并整理，得 2-7x11nnA(x)=+=(3+4). 21-7x+12x1-3x1-4xn=

4、0f(n)=3f(n-1)+53n; f(0)=0解：令A(x)=f(n)xn，则有 n=02A(x)-f(0)= (3f(n-1)+53)xnn=1n=3xf(n)x+15x3nxn nn=0n=0=3xA(x)+15x11-3x. A(x)= 15x2(1-3x)f(n)=2f(n-1)+f(n-2)f(0)=0,f(1)=1n=0; 解：令A(x)=f(n)xn，则有 A(x)-f(0)-f(1)x=(2f(n-1)+f(n-2)x=2xf(n)x+xnnn=22=2x(A(x)-f(0)+xA(x). 将f(0)=0，f(1)=1代入上式并整理，得A(x)=4. 设序列an的生成函数为

5、：2n=1f(n)xn=0nx1-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=-58-2(-7). 6. 有红,黄,蓝,白球各两个,绿,紫,黑球各3个,从中

6、取出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出现的次数位偶数,其它数字出现的次数无限制. 解：

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!1nxnn=(5+23+1) 4n=0n!=5-2=-51-21所以an=14(5n+23n+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其

8、中的系数为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. 从na,nb,nc中取出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.

9、把正整数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+24+21+2 符合题意的方案数为x的系数，为-22-2+1=13. 213. 在一个程序设计课程里,每个学生的每个任务最多可以运行10次.教员发现某个任务共运行了38次.设有15名学生,每个学生对这一任务至少做一次.求观察到的总次数的组合数. 解：M1

10、=M2 =M15=1,2,3,10，生成函数为 81-x1015(x+x+x+x)=x， 1-x3715271517其中x38的系数为-+。 141142142310151514. 用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或

11、8次； 每个ei至少出现6次； 解：由题意知，M1=M2=M3=M4=1,3,5,，故该组合数序列的生成函 n+3nn+34+n123444x. 数为(x+x+x+)=x= xx=4(1-x)n=0nn=0nXn的系数为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+1n372682259111315x. (x+x)(x+x+x)(1+x+x+)=(x+2x+x+x+x) n=01Xn的系数为 n-5+1n-

12、9+1n-11+1n-13+1n-15+11+21+1+1+16n-56. 27 组合数学 由题意知，M1=M2=M3=M4=6,7,8,，故该组合数序列的生成函 1n+3nn+324+n67842424x. 数为(x+x+x+)=x= xx=4(1-x)n=0nn=0nn-21X的系数为. 3n16. 设多重集合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!由题意

13、知，M1=M2=M3=Mk=4,5,6,，故该组合数序列的生成 函数为 23x4x5xxkk(+.)=(e(x)-1-) 4!5!2!3!kkii e(k-i)x)e(1)+e(2)+e(3)i=(-1)i=0+x4+.)k=e(x)+e(-x)k. kiin(-1)n1+e(2)+e(3)x/n! i=n=0i=0kkan=(-1)(k-i)n1+e(2)+e(3)i i=0ikn由题意知，M1=M2=M3=Mk=0,1,2,i，故该组合数序列的生 x2xik成函数为(1+x+.+). 2!i!由题意知，M1=M2=M3=Mk=i,i+1,i+2,，故该组合数序列的 xixi+1生成函数为

14、(+.)k. i!(i+1)!17. 用生成函数法证明下列等式： n+2n+1nn-2+= rrrr-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 nn+1nn+2+2-，对比左右两边xr的系数，左边=，右边= rr-2rrn+2n+1nn整理得：-2+=. rrrr-2等式得证. 28 组合数学 njqn+q-j(-1)= rj=0jr-qq证明：(1+x)n(1+x)-1q=xq(1+x)n， 对比左右两边xr的系数， qqn+q-jnqq-jq左边=(1+x)(1+x)=(-1)，右边=， jj=

15、0jj=0r-qrqn因此等式得证. 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的正整数解的个数. 解：由

16、题目可以看出，x1为奇数，故生成函数为 k+24k3524648127911(x+x+x+)(x+x+x+)(x+x+x+)=(x+2x+x)x， 2k=0展开式中x21的系数为20，亦即该方程正整数解的个数。 n+3n2320. H=1+4x+10x+20x+L+x+L 3n+2nx 证明：(1-x)H=2n=0求H的表达式. 解：H的生成函数为Gn+31=，所以 4n(1-x)1n+2n(1-x)H=x. 32(1-x)n=021. 数1,2,3, ,9的全排列中,求偶数在原来位置上,其余都不在原来位置上的错排数目. 解：实际上是1，3，5，7，9这5个数的错排问题，总数为 5！-C(5,

17、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，至少出现

18、一个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