动漫视频网站-军事经济学院分数线

第四章 生成函数
1. 求下列数列的生成函数：
（1）{0,1,16,81,…,n
4
,…}
解：G{k}=
4
x(111x11x
2
x
3
)
5
（1x）


3

4

n3

< br>（2）


,

,

,
< br>

333






n3


1
解：
G


=< br>

(1x)
4

n



（3）{1,0,2,0,3,0,4,0,……} < br>解：A(x)=1+2x
2
+3x
4
+4x
6
+…= （
（4）{1,k,k
2
,k
3
,…}
解：A(x)=1 +kx+k
2
x
2
+k
3
x
3
+…=1
.
1kx
1
2
）.
2
1x
2. 求下列和式：
（1）1
4
+2
4
+…+n
4

解：由上面第一题可知，{n
4
}生成函数为
x(111x11x2
x
3
)

k
ax
A(x)==，

k
5
（1x）
k0
此处a
k
=k.令b< br>n
=1+2+…+n，则b
n
=

a
k
，由 性质3即得数列{b
n
}的生
4444
k0
n

i5

i
x
. 成函数为 B(x)=

b
n
x
==
(x11x11xx)


i
1 x
i1

n0


n
A(x)
234

比较等式两边x
n
的系数，便得

n15

n25

n35

n45

444
1+2+…+n=b
n
=

11
n2

11

n3



n 4


n1

30
（2）1·2+2·3+…+n(n+1) < br>
1
n(n1)(6n
3
9n
2
n1)
2x
(1x)

解：{ n(n+1)}的生成函数为A(x)=
k
ax
=，此处a
k
= n(n+1).

k< br>3
k0
n
令b
n
=1·2+2·3+…+n(n+1)，则 b
n
=

a
k
.由性质3即得数列{b
n
}的生成
k0
函数为B(x)=

b
n
x
=< br>n
n0

A(x)
1x
=
2x
(1x )
4
=
2x



k3

k< br>x
.

k

k0

n
比较等式 两边x
n
的系数，便得
24


n2

n(n1)(n2)
1·2+2·3+…+n(n+1)= b
n
=
2

.


n1
3

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
n2

n2


n

=
7x
f(n)x12x
n
n1
2

f(n)x
n0< br>
n

=7x(A(x)-f(0))-12xA(x).
将f(0)=2，f(1)=7代入上式并整理，得

27x11
nn
A(x)(34)
.
< br>2
17x12x13x14x
n0
2

f(n) 3f(n1)53
n
（2）

;

f(0)0< br>解：令A(x)=

f(n)x
n
，则有
n0

A(x)-f(0)=


(3f(n1 )53
n1

n
)x
=
3x

f( n)x

15
x

3
n
x
n
< br>nn
n0n0

=3xA(x)+15x·
15x
(1 3x)
2
1
13x
.
A(x)=

f(n)2f(n1)f(n2)
（3）

;

f(0)0,f(1)1
解：令A(x)=

f(n)x
n< br>，则有
n0

A(x)-f(0)-f(1)x=

(2 f(n1)f(n2))x
=
2x

f(n)x

x
nn
n2


2
=2x(A(x)-f(0))+xA( x).
将f(0)=0，f(1)=1代入上式并整理，得
A(x)
4. 设序列 {
a
n
}的生成函数为：
x
12xx
2
2n1

f(n)x
n0

n

. 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
}的生成函数.
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
.

25

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
2
18x17x
1x56x
8x17x1
nn< br> 所以a
n
=-5·8-2·(-7).
6. 有红,黄,蓝,白球各两个,绿,紫,黑球各3个,从中取出10个球,试问有多少种
不同的取法？ < br>解：M
r
=M
y
=M
b
=M
w
={ 0,1,2}，M
g
=M
p
=M
h
={0,1,2,3}， 所以该取法的个数为
(1+x+x
2
)
4
(1+x+x
2
+x
3
)
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+x
2
)(1+x+x
2
+x
3
) (1+x+x
2
+x
3
+x
4
+x
5
)中 x
5
的系数，为12。
8. 求1,3,5,7,9这5个数字组成的n位数个数, 要求其中3和7出现的次数位
偶数,其它数字出现的次数无限制.
解：M
1
=M
5
=M
9
={0,1,2,3,…}，M
3
=M
7
={0,2,4,…}
该排列的生成函数为
x
2
x
4
x
2
11
2
(1...)(1x...)
3
=(e
x
+e
-x
)
2
e
3x
=(e
5x
+e
3x
+e
x
)
2!4! 2!
44
x
n
1

nn
=

(5 231)

n!
4
n0
=
5

2
=
5

1
2
1

所以a
n
=
1
4
(5
n
23
n
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
2< br>x
3
x
2
x
5
(1x)(1x)(1x )
.
2!3!2!5!
x
3
其中的系数为20，即可以组成20个偶的四位数。
3!
10. 求由A,B,C,D组成的允许重复的排列中AB至少出现一次的排列数目.
解：可把AB看作一个整体，用E表示，则
M
A
=M
B
= M
C
=M
D
={0,1,2,…}，M
E
={1,2,…}
x
2
x
2
4
)(x)
=e(4x)(e (x)-1)=e(5x)-e(4x)=5
n
-4
n
. 故有
(1x
2!2!
11. 从
{na,nb,nc}
中 取出n个字母,要求a的个数为3的倍数,b的个数是
偶数,问有多少种取法?
解：由题意可 知，M
a
={0,3,6,…}，M
b
=M
c
={0,1, 2,…}，该取法的生成函数为
1x
4
2
1
36232
)
(1+x+x+…) (1+x+x+x)=·
(
3
1x
1x
12. 把正整数8写成 三个非负整数之和，要求n
1
≤3,n
2
≤3,n
3
≤6. 问有多少种
26

不同的方案？
解：由题意可知，M
1
=M
2
={0,1,2,3}，M
3
={0,1,2,3,…,6}，则生成函数为
(1 +x+x
2
+x
3
)
2
(1+x+x
2
+ x
3
+…+x
6
)
1x
4
2
1x
7
1
)
·=
(
=(1-2x
4
-x
7
+x
8
+2x
1 1
-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
=M
2
=…=M
15
={1,2,3,…,10}，生成函数为
8
1x
10
15
)
， (x+x+x+…+x)=
x(
1x

37

15

27
 
15

17

38
其中x的系数为





。

14

1

14

2

14

23101 5
15
14. 用1角、2角、3角的邮票可贴出多少种不同数值的邮资？
解：生成 函数为G(x)=(1+x+x
2
+…)(1+x
2
+x
4
+…)(1+x
3
+x
6
+…)
=
111
·· =1+x+2x
2
+3x
3
+4x
4
+…
23
1x1x1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）< br>e
1
出现3或7次,
e
3
出现2,6或8次；
（4）每个
e
i
至少出现6次（i＝1,2,3,4）；
解：（1 ）由题意知，M
1
=M
2
=M
3
=M
4
= {1,3,5,…}，故该组合数序列的生成函


n3

n< br>

n3

4n
1
23444
x
=

x
. 数为(x+x+x+…)=x·= x·


4
(1x)
n0

n

n0

n



X
n
的系数为


n1

.


3

（2）由题意知，M
1< br>=M
2
=M
3
=M
4
={0,4,8,…}，故该组 合数序列的生成函
1
数为(1+x
4
+x
8
+…)
4
= .
44
(1x)
（3）由题意知，M
1
={3,7}，M
2
= M
4
={0,1,2,…}，M
3
={2,6,8}
故该组合数序列的生成函数为


n1

n
3 72682259111315
(x+x)(x+x+x)(1+x+x+…)=(x+2x+x+x+ x) ·

x
.
1
n0


X
n
的系数为

n51

n91

n111

n1 31

n151


1

2

1







＝6n -56.
111


27

（ 4）由题意知，M
1
=M
2
=M
3
=M
4
={6,7,8,…}，故该组合数序列的生成函

1

n3

n


n3

24n
67842424
数为(x+x+x+…)=x·= x·

x
=

n

x
.
n< br>(1x)
4
n0

n0






n21

X的系数为

.
3

n
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
=M
2
=M
3
=…=M
k
={0,2,4,… }，故该组合数序列的生成
函数为
(1
x
2
2
2!4!

（2）由题意知，M
1
=M
2
=M
3
= …=M
k
={4,5,6,…}，故该组合数序列的生成
函数为
2
3
x
4
x
5
xx
kk
(...)
=
(e(x)
1
)

4!5!
2!3!
kk

i
i


e((ki)x)[e(1)e (2)e(3)]

=(-1)
i
i0

x
4
...)
k
=


e(x)e(x)
k

.


n

k

n
i
x
=


(

(1)
i

(ki)
[1e(2)e(3)]
)
n!

n0i0

k
i

k

a
n


(1)

(ki)
n
[1e(2 )e(3)]
i

i0

i

k
i< br>（3）由题意知，M
1
=M
2
=M
3
=…=M
k
={0,1,2,…,i}，故该组合数序列的生
x
2
x
i
k
...)
. 成函数为
( 1x
2!i!
（4）由题意知，M
1
=M
2
=M
3
=…=M
k
={i,i+1,i+2,…}，故该组合数序列的
x
i
x
i1
...)
k
. 生成函数为
(
i!(i1)!
17. 用生成函数法证明下列等式：

n 2

n1

n

n

（1）< br>
2






< br>r

r

r

r2

证明 ：(1+x)
n+2
=(1+x)
n
·(1+x)
2
=(1 +2x+x
2
) (1+x)
n
=x
2
(1+x)
n
+2(1+x)
n+1
-(1+x)
n


n< br>
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

等式得证.
28

（2）

n

j

q< br>
nqj

(1)


r
j0

j

rq

q
证 明：(1+x)
n
[(1+x)-1]
q
=x
q
(1+x)
n
，
对比左右两边x
r
的系数，
q
q


nq

q

qjj

左边=< br>(1x)

(1)

(1x)


(1)

r
j0j0

j

j



n

=

，

rq

q
nj
j


，右边

因此等式得证.
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+x
2
+x
3
)(1 +x
2
+x
4+x
6
+x
8
)(1+x
4
+x
8
)
=1+x+2x
2
+2x
3
+3x
4
+3x
5
+4x
6
+4x
7
+5x
8
+5x
9
+5x
10
+5x
11
+4x
12
+4x
13
+3x
14
+3x
15
+2x
16
+2x17
+x
18
+x
19

故共能称出20种重量，指数即为重量类型，系数为方案数.
19. 求方程x
1
+2x
2
+4x
3
=21的正整数解的个数.
解：由题目可以看出，x
1
为奇数，故生成函数为
(xx
3x
5
...)(x
2
x
4
x
6
...)(x
4
x
8
x
1
2...)
 x
7
(1x
2
x
4
...)(1x
2x
4
...)(1x
4
x
8
...)
x
7
7
11

(1x
2
)
2
1x
4
1(1x
2
)
2
(1x
2
)
2
x
(1x
2
)
2
(1x
4< br>)
3
(1x
2
)
2
1
7911
 x(x2xx)
(1x
4
)
3
(1x
4
)
3
7


k2

4k
(x2x x)


x
k0

2

展开式中x< br>21
的系数为20，亦即该方程正整数解的个数。

n3

n23
x


20. H14x10x20x




3
7911

（1）证明：
(1x)H


（2）求 H的表达式.

n2

n
x


2< br>
n0




n3

1
解：H的生成函数为
G


=


(1x)
4
，所以
n




1< br>
n2

n
(1x)Hx
.

 
3
2

(1x)
n0

21. 数1,2,3,… ,9的全排列中,求偶数在原来位置上,其余都不在原来位置上
的错排数目.

29

解：实际上是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的和允许重复，故其生成函数为 < br>G(x)=(1+x+x
2
+…)(1+x
2
+x
4
+…)…(1+x
m
+x
2m
+…)
=

111
··…·
2m
1x1x1x
若要m至少出现1次，则生成函数为
G
1
(x)=(1+x+x
2
+…)(1+x
2
+x
4
+…)…(x
m
+x
2m
+…)
x
m
11
= ··…·
m
2
1x
1 x1x
即：整数n拆分成1到m的拆分数，减去n拆分成1到m－1的拆分数，
即为拆分成 1到m，至少出现一个m的拆分数。
23. n个完全相同的球放到m个有标志的盒子,不允许有空盒,问共有多少种
不同的方案？其中m≤n.
解：令n个球放到m个有标志的盒子的方案数为a
n
，由于不允许有空盒，因
此序列{a
n
}的生成函数为
x
m
G(x)=(x+x+…)(x+x+…)…(x+x+…)= .
m
(1x)
222
(1-x)
-m
=1+mx+
n-mm(m1)
2!
x
2
+…
故其中x的系数为
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个字母保持不动，相当

m(m 1)...(n1)

(n1)!
C(n1,m1)
于4个元素 的错排，其数目为
4!

1


1
1!

1
2!

1
3!

1

9
.
4!

故8个字母的全排列中有4个不在原来位置上的排列数应 为
C(8,4)·9=630.
30