第四章生成函数

第四章生成函数

1. 求下列数列的生成函数：（1）{0,1,16,81,…, n 4, …} 解：G{k}=

x (1+11x +11x 2+x 3)

（1-x ）

⎧⎛3⎫⎛4⎫⎛n +3⎫⎫（2）⎨ ⎪, ⎪, , ⎪⎬ 333⎝⎭⎭⎩⎝⎭⎝⎭

⎧⎛n +3⎫⎫1解：G ⎨ = ⎬⎪4

⎩⎝n ⎭⎭(1-x ) （3）{1,0,2,0,3,0,4,0,……} 解：A(x)=1+2x2+3x4+4x6+…=（4）{1,k , k 2, k 3, …}

解：A(x)=1+kx+k2x 2+k3x 3+…=

. 1-kx 1

. 2

1-x

2. 求下列和式：（1）14+24+…+n 4

解：由上面第一题可知，{n4}生成函数为

x (1+11x +11x 2+x 3) ∞k

A(x)==， a x ∑k 5

（1-x ）k =0

此处a k =k. 令b n =1+2+…+n ，则b n =∑a k ，由性质3即得数列{bn }的生

k =0n

⎛i +5⎫i

成函数为 B(x)= ∑b n x ==(x +11x +11x +x ) ∑ x . ⎪1-x n =0i =1⎝i ⎭

∞

A (x )

234

∞

比较等式两边x n 的系数，便得

⎛n -1+5⎫⎛n -2+5⎫⎛n -3+5⎫⎛n -4+5⎫444

1+2+…+n =bn = +11 +11 + ⎪⎪⎪⎪

⎝n -1⎭⎝n -2⎭⎝n -3⎭⎝n -4⎭

（2）1·2+2·3+…+n (n +1)

n (n +1)(6n 3+9n 2+n -1)

解：{ n(n +1)}的生成函数为A(x)=

2x (1-x ) 3

=∑a k x k ，此处a k = n(n +1).

k =0

∞

令b n =1·2+2·3+…+n (n +1)，则b n =∑a k . 由性质3即得数列{bn }的生成

k =0

函数为B(x)=

1-x (1-x ) 4

比较等式两边x n 的系数，便得

n =0

∑b n x =

∞

A (x )

=2x ∑

⎛k +3⎫k

x . ⎪k ⎭k =0⎝

⎛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) （1）⎨;

⎩f (0)=2, f (1)=7解：令A(x)=∑f (n ) x n

n =0∞

则有A(x)-f(0)-f(1)x=

∑f (n ) x =∑(7f (n -1) -12f (n -2)) x

n =2∞

n =2

∞

=7x ∑f (n ) x -12x

n =1

∑f (n ) x

n =0

∞

=7x(A(x)-f(0))-12xA(x).

将f(0)=2，f(1)=7代入上式并整理，得

∞

2-7x 11n n

A (x ) ==+=(3+4) . ∑2

1-7x +12x 1-3x 1-4x n =0

⎧f (n ) =3f (n -1) +5⋅3n

（2）⎨;

⎩f (0)=0解：令A(x)=∑f (n ) x n ，则有

n =0∞

A(x)-f(0)=

∑(3f (n -1) +5⋅3) x

n =1

∞

=3x ∑f (n ) x +15x ∑3n x n

n =0

∞∞

=3xA(x)+15x·

11-3x

A(x)= （3）⎨

15x

(1-3x )

⎧f (n ) =2f (n -1) +f (n -2)

⎩f (0)=0, f (1)=1

∞n =0

;

解：令A(x)=∑f (n ) x n ，则有

A(x)-f(0)-f(1)x=∑(2f (n -1) +f (n -2)) x =2x ∑f (n ) x +x

n =2∞

∞

=2x(A(x)-f(0))+xA(x).

将f(0)=0，f(1)=1代入上式并整理，得A (x ) =4. 设序列{a n }的生成函数为：

n =1

∑f (n ) x

n =0

∞

x 1-2x -x

4-3x

, 但b 0=a 0, b 1=a 1-a 0, 3

(1-x )(1+x -x )

……, b n =a n -a n -1, ……, 求序列{b n }的生成函数.

解：由b 0=a 0, b 1=a 1-a 0, ……, b n =a n -a n -1, 得∑b k =a n ，所以A(x)=

k =0

B (x ) 1-x

4-3x

，亦即序列{b n }的生成函数。 3

1+x -x 3-9x

5. 已知生成函数, 求对应的序列{a n }. 2

1-x -56x

由此得B(x)=(1-x)A(x)= 解：

3-9x

1-8x 1+7x 1-x -56x 8x -17x +1

n n

所以a n =-5·8-2·(-7).

6. 有红, 黄, 蓝, 白球各两个, 绿, 紫, 黑球各3个, 从中取出10个球, 试问有多少种

不同的取法？

解：M r =My =Mb =Mw ={0,1,2}，M g =Mp =Mh ={0,1,2,3}，所以该取法的个数为

(1+x+x2) 4(1+x+x2+x3) 3中x 10的系数，为678.

7. 口袋中有白球5个, 红球3个, 黑球2个, 每次从中取5个, 问有多少种取法？解：M w ={0,1,2,3,4,5}，M r ={0,1,2,3}，M b ={0,1,2}，所以从中取5个的取法个

数为(1+x+x2)(1+x+x2+x3) (1+x+x2+x3+x4+x5) 中x 5的系数，为12。

8. 求1,3,5,7,9这5个数字组成的n 位数个数, 要求其中3和7出现的次数位

偶数, 其它数字出现的次数无限制.

解：M 1=M5 =M9={0,1,2,3,…}，M 3 =M7={0,2,4,…}

该排列的生成函数为

x 2x 4x 2112

(1+++...) (1+x ++...) 3=(ex +e-x ) 2e 3x =(e5x +e3x +ex )

442! 4! 2!

1∞n x n n

=∑(5+2⋅3+1) 4n =0n !

=-5⋅

-2⋅

所以a n =

(5n +2⋅3n +1) .

9. 用3个1,2个2,5个3这十个数字能构成多少个偶的四位数？

解：因要组成偶的四位数，所以个位必为2，然后确定其它三位的排列即可.

M 1={0,1,2,3}，M 2 ={0,1}，M 3={0,1,2,3,4,5}，故生成函数为

x 2x 3x 2x 5

(1+x )(1+x ++)(1+x ++ +) .

2! 3! 2! 5!

x 3

其中的系数为20，即可以组成20个偶的四位数。

10. 求由A,B,C,D 组成的允许重复的排列中AB 至少出现一次的排列数目. 解：可把AB 看作一个整体，用E 表示，则

M A =MB =MC =MD ={0,1,2,…}，M E ={1,2,…}

x 2x 24

故有(1+x ++ ) (x ++ ) =e(4x)(e(x)-1)=e(5x)-e(4x)=5n -4n .

2! 2!

11. 从{n ⋅a , n ⋅b , n ⋅c }中取出n 个字母, 要求a 的个数为3的倍数, b 的个数是

偶数, 问有多少种取法?

解：由题意可知，M a ={0,3,6,…}，M b =Mc ={0,1,2,…}，该取法的生成函数为

1-x 42136232

(1+x+x+…)(1+x+x+x) =·() 3

1-x 1-x

12. 把正整数8写成三个非负整数之和，要求n 1≤3,n 2≤3,n 3≤6. 问有多少种

不同的方案？

解：由题意可知，M 1=M2 ={0,1,2,3}，M 3={0,1,2,3,…,6}，则生成函数为 (1+x+x2+x3) 2(1+x+x2+x3+…+x6)

1-x 421-x 71= (=(1-2x4-x 7+x8+2x11-x 15) · ) ·3

1-x 1-x (1-x )

⎛8+2⎫⎛4+2⎫⎛1+2⎫

符合题意的方案数为x 的系数，为 ⎪-2 2⎪- 2⎪+1=13. 2⎝⎭⎝⎭⎝⎭

13. 在一个程序设计课程里, 每个学生的每个任务最多可以运行10次. 教员发

现某个任务共运行了38次. 设有15名学生, 每个学生对这一任务至少做一次. 求观察到的总次数的组合数.

解：M 1=M2 =…=M15={1,2,3,…,10}，生成函数为

1-x 1015

(x+x+x+…+x) =x () ，

1-x

⎛37⎫⎛15⎫⎛27⎫⎛15⎫⎛17⎫

其中x 38的系数为 ⎪- ⎪⎪+ ⎪⎪。

⎝14⎭⎝1⎭⎝14⎭⎝2⎭⎝14⎭

1015

14. 用1角、2角、3角的邮票可贴出多少种不同数值的邮资？解：生成函数为G(x)=(1+x+x2+…)(1+x2+x4+…)(1+x3+x6+…)

111·· =1+x+2x2+3x3+4x4+… 23

1-x 1-x 1-x

15. 设多重集合S ={∞⋅e 1, ∞⋅e 2, ∞⋅e 3, ∞⋅e 4}, a n 表示集合S 满足下列条件的

n 组合数, 分别求数列{a n }生成函数. （1）每个e i 出现奇数次（i ＝1,2,3,4）；（2）每个e i 出现4的倍数次i ＝1,2,3,4）；（3）e 1出现3或7次, e 3出现2,6或8次；（4）每个e i 至少出现6次（i ＝1,2,3,4）；解：（1）由题意知，M 1=M2=M3=M4={1,3,5,…}，故该组合数序列的生成函

∞

⎛n +3⎫n ∞⎛n +3⎫4+n 123444

x . 数为(x+x+x+…) =x·= x· x = ⎪4⎪(1-x ) n =0⎝n ⎭n =0⎝n ⎭

∑∑

X n 的系数为

⎛n -1⎫

. ⎪⎝3⎭

（2）由题意知，M 1=M2=M3=M4={0,4,8,…}，故该组合数序列的生成函

数为(1+x4+x8+…) 4= . 44

(1-x )

（3）由题意知，M 1={3,7}，M 2= M4={0,1,2,…}，M 3={2,6,8} 故该组合数序列的生成函数为

∞

⎛n +1⎫n [**************]

x . (x+x)(x+x+x)(1+x+x+…) =(x+2x+x+x+x) · ⎪

n =0⎝1⎭

∑

X n 的系数为

⎛n -5+1⎫⎛n -9+1⎫⎛n -11+1⎫⎛n -13+1⎫⎛n -15+1⎫

⎝

⎪+2 ⎭⎝

⎪+ ⎭⎝

⎪＝6n-56. ⎭

（4）由题意知，M 1=M2=M3=M4={6,7,8,…}，故该组合数序列的生成函

∞

1⎛n +3⎫n ∞⎛n +3⎫24+n 67842424

x . 数为(x+x+x+…) =x·= x· x = ⎪⎪4

(1-x ) n =0⎝n ⎭n =0⎝n ⎭

∑∑

⎛n -21⎫

X 的系数为 ⎪. 3⎝⎭

16. 设多重集合S ={∞⋅e 1, ∞⋅e 2, ∞⋅e 3, , ∞⋅e k }, a n 表示集合S 满足下列条件的n 排列

（1）S 的每个元素出现偶数次；（2）S 的每个元素至少出现4次；

（3）S 的每个元素至多出现i 次（i =1,2,…,k ）；（4）S 的每个元素至少出现i 次（i =1,2,…,k ）；解：（1）由题意知，M 1=M2=M3=…=Mk ={0,2,4,…}，故该组合数序列的生成

函数为(1+

x 2

22! 4! ⎝

（2）由题意知，M 1=M2=M3=…=Mk ={4,5,6,…}，故该组合数序列的生成函数为

x 4x 5x x k k

(++...) =(e (x ) -1--) 4! 5! 2! 3!

k k ⎛⎫i i ∑ e ((k -i ) x )[e (1)+e (2)+e (3)] i ⎪=(-1)

i =0

x 4

+...) k =

⎛e (x ) +e (-x ) ⎫

⎪.

⎭

⎝⎭

k i ⎛⎫i n

((-1) n [1+e (2)+e (3)]) x /n ! ∑∑ i ⎪=

n =0i =0⎝⎭

∞

⎛k ⎫

a n =∑(-1) ⎪(k -i ) n [1+e (2)+e (3)]i

i =0⎝i ⎭

（3）由题意知，M 1=M2=M3=…=Mk ={0,1,2,…,i}，故该组合数序列的生

x 2x i k

成函数为(1+x ++... +) .

2! i !

（4）由题意知，M 1=M2=M3=…=Mk ={i,i+1,i+2,…}，故该组合数序列的

x i x i +1

生成函数为 (++...) k .

i ! (i +1)!

17. 用生成函数法证明下列等式：

⎛n +2⎫⎛n +1⎫⎛n ⎫⎛n ⎫（1） ⎪-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- ⎪，对比左右两边x r 的系数，左边= ，右边= ⎪ ⎪⎪

⎝r ⎭⎝r -2⎭⎝r ⎭⎝r ⎭

⎛n +2⎫⎛n +1⎫⎛n ⎫⎛n ⎫

整理得： ⎪-2 ⎪+ ⎪= ⎪.

⎝r ⎭⎝r ⎭⎝r ⎭⎝r -2⎭

等式得证.

（2）

⎛n ⎫j ⎛q ⎫⎛n +q -j ⎫(-1) =∑ ⎪⎪ ⎪

r j =0⎝j ⎭⎝⎭⎝r -q ⎭

证明：(1+x)n [(1+x)-1]q =xq (1+x)n ，

对比左右两边x r 的系数，

q ⎫⎛n +q -j ⎫⎛n ⎫⎛q ⎫q -j q ⎛左边=(1+x ) ∑ ⎪(1+x ) =∑(-1) ⎪，右边= ， ⎪⎪j j =0⎝j ⎭j =0⎝r -q ⎭⎝r ⎭⎝⎭

q n

因此等式得证.

18. 设有砝码重为1g 的3个, 重为2g 的4个, 重为4g 的2个, 问能称出多少种

重量？各有多少种方案？

解：由题意知，M 1={0,1,2,3}，M 2={0,1,2,3,4}，M 4={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. 求方程x 1+2x2+4x3=21的正整数解的个数. 解：由题目可以看出，x 1为奇数，故生成函数为

∞

⎛k +2⎫4k [1**********]11

(x+x+x+…)(x+x+x+…)(x+x+x+…)=(x+2x+x) ∑ ⎪x ， 2k =0⎝⎭展开式中x 21的系数为20，亦即该方程正整数解的个数。

⎛n +3⎫n 23

20. H =1+4x +10x +20x + + x + ⎪

⎝3⎭

∞

⎛n +2⎫n

x （1）证明：(1-x ) H =∑ ⎪2⎭n =0⎝（2）求H 的表达式. 解：H 的生成函数为G ⎨

⎧⎛n +3⎫⎫1=，所以 ⎬⎪4

⎩⎝n ⎭⎭(1-x )

∞

1⎛n +2⎫n

(1-x ) H ==x . ∑ ⎪3

2⎭(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··…· 2m

1-x 1-x 1-x

若要m 至少出现1次，则生成函数为

G 1(x)=(1+x+x2+…)(1+x2+x4+…) …(xm +x2m +…)

x m 11

= ··…· 2m

1-x 1-x 1-x

即：整数n 拆分成1到m 的拆分数，减去n 拆分成1到m －1的拆分数，即为拆分成1到m ，至少出现一个m 的拆分数。

23. n 个完全相同的球放到m 个有标志的盒子, 不允许有空盒, 问共有多少种

不同的方案？其中m ≤n .

解：令n 个球放到m 个有标志的盒子的方案数为a n ，由于不允许有空盒，因

此序列{an }的生成函数为

x m

G(x)=(x+x+…)(x+x+…) …(x+x+…)= . m

(1-x )

(1-x)-m =1+mx+

m (m +1) 2!

x 2+…

故其中x n-m 的系数为 m (m +1)...(m +n -m -1)

(n -m )! (n -m )! (m -1)!(n -m )!

即a n =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!

2! 3!

1⎫

⎪=9. 4! ⎭

故8个字母的全排列中有4个不在原来位置上的排列数应为C(8,4)·9=630.

相关内容

热门内容