逝去日子吉他谱-配色方案大全

第四章 生成函数
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


=


4


n


(1x)< br>（3）{1,0,2,0,3,0,4,0,……}
解：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
1x
2. 求下列和式：
（1）1
4
+2
4
+…+n
4

解：由上面第一题可知，{n
4
}生成函数为
x(111x11x2
x
3
)

k
A(x)==，
ax

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
成函数为 B(x)=

b
n
x==
(x11x11xx)


x
.

1x
n0
i1

i


n
A(x )
2
34

比较等式两边x
n
的系数，便得
< br>n15

n25

n35

n 45

444
1+2+…+n=b
n
=

11

11




n1
n2

n3

n4

30（2）1·2+2·3+…+n(n+1)

1
n(n1)(6n
3
9n
2
n1)

解：{ n(n+1)}的生成函数为A(x)=
2x
(1x)
3
n
=< br>
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即得数列{b
n
}的生成
k0
函数为B(x)=
1x
(1x)
4
比较等式两边x
n
的系数，便得 n0

b
n
x
=
n

A(x)=
2x
=
2x



k3

k
x
.

k

k0

n
24


n2

n(n1)(n2)
1·2+2·3+…+n(n +1)= b
n
=
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
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

f(n)3f(n 1)53
n
（2）

;

f(0)0
解： 令A(x)=

f(n)x
n
，则有
n0

2
A(x)-f(0)=


(3 f(n1)53)x
n
n1

n
=
3x

f(n)x

15
x

3
n
x
n

n
n0n0

=3xA(x)+15x·
1
13x
.
A(x)=
（3）

15x
2
( 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
nn
n2


2=2x(A(x)-f(0))+xA(x).
将f(0)=0，f(1)=1代入上式并整理，得
A(x)
4. 设序列{
a
n
}的生成函数为：
2
n1

f(n)x
n 0

n

x
12xx
2
.
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
)
442!4!2!
1

n
x
n
n
=
(5231)

4
n0
n!
=
5
< br>2
=
5

1
2
1

所以a< br>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
故有
(1x)(x)< br>=e(4x)(e(x)-1)=e(5x)-e(4x)=5
n
-4
n
.
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
11
- 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
< br>37

15

27

15

17

其中x
38
的系数为




。

14

1

1 4

2

14

231015
15
1 4. 用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+x)(1+x+x+…)=(x+2x+x+x+x) ·

n0< br>
1


X
n
的系数为

n5 1

n91

n111

n131< br>
n151



1

2


1




1



1




1

＝ 6n-56.

27

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



i

=
n0i0

k

< br>k

a
n


(1)

(k i)
n
[1e(2)e(3)]
i

i0

i

k
n
（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）

2







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

n1

n


n2

2

，对比左右两边x
r< br>的系数，左边=

，右边=



r


r2

r

r


n2

n1

n

n

整理得 ：

2





.

r

r

r

r2

等式得证.
28

（2）

n
j

q

nqj

(1)



r
j0

j

rq< br>
q
证明：(1+x)
n
[(1+x)-1]
q
=x
q
(1+x)
n
，
对比左右两边x
r
的系数，
q
q


nqj


n
< br>
q

qjq

左边=
(1x)

(1x)


(1)

，右边=

，


j
j0

j

j 0

rq


r


q
n< br>
因此等式得证.
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
为奇数，故生成函数为


k 2

4k
3524648127911
(x+x+x+…)(x+x+x+ …)(x+x+x+…)=(x+2x+x)


x
，
2
k0

展开式中x
21
的系数为20，亦即该方程正整数解的个数。

n3

n23
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+ 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
+…)

29

x
m
11
= ··…·
2
m
1 x1x
1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+
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)


1
1!

1
2!3!

1

1


9
.
4!

故8个字母的全排列中有4个不在原来位置上的排列数应为
C(8,4)·9=630.
30