第二章 母函数与递推关系组合数学
§ 2.1 母函数递推关系是计数的一个强有力的工具，
特别是在做算法分析时是必需的。递推关系的求解主要是利用母函数。当然母函数尚有其他用处，但这主要是介绍解递推关系上的应用。例如
1)-1-(2
)()(1
)1()1)(1(
21
2
1312121
21
n
n
nnn
n
xaaa
xaaaaaaxaaa
xaxaxa
§ 2.1 母函数项的系数中所有的项包括 n个元素 a1,a2,…an中取 两个 组合的全体；同理项系数包含了从
n个元素 a1,a2,… an中取 3个 元素组合的全体。以此类推。
2x nn aaaaaa 13121
§ 2.1 母函数若令 a1=a2=…=an=1,在（ 2-1-1）式中 项系数,中每一个组合有 1个贡献，其他各项以此类推。
故有：
2x nn aaaaaa 13121
2)-1-(2
),()2,()1,(1)1( 2 nn xnnCxnCxnCx
§ 2.1 母函数另一方面：
nmnm xxx )1()1()1(?
nm
m
m
n
xnmnmC
xnmCnmCx
xmmCxmCmC
xnnCxnCnC
),(
)1,()0,([
]),()1,()0,([
]),()1,()0,([
1
§ 2.1 母函数比较等号两端项对应系数，可得一等式
)0,(),( )1,()1,(
),()0,(),(
nCrmCrnCmC
rnCmCrnmC
§ 2.1 母函数同样对于,
（设 ），用类似的方法可得等式：
mn xx )/11()1( mn?
3)-1-(2 )0,()0,(
)0,()0,()0,()0,(),(
mCnC
mCnCmCnCmnmC
nmmmn xxxx )1()/11()1(?
正法如下：
§ 2.1 母函数比较等式两端的常数项，即得公式 (2-1-3)
nm
m
m
n
xnmnmC
xnmCxnmCnmCx
xmmCxmCmC
xnnCxnCnC
),(
)2,()1,()0,([
]),()1,()0,([
]),()1,()0,([
2
1
§ 2.1 母函数又如等式：
nxnnC
xnCxnCnCx
),(
)2,()1,()0,()1( 2
令 x=1 可得
4)-1-(2
2),()2,()1,()0,( nnnCnCnCnC
§ 2.1 母函数
(2-1-2)式等号的两端对 x求导可得：
5)-1-(2 2
),()3,(3)2,(2)1,(
1
nn
nnnCnCnCnC?
等式 (2-1-5)两端令 x=1,得：
5)-1-(2 2
),()3,(3)2,(2)1,(
1
nn
nnnCnCnCnC?
§ 2.1 母函数用类似的方法还可以得到：
1
32
)1(),(
)3,(3)2,(2)1,(
nn xnxxnnnC
xnCxnCxnC
7)-1-(2 2)1(
),()3,(3)2,(2)1,(
2
222
nnn
nnCnnCnCnC?
定义,对于序列 构造一函数：
§ 2.1 母函数还可以类似地推出一些等式，但通过上面一些例子已可见函数 在研究序列的关系时所起的作用。对其他序列也有同样的结果。现引进母函数概念如下：
nx)1(?
),(,),1,(),0,( nnCnCnC?
,,,,210?aaa
,)( 2210 xaxaaxG
,,,210 aaa称函数 G(x)是序列 的母函数序列 可记为 。
如若已知序列 则对应的母函数 G(x)便可根据定义给出。反之，如若以求得序列的母函数 G(x),则该序列也随之确定。
§ 2.1 母函数例如
n x) 1 (?
),(,),1,(),0,( nnCnCnC?
,,,,210?aaa
,,,,210?aaa }{ na
§ 2.2 递推关系利用递推关系进行计数这个方法在算法分析中经常用到，举例说明如下：
例一,Hanoi问题：这是个组合数学中的著名问题。 N个圆盘依其半径大小，从下而上套在 A柱上，如下图示。每次只允许取一个移到柱 B或 C上，而且不允许大盘放在小盘上方。若要求把柱 A上的 n个盘移到 C柱上请设计一种方法来，并估计要移动几个盘次。现在只有 A,B,C三根柱子可用。
§ 2.2 递推关系
Hanoi问题是个典型的问题，第一步要设计算法，进而估计它的复杂性，集估计工作量。
算法,N=2时第一步先把最上面的一个圆盘套在 B上?第二步把下面的一个圆盘移到 C上最后把 B上的圆盘移到 C上到此转移完毕
A B C
§ 2.2 递推关系
对于一般 n个圆盘的问题，
假定 n-1个盘子的转移算法已经确定。
先把上面的 n-1个圆盘经过 C转移到 B。
第二步把 A下面一个圆盘移到 C上
最后再把 B上的 n-1个圆盘经过 A转移到 C上
A B C
§ 2.2 递推关系上述算法是递归的运用。 n=2时已给出算法； n=3时，第一步便利用算法把上面两个盘移到 B上，第二步再把第三个圆盘转移到柱 C上；最后把柱 B上两个圆盘转移到柱 C上。 N=4,5,…以此类推。
§ 2.2 递推关系算法分析,令 h(n)表示 n个圆盘所需要的转移盘次。根据算法先把前面 n-1个盘子转移到 B上；然后把第 n个盘子转到 C上；最后再一次将 B上的 n-1个盘子转移到 C上。
n=2时，算法是对的，因此,n=3是算法是对的。以此类推。于是有
§ 2.2 递推关系算法复杂度为：
1)-2-(2 1)1(,1)1(2)( hnhnh
,)3()2()1()( 32 xhxhxhxH
H(x)是序列 的母函数。
给定了序列，对应的母函数也确定了。反过来也一样，求得了母函数，对应的序列也就可得而知了。当然，利用递推关系 (2-2-1)式也可以依次求得,这样的连锁反应关系，
叫做递推关系。
),3(),2(),1( hhh
),3(),2( hh
§ 2.2 递推关系下面介绍如何从 (2-2-1)式求得母函数
H(x)的一种形式算法。所谓形式算法说的是假定这些幂级数在作四则运算时，一如有限项的代数式一样。
,)3()2()1()( 32 xhxhxhxH
,)2(2)1(2- )(2 ) xhxhxxH _ _ _ _ _ _ __ _ _ _ _ _ _ _ _ __ _ _ _ _ _ _ _ _ __ _ _ _ _ _ _ _ _ _
3
2
)]2(2)3([
)]1(2)2([)1()()21(
xhh
xhhxhxHx
§ 2.2 递推关系根据 (2-2-1)，
,1)2(2)3(,1)1(2)2(,1)1( hhhhh
)1/()()21( 32 xxxxxxHx
或利用递推关系 (2-2-1)有
1)1(2)2(:2 hhx
1)2(2)3(:3 hhx
)? _ _ _ _ _ _ __ _ _ _ _ _ _ _ _ __ _ _ _ _ _ _ _ _ __ _ _ _ _ _ _ _ _ _
)1/()(2)( 2 xxxxHxxH
§ 2.2 递推关系上式左端为：
xxHxhxHxhxh )()1()()3()2( 32?
右端第一项为：
)(2x
])2()1([2)2(2)1(2 232
xH
xhxhxxhxh
右端第二项为：
)1/(232 xxxx
§ 2.2 递推关系整理得
x
xx
x
xxHx
11
)()21(
2
)21)(1(
)(
xx
xxH
这两种做法得到的结果是一样的。即：
§ 2.2 递推关系令
)21)(1(
2
)21(1(
)1()21(
211
)(
xx
B ) xAB ) - ((A
xx
xBxA
x
B
x
A
xH
xxBABA )2()(
如何从母函数得到序列？下面介绍一种化为部分分数的算法。),2(),1( hh
§ 2.2 递推关系由上式可得：
.1,1 BA
即：
12 BA{
0 BA
1
23322
)12(
)12()12()12(
)1()2221(
1
1
21
1
)(
k
kk
x
xxx
xxxxx
xx
xH
§ 2.2 递推关系因为：
1
)()(
k
kxkhxH
12)( kkh
§ 2.2 递推关系例 2,求 n位十进制数中出现偶数个 5的数的个数。
先从分析 n位十进制数出现偶数个 5的数的结构入手 是 n-1位十进制数，若含有偶数个 5，则 取 5以外的 0,1,2,3,4，
6,7,8,9九个数中的一个，若只有奇数个 5，则取,使成为出现偶数个 5的十进制数。
121?nppp?
1?np
121?nppp?
5?np nn pppp 121
§ 2.2 递推关系解法 1：
令 位十进制数中出现 5的数的个数，
位十进制数中出现奇数个 5的数的个数。
nan?
nbn?
故有：
119 nnn baa
119 nnn abb
{? 1,8 11 ba
)222(
也有类似解释。
§ 2.2 递推关系
(2-2-2)式中的 表达了含有偶数个 5的 n位十进制数的两个组成部分。
表达由含有偶数个 5的 n-1位十进制数
，令 取 5以外的 0,1,2,3,4，
6,7,8,9九个数中的一个数构成的。 项表示当 是含有奇数个 5的 n-1位十进制数，令 而得 是含偶数个
5的 n位十进制数。
119 nnn abb
119 nnn baa
19?na
121?nppp? np
1?nb
121?nppp?
5?np nppp?21
(2-2-2)是关于序列 和 的连立关系。
§ 2.2 递推关系设序列 的母函数为,序列 的母函数为 。
}{ na }{ nb
}{ na )(xA }{ nb
)(xB
2
21
2
21
2
321
2
321
)( )
99)(9
)(
)(
xbxbxxB
xaxaxxA
xbxbbxB
xaxaaxA
即：
_ _ _ _ _ _ _ _ _ __ _ _ _ _ _ _ _ _ __ _ _ _ _ _ _ _ _ _
8)()()91( xxBxAx
§ 2.2 递推关系承前页：
)
9,
9,
9,
334
3
223
2
112
baax
baax
baax
___ _ _ _ _ _ _ _ _ __ _ _ _ _ _ _ _ _ _
)()(98)( xxBxxAxA
8)()()91( xxBxAx
§ 2.2 递推关系又：
___ _ _ _ _ _ _ _ _ __ _ _ _ _ _ _ _ _ _
1)()()91( xxAxBx
故得关于母函数 和 得连立方程组：)(xA )(xB
1)()91()(
8)()()91(
xBxxxA
xxBxAx
{
2
21
2
21
2
321
)( )
99)(9
)(
xaxaxxA
xbxbxxB
xbxbxbxB
§ 2.2 递推关系
x
x
x
x
D
91
91
xx )91( 280181 xx
)101)(81( xx
)101)(81(
871
91
1
8
80181
1)(
2 xx
x
x
x
xx
xA
)101)(81(
1
1
8
91
)101)(81(
1)(
xx
x
x
x
xx
xB
§ 2.2 递推关系
0
)10987(21)101 981 7(21)(
k
kkk x
xxxA
11 10
2
98
2
7 kk
ka
§ 2.2 递推关系解法二：
n-1位的十进制数的全体共 从中去掉含有偶数个 5的数，余下的便是 n-1位中含有奇数个 5的数。故有：
2109 n
1
2
1
11
109
9
n
n
n
nnn
ab
baa
8,1098 121 aaa nnn
§ 2.2 递推关系令
2
21
2
321
88)(8 )
)(
xaxaxxA
xaxaaxA
___ _ _ _ _ _ _ _ _ __ _ _ _ _ _ _ _ _ _
22312 )8()8(8)()81( xaaxaaxAx
§ 2.2 递推关系
x
x
x
x
xxxAx
101
718
101
9
8
10998)()81( 2
0
)10987(
2
1
)
101
9
81
7
(
2
1
)101)(101(
718
)(
k
kkk
x
xxxx
x
xA
11 10
2
98
2
7 kka
1）不出现某特定元素设为,其组合数为,相当于排除 后从中取 r个做允许重复的组合。
§ 2.2 递推关系例三,从 n个元素 中取 r个进行允许重复的组合。假定允许重复的组合数用 表示，其结果可能有以下两种情况。
naaa,,,21?
),( rnC
1a),1( rnC?
1a naa,,2?
§ 2.2 递推关系
2）至少出现一个,取组合数为相当于从 中取 r-1个做允许重复的组合，然后再加上一个 得从 n个元素中取 r个允许重复的组合。
1a )1,(?rnC
1a
naaa,,,21?
依据加法原则可得：
),1()1,(),( rnCrnCrnC
因,故令 1)1,1(,)1,( nnCnnC 1)0,(?nC
§ 2.2 递推关系递推关系 (2-2-3)带有两个参数 n和 r。
xnCxnCxG
xnCxnCxxG
xnCxnCnCxG
n
n
n
)1,1()0,1()( )
)1,()0,( )(
)2,()1,()0,()(
1
2
2
___ _ _ _ _ _ _ _ _ __ _ _ _ _ _ _ _ _ _ )322( 0)()()1(
1 xGxGx nn
§ 2.2 递推关系
(2-2-3)式是关于 的递推关系，但系数 不是常数。但
)(xGn
)1( x?
x
xx
xCxCCxG
1
1
1
)2,1()1,1()0,1()(
2
2
1
n11-n
221
x)-(1
1
)(
x)-(1
1
)(
)1(
1
)(
1
1
)(
xG
xG
x
xG
x
xG
nnn
§ 2.2 递推关系由二项式定理
32 !3 )2)(1(!2 )1(1)1( xnnnxnnnxx
可得
),1(
)!1(
)!1(
!
)1()1(
),(
rrnC
n
rn
r
rnnn
rnC
§ 2.3 母函数的性质
§ 2.3 母函数的性质一个序列和它的母函数一一对应。给了序列便得知它的母函数；反之，求得母函数序列也随之而定。这种关系颇像数学中的积分变换，
特别酷似离散序列的 Z变换。如 § 2的例子所示的那样，为了求满足某种第推关系的序列，可把它转换为求对应的母函数,可能满足一代数方程，或代数方程组，甚至于是微分方程。
)(xG )(xG
§ 2.3 母函数的性质最后求逆变换，即从已求得的母函数得到序列 。关键在于要搭起从序列到母函数，从母函数到序列这两座桥。这一节便是以此为目的的。不特别说明下面假设,
两个序列对应的母函数分别为,
)(xG
}{ na
}{ ka }{ kb
)(xA )(xB
§ 2.3 母函数的性质性质 1：
若 则?kb lk? 0 lka
lk {
)()( xAxxB l?
证：
)(
000)(
1
10
1
1
xAx
xaxa
xbxbxB
l
ll
l
l
l
l
§ 2.3 母函数的性质例,已知 1!3!2!1
32
xexxxxA?
则
)1(!3!2!1)( 1
21
xm
mmm
exxxxxB?
§ 2.3 母函数的性质性质 2,若,lkk ab
则
l
l
k
k
k xxaxAxB /])([)(
1
0
§ 2.3 母函数的性质
l
l
k
k
k
ll
l
l
l
l
l
l
ll
lll
xxaxA
xxaxaxaaxA
xaxaxa
x
xaxaaxB
/])([
/])([
)(
1
)(
1
0
1
1
2
210
2
2
1
1
2
21
证, 2210)( xbxbbxB
§ 2.3 母函数的性质例, !5!3s i n)(
53 xx
xxxA
653
3
/]
!5
1
!3
1
[ s i n
!9
1
!7
1
)(
xxxxx
xxxB
§ 2.3 母函数的性质性质 2,若,则?
k
i
i
k ab
0 x
xAxB
1
)()(
证：
)
,
,
,
:1
210
2101
2
101
00
n
n
aaaabx
aaabx
aabx
ab
§ 2.3 母函数的性质
)
,
,
,
:1
210
2101
2
101
00
n
n
aaaabx
aaabx
aabx
ab
_ _ _ _ _ _ _ __ _ _ _ _ _ _ _ _ __ _ _ _ _ _ _ _ _ _
)1/()()1/(][
)1/()1/()1/()(
2
210
2
210
xxAxxaxaa
xxaxxaxaxB
§ 2.3 母函数的性质例,已知 xxxxxA n 1
11)( 2
2
32
)1(
14321)(
xxxxxB
2
0 )1(
1)1(
x
xk
k
k
§ 2.3 母函数的性质类似可得：
0
3
32
32
32
)1(
1
)2)(1(
2
1
10631
)1(
)4321()(
k
k
x
xkk
xxx
xxx
xxxxC
§ 2.3 母函数的性质性质 2,若 收敛，则?
0k
ka x
xxAAxB
1
)()1()(
)
)1(,
)1(,
)1(:1
1021
2
0211
2100
aaAabx
aAaabx
Aaaab
_ _ _ _ _ _ _ __ _ _ _ _ _ _ _ _ __ _ _ _ _ _ _ _ _ _
)1(
)1(]1)[1()(
22
1
2
0
2
xxxa
xxxaxxAxB
§ 2.3 母函数的性质
x
xxAA
xxxaa
x
A
xB
1
)()1(
)1/()(
1
)1(
)(
10
§ 2.3 母函数的性质性质 5,若,则 。kk kabxxAxB '?
例, xxxxA 1
11 2?
2
32
11
132
x
x
x
xxxx
则
§ 2.3 母函数的性质
k
ab k
k 1
x dxxA
xxB 0
1
性质 5和性质 6的结论是显而易见的。
性质 6,若,则
§ 2.3 母函数的性质性质 7,若则
022110 babababac kkkkk
k
i
ikiba
0
xBxAxcxccxC2210
§ 2.3 母函数的性质证,
。
22100 xbxbbaxC
22101 xbxbbxa
221022 xbxbbxa
22102210 xbxbbxaxaa
xBxAxC
)?
,:1 000 bac?
,:2 01101 babac
,:3 0211202 bababac
___ _ _ _ _ _ _ _ _ __ _ _ _ _ _ _ _ _ _
§ 2.3 母函数的性质例,已知则
,
2
1
321
,
1
32
,
1
1
1
2
32
2
kk
kC
x
x
xxxxB
x
xxxA
k
3
1 x
xxC
§ 2.4 Fibonacci数列
§ 2.4.1 递推关系
Fibonacci数列是递推关系的又一个典型问题，数列的本身有着许多应用。
问题,有雌雄兔子一对，假定过两月便可繁殖雌雄各一的一对小兔。问过了 n个月后共有多少对兔子？
设满 n个月时兔子对数为 其中当月新生兔数目设为 对。第 n-1个月留下的兔子数目设为 对。
nF
nN
nO
nnn ONF
§ 2.4.1 递推关系但 211, nnnnn FONFO
即第 n-2个月的所偶兔子到第 n个月都有繁殖能力了。
)132( 1,2121 FFFFF nnn
由递推关系 (2-3-1)式可依次得到
,523
,3,2
435
324213
FFF
FFFFFF
§ 2.4.2 问题的求解
221)( xFxFxG
)
,
,
234
4
123
3
FFFx
FFFx
_ _ _ _ _ _ _ _ __ _ _ _ _ _ _ _ _ _
)())(()( 22 xGxxxGxxxxG
xxGxx )()1( 2
设
§ 2.4.2 问题的求解承前页
x
B
x
A
xx
x
xx
x
xG
2
51
1
2
51
1
)
2
51
1)(
2
51
1(
1
)(
2
§ 2.4.2 问题的求解承前页
1)(
2
5
0
BA
BA
{ {
5
2
0
BA
BA
5
1,
5
1 BA
§ 2.4.2 问题的求解承前页
])()[(
5
1
]
2
51
1
1
2
51
1
1
[
5
1
)(
222
xx
xx
xG
5
)(F
n
nn
§ 2.4.2 问题的求解其中
2
51
51
2,
2
51
51
2
2)-3-(2 )2 51(51)(51 nnnnF
618.1
2
51
1
n
n
F
F
§ 2.4.3 若干等式
1） 3)-3-(2 1221nn FFFF?
证明：
12
11
342
231
)
nnn
nnn
FFF
FFF
FFF
FFF
_ _ _ __ _ _ _ _ _ _ _ _ __ _ _ _ _ _ _ _ _ _
1 222211 nnn FFFFFF?
§ 2.4.3 若干等式
2） 4)-3-(2 212531 nn FFFFF
证明：
22212
465
243
21
)
nnn
FFF
FFF
FFF
FF
_ _ _ __ _ _ _ _ _ _ _ _ __ _ _ _ _ _ _ _ _ _
nn FFFFF 212531
§ 2.4.3 若干等式
3） 5)-3-(2 122221 nnn FFFFF?
证明：
)( )
)(
)(
1111
2
3243243
2
3
1232132
2
2
12
2
1
nnnnnnnn
FFFFFFFF
FFFFFFFF
FFFFFFFF
FFF
_ _ _ __ _ _ _ _ _ _ _ _ __ _ _ _ _ _ _ _ _ _
122221 nnn FFFFF?
§ 2.4.4 在选优法上的应用设函数 在区间 上有一单峰极值点，假定为极大点。
)( xfy? ),( ba
所谓单峰极值，即只有一个极值点,而且当 x与 偏离越大，偏差 也越大。
如下图：
)()(?fxf?
y
x0?a b
§ 2.4.4 在选优法上的应用设函数 在 点取得极大值。要求用若干次试验找到 点准确到一定的程度。最简单的方法，把 三等分，令：
)(xfx
),( ba
)(32 ),(31 21 abaxabax
如下图,y
x0 a b1x 2x
)( 1xf )( 21xf
)( xfy?
§ 2.4.4 在选优法上的应用依据 的大小分别讨论如下,)(),( 21 xfxf
当,则极大点 必在 区间上，区间 可以舍去。
)()( 21 xfxf ),( 2xa
),( 2 bx
y
x0
)( xfy?
a b1x 2x
)()( 21 xfxf?
y
x0
)( 1xf )( 21xf
a 2x1x
§ 2.4.4 在选优法上的应用当,则极大点 必在 区间上，区间 可以舍去。
)()( 21 xfxf ),( 1 bx
),( 1xa
y
x0
)( xfy?
a b1x 2x
)()( 21 xfxf?
y
x0
)( 1xf )( 2xf
2x1x b
§ 2.4.4 在选优法上的应用当,则极大点 必在 区间上，区间 和 均可以舍去。
)()( 21 xfxf ),( 21 xx
),( 1xa ),( 2 bx
y
x0
)( xfy?
a b1x 2x
)()( 21 xfxf?
y
x0
)( 1xf )( 21xf
2x1x
§ 2.4.4 在选优法上的应用可见做两次试验，至少可把区间缩至原来区间的 2/3，比如,进一步在区间上找极值点。若继续用三等分法，
将面对着这一实事，即其中 点的试验没发挥其作用。为此设想在 区间的两个对称点 分别做试验。
)()( 21 xfxf?
),( 2xa
1x)1,0(
xlx?,
0 xl? x 1
§ 2.4.4 在选优法上的应用设保留 区间，继续在 区间的下面两个点 处做试验，若
),0( x ),0( x
xxx )1(,2?
6)-3-(2 )1(2 xxx
则前一次 的点的试验，这一次可继续使用可节省一次试验。由 (2-3-6)式有
x?1
012 xx
61 8.02 51 x
0 2)618.0(382.0?618.0 1
§ 2.4.4 在选优法上的应用这就是所谓的 0.618优选法。即若在区间上找单峰极大值时，可在
)1,0(
3 8 3 2.06 1 8,01,6 1 8.0 21 xx
点做试验。比如保留区间,由于
，故只要在
)618.0,0(
3 2 8.0)6 1 8.0( 2?
2 3 6.03 2 8.06 1 8.0
点作一次试验。
§ 2.4.4 在选优法上的应用优选法中可利用 Fibonacci数列，和 0.618法不同之点在于它预先确定试验次数，分两种情况介绍其方法。
(a) 所有可能试验数正好是某个 。nF
10 2?nF nF1?nF
§ 2.4.4 在选优法上的应用这时两个试验点放在 和 两个分点上，如果 分点比较好，则舍去小于 的部分；如果 点更好，则舍去大于 的部分。在留下的部分共 个分点，其中第 和第 二试验点，恰好有一个是刚才留下来的试验可以利用。
2?nF1?nF
1?nF 2?nF
2?nF 1?nF
1?nF 2?nF
3?nF
可见在 个可能试验中，最多用 n-1次试验便可得到所求的极值点 n
F
§ 2.4.4 在选优法上的应用
(b)利用 Fibonacci数列进行优选不同于
0.618法之点,还在于它适合于参数只能取整数数值的情况,如若可能试验的数目比 小,
但比 大时,可以虚加几个点凑成 个点，
但新增加的点的试验不必真做，可认定比其他点都差的点来处理。
nF
1?nF nF
§ 2.4.4 在选优法上的应用下面给出两个定理作为这一节的结束。
定理,测试 n次可将包含单峰极值点的区间缩小到原区间的,其中 是任意小的正整数，
1/1 nF?2?n
§ 2.4.4 在选优法上的应用证,对 n用数学归纳法。
n=2时，将区间 平分成 段。在分点（包括端点 a,b） 分别标上 。在 1点的两侧取,在 与 两点上测试，无论哪一点较优，保留下来的区间长度均为,命题成立。
),( ba 212F
2,1,0?
11
1
§ 2.4.4 在选优法上的应用假设对于 n-1,命题成立对于 n,将 平分成 段，对分点（包括端点 a,b） 依次标上 。先在 点与 点测试，无论哪一点较优，保留下来的区间均为 段。根据归纳假设，再做 n-1次测试
（内含前两次测试之一）可将含极值点的区间缩小到 段，即原区间 的 。
),( ba 1?nF
1,,1,0?nF? 1?nF
nF
nF
1 ),( ba1/1 nF
§ 2.4.4 在选优法上的应用因,当 n较大时，可将相继的两个测试点取在待测区间的
0.618及 1-0.618处。由
6 1 8.02/)15(/ 1nn FF
,2,)
2
15(1)
2
15( 1 n
F
n
n
n
可知,0.618法比 法最多多测试一次。 0.618 nF
§ 2.4.4 在选优法上的应用定理,设在给定区间内有单峰极值点。如果包含极值点在内的可测点为 个，则测试 n次必可找到极值点,。
12nF
2?n
证,对 n用数学归纳法。
n=2时，,命题成立 2122F
§ 2.4.4 在选优法上的应用下面证明对 n命题成立。设可测试点的标号依次是 。先在 点及 点测试。无论哪一点较优，保留下来的可测点都为 个。根据归纳假设，再测试 n-1
必可找到极值点。而在保留的 个可测试点中，有一点（ 或 ）的测试结果下一次比较好时正好用上，这样总测试次数为 n。
假设对于 n-1,命题成立
1,,,,,2,1 21 nnn FFF nF
1?nF 1
1nF 1
1nF
nF 1?nF
§ 2.5 线性常系数递推关系
§ 2.5 线性常系数递推关系定义 如果序列 满足na
,02211 knknnn aCaCaCa152
,,,,111100 kk dadada252
及 是常数，,则称为 的 阶常系数线性递推关系，
称为 的初始条件，
kCCC?,,21 110,,?kddd? 0?kC
152 na k
252 na
kkkk CxCxCxxC 111)(?
称为 的特征多项式na
§ 2.5 线性常系数递推关系设 为 的母函数)(xG }{ na
nn xaxaaxG 10)(
根据 (2-5-1)，有
0)(
0)(
0)(
2211
11211
1
02211
knknnn
n
kkkk
k
kkkk
k
aCaCaCax
aCaCaCax
aCaCaCax
§ 2.5 线性常系数递推关系将这些式子两边分别相加，得到
0
1
0
2
0
1
xGxC
xaxGxCxaxG
k
k
k
i
k
i
i
i
i
i
即
1
0
1
0
2
211
k
j
jk
i
i
i
j
j
k
k xaxCxGxCxCxC?
其中 10?C
§ 2.5 线性常系数递推关系令,多项式 的次数不大于 。
特征多项式
1
0
1
0
k
j
jk
i
i
i
j
j xaxCxPxP
1?k
kkk CxCxxC11
§ 2.5 线性常系数递推关系因此,k
k
k xCxC
xCx
11
1
是 次多项式，我们知道 在复数域中有 个根。设
k
k
0?xC
kkkk
axaxaxxC
i
k
i
kk i
21
21
21
§ 2.5 线性常系数递推关系则
ikikk
k
k
k
xaxaxa
xCxC
x
Cx
111
1
1
21
21
1
于是xPxGxCxC kk11
k
k xCxC
xPxG
11
)452( 111 21 21 ikikk xaxaxa
xP
§ 2.5 线性常系数递推关系
(2-5-3)式是有理式，且分子的次数低于分母的次数，有分项表示，即：
t
t
k
t
tk
t
t
t
t
k
k
k
k
x
A
x
A
x
A
x
A
x
A
x
A
x
A
x
A
x
A
xG
)1()1(1
)1()1(1
)1()1(1
)(
2
21
2
2
2
2
22
2
21
1
1
2
1
12
1
11
2
2
1
1
§ 2.5 线性常系数递推关系承上页,)452(
)1(1 1
t
i
k
j
j
i
ij
i
x
A
)(xG
的系数是 。 是常数。
nx
n
i
t
i
k
j
ijn an
nj
Aa
i
1
1 1
ij
A
§ 2.5 线性常系数递推关系定理,设 是有理分式，多项式的次数低于 的次数。则 有分项表示，
且表示唯一
)(
)(
xQ
xP
)(xP
)(xQ )(
)(
xQ
xP
§ 2.5 线性常系数递推关系证明,设 的次数为 n,对 n用数学归纳法。
)(xQ
n=1时,是常数，命题成立。)(xP
假设对小于 n的正整数，命题成立。
下面证明对正整数 n命题成立。设 是的 重根，
)(xQ
k
0)( ),()()( 11 xQxQxxQ k?
§ 2.5 线性常系数递推关系不妨设 与 互素，设)(xP )(xQ
)()(
)(
)()(
)(
1
1
xQx
xP
x
A
xQ
xP
kk
0)(/)(
)()()()(
1
11
xQPA
xPxPxxAQ
)/()]()([)( 11 xxAQxPxP
§ 2.5 线性常系数递推关系的次数低于 。根据归纳假设，)(xP )(xQ
)()(
)(
1
1
xQx
xP
k
可分项表示。因此，
)(
)(
xQ
xP
可分项表示。 由 (2-5-6)式及 (2-5-7)式可知表示是唯一的 。
§ 2.5 线性常系数递推关系以下分别各种情况讨论具体计算的问题。
（ 1）特征多项式 无重根设可见化为
xC
kaxaxaxxC21
452
k
i i
i
k
k
xa
A
xa
A
xa
A
xa
A
xG
1
2
21
1
1
1
111
852
§ 2.5 线性常系数递推关系的系数是nx?
k
i
n
iin aAa
1
952
kAAA,,,21?可由线性方程组
daAaAaA
daAaAaA
dAAA
k
kk
kk
kk
k
11
22
1
11
12211
021
1052
解出。
§ 2.5 线性常系数递推关系的系数矩阵的行列式是 Vander
mond 行列式
1052
11
2
1
1
21
1 1 1
k
k
kk
k
aaa
aaa
1152
ji
ii aa 0
不难看出 有唯一解。?1052
§ 2.5 线性常系数递推关系
（ 2）特征多项式 有共轭复根设 是 的一对共轭复根。21,aa
xC
xC
)s i n(c o s,s i nc o s 121 iaaia
中 的系数是 xa
A
xa
A
2
2
1
1
11?
nx
§ 2.5 线性常系数递推关系
nBnA
nAAinAA
ninAninA
iAiA
AA
nn
nn
nn
nnnn
nn
s i nc o s
s i n)(c o s)(
)s i n( c o s)s i n( c o s
)s i n( c o s)s i n( c o s
2121
21
2
1
1
2211
§ 2.5 线性常系数递推关系其中 )(,2121 AAiBAAA
在具体计算时，可先求出各对共轭复根，再求待定系数 A,B,避免中间过程的复数运算。
（ 3）特征多项式 有重根设 是 的 重根，则 (2-5-4)可简化为? )(xC k
)(xC
k
i
i
i
x
A
1 )1(?
§ 2.5 线性常系数递推关系的系数 。其中nx
n
k
j
jn an
nj
Aa?
1
1
1
11
j
nj
n
nj
是 n的 j-1次多项式。因此,是 与 n的 k-1次多项式的乘积。
na n?
§ 2.5 线性常系数递推关系为了简化计算，下面引入一些记号，介绍几个命题。
设 x是任意变量,n是非负整数，令
n
x
{
,0,1 是当?n
,1,! )1()1( 时当 nn nxxx?
§ 2.5 线性常系数递推关系不难证明，多项式可用 唯一线性表示。其中是常数
0111)( axaxaxaxf nnnn
n
xxx
,
1
,
0 ka
)0( nk
§ 2.5 线性常系数递推关系设 是给定序列，令称为 的 阶差分。
)(,11 nknknnn aaaaa
}{ na
nka? na k
不难证明，如果对任意的 n有,则有
0 nra
0)1(
0
irn
r
i
i a
i
r
因而序列 的特征多项式为}{ na rxxC )1()(
§ 2.5 线性常系数递推关系不难证明，如果 是 n的 r次多项式，则是 n的 r+1次多项式。
na?
na
以上几个命题作为习题，请读者自己证明。
§ 2.5 线性常系数递推关系总之：
(1)若特征多项式 有 n个不同零点则递推关系 (2-5-1)的解
)(xC,,,,
11 naaa?
knnkkk alalala2211
其中 是待定系数，有初始条件
(2-5-2)来确定。
,,,,11 nlll?
§ 2.5 线性常系数递推关系
(2)若特征多项式 有不同的复根，
可依照 (1)的办法处理。不过任意复数可写为 形式，设是 的一个零点，其共轭复根为
)s i n( c o s1 ie i
)(xC bia?
ie
)(xC
)s i n( c o s2 ie i
§ 2.5 线性常系数递推关系
kllikll
kikl
kiklll
kk
k
kkk
s i n)(c o s)(
)s i n( c o s
)s i n( c o s
2121
2
12211
和 仍然是待定常数。即有一对共轭复根 和 时，递推关系 (2-5-1)的解有对应的项
21 ll? )( 21 lli? 0)(?xC
ie?1 ie2
kBkA kk s i nc o s?
其中 A,B是待定常数。
§ 2.5 线性常系数递推关系
(3)若 k重根。不妨设 是 k的重根。
则递推关系 (2-5-1)的解对应于的项为其中 是 k个待定常数。
nkk nAnAA 11110 )(
)(xC 1?
110,,,?kAAA?
§ 2.5 线性常系数递推关系例 1,求下列 n阶行列式 的值。nd
20
01210
00121
00012
n
d
§ 2.5 线性常系数递推关系根据行列式性质
3,2,02 2121 ddddd nnn
对应的特征方程为
1
0)1(12
21
22
mm
mmm
故 是二重根1?m
BnABnAd nn )1)((
§ 2.5 线性常系数递推关系时有1?n 21 BAd
时有2?n 322 BAd
1
32
2
BA
BA
BA
即 1 nd n
§ 2.5 线性常系数递推关系例 2,求?
n
k
n kS
0
1321
1321
1
nS
nnS
n
n
nSS nn 1
同理 121 nSS nn
相减得 12 21 nnn SSS
§ 2.5 线性常系数递推关系同理 12 321 nnn SSS
3,1,0
033
210
321
SSS
SSSS nnnn
对应的特征方程为
0)1(133 323 mmmm
§ 2.5 线性常系数递推关系是三重根1?m
22 )1)(( CnBnACnBnAS nn
0,00 AS
0,11 CBS
0,342,32 CBCBS
即 )1(2
1
2
1
2
1 2 nnnnS
n
)1(21321 nnn?这就证明了
§ 2.5 线性常系数递推关系例 2,求?
n
k
n kS
0
2
222
1
2222
)1(321
)1(321
nS
nnS
n
n
21 nSS nn
同理 221 )1( nSS nn
相减得 122 21 nSSS nnn
§ 2.5 线性常系数递推关系同理 1)1(22 321 nSSS nnn
14,5,1,0
0464
3210
4321
SSSS
SSSSS nnnnn
对应的特征方程为
0)1(1464
01464
4234
234
rrrrr
mmmm
相减得 233 321 nnnn SSSS
同理 233 4321 nnnn SSSS
§ 2.5 线性常系数递推关系是四重根1?r
nn DnCnBnAS )1)(( 32
依据 得关于 A,B、
C,D的连立方程组：
14,5,1,0 3210 SSSS
142793
5842
1
0
DCB
DCB
DCB
A
§ 2.5 线性常系数递推关系
12
2793
842
111
6
1
27914
845
111
2
1
B
§ 2.5 线性常系数递推关系已知 是 n的 3次式，故不妨令nS
)2)(1(!31)1(!21 nnDnnCnBnAS n
确定待定系数时，比较方便，无需解一联立方程组。
例如 0,0 0 ASn 时
1,1,1 1 BBASn 时
3,52,2 2 CCBSn 时
2,1433,3 3 DDCBSn 时
§ 2.5 线性常系数递推关系
)12)(1(
6
1
)2)(1(
3
1
)1(
2
3
nnn
nnnnnnS
n
§ 2.5 线性常系数递推关系例 4,求 333 21 nS n
解,是 n的 3次多项式，因此 是满足递推关系：
31 )1( nSSS nnn
nS
0510105 54321 nnnnnn SSSSSS
设
4321 4321
n
A
n
A
n
A
n
AS n
§ 2.5 线性常系数递推关系
6
,4126741100436
12,
2
3
7313639
7,
1
2
1921
1
4
4
3
4
33
3
3
22
33
2
11
A
AS
AAS
AAS
AS
§ 2.5 线性常系数递推关系
4
6
3
12
2
7
1
nnnn
S n
以 n=5对上面的结果验证一下
2 2 551 0 0 35S
25 53012 0705
4
5
6
3
5
12
2
5
7
1
5
§ 2.5 线性常系数递推关系例 5,求中 的 系数。
)1)(1()1(
1)(
323 xxxxG
nx na
解,的特征多项式是}{ na
)1)(1()1( 23 xxxx
§ 2.5 线性常系数递推关系是 3重根1?x
是 1重根1x
的根是 012 xx
32,1,2 31 3
2
iei
§ 2.5 线性常系数递推关系因此可设
3
2
si n
3
2
c o s
)1(
2
nFE
D
n
CBnAa
n
n
§ 2.5 线性常系数递推关系通过做长除法，求得
876
5432
6542
323
1087
54321
1
1
)1)(1()1(
1
)(
xxx
xxxxx
xxxxx
xxx
xG
§ 2.5 线性常系数递推关系可知
,1,1,1
,1,1,1,1,1,1
876
543210
aaa
aaaaaa
利用 的值解得。
故
543210,,,,,aaaaaa
FEDCBA,,,,,
3
2
si n
3
2
c o s)1(
2
nF
ED
n
CBnAa
n
n
§ 2.5 线性常系数递推关系通过上式，计算得 与用长除法得到的结果相同。
,10,8,7 876 aaa
§ 2.6 整数的拆分和 Ferrers图像
§ 2.6.1 问题举例所谓整数拆分即把整数分解成若干整数的和，相当于把 n个无区别的球放到 n个无标志的盒子，盒子允许空着，也允许放多于一个球。整数拆分成若干整数的和，办法不一，不同拆分法的总数叫做拆分数。
§ 2.6.1 问题举例例 1,若有 1克,2克,3克,4克的砝码各一枚，问能称出那几种重量？有几种可能方案？
10987
65432
74332
432
1
)1)(1(
)1)(1)(1)(1(
xxxx
xxxxxx
xxxxxx
xxxx
§ 2.6.1 问题举例从右端的母函数知可称出从 1克到 10克，
系数便是方案数。例如右端有 项，即称出 5克的方案有 2
52x
41325
同样，
432110
243216
故称出 6克的方案有 2，称出 10克的方案有 1
§ 2.6.1 问题举例例 2,求用 1分,2分,3分的邮票贴出不同数值的方案数。
因邮票允许重复，故母函数为
)1(
)1)(1()(
63
422
xx
xxxxxG
以其中为例，其系数为 4，即 4拆分成 1、
2,3之和的拆分数为 4，即
223121111114
§ 2.6.1 问题举例例 3,若有 1克砝码 3枚,2克砝码 4枚,4
克砝码 2枚的砝码各一枚，问能称出那几种重量？各有几种方案？
§ 2.6.1 问题举例
191817161514
1312111098
765432
841110987
65432
84
864232
2233
445555
4433221
)1)(222
222221(
)1(
)1)(1()(
xxxxxx
xxxxxx
xxxxxxx
xxxxxxx
xxxxxx
xx
xxxxxxxxG
§ 2.6.1 问题举例例 4,整数 n拆分成 1,2,3,…,m的和，
并允许重复，求其母函数。如若其中 m至少出现一次，其母函数如何？
若整数 n拆分成 1,2,3,…,m的和，
并允许重复，其母函数为：
)1(
)1)(1()(
2
422
1
mm xx
xxxxxG
§ 2.6.1 问题举例
)1()1)(1(
1
1
1
1
1
1
1
)1(
)1)(1()(
2
2
2
422
1
m
m
mm
xxx
xxx
xx
xxxxxG
§ 2.6.1 问题举例若拆分中 m至少出现一次，其母函数为：
)1()1)(1(
)(
)1)(1()(
2
2
422
2
m
m
mm
xxx
x
xx
xxxxxG
§ 2.6.1 问题举例显然有
)162(
)1()1)(1(
1
)1()1)(1(
1
)(
12
22
m
m
xxx
xxx
xG
等式 (2-6-1)的组合意义：即整数 n拆分成 1到
m的和的拆分数减去拆分成 1到 m-1的和的拆分数，即为至少出现一个 m的拆分数。
§ 2.6.1 问题举例例 1,若有 1,2,4,8,16,32克的砝码各一枚，问能称出那几种重量？有几种可能方案？
63
0
632
64
32
64
16
32
8
16
4
8
2
42
32
16842
)1(
1
1
1
1
1
1
1
1
1
1
1
1
1
1
)1(
)1)(1)(1)(1)(1( )(
k
k
xxxx
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
xxxxxxG
§ 2.6.1 问题举例从母函数可以得知，用这些砝码可以称出从 1克到 63克的重量，而且办法都是唯一的。
这问题可以推广到证明任一十进制数 n，
可表示为
0,10,2
0
kaan k
k
k
k
而且是唯一的。
§ 2.6.2 拆分数估计式定理,设 为整数 n的拆分数，则np
n
n ep
3
20
证,令 2210)( xpxppxG
一个整数 n拆分成若干整数的和，在拆分中每个整数允许重复出现。故
)1)(1)(1(
1)(
32 xxxxG
§ 2.6.2 拆分数估计式
)1l n (
)1l n ()1l n ()(ln
3
2
x
xxxG
32 3121)1l n ( xxxx
6422 3121)1l n ( xxxx
§ 2.6.2 拆分数估计式
)262(
13
1
12
1
1
)
3
1
2
1
(
)
3
1
2
1
(
)
3
1
2
1
()(ln
3
3
2
2
642
642
32
x
x
x
x
x
x
xxx
xxx
xxxxG
§ 2.6.2 拆分数估计式
12
1
111?
n
n
n
n
xxx
x
x
x
x
x
由于,1 32 nxxxx
11321 nn nxxxxx?
)362( 111 xxnxx n
n
§ 2.6.2 拆分数估计式把 (2-6-3)式代入 (2-6-2)式得
)
3
1
2
1
1(
1
13
1
12
1
1
)(ln
22
22
x
x
x
x
x
x
x
x
xG
由于
2
1
1
2
1
1
4
1
11
2
2
nnn
n
§ 2.6.2 拆分数估计式因而
)46(2
13
5
)(ln
3
5
2
1
2
1
1
3
1
2
1
1
2
1
1
)1(
11
22
22
x
x
xG
n
nn
§ 2.6.2 拆分数估计式设,有 )1,0(?x
)562(
1
ln)(lnln
lnln)(ln
)(
2
210
x
nxGp
xnpxG
xp
xpxpxppxG
n
n
n
n
n
n
§ 2.6.2 拆分数估计式把 (2-6-4)式代入 (2-6-5)式得
)662( 1ln1 2ln xnxxp n
曲线 是上凸，故曲线位于曲线的切线下方，点 的切线为
yz ln? yz ln?
)0,1(
1 yz
故有 1ln yy
§ 2.6.2 拆分数估计式
yz ln?
)0,1(0 x
y
图 (2-6-1)
§ 2.6.2 拆分数估计式
1- 1 1ln xx?
以上式代入 (2-6-5)式得：
)762(
)1(
)1(3
5
)1
1
(
)1(3
5
ln
x
xn
x
x
x
n
x
x
p
n
§ 2.6.2 拆分数估计式不等式 (2-6-7)的左端 是常数，右端是 的函数,即不等式对于 成立。
右端函数取极小值时将给出较好的上界值。
令
nplnx
)1,0(?x
x
xn
x
xy )1(
)1(3
5
求导得
22)1(3
5
x
n
xy
§ 2.6.2 拆分数估计式令,得0y
036)53( 2 nnxxn
解方程，得
53
153
n
nnx
)1,0(53 3,153 153 21 n nxn nnx
§ 2.6.2 拆分数估计式因为 0,2
)1(
1
3
10
233
xyx nxy
所以 是极小值。以 的值代入,得2x 2x y
ny 320?
n
n ep
3
20
§ 2.6.2 拆分数估计式利用,上式可改进为 62
1
2
11 2
22
n
n ep
3
20
§ 2.6.3 Ferrers图像一个从上而下的 n层格子,为第 层的格子数，当,
即上层的格子数不少于下层的格子数时，
称之为 Ferrers图像，如图 (2-6-2)示。
im i )1,2,1(,
1 nimm ii?
图 2-6-2
§ 2.6.3 Ferrers图像
Ferrers图像具有如下性质：
1.每一层至少有一个格子。
2.第一行与第一列互换，第二行于第二列互换,…，即图 (2-6-3)绕虚线轴旋转所得的图仍然是 Ferrers图像。两个 Ferrers
图像称为一对共轭的 Ferrers图像。
§ 2.6.3 Ferrers图像利用 Ferrers图像可得关于整数拆分的十分有趣的结果。
(a)整数 n拆分成 k个数的和的拆分数，
和数 n拆分成个数的和的拆分数相等。
因整数 n拆分成 k个数的和的拆分可用一 k行的图像表示。所得的 Ferrers图像的共轭图像最上面一行有 k个格子。例如：
§ 2.6.3 Ferrers图像
24=6+6+5+4+3
5个数，最大数为 6
24=5+5+5+4+3+2
6个数，最大数为 5
图 (2-6-3)
§ 2.6.3 Ferrers图像
(b)整数 n拆分成最多不超过 m个数的和的拆分数，和 n拆分成最大不超过 m的拆分数相等。
理由和 (a)相类似。
因此，拆分成最多不超过 m个数的和的拆分数的母函数是
)1()1)(1(
1
2 mxxx
§ 2.6.3 Ferrers图像拆分成最多不超过 m-1个数的和的拆分数的母函数是
)1()1)(1(
1
12 mxxx?
所以正好拆分成 m个数的和的拆分数的母函数为
§ 2.6.3 Ferrers图像所以正好拆分成 m个数的和的拆分数的母函数为
)1()1)(1(
)1()1)(1(
1
)1()1)(1(
1
2
12
2
m
m
m
m
xxx
x
xxx
xxx
§ 2.6.3 Ferrers图像
(c)整数 n拆分成互不相同的若干奇数的和的的拆分数,和 n拆分成自共轭的
Ferrers图像的拆分数相等,
设,)12()12()12( 21 knnnn?
其中 。 knnn21
构造一个 Ferrers图像，其第一行，第一列都是 格，对应于,第二行，
第二列各 格，对应于 。以此类推。由此得到的 Ferres图像是共轭的。反过来也一样。
11?n 12 1?n
12?n 12 2?n
§ 2.6.3 Ferrers图像例如 35917
对应为 Ferrers图像为
9+5+3=17
图 (2-6-4)
§ 2.7 指数型母函数
§ 2.7.1 问题提出设有 n个元素，其中元素 重复了 次，
元素 重复了 次,…,重复了 次，
从中取 r个排列，求不同的排列数
1a 1n
2a 2n ka kn
knnnn21
如果,则是一般的排列问题。
121 knnn?
§ 2.7.1 问题提出现在由于出现重复，故不同的排列计数便比较复杂。先考虑 个元素的全排列，
若 个元素没有完全一样的元素，则应有种排列。若考虑 个元素 的全排列数为
，则真正不同的排列数为
n
n !n
in ia!
in
!!!
!
21 knnn
n
§ 2.7.2 解的分析先讨论一个具体问题：若有 8个元素，
其中设 重复 3次,重复 2次,重复 3次。
从中取 r个组合，其组合数为,则序列的母函数为
1a 3a2a
rc
76543210,,,,,,,cccccccc
8765432
325432
32232
369109631
)1( )23321(
)1)(1)(1()(
xxxxxxxx
xxxxxxxx
xxxxxxxxxG
§ 2.7.2 解的分析从 的系数可知，这 8个元素中取 4个组合，其组合数为 10。这 10个组合可从下面展开式中得到
4x
)1(
])()(
)()(1[
)1)(1)(1(
3
3
2
33
2
2
3
1
2
2
2
12
3
1
2
212
2
1
3
1
2
221
2
121
3
3
2
33
2
22
3
1
2
11
xxx
xxxxxxxxxxx
xxxxxx
xxxxxxxx
§ 2.7.2 解的分析
)
()
()
()1( 1
2
2
2
1
3
3
13
2
2132
2
13
3
1
2
3
2
2
2
321
2
3
2
1
3
32
3
31
3
3
2
32
2
313
2
2
3213
2
1
2
212
2
1
3
1
3
332
31
2
221
2
1321
xx
xxxxxxxxxxxxxxx
xxxxxxxxxxxxx
xxxxxxxxxxxxx
xxxxxxxxx
承前页
§ 2.7.2 解的分析其中 4次方项有
)272( 222133132213221
3
3
1
2
3
2
2
2
321
2
3
2
1
3
32
3
31
xxxxxxxxxx
xxxxxxxxxxxxx
(2-7-2)表达了从 8个元素 ( 各 3个,
2个 )中取 4个的组合。例如 为一个,3
个 的组合,为两个,两个 的组合，
以此类推。
31,aa 2a
331xx 1a
3a 2321 xx 3a1a
§ 2.7.2 解的分析若研究从中取 4个的不同排列总数，以对应的两个两个的不同排列为例，其不同排列数为
2321 xx
6!2!2 !4?
即六种。同样,1个 3个的不同排列数为
,3311 aaaa,1331 aaaa,3131 aaaa,1313 aaaa
,1133 aaaa,3113 aaaa 1a
3a 4
!3
!4?
§ 2.7.2 解的分析即以此类推。故从 (2-7-2)式可得问题的解，
其不同的排列数为
,3331 aaaa,1333 aaaa,3133 aaaa,3313 aaaa
70361816
!3!2!2
!3!23!33!2!24
!4)
!2
3
!2!2
3
!3
4
(!4
)
!2!2
1
!1!3
1
!1!2!1
1
!1!1!2
1
!1!3
1
!2!2
1
!2!1!1
1
!2!2
1
!3!1
1
!3!1
1
(!4
§ 2.7.3 指数型母函数为了便于计算，利用上述特点，形式地引进函数
)
!3!2!1
1(
)
!2!1
1)(
!3!2!1
1()(
32
232
xxx
xxxxx
xG
e
§ 2.7.3 指数型母函数
)372(
72
1
72
8
72
35
12
17
12
35
3
14
2
9
31
)
6
1
2
1
1(
)
12
1
12
5
6
7
22(1 )(
876
5432
32
5432
xxx
xxxxx
xxx
xxxxxxG
e
承上页
§ 2.7.3 指数型母函数从 (2-7-3)式计算结果可以得出：取一个的排列数为,取两个的排列数为取 3个的排列数为,取 4个的排列数为,如此等等。把 (2-7-
3)式改写成下面形式便一目了然了 。
3,92/92
283/14!3
7012/35!4
)472(
!8
560
!7
560
!6
350
!5
170
!4
70
!3
28
!2
9
1!
3
1! )(
876
5432
xxx
xxxxxxG
e
§ 2.7.3 指数型母函数定义,对于序列,函数?,,,210 aaa
kk
e
x
k
a
x
a
x
a
x
a
axG
!
!3!21!
)(
33221
0
称为是序列 得指数型母函数?,,,210 aaa
§ 2.7.3 指数型母函数综合上述可得如下两个结论：
(a) 若元素 有 个，元素 有 个，
……，元素 有 个，由此；组成的 n个元素的排列，不同的排列总数为
1a 1n 2a 2n
knka
!!!
!
21 knnn
n
其中 knnnn21
§ 2.7.3 指数型母函数
(b) 若元素 有 个，元素 有 个，
……，元素 有 个，由此；组成的 n个元素中取 r个排列，设其不同的排列数为 。则序列 的指数型母函数为
1a 1n 2a 2n
knka
rp
nppp?,,10
)
!!21!
1( )
!!21!
1(
)
!!21!
1( )(
2
2
2
1
2
2
1
k
nn
n
e
n
xxx
n
xxx
n
xxx
xG
k
§ 2.7.3 指数型母函数与 (2)中所用的方法相比，可以看出指数型母函数在解决有重复元素的排列时的优越性。
§ 2.7.4 举例例 1,求由两个,1个,2个 组成的不同排列总数。
a b c
根据结论一，不同的排列总数为
30!1!2!2 !5n
§ 2.7.4 举例例 2,由 1,2,3,4四个数字组成的五位数中，要求数 1出现次数不超过 2次，但不能不出现； 2出现次数不超过 1次； 3出现次数可达 3次，也可以不出现； 4出现次数为偶数。求满足上述条件的数的个数。
§ 2.7.4 举例设满足上述条件的 r位数为,序列的指数型母函数为
ra
1021,,aaa?
)
144488
1
24
7
3
2
1)(
2
1
2
3
(
)
!4!2
1(
)
!3!2!1
1)(1)(
!21!
( )(
76
54
3232
42
322
xx
xx
xxxxxx
xx
xxx
x
xx
xG
e
§ 2.7.4 举例
10987
65432
288
1
48
1
288
1
48
17
48
43
24
43
3
8
3
2
5
xxxx
xxxxxx
!10
12 60 0
!9
76 50
!8
140
!7
17 85
!6
645
!5
215
!4
64
!3
18
!2
5
!1
10987
65432
xxxx
xxxxxx
由此可见满足条件的 5位数共 215个。
§ 2.7.4 举例例 3,求 1,3,5,7,9五个数字组成的 位数的个数，要求其中 3,7出现的次数为偶数，
其他 1,5,9出现次数不加限制。
设满足条件的 位的个数为,则序列对应的指数型母函数为
r
n
ra
,,,321 aaa
)!3!21()!4!21()(
32
2
42
xxxxxxG e
§ 2.7.4 举例由于 ),!3!21
32
xxxe x
).(21!4!21
42
xx eexx
xxx
xxx
e
eee
eeexG
322
32
)2(
4
1
)(
4
1
)(
§ 2.7.4 举例
).1325(
4
1
.
!
)1325(
4
1
)
!!
3
2
!
5
(
4
1
)2(
4
1
0
0 00
35
nn
n
n
n
n
n
n n
nnn
n
n
n
xxx
a
n
x
n
x
n
x
x
n
eee
§ 2.8 母函数和递推关系应用举例
§ 2.8 母函数和递推关系应用举例例 1,下图是一逻辑回路，符号 D是一延迟装臵，即在时间 t输入一个信号给延迟装臵 D,在 t+1时刻 D将输出同样的信号，符号表示加法装臵?
D D D
输入 u
输出 v
图 2-8-1
§ 2.8 母函数和递推关系应用举例若在 时刻，输入信号求相同时刻的输出信号 。
,2,1,0?t,,,10?uu
,,10 vv
显然，,,,12201100 uuvuuvuv
。,0233 uuuv
一般的有,3,31 nuuuv nnnn
§ 2.8 母函数和递推关系应用举例若信号输入的序列 的母函数为,输出的信号序列 的母函数为,则
,,,10?uu
)(xU,,,10?vv
)(xV
)()()()1()( 3 xUxPxUxxxV
其中 31)( xxxP
被装臵（图 2-8-1）的特性所确定，可以看作是该装臵的传递函数，如图 2-8-2
)(xU )(xV)(xP
§ 2.8 母函数和递推关系应用举例例 2,由红球两个，白球、黄球各一个，
试求有多少种不同的组合方案。
设 r,w,y分别代表红球，白球，黄球。
ywrry wwryr
ywrwryrwyr
ywwyrr
ywrr
222
2
2
2
)(
)()(1
)1)(1(
)1)(1)(1(
§ 2.8 母函数和递推关系应用举例由此可见，出一个球也不取的情况外，有：
（ a） 取一个球的组合数为三，即分别取红，白，黄，三种。
（ b） 取两个球的组合数为四，即两个红的，一红一黄，一红一白，一白一黄。
（ c） 取三个球的组合数为三，即两红一黄，两红一白，一红一黄一白。
（ d） 取四个球的组合数为一，即两红一黄一白。
§ 2.8 母函数和递推关系应用举例令取 r的组合数为,则序列的母函数为
rc 43210,,,,ccccc
432
22
3431
)1)(1()(
xxxx
xxxxG
共有 1+3+4+3+1=12种组合方式。
§ 2.8 母函数和递推关系应用举例例 3,n个完全一样的球放到 m个有标志的盒子中，不允许有空盒，问共有多少种不同的方案？其中 mn?
由于不允许有空盒，令 n个球放到 m个有标志的盒子的方案数为,序列 对应的母函数为 。则
na }{ na)(xG
m
m
x
x
xxxxxxxG
)1(
)())(()( 222
§ 2.8 母函数和递推关系应用举例因
3
2
!3
)2)(1(
!2
)1(
1)1(
x
mmm
x
mm
mxx
m
故二项式 中 项系数为mx )1( mnx?
)!(
)1()1(
)!(
)1()1(
mn
nmm
mn
mnmmm
§ 2.8 母函数和递推关系应用举例即
)1,1(
),1(),1)((
mnC
mnnCmnmnmC
§ 2.8 母函数和递推关系应用举例例 4,某单位有 8个男同志,5个女同志，
现要组织一个有数目为偶数的男同志和数目不少于 2的女同志组成的小组，试求有多少种组成方式。
令 为从 8位男同志中抽取出 n个的允许组合数。由于要男同志的数目必须是偶数，
故
。
na
,28)2,8(,1,0 207531 Caaaaaa
1,28)6,8(,70)4,8( 864 aCaCa
§ 2.8 母函数和递推关系应用举例故数列 对应一母函数 8210,,,,aaaa?
8642 2870281)( xxxxxA
类似的方法可得女同志的允许组合数对应的母函数位
5432 51010)( xxxxxB
§ 2.8 母函数和递推关系应用举例
131211
10987
65432
5432
8642
538
150350630728
8402812851010
)51010(
)2870281(
)()()(
xxx
xxxx
xxxxx
xxxx
xxxx
xBxAxC
§ 2.8 母函数和递推关系应用举例中 项的系数 为符合要求的 个人组成的小组的数目，总的组成方式数目为
)(xC kx kc k
3 3 2 815381 5 03 5 0
6 3 07 2 88 4 02 8 12 8 51010
§ 2.8 母函数和递推关系应用举例例 5,10个数字（ 0到 9）和 4个四则运算符 组成的 14个元素。求由其中的
n个元素的排列构成一算术表达式的个数。
),,,(
因所求的 n个元素的排列是算术表达式，
故从左向右的最后一个符号必然是数字。而第 n-1位有两种可能，一是数字，一是运算符。如若第 n-1位是十个数字之一，则前 n-1
位必然构成一算术表达式。
§ 2.8 母函数和递推关系应用举例如若不然，即第 位是 4个运算符之一，
则前 位必然是算术表达式。根据以上分析，令 表 个元素排列成算术表达式的个数。则
1?n
2?n
na n
.1 2 0,10
1)-8-(2,4010
21
21
aa
aaa nnn
指的是从 0到 99的 100个数，以及1202?a,0?
.9,,1
§ 2.8 母函数和递推关系应用举例利用递推关系,得特征多项式 。它的根是
)182(,2
1
0?a
40102 xx
,)655()655(
.655
nn
n BAa
x
解方程
,10)655()655(
,
2
1
BA
BA
§ 2.8 母函数和递推关系应用举例得
.654/)6515(
,654/)6515(
B
A
].)655)(6515(
)655)(6515[(
654
1
n
n
na
§ 2.8 母函数和递推关系应用举例例 6,设有 n条封闭的曲线，两两相交于两点，任意三条封闭曲线不相交于一点。求这样的 n条曲线把平面分割成几个部分？
设满足条件的 n条封闭曲线所分割成的域的数目为
，其中 条封闭曲线所分割成的域的数目为 图 2-8-3
na 1?n
1?na
§ 2.8 母函数和递推关系应用举例第 n条封闭曲线和这些曲线相交于 个点，这 个点把第 n条封闭曲线截成条弧，每条弧把 个域中的每个域一分为二。故新增加的域数为
)1(2?n
)1(2?n
)1(2?n )1(2?n
).1(2?n
2)-8-(2,2 ),1(2 11 anaa nn
利用递推关系 得 2)-8-(2,20?a
§ 2.8 母函数和递推关系应用举例设
.
2
22
,2,24
,0,22
2
,
2
222
111
00
210
n
a
AAa
AAa
Aa
n
AnAAa
n
n
§ 2.8 母函数和递推关系应用举例另解：利用欧拉公式点数 +域数 -边数 =2
点数 =,
边数 = 点数域数 =
2
2
n
2
.
2
222
2
2
2
4?
nnn
§ 2.8 母函数和递推关系应用举例例 7,平面上有一点 P,它是 n个域的共同交界点，见图 现取 k种颜色对这 n个域进行着色，
要求相邻两个域着的颜色不同。
试求着色的方案数。
令 表示这 n个域的着色方案数。无非有两种情况：
1D
2D
3D
1?nD
nD
P?
图 2-8-4
nDDD,,,21?
482
na
§ 2.8 母函数和递推关系应用举例
（ 1） 和 有相同的颜色；（ 2） 和 所着颜色不同。第一种情形,域有 种颜色可用，即 域所用颜色除外；而且从到 的着色方案，和 个域的着色方案一一对应。后一种 域有 种颜色可供使用；而且从 到 的每一个着色方案和 个域的着色方案一一对应。
1D
1D
1D1D
11,?nDD
1?nD
1?nD1?nD 1?k
2?nD 2?n
nD 2?k
1?n
§ 2.8 母函数和递推关系应用举例利用 得的特征方程为
).2)(1( ),1(
3)-8-(2,)1()2(
32
21
kkkakka
akaka nnn
3)-8-(2
3)-8-(2,,0 01 kaa
.)1()1(
.1,1
,0)1()2(
21
2
nn
n BkAa
xkx
kxkx
§ 2.8 母函数和递推关系应用举例解方程
.0)1(
,
BAk
kBA
)482(
得
,
.2,)1)(1()1(
.1
,1
1
ka
nkka
kB
A
nn
n
§ 2.8 母函数和递推关系应用举例例 8,求下列行列式（ n行 n列 ）
行nd
n
1 1 0 0 0 0
0 0 1 1 1 0
0 0 0 1 1 1
0 0 0 0 1 1
§ 2.8 母函数和递推关系应用举例利用行列式展开法，沿第一行展开得利用 式得
5)-8-(2,0,1,2121 ddddd nnn
5)-8-(2 1,0?d
特征方程是解方程，得
012 xx
.2 31 3 ieix
§ 2.8 母函数和递推关系应用举例设
,3s i n3c o s nBnAd n
解方程
1)
2
3
()
2
1
(
1)
3
0s i n ()
3
0c o s (
BA
BA
§ 2.8 母函数和递推关系应用举例得
.1,
3
s i n
3
1
3
c o s
3
1
1
nnnd
B
A
n
§ 2.8 母函数和递推关系应用举例例 9,求 n位 2进制最后三位出现 010图象的数的个数。
对于 n位 2进制数 从左而右进行扫描，一当出现 010图象，便从这图象后面一位从头开始扫描，例如对 11位 2进制数
00101001010从左而右的扫描结果应该是 2-
4,7-9位出现 010图象，即
nbbb?21
10010100100
§ 2.8 母函数和递推关系应用举例而不是 4-6,7-9位出现的 010图象，即不是为了区别于前者起见，我们说 4-6,9-11
位是 010，但不是“出现 010图象”，这作为约定。
为了找出关于数列 的第推关系，需对满足条件的数的结构进行分析。由于 n位中除了最后三位是 010已确定，其余 位可取 0或 1：
0 1 0010 1 00 0 1
na
3?n
§ 2.8 母函数和递推关系应用举例故最后 3位是 010的 n位 2进制数的个数是 。
其中包含最后 3位出现 010图象的以及在 位到第 位出现 010图象，而在最后 3位并不出现 010图象的两类数，后一种数为
00 1
32?n
4?n
2?n
01010
§ 2.8 母函数和递推关系应用举例故有
2.,1
,5,2
43
3
2
aa
naa nnn
6)-8-(2
利用 推得特征方程为
6)-9-(2,2
1,0,0
012 aaa
.,2
.0)1)(2(
2
3,21
2
i
exx
xx
§ 2.8 母函数和递推关系应用举例设
,2)2s i n ()2c o s ( nn CnBnAa
解方程组
.04
,02
,
2
1
CA
CB
CA
§ 2.8 母函数和递推关系应用举例得
.
10
1
,
5
1
,
5
2
C
B
A
.3,210 1)2s i n (51)2c o s (52 nnna nn
§ 2.8 母函数和递推关系应用举例例 10,求 n位的 2进制数中最后三位才第一次出现 010图象的数的个数。
即求对 n位 2进制数 从左而右扫描，第一次在最后三位出现 010图象的数的个数。自然，最后三位除外任取连续三个都不会是 010的。
设 表满足条件的 n位数个数，和前例类似，最后三位是 010的 n位 2进制数共 个，
nbbb?21
na
32?n
§ 2.8 母函数和递推关系应用举例对这 个数分析如下。
（ a） 包含了在最后三位第 1次出现 010图象的个数，其个数为,排除了在第 到第位第 1次出现 010图象的可能。
（ b）包含了在第 到第 位第 1次出现
010图象的数，其个数为
32?n
na
)4(?n
)4(?n
)2(?n
)2(?n
.2?na
00 1 1 0
§ 2.8 母函数和递推关系应用举例
（ c） 包含了在第 位到第 位第 1
次出现 010图象的数，其个数是,3?na
)5(?n )3(?n
00 1 1 00
§ 2.8 母函数和递推关系应用举例
（ d） 包含了在第 位到第 位第 1
次出现 010图象的数，其个数是,因在第 位（打 *号的格）可以取 0或 1两种状态。
)6(?n )4(?n
42?na
3?n
00 1 1 00?
§ 2.8 母函数和递推关系应用举例一般可以归纳为对,从第 位到第 位第一次出现 010图象的数，其数目为 。从第 位到第 位中间的 位可以取 0,1两种值，故有 种状态。
3?k )2( kn
kn?
knk a32 kn? 3?n3?k
32?k
00 1 1 00
§ 2.8 母函数和递推关系应用举例故得递推关系如下：
7)-8-(2,3,2,1
6,222
543
3
3
6
432
aaa
naaaaa nnnnnn?
时有下面几种状态：
排除了 01010，因从左而右扫描时 01010属于前三位出现 010图象的。
5n?
.11010,10010 00010,
§ 2.8 母函数和递推关系应用举例请注意，递推关系 式不是常系数递推关系。
.3,2,1 543 aaa
7)-8-(2
故 时有时有其它依此类推。
6n?
.58,2 3473346 aaaaaa
7n?
.9216,22 345743457 aaaaaaaa
§ 2.8 母函数和递推关系应用举例令 47362321)( xaxaxxxA
5
3
2
4568
5
4
3457
4
3
346
3
222:
22:
2:
aaaaax
aaaax
aaax
)
.212)()22(
]1)([]321)([
335243
22
xxxAxxx
xAxxxxA
§ 2.8 母函数和递推关系应用举例整理得
.
21
1
21
84412
)(
21
221
.421
21
2
)()
21
1(
32233332
2
333
2
x
x
xxxx
xA
x
xxxx
xx
x
x
xA
x
x
x
§ 2.8 母函数和递推关系应用举例
,49,28,16,9
,5,3,2,1
4928169
5321
21
1
)(
10987
6543
7654
32
32
aaaa
aaaa
xxxx
xx
xxx
xA
§ 2.8 母函数和递推关系应用举例例 11,解图 电路网络中的设其中
582,jv
.,,2,1,0 nj,)( vtv?
2 2 2 2 2 2 2
4 4 4 4 4 4 0v1v2vjv1?jv2?jv1?nv 2?nvnv
2)(tv
§ 2.8 母函数和递推关系应用举例图 根据欧姆定律有
2
1?ji ji jv1?jv2?jv
22
1 4
图 2-8-5
582
.4
,4
1
121
jjj
jjj
vvi
vvi
§ 2.8 母函数和递推关系应用举例由于各点的电流代数和为零，
).(
4
1
)882( ),(
4
1
1
121
jjj
jjj
vvi
vvi
9)-8-(2,21 11 jjj vii
§ 2.8 母函数和递推关系应用举例代入 得递推关系
)1082(,04141 12 jjj vvv
)882( 9)-8-(2
或,2,,2,1,0,04 12 njvvv jjj?
由 点的电流代数和为零，可得
.3
,
2
1
)(
4
1
01
001
vv
vvv
0v
§ 2.8 母函数和递推关系应用举例特征方程是,0142 xx
设解方程组
32x
,)32()32( nnn BAv
.3)32()32(
,
0
0
vBA
vBA
§ 2.8 母函数和递推关系应用举例得
].)32)(31(
)32)(31[(
32
)31(
32
1
)31(
32
1
0
0
0
n
n
n
v
v
vB
vA
§ 2.8 母函数和递推关系应用举例例 12,求图 2-8-6所示的 n级网络的等效电阻 。nR
所谓等效电路，相当于图 2-8-6中虚线所包围的块用一电阻 取代，使在两端点之间的效果一样。
nRn n?
n
n?
R R R R
R R R R
R R R R R R
图 2-8-6
n
n? nR
§ 2.8 母函数和递推关系应用举例可以作为由 等效电阻如图 所示的方式串并联构成的,
1?nR
R
R
R
图 2-8-7
nR 1?nR 782
§ 2.8 母函数和递推关系应用举例得递推关系如下
.
)2(
3
)2(
2
2
111
1
1
1
1
1
n
n
n
n
nn
RRR
RR
RRR
RRR
RRRR
.
4
3
,
11)-8-(2
3
)2(
21
1
1
RRRR
RR
RRR
R
n
n
n
§ 2.8 母函数和递推关系应用举例令
,1,,11 bRa
b
aR
n
n
n,
3
2
3
)2(
11
11
2
1
1
1
1
nn
nn
n
n
n
n
n
n
aRb
RabR
b
a
R
b
a
RR
b
a
因此
§ 2.8 母函数和递推关系应用举例令 )1282(
.3
,2
11
11
2
nnn
nnn
aRbb
RabRa
将 代入得到
11 3 nnn Rbba,2 112 nnn RabRa
.0,4
.04
),3(23
02
1
2
1
11
2
1
bRb
bRRbb
RbbRbRRbb
nnn
nnnnn
§ 2.8 母函数和递推关系应用举例解方程组特征方程是 04 22 RRxx
.])32()32([
,)32(
nnn
n RBAb
Rx
.1)32()32(
,0
RBA
BA
§ 2.8 母函数和递推关系应用举例得
.
32
1
,
32
1
R
B
R
A
nnn
nn
n
n
Rbba
R
b
3
],)32()32[(
32
1
1
§ 2.8 母函数和递推关系应用举例
].)32)(13(
)32)(13[(
32
n
n
nR
,)13(
)32()32(
)32)(13()32)(13(
RR
b
a
n
nn
nn
n
n
§ 2.8 母函数和递推关系应用举例例 13,设有地址从 1到 n的单元，用以纪录一组信息。这个信息的每个元素都占用两个单元，而且存放的地址是完全随机的，因而可能出现两个存放信息单元之间留下一个空单元无法存放其他信息，求这 n各单元留下空单元的平均数。
§ 2.8 母函数和递推关系应用举例设这个平均数为 。na
1 2 i+1 i+2 n-1 n
存储单元如上图，设某一信息占用了第 i+1，
i+2两个单元，把这组单元分割成两个部分，
一是从 1到 i,另一从 i+3到 n。 由于用相邻两个单元的几率相等，
§ 2.8 母函数和递推关系应用举例
)],(
)()[(
1
1
02
3120
aa
aaaa
n
a
n
nnn
2
0
)1382( 2)1(
n
k
kn aan
（ 2-8-13）式是变系数递推关系，可改为
.0,1,0
,02)2()1(
210
21
aaa
aanan nnn
§ 2.8 母函数和递推关系应用举例设
,432)(
,)(
3
5
2
43
4
5
3
4
2
31
xaxaxaxG
xaxaxaaxG
)
,234,
,223,
,22,
345
3
234
2
123
aaax
aaax
aaax
___ _ _ _ _ _ _ _ _ __ _ _ _ _ _ _ _ _ _
.2)( xGGxxG
§ 2.8 母函数和递推关系应用举例
,2)1( xGGx
,1 221 2 xxxGG
,)1l n (2ln 2 CxxG
22 )1( xkeG x
.1,110 kaG x
§ 2.8 母函数和递推关系应用举例
5432
32
22
15
4
3
2
1
]
!3
)2(
!2
)2(
21[
)1(
xxxx
xx
x
xeG
x
§ 2.8 母函数和递推关系应用举例
.
!
)1(2
)1(
!
2
)1(
)2(
!3
2
)1(
!2
2
2)1(
0
32
1
k
kn
n
nnnna
kn
k
k
n
n
n
一般有
§ 2.9 排错问题
§ 2.9 排错问题
n个有序的元素应有 个不同的排列，
如若一个排列使得所有的元素在原来的位臵上，则称这个排列为错排；有的叫重排。
以 1,2,3,4四个数的错排为例，分析其结构，找出规律性的东西来。
!n
§ 2.9 排错问题即 12 3 2 1 33 13 2
1 2的错排是唯一的，即 2 1。
1 2 3的错排有 3 1 2,2 3 1。 这二者可以看作是 1 2错排,3分别与 1,2换位而得的。
§ 2.9 排错问题
1 2 3 4的错排有
4 3 2 1,4 1 2 3,4 3 1 2，
3 4 1 2,3 4 2 1,2 4 1 3，
2 1 4 3,3 1 4 2,2 3 4 1。
第一列是 4分别与 1,2,3互换位臵，其余两个元素错排，由此生成的。
§ 2.9 排错问题第 2列是 4分别与 3,1,2（ 123的一个错排）的每一个数互换而得到的。即
3 42 14 3 2 3 4 1 1 4
1 3 4 2 24
§ 2.9 排错问题第三列则是由另一个错排 231和 4换位而得到，即
1 3 4 2 24 1 2 4 3 3 4
3 2 4 1 14
§ 2.9 排错问题上面的分析结果，实际上是给出一种产生错排的结果。
设 n个数 1,2,…,n错排的数目为,
任取其中一数,数 分别与其他的 n-1个数之一互换，其余 n-2个数进行错排，共得个错排。另一部分位数 以外的
n-1个数进行错排，然后 与其中每个数互换得 个错排。
nDi i
2)1( nDn ii
1)1( nDn
§ 2.9 排错问题综合以上分析结果得递推关系
.1
1)-9-(2,1,0
),)(1(
0
21
21
D
DD
DDnD nnn
§ 2.9 排错问题
（ 2-9-1）是一非常系数的递推关系，下面提供一种解法。
)()1(
])2([)1(
])1([
01
1
32
2
211
DD
DnD
DnDnDD
n
nn
nnnn
由于 故得关于 得递推关系
,1,0 01 DD nD
)292(,)1(1 nnn nDD
§ 2.9 排错问题令
3322
10 !3!2)( x
DxDxDDxG
e
)1(
)1(
)1(
3
23
2
12
1
01
DD
DD
DD
§ 2.9 排错问题可得 x
ee exxGxG )()(
!)
!
1
!2
1
11(
).1/()
!2
1(
1
)(
`2
n
n
D
x
x
x
x
e
xG
n
x
e
§ 2.10 Stirling数
§ 2.10 Stirling数前面见到的递推关系都是一个参数的。 St
irling数问题则不然。它导出的递推关系式是两个参数的。
（ 1）多项式系数
n个有区别的球放到两个有区别的盒子里，
若要求第 1个盒子放 k个球，第二个盒子放 n-k
个球 方案数应是 中 ),,,2,1,0( nk nxx )( 21?
§ 2.10 Stirling数项的系数 依据加法法则有可把上面的讨论推广到 n个有区别的球放到 m
个有区别的盒子里，要求 m个盒子放的球数分别是 的情况，
其不同方案数用
knk xx?21 ).,( knC
.2),()1,()0,( nnnCnCnC
)(,,,2121 mm nnnnnnn
§ 2.10 Stirling数表示。
从 n个有区别的球中取出 个放到第 1个盒子里去，其选取方案数为 ；当第 1个盒子的 个球选定后，第 2个盒子里的 个
mnnn
n
21
1n
1n
n
2n 3n
§ 2.10 Stirling数球则是从 个中选取的，其方案数应为；第 3个盒子的 个球则是从中选取，其方案数为 ；依此类推，
根据乘法法则可得
1nn?
2
1
n
nn
21 nnn
3
21
n
nnn3n
§ 2.10 Stirling数
m
m
m
n
nnnn
n
nnn
n
nn
n
n
nnn
n
121
3
21
2
1
121
§ 2.10 Stirling数
.
!!!
!
!0!
!
)!(!
)!(
)!(!
)!(
)!(!
!
21
3213
21
212
1
11
mm
m
nnn
n
n
n
nnnnn
nnn
nnnn
nn
nnn
n
§ 2.10 Stirling数
n个有区别的球，放到 m个有标志的盒子的问题，也可以考虑把 n个有区别的球进行全排列。对于每一个排列依次取 个放到第 1个盒子里，取 个放到第 2个盒子里,…，最后个放到第 m个盒子里。然而，放到盒子里的球不考虑球的顺序，故得不同的方案数为
1n
2n 3n
§ 2.10 Stirling数结果和 式一致。
称 为多项式系数。
.
!!!
!
21 mnnn
n
mnnn
n
21
)1102(
§ 2.10 Stirling数
2)-10-(2 )(
)(
)()(
21
21
2121
m
m
m
n
m
xxx
xxx
xxxxxx
多项式 的展开式是由式右端的 n项中，每项各取一个元素相乘而得到的。
nmxxx )( 21
2)-10-(2
§ 2.10 Stirling数表达式 中共有 n个因子项，令第 i
个因子项对应于第 i个有标志的球，从第 i个因子项中取 对应于把第 i个有标志的球放到第 i个盒子。 式展开的一般项表示第一个盒子有 个球，第二个盒子有个球，等等。因此 式中
2)-10-(2
2)-10-(2
2)-10-(2
)( 2121 21 nnnnxxx mnmnn m
1n 2n
mnmnn xxx?21 21
§ 2.10 Stirling数项的系数应为
mnnn
n
21
即
)3102(,
)(
21
21
21
21
21
m
m
n
m
nn
nnnn m
n
m
xxx
nnn
n
xxx
§ 2.10 Stirling数定理,展开式的项数等于
，而且这些系数之和等于证明,展开式中的项 和从 m个元素 中取 n个作允许重复的组合一一对应。故得 展开式的
nmxxx )( 21
mnmnn xxx?21 21 )( 21 nnnn m
mxxx,,,21?
nmxxx )( 21
nmxxx )( 21
,
1
n
mn
nm
§ 2.10 Stirling数项数等于 。从 m个中取 n个作允许重复的组合的全体，对于每个球都有 m个盒子可供选择，根据乘法法则有 4)-10-(2,
21 21
n
nnnn m
m
nnn
n
m
n
mn 1
§ 2.10 Stirling数
(2)Stirling数只准备讨论其中的第二类 Stirling数,至于第一类的 Stirling数只准备给出它的定义和递推关系,
定义,
.),(
)2,()1,()0,(
)1()2)(1(][
2
n
n
xnns
xnsxnsns
nxxxxx
§ 2.10 Stirling数称 为第一类 Stirling数 ),(,),1,(),0,( nnsnsns
,)1,1(
)1,1()0,1(
)](),()1,()0,([][
1
1
n
n
n
xnns
xnsns
nxxnnsxnsnsx
显然有
)5102( ).,()1,(),1( knnsknskns
§ 2.10 Stirling数定义,n个有区别的球放到 m个相同的盒子中,要求无一空盒,其不同的方案数用表示,称为第二类 Stirling数,
例如红,黄,蓝,白四种颜色的球,放到两个无区别的盒子里,不允许有空盒,其方案有如下七种,
),( mnS
§ 2.10 Stirling数其中 r表红球,y表黄球,b表蓝球,w表白球,
1 2 3 4 5 6 7
第 1 盒子 r y b w ry rb Rw
第 2 盒子 ybw r b w r y w r y b bw yw yb
.7)2,4( S
§ 2.10 Stirling数定理,第二类 Stirling数 有下列性质,
),( knS
.1),( )(
),2,()1,( )(,12)2,( )(
,1)1,( )(,0)0,( )(
1
nnSe
nCnnSdnSc
nSbnSa
n
证明,公式 (a),(b),(e)是显然的,只证 (c),
(d).
§ 2.10 Stirling数
(c)设有 n个不相同的球 从中取出球,其余的 个球,每个都有与 同盒
,或不与 同盒两种选择,但必须排除一种情况,即全体与 同盒,因这时另一盒将是空盒,
故实际上只有 种方案,
即 12)2,(
1nnS
,,,,,321 nbbbb?
1b 1?n
12 1n
1b
1b
§ 2.10 Stirling数
(d)n个球放到 个盒子里,不允许有一空盒,故必有一盒有两个球,从 n个有区别的球中取 2个共有 种组合方案,
定理,第二类 Stirling数满足下面的递推关系,
1?n
)2,(nC
).1,1(
)6102(),1,1(),1(),(
mn
mnSmnmSmnS
§ 2.10 Stirling数证明,设有 n个有区别的球 从中取一个球设为,把 n个球放到 m个盒子无一空盒的方案的全体可分为两类。
（ a） 独占一盒，其方案数显然为
（ b） 不独占一盒，这相当于先将剩下的 个球放到 m个盒子，不允许空盒，共
,,,,21 nbbb?
1b
).1,1( mnS1
b
1b
1?n
§ 2.10 Stirling数共有 种不同方案，然后将 球放进其中一盒，从乘法法则得 不独占一盒的方案数应为
),1( mnS?
).,1( mnmS?
1b
1b
根据加法法则有上面证明递推公式 的过程，
也就是给出构造所有方案的办法。例如今将
).,1()1,1(),( mnmSmnSmnS
)6102(
§ 2.10 Stirling数红、黄、蓝、白、绿五个球放到无区别的两个盒子里。
故共有 15种不同的方案。
先把绿球取走，余下的四个球放到两个盒子的方案已见前面的例子。和前面一样用
r,y,b,w分别表示红，黄，蓝，白球，绿球用 g表示，故得表
,15172)1,4()2,4(2)2,5( SSS
1102
§ 2.10 Stirling数
g 不独占一盒 g 独占一盒第 1 盒子 第 2 盒子 第 1 盒子 第 2 盒子 第 1 盒子 第 2 盒子
rg
yg
bg
wg
r yg
r bg
r w g
ybw
r bw
r yw
r yb
bw
yw
yb
r
y
b
w
ry
rb
rw
yb w g
r bw g
r yw g
r yb g
bw g
yw g
ybg
g r yb w
表 2-10-1
§ 2.10 Stirling数
n个球放到 m个盒子里，依球和盒子是否有区别？是否允许空盒？共有 种状态。
其方案计数分别列于下表 。
823?
n个球有区别,m个盒子有区别，有空盒时方案计数为 nm
n个球有区别,m个盒子有区别，无空盒时方案计数为 ),(! mnSm
§ 2.10 Stirling数
n个球有区别,m个盒子无区别，有空盒时方案计数为
mn
nnSnSnS
mn
mnSnSnS
),,()2,()1,(
),,()2,()1,(
§ 2.10 Stirling数
n个球有区别,m个盒子无区别，无空盒时方案计数为 ),( nnS
n个球无区别,m个盒子有区别，有空盒时方案计数为 ),1( nmnC
§ 2.10 Stirling数
n个球无区别,m个盒子有区别，无空盒时方案计数为
)1,1(
),1(
),1)((
mnC
mnnC
mnmnnC
§ 2.10 Stirling数
n个球无区别,m个盒子无区别，有空盒时方案计数为
)1()1)(1(
1
)( 2 m
xxx
xG
的 项系数。nx
§ 2.10 Stirling数
n个球无区别,m个盒子无区别，无空盒时方案计数为
)1()1)(1(
)(
2 m
m
xxx
x
xG
的 项系数。nx
§ 2.10 Stirling数利用
，还可以如 Pascal三角形一样得到表 2-10-3。 表 2-10-3见书 119页。
),,1()1,1(),( mnmSmnSmnS
1),()1,( nnSnS
§ 2.11 Catalan 数
§ 2.11 Catalan 数这一节讨论 Catalan数,其递推关系是非线性的,许多有意义的计数问题都导致这样的递推关系,本节将举出一些,后面还将见到,
一个凸 n边形,通过不相交于 n边形的对角线,把 n边形拆分成若干三角形,不同拆分的数目用 表之,
nh
§ 2.11 Catalan 数例如五边形有如下五种拆分方案，故,5?nh
图 2-11-1
§ 2.11 Catalan 数
1.递推关系定理：
)2112( ),
(
2
)3( )(
)1112(,)(
3142
2413
21321
hhhh
hhhh
n
hnb
hhhhhhha
nn
nnn
nnnn
§ 2.11 Catalan 数证明,的证明：
如图 所示，
以 作为一个边的三角形,
将凸 边形分割成两部分，一部分是边形，
1v
2v
3v
kv
nv
1?nv
边形k
边形2 kn
图 2-11-2
)(a
1112
11?nvv
1?n
11?nkvvv
k
§ 2.11 Catalan 数另一部分是 边形,即点可以是 点中任意一点。依据加法法则有
2 kn,,,3,2 nk kv
nvvv,,,32?
,231132
2
21
hhhhhhhh
hhh
nnnn
n
k
knkn
§ 2.11 Catalan 数的证明：
如图 所示，
从 点向其它 个顶点可引出 条对角线。
对角线 把 边形分割成两个部分，因此
1v
2v
kv
nv
边形k
边形2 kn
图 2-11-3
)(b
3112
1v 3?n
},,,{ 143?nvvv?
kvv1
3?n
n
§ 2.11 Catalan 数以 对角线作为拆分线的方案数为可以是 中任一点，对所有这些点求和得以 取代 点也有类似的结果。但考虑到对角线有两个顶点，同一对角线在两个顶点分别计算了一次，
kvv1 2knk hh
kv 143,,,?nvvv?
.31422413 hhhhhhhh nnnn
nvvv,,,32? 1v
§ 2.11 Catalan 数作
)3112(),(2 31422413 hhhhhhhhn nnnn?
式并不就给出剖分数，无疑其中是有重复的。其重复度是由于一个凸 边形的剖分有 条对角线，而对其每一条边计数时该剖分都计数了一次，故重复了次即 式给出的结果是 的 倍。
)3112(
3?n
3?n
n
3112 nh 3?n
§ 2.11 Catalan 数式和 式都是非线性的递推关系。
),
(
2
)3(
3142
2413
hhhh
hhhh
n
hn
nn
nnn
)1112( )2112(
§ 2.11 Catalan 数
2.Catalan 数计算公式由 式及,故得)1112( 12?h
)2(
2
)(
2
)3(
.2
1
312413
314224131
nn
nnnn
nnnnnn
hh
n
hhhhhh
n
hn
hhhhhhhhhh
§ 2.11 Catalan 数由整理得令
),2(2)3( 1 nnn hhnhn
.2)3(2 1 nnn nhnhhn
.)64( 1 nn hnnh
,11 nn nhf
.
)1)(1(
)32)(22(
1
)3(2
1
)64(
1
n
n
n
n
f
nn
nn
f
n
n
n
f
nf
§ 2.11 Catalan 数即,1,)1)(1(
)32)(22(
22
1
hf
nn
nn
f
f
n
n
11
22
22
34
)2)(2(
)52)(42(
)1)(1(
)32)(22(
2
3
3
4
2
1
1
1
1
nn
nn
nn
nn
f
f
f
f
f
f
f
f
f
f
f
n
n
n
n
n
n
n
§ 2.11 Catalan 数
.
1
221
.
1
22
)!1()!1(
)!22(
1
1
n
n
n
h
nb
n
n
nn
n
n
n
§ 2.11 Catalan 数
3.母函数方法设,)( 2432 xhxhhxG
253443524
4
2433424
3
23324
2
:
,:
,:
hhhhhhhhhx
hhhhhhhx
hhhhhx
)
§ 2.11 Catalan 数
.)(
)(
)(
)(
)(1)(
3
4
2
323
3
4
2
322
2
32
2
4
2
323
3
4
2
32
xhxhxhxh
xhxhxhhx
xhxhxh
xhxhxh
xhxhhxxG
即,)]([1)( 2xGxxG,012GxG
§ 2.11 Catalan 数后面将看到只能取 才有意义,
由二项式定理
.2 411 x xG
x
xG
2
411
221
!2
)1
2
1
(
2
1
2
1
1)1( yyy
§ 2.11 Catalan 数
,
!3
)2
2
1
)(1
2
1
(
2
1
3
y
,4
!2
)32(7531
4
!32
311
4
!22
11
21)41(
33
3
22
2
21
kk
k
x
k
k
xxxx
§ 2.11 Catalan 数即 中 项的系数为 21)41( x? 1?nx
)12(531
)!1(
2
2
2
)12(31
)!1(
)1(
)4)(
2
1
()2
2
1
)(1
2
1
(2
)!1(
1
1
22
1
12
1
n
n
n
n
n
n
n
n
n
n
n
§ 2.11 Catalan 数的系数为正，而且得
.
2
1
2
)!)(1(
)!2(2
2
n
n
nnn
n
x
xxG
2
411)(
.
1
221
1
n
n
n
h n
§ 2.11 Catalan 数从递推关系 同样可推出
,1,)64( 21 hhnnh nn
x
xxG
2
411)(
令
)()(
,)(
1
3
4
2
32
2
432
xGxhxhxhxxG
xhxhhxG
§ 2.11 Catalan 数
,0)0(,1)(2)()41(
),(6)]([41)(
)
6343,
6242,
11
'
1
1
'
1
'
1
334
2
223
GxGxGx
xGxxGxG
hhhx
hhhx
，
，
§ 2.11 Catalan 数用 乘等式两端得 3)41(
1
x?
.
412
1
41
)(
,
)41(
1
41
)(
,
)41(
1
)41(
)(2
)(
41
1
1
3
1
33
1'
1
C
xx
xG
xx
xG
dx
d
xx
xG
xG
x
§ 2.11 Catalan 数即
.
2
411
)(
,
2
411
)(
,
2
1
,0)0(,
2
1
41)(
1
11
x
x
xG
x
xG
C
GxCxG
§ 2.11 Catalan 数
4.举例
§ 2.11 Catalan 数图 2-11-4
§ 2.11 Catalan 数例 1.,见图例 2,为 n个数的乘积,依据乘法的结合率,不改变其顺序,
只用括号表示成对的乘积,试问有几种不同的乘法方案?
14
4
8
5
1
6
h
4112
naaaaP?321? naaa,,,21?
§ 2.11 Catalan 数令 表示 n个数乘积的 对括号插入的不同方案数,
令 故得而且 故 即为 Catalan数
np 1?n
.1,21112211 ppppppppp nnnn?
,,,3,2,1,1 nkpp kk
,2311321 hhhhhhhhh nnnnn
.111 nn hh np 1?nh
§ 2.11 Catalan 数以 为例4?n,53
6
4
1
54
hp
4)-11-(2 )).)((())),(((
)),)(((),))(((),))(((
43214321
432143214321
aaaaaaaa
aaaaaaaaaaaa
Catalan数,下面建立 式中不同的乘法顺序和一个 5边形不同拆分的一一对应关系，如图 6112
4p 5h 4)-11-(2
§ 2.11 Catalan 数
2a
)))((( 4321 aaaa
1a 2a 3a 4a
0a
1a 3a
4a
))(( 321 aaa )(
32aa
)))(( ( 4321 aaaa
1a 2a 3a 4a
0a
1a
2a
3a
4a))((
321 aaa
)( 21aa
§ 2.11 Catalan 数
)))((( 4321 aaaa
1a 2a 3a 4a
0a
1a
2a
3a
4a
)( 21aa )( 43aa
)) )((( 4321 aaaa
1a 2a 3a 4a
0a
1a
2a
3a
4a))((
432 aaa )(
43aa
§ 2.11 Catalan 数
)))((( 4321 aaaa
1a 2a 3a 4a
0a
1a
2a
3a
4a))((
432 aaa)(
32aa
图 2-11-6
§ 2.11 Catalan 数运算用二分树表示，两片叶子分别表乘数和被乘数，分支点为运算符,如图
)( ba?
a b
图 2-11-5
ba?
5112
§ 2.11 Catalan 数例 3,n个 1和 n个 0组成一 2n位的 2进制数，要求从左到右扫描,1的累计数不小于 0的累计数，试求满足这条件的数有多少？
下面介绍两种算法。
解法 1,设 为这样所得的数的个数。在 2n
位上填入 n个 1的方案数为,不填 1的其余
np2
n
n2
§ 2.11 Catalan 数
n位自动填以数 0。从 中减去不符合要求的方案数即为所求。不合要求的数指的是从左而右扫描，出现 0的累计数超过 1的累计数的数。
不合要求的数的特征是从左而右扫描时，
必然在某一奇数 位上首先出现
n
n2
12?m 1?m
§ 2.11 Catalan 数个 0的累计数，和 m个 1的累计数。
此后的 位上有 个 1，
个 0。如若把后面这部分位,0与 1交换，使之成为 个 0，
个 1，结果得 1个由 个 0和 个 1组成的 2n位数，即一个不合要求的数对应于一个由 个 0和 个 1组成的一个排列。
1)(2 mn mn?
1 mn 1)(2 mn
mn? 1 mn
1?n 1?n
1?n1?n
§ 2.11 Catalan 数反过来，任何一个由 个 0,个 1组成的 2n位数，由于 0的个数多 2个,2n是偶数，
故必在某一个奇数位上出现 0的累计数超过 1
的累计数。同样在后面的部分，令 0和 1互换，
使之成为由 n个 0和 n个 1组成的 2n位数。即个 0和 个 1组成的 2n位数，必对应于一个不合要求的数。
1?n
1?n 1?n
1?n
§ 2.11 Catalan 数用上述方法建立了由 个 0和 个 1
组成的 2n位数，与由 n个 0和 n个 1组成的 2n位数中从左向右扫描出现 0的累计数超过 1的累计数的数一一对应。
例如 是由 4个 0和 4个 1组成的 8位 2
进制数。但从左而右扫描在第 5位（打 *号）
出现 0的累计数 3超过 1的累计数 2，它对应于
1?n 1?n
* 10100101
§ 2.11 Catalan 数由 3个 1,5个 0组成的 。10100010
反过来 对应于 。
因而不合要求的 2n位数与 个 0，
个 1组成的排列一一对应，故有
* 10100010 10100101
1?n 1?n
)!1()!1(
1
!!
1)!2(
1
22
2 nnnnnn
n
n
n
p n
§ 2.11 Catalan 数
.
2
1
1
!)!1(
)!2(
!)!1(!)!1(
1
)!2(
n
n
n
nn
n
nn
n
nn
n
n
§ 2.11 Catalan 数解法 2.这个问题可以一一对应于图中从原点 到 点的路径要求中途所经过的点 满足关系对应的办法是从 出发，对 2n位数从左而右扫描，若遇到 1便沿 y轴正方向走一格；
若遇到 0便沿 x轴正方向走一格。由于有 n个 0，
n个 1，故对应一条从 点到达 点的路)0,0(
)0,0(
),( nn
)0,0( ),( nn
),( ba
7112
ba?
§ 2.11 Catalan 数径，由于要求 1的累计数不少于 0的累计数，
故可以途经对角线 上的点，但不允许穿越过对角线。反过来，满足这条件的路径对应一满足要求的 2n位 2进制数。见图问题导致求从 出发，途经对角线及对角线上方的点到达 点的路径数。
OA
8112
)0,0(
),( nn
§ 2.11 Catalan 数
x
y
0
1
1
1
1
00
0
0
图 2-11-8
)0,0(O
)1,0('O
B
),( nnA
)1,('?nnA
x
y
图 2-11-7
§ 2.11 Catalan 数从一点到另一点的路径数的讨论见第 1章 § 3
例 1。见图,从 点出发经过 及上方的点到达 点的路径对应一条从点出发经过 及 上方的点到达 点的路径，这是显而易见的。
从 点出发途经 上的点到达 点的路径，故对应一点从 点出发穿越 到达
OA
OA
O
A
''AO ''AO 'O
7112
OA
OAO
'O 'A
'A
§ 2.11 Catalan 数点的路径，故对应一从 点出发穿越 到达点的路径。
所以从 点出发经过 及 以上的点最后到达 点的路径树，等于从 点出发到达 点的所有路径数，减去从 点出发路径上的点到达 点的路径数。即
O OA
A
O OA OA
A
'O'A
OA 'A
§ 2.11 Catalan 数
)!1()!1(
1
!!
1)!2(
1
22
2 nnnnnn
n
n
n
p n
.
2
1
1
!)!1(
)!2(
!)!1(!)!1(
1
)!2(
2?
n
h
n
n
n
nn
n
nn
n
nn
n
n
§ 2.11 Catalan 数例 4,由 n个 1,n个 0组成的 2n位二进制数，要求从左向右扫描前 位时 1的累计数大于 0
的累计数，求满足这样条件的数的个数。此问题可归结为图 中从 点出发只经过对角线 上方的点抵达 点，求这样的路径数。相当于求从 点不经过对角线,
抵达 点的路径数，于是便转换为
12?n
7112 O
OA A
)1,0('O OA
),1(' nnA?
§ 2.11 Catalan 数例 3的问题。
根据例 3的结果。从 点通过 的点，以及 上方的点到达 的路径数为
)1,0('O ''AO
''AO ),1(' nnA?
)!1(!
1
)!22(]
)!2(!
1
)!1()!1(
1
[)!22(
22
1
22
nn
nn
n
nn
nn
n
n
n
n
n
§ 2.11 Catalan 数
.
1
221
1
nh
n
n
n
§ 2.1 母函数递推关系是计数的一个强有力的工具，
特别是在做算法分析时是必需的。递推关系的求解主要是利用母函数。当然母函数尚有其他用处，但这主要是介绍解递推关系上的应用。例如
1)-1-(2
)()(1
)1()1)(1(
21
2
1312121
21
n
n
nnn
n
xaaa
xaaaaaaxaaa
xaxaxa
§ 2.1 母函数项的系数中所有的项包括 n个元素 a1,a2,…an中取 两个 组合的全体；同理项系数包含了从
n个元素 a1,a2,… an中取 3个 元素组合的全体。以此类推。
2x nn aaaaaa 13121
§ 2.1 母函数若令 a1=a2=…=an=1,在（ 2-1-1）式中 项系数,中每一个组合有 1个贡献，其他各项以此类推。
故有：
2x nn aaaaaa 13121
2)-1-(2
),()2,()1,(1)1( 2 nn xnnCxnCxnCx
§ 2.1 母函数另一方面：
nmnm xxx )1()1()1(?
nm
m
m
n
xnmnmC
xnmCnmCx
xmmCxmCmC
xnnCxnCnC
),(
)1,()0,([
]),()1,()0,([
]),()1,()0,([
1
§ 2.1 母函数比较等号两端项对应系数，可得一等式
)0,(),( )1,()1,(
),()0,(),(
nCrmCrnCmC
rnCmCrnmC
§ 2.1 母函数同样对于,
（设 ），用类似的方法可得等式：
mn xx )/11()1( mn?
3)-1-(2 )0,()0,(
)0,()0,()0,()0,(),(
mCnC
mCnCmCnCmnmC
nmmmn xxxx )1()/11()1(?
正法如下：
§ 2.1 母函数比较等式两端的常数项，即得公式 (2-1-3)
nm
m
m
n
xnmnmC
xnmCxnmCnmCx
xmmCxmCmC
xnnCxnCnC
),(
)2,()1,()0,([
]),()1,()0,([
]),()1,()0,([
2
1
§ 2.1 母函数又如等式：
nxnnC
xnCxnCnCx
),(
)2,()1,()0,()1( 2
令 x=1 可得
4)-1-(2
2),()2,()1,()0,( nnnCnCnCnC
§ 2.1 母函数
(2-1-2)式等号的两端对 x求导可得：
5)-1-(2 2
),()3,(3)2,(2)1,(
1
nn
nnnCnCnCnC?
等式 (2-1-5)两端令 x=1,得：
5)-1-(2 2
),()3,(3)2,(2)1,(
1
nn
nnnCnCnCnC?
§ 2.1 母函数用类似的方法还可以得到：
1
32
)1(),(
)3,(3)2,(2)1,(
nn xnxxnnnC
xnCxnCxnC
7)-1-(2 2)1(
),()3,(3)2,(2)1,(
2
222
nnn
nnCnnCnCnC?
定义,对于序列 构造一函数：
§ 2.1 母函数还可以类似地推出一些等式，但通过上面一些例子已可见函数 在研究序列的关系时所起的作用。对其他序列也有同样的结果。现引进母函数概念如下：
nx)1(?
),(,),1,(),0,( nnCnCnC?
,,,,210?aaa
,)( 2210 xaxaaxG
,,,210 aaa称函数 G(x)是序列 的母函数序列 可记为 。
如若已知序列 则对应的母函数 G(x)便可根据定义给出。反之，如若以求得序列的母函数 G(x),则该序列也随之确定。
§ 2.1 母函数例如
n x) 1 (?
),(,),1,(),0,( nnCnCnC?
,,,,210?aaa
,,,,210?aaa }{ na
§ 2.2 递推关系利用递推关系进行计数这个方法在算法分析中经常用到，举例说明如下：
例一,Hanoi问题：这是个组合数学中的著名问题。 N个圆盘依其半径大小，从下而上套在 A柱上，如下图示。每次只允许取一个移到柱 B或 C上，而且不允许大盘放在小盘上方。若要求把柱 A上的 n个盘移到 C柱上请设计一种方法来，并估计要移动几个盘次。现在只有 A,B,C三根柱子可用。
§ 2.2 递推关系
Hanoi问题是个典型的问题，第一步要设计算法，进而估计它的复杂性，集估计工作量。
算法,N=2时第一步先把最上面的一个圆盘套在 B上?第二步把下面的一个圆盘移到 C上最后把 B上的圆盘移到 C上到此转移完毕
A B C
§ 2.2 递推关系
对于一般 n个圆盘的问题，
假定 n-1个盘子的转移算法已经确定。
先把上面的 n-1个圆盘经过 C转移到 B。
第二步把 A下面一个圆盘移到 C上
最后再把 B上的 n-1个圆盘经过 A转移到 C上
A B C
§ 2.2 递推关系上述算法是递归的运用。 n=2时已给出算法； n=3时，第一步便利用算法把上面两个盘移到 B上，第二步再把第三个圆盘转移到柱 C上；最后把柱 B上两个圆盘转移到柱 C上。 N=4,5,…以此类推。
§ 2.2 递推关系算法分析,令 h(n)表示 n个圆盘所需要的转移盘次。根据算法先把前面 n-1个盘子转移到 B上；然后把第 n个盘子转到 C上；最后再一次将 B上的 n-1个盘子转移到 C上。
n=2时，算法是对的，因此,n=3是算法是对的。以此类推。于是有
§ 2.2 递推关系算法复杂度为：
1)-2-(2 1)1(,1)1(2)( hnhnh
,)3()2()1()( 32 xhxhxhxH
H(x)是序列 的母函数。
给定了序列，对应的母函数也确定了。反过来也一样，求得了母函数，对应的序列也就可得而知了。当然，利用递推关系 (2-2-1)式也可以依次求得,这样的连锁反应关系，
叫做递推关系。
),3(),2(),1( hhh
),3(),2( hh
§ 2.2 递推关系下面介绍如何从 (2-2-1)式求得母函数
H(x)的一种形式算法。所谓形式算法说的是假定这些幂级数在作四则运算时，一如有限项的代数式一样。
,)3()2()1()( 32 xhxhxhxH
,)2(2)1(2- )(2 ) xhxhxxH _ _ _ _ _ _ __ _ _ _ _ _ _ _ _ __ _ _ _ _ _ _ _ _ __ _ _ _ _ _ _ _ _ _
3
2
)]2(2)3([
)]1(2)2([)1()()21(
xhh
xhhxhxHx
§ 2.2 递推关系根据 (2-2-1)，
,1)2(2)3(,1)1(2)2(,1)1( hhhhh
)1/()()21( 32 xxxxxxHx
或利用递推关系 (2-2-1)有
1)1(2)2(:2 hhx
1)2(2)3(:3 hhx
)? _ _ _ _ _ _ __ _ _ _ _ _ _ _ _ __ _ _ _ _ _ _ _ _ __ _ _ _ _ _ _ _ _ _
)1/()(2)( 2 xxxxHxxH
§ 2.2 递推关系上式左端为：
xxHxhxHxhxh )()1()()3()2( 32?
右端第一项为：
)(2x
])2()1([2)2(2)1(2 232
xH
xhxhxxhxh
右端第二项为：
)1/(232 xxxx
§ 2.2 递推关系整理得
x
xx
x
xxHx
11
)()21(
2
)21)(1(
)(
xx
xxH
这两种做法得到的结果是一样的。即：
§ 2.2 递推关系令
)21)(1(
2
)21(1(
)1()21(
211
)(
xx
B ) xAB ) - ((A
xx
xBxA
x
B
x
A
xH
xxBABA )2()(
如何从母函数得到序列？下面介绍一种化为部分分数的算法。),2(),1( hh
§ 2.2 递推关系由上式可得：
.1,1 BA
即：
12 BA{
0 BA
1
23322
)12(
)12()12()12(
)1()2221(
1
1
21
1
)(
k
kk
x
xxx
xxxxx
xx
xH
§ 2.2 递推关系因为：
1
)()(
k
kxkhxH
12)( kkh
§ 2.2 递推关系例 2,求 n位十进制数中出现偶数个 5的数的个数。
先从分析 n位十进制数出现偶数个 5的数的结构入手 是 n-1位十进制数，若含有偶数个 5，则 取 5以外的 0,1,2,3,4，
6,7,8,9九个数中的一个，若只有奇数个 5，则取,使成为出现偶数个 5的十进制数。
121?nppp?
1?np
121?nppp?
5?np nn pppp 121
§ 2.2 递推关系解法 1：
令 位十进制数中出现 5的数的个数，
位十进制数中出现奇数个 5的数的个数。
nan?
nbn?
故有：
119 nnn baa
119 nnn abb
{? 1,8 11 ba
)222(
也有类似解释。
§ 2.2 递推关系
(2-2-2)式中的 表达了含有偶数个 5的 n位十进制数的两个组成部分。
表达由含有偶数个 5的 n-1位十进制数
，令 取 5以外的 0,1,2,3,4，
6,7,8,9九个数中的一个数构成的。 项表示当 是含有奇数个 5的 n-1位十进制数，令 而得 是含偶数个
5的 n位十进制数。
119 nnn abb
119 nnn baa
19?na
121?nppp? np
1?nb
121?nppp?
5?np nppp?21
(2-2-2)是关于序列 和 的连立关系。
§ 2.2 递推关系设序列 的母函数为,序列 的母函数为 。
}{ na }{ nb
}{ na )(xA }{ nb
)(xB
2
21
2
21
2
321
2
321
)( )
99)(9
)(
)(
xbxbxxB
xaxaxxA
xbxbbxB
xaxaaxA
即：
_ _ _ _ _ _ _ _ _ __ _ _ _ _ _ _ _ _ __ _ _ _ _ _ _ _ _ _
8)()()91( xxBxAx
§ 2.2 递推关系承前页：
)
9,
9,
9,
334
3
223
2
112
baax
baax
baax
___ _ _ _ _ _ _ _ _ __ _ _ _ _ _ _ _ _ _
)()(98)( xxBxxAxA
8)()()91( xxBxAx
§ 2.2 递推关系又：
___ _ _ _ _ _ _ _ _ __ _ _ _ _ _ _ _ _ _
1)()()91( xxAxBx
故得关于母函数 和 得连立方程组：)(xA )(xB
1)()91()(
8)()()91(
xBxxxA
xxBxAx
{
2
21
2
21
2
321
)( )
99)(9
)(
xaxaxxA
xbxbxxB
xbxbxbxB
§ 2.2 递推关系
x
x
x
x
D
91
91
xx )91( 280181 xx
)101)(81( xx
)101)(81(
871
91
1
8
80181
1)(
2 xx
x
x
x
xx
xA
)101)(81(
1
1
8
91
)101)(81(
1)(
xx
x
x
x
xx
xB
§ 2.2 递推关系
0
)10987(21)101 981 7(21)(
k
kkk x
xxxA
11 10
2
98
2
7 kk
ka
§ 2.2 递推关系解法二：
n-1位的十进制数的全体共 从中去掉含有偶数个 5的数，余下的便是 n-1位中含有奇数个 5的数。故有：
2109 n
1
2
1
11
109
9
n
n
n
nnn
ab
baa
8,1098 121 aaa nnn
§ 2.2 递推关系令
2
21
2
321
88)(8 )
)(
xaxaxxA
xaxaaxA
___ _ _ _ _ _ _ _ _ __ _ _ _ _ _ _ _ _ _
22312 )8()8(8)()81( xaaxaaxAx
§ 2.2 递推关系
x
x
x
x
xxxAx
101
718
101
9
8
10998)()81( 2
0
)10987(
2
1
)
101
9
81
7
(
2
1
)101)(101(
718
)(
k
kkk
x
xxxx
x
xA
11 10
2
98
2
7 kka
1）不出现某特定元素设为,其组合数为,相当于排除 后从中取 r个做允许重复的组合。
§ 2.2 递推关系例三,从 n个元素 中取 r个进行允许重复的组合。假定允许重复的组合数用 表示，其结果可能有以下两种情况。
naaa,,,21?
),( rnC
1a),1( rnC?
1a naa,,2?
§ 2.2 递推关系
2）至少出现一个,取组合数为相当于从 中取 r-1个做允许重复的组合，然后再加上一个 得从 n个元素中取 r个允许重复的组合。
1a )1,(?rnC
1a
naaa,,,21?
依据加法原则可得：
),1()1,(),( rnCrnCrnC
因,故令 1)1,1(,)1,( nnCnnC 1)0,(?nC
§ 2.2 递推关系递推关系 (2-2-3)带有两个参数 n和 r。
xnCxnCxG
xnCxnCxxG
xnCxnCnCxG
n
n
n
)1,1()0,1()( )
)1,()0,( )(
)2,()1,()0,()(
1
2
2
___ _ _ _ _ _ _ _ _ __ _ _ _ _ _ _ _ _ _ )322( 0)()()1(
1 xGxGx nn
§ 2.2 递推关系
(2-2-3)式是关于 的递推关系，但系数 不是常数。但
)(xGn
)1( x?
x
xx
xCxCCxG
1
1
1
)2,1()1,1()0,1()(
2
2
1
n11-n
221
x)-(1
1
)(
x)-(1
1
)(
)1(
1
)(
1
1
)(
xG
xG
x
xG
x
xG
nnn
§ 2.2 递推关系由二项式定理
32 !3 )2)(1(!2 )1(1)1( xnnnxnnnxx
可得
),1(
)!1(
)!1(
!
)1()1(
),(
rrnC
n
rn
r
rnnn
rnC
§ 2.3 母函数的性质
§ 2.3 母函数的性质一个序列和它的母函数一一对应。给了序列便得知它的母函数；反之，求得母函数序列也随之而定。这种关系颇像数学中的积分变换，
特别酷似离散序列的 Z变换。如 § 2的例子所示的那样，为了求满足某种第推关系的序列，可把它转换为求对应的母函数,可能满足一代数方程，或代数方程组，甚至于是微分方程。
)(xG )(xG
§ 2.3 母函数的性质最后求逆变换，即从已求得的母函数得到序列 。关键在于要搭起从序列到母函数，从母函数到序列这两座桥。这一节便是以此为目的的。不特别说明下面假设,
两个序列对应的母函数分别为,
)(xG
}{ na
}{ ka }{ kb
)(xA )(xB
§ 2.3 母函数的性质性质 1：
若 则?kb lk? 0 lka
lk {
)()( xAxxB l?
证：
)(
000)(
1
10
1
1
xAx
xaxa
xbxbxB
l
ll
l
l
l
l
§ 2.3 母函数的性质例,已知 1!3!2!1
32
xexxxxA?
则
)1(!3!2!1)( 1
21
xm
mmm
exxxxxB?
§ 2.3 母函数的性质性质 2,若,lkk ab
则
l
l
k
k
k xxaxAxB /])([)(
1
0
§ 2.3 母函数的性质
l
l
k
k
k
ll
l
l
l
l
l
l
ll
lll
xxaxA
xxaxaxaaxA
xaxaxa
x
xaxaaxB
/])([
/])([
)(
1
)(
1
0
1
1
2
210
2
2
1
1
2
21
证, 2210)( xbxbbxB
§ 2.3 母函数的性质例, !5!3s i n)(
53 xx
xxxA
653
3
/]
!5
1
!3
1
[ s i n
!9
1
!7
1
)(
xxxxx
xxxB
§ 2.3 母函数的性质性质 2,若,则?
k
i
i
k ab
0 x
xAxB
1
)()(
证：
)
,
,
,
:1
210
2101
2
101
00
n
n
aaaabx
aaabx
aabx
ab
§ 2.3 母函数的性质
)
,
,
,
:1
210
2101
2
101
00
n
n
aaaabx
aaabx
aabx
ab
_ _ _ _ _ _ _ __ _ _ _ _ _ _ _ _ __ _ _ _ _ _ _ _ _ _
)1/()()1/(][
)1/()1/()1/()(
2
210
2
210
xxAxxaxaa
xxaxxaxaxB
§ 2.3 母函数的性质例,已知 xxxxxA n 1
11)( 2
2
32
)1(
14321)(
xxxxxB
2
0 )1(
1)1(
x
xk
k
k
§ 2.3 母函数的性质类似可得：
0
3
32
32
32
)1(
1
)2)(1(
2
1
10631
)1(
)4321()(
k
k
x
xkk
xxx
xxx
xxxxC
§ 2.3 母函数的性质性质 2,若 收敛，则?
0k
ka x
xxAAxB
1
)()1()(
)
)1(,
)1(,
)1(:1
1021
2
0211
2100
aaAabx
aAaabx
Aaaab
_ _ _ _ _ _ _ __ _ _ _ _ _ _ _ _ __ _ _ _ _ _ _ _ _ _
)1(
)1(]1)[1()(
22
1
2
0
2
xxxa
xxxaxxAxB
§ 2.3 母函数的性质
x
xxAA
xxxaa
x
A
xB
1
)()1(
)1/()(
1
)1(
)(
10
§ 2.3 母函数的性质性质 5,若,则 。kk kabxxAxB '?
例, xxxxA 1
11 2?
2
32
11
132
x
x
x
xxxx
则
§ 2.3 母函数的性质
k
ab k
k 1
x dxxA
xxB 0
1
性质 5和性质 6的结论是显而易见的。
性质 6,若,则
§ 2.3 母函数的性质性质 7,若则
022110 babababac kkkkk
k
i
ikiba
0
xBxAxcxccxC2210
§ 2.3 母函数的性质证,
。
22100 xbxbbaxC
22101 xbxbbxa
221022 xbxbbxa
22102210 xbxbbxaxaa
xBxAxC
)?
,:1 000 bac?
,:2 01101 babac
,:3 0211202 bababac
___ _ _ _ _ _ _ _ _ __ _ _ _ _ _ _ _ _ _
§ 2.3 母函数的性质例,已知则
,
2
1
321
,
1
32
,
1
1
1
2
32
2
kk
kC
x
x
xxxxB
x
xxxA
k
3
1 x
xxC
§ 2.4 Fibonacci数列
§ 2.4.1 递推关系
Fibonacci数列是递推关系的又一个典型问题，数列的本身有着许多应用。
问题,有雌雄兔子一对，假定过两月便可繁殖雌雄各一的一对小兔。问过了 n个月后共有多少对兔子？
设满 n个月时兔子对数为 其中当月新生兔数目设为 对。第 n-1个月留下的兔子数目设为 对。
nF
nN
nO
nnn ONF
§ 2.4.1 递推关系但 211, nnnnn FONFO
即第 n-2个月的所偶兔子到第 n个月都有繁殖能力了。
)132( 1,2121 FFFFF nnn
由递推关系 (2-3-1)式可依次得到
,523
,3,2
435
324213
FFF
FFFFFF
§ 2.4.2 问题的求解
221)( xFxFxG
)
,
,
234
4
123
3
FFFx
FFFx
_ _ _ _ _ _ _ _ __ _ _ _ _ _ _ _ _ _
)())(()( 22 xGxxxGxxxxG
xxGxx )()1( 2
设
§ 2.4.2 问题的求解承前页
x
B
x
A
xx
x
xx
x
xG
2
51
1
2
51
1
)
2
51
1)(
2
51
1(
1
)(
2
§ 2.4.2 问题的求解承前页
1)(
2
5
0
BA
BA
{ {
5
2
0
BA
BA
5
1,
5
1 BA
§ 2.4.2 问题的求解承前页
])()[(
5
1
]
2
51
1
1
2
51
1
1
[
5
1
)(
222
xx
xx
xG
5
)(F
n
nn
§ 2.4.2 问题的求解其中
2
51
51
2,
2
51
51
2
2)-3-(2 )2 51(51)(51 nnnnF
618.1
2
51
1
n
n
F
F
§ 2.4.3 若干等式
1） 3)-3-(2 1221nn FFFF?
证明：
12
11
342
231
)
nnn
nnn
FFF
FFF
FFF
FFF
_ _ _ __ _ _ _ _ _ _ _ _ __ _ _ _ _ _ _ _ _ _
1 222211 nnn FFFFFF?
§ 2.4.3 若干等式
2） 4)-3-(2 212531 nn FFFFF
证明：
22212
465
243
21
)
nnn
FFF
FFF
FFF
FF
_ _ _ __ _ _ _ _ _ _ _ _ __ _ _ _ _ _ _ _ _ _
nn FFFFF 212531
§ 2.4.3 若干等式
3） 5)-3-(2 122221 nnn FFFFF?
证明：
)( )
)(
)(
1111
2
3243243
2
3
1232132
2
2
12
2
1
nnnnnnnn
FFFFFFFF
FFFFFFFF
FFFFFFFF
FFF
_ _ _ __ _ _ _ _ _ _ _ _ __ _ _ _ _ _ _ _ _ _
122221 nnn FFFFF?
§ 2.4.4 在选优法上的应用设函数 在区间 上有一单峰极值点，假定为极大点。
)( xfy? ),( ba
所谓单峰极值，即只有一个极值点,而且当 x与 偏离越大，偏差 也越大。
如下图：
)()(?fxf?
y
x0?a b
§ 2.4.4 在选优法上的应用设函数 在 点取得极大值。要求用若干次试验找到 点准确到一定的程度。最简单的方法，把 三等分，令：
)(xfx
),( ba
)(32 ),(31 21 abaxabax
如下图,y
x0 a b1x 2x
)( 1xf )( 21xf
)( xfy?
§ 2.4.4 在选优法上的应用依据 的大小分别讨论如下,)(),( 21 xfxf
当,则极大点 必在 区间上，区间 可以舍去。
)()( 21 xfxf ),( 2xa
),( 2 bx
y
x0
)( xfy?
a b1x 2x
)()( 21 xfxf?
y
x0
)( 1xf )( 21xf
a 2x1x
§ 2.4.4 在选优法上的应用当,则极大点 必在 区间上，区间 可以舍去。
)()( 21 xfxf ),( 1 bx
),( 1xa
y
x0
)( xfy?
a b1x 2x
)()( 21 xfxf?
y
x0
)( 1xf )( 2xf
2x1x b
§ 2.4.4 在选优法上的应用当,则极大点 必在 区间上，区间 和 均可以舍去。
)()( 21 xfxf ),( 21 xx
),( 1xa ),( 2 bx
y
x0
)( xfy?
a b1x 2x
)()( 21 xfxf?
y
x0
)( 1xf )( 21xf
2x1x
§ 2.4.4 在选优法上的应用可见做两次试验，至少可把区间缩至原来区间的 2/3，比如,进一步在区间上找极值点。若继续用三等分法，
将面对着这一实事，即其中 点的试验没发挥其作用。为此设想在 区间的两个对称点 分别做试验。
)()( 21 xfxf?
),( 2xa
1x)1,0(
xlx?,
0 xl? x 1
§ 2.4.4 在选优法上的应用设保留 区间，继续在 区间的下面两个点 处做试验，若
),0( x ),0( x
xxx )1(,2?
6)-3-(2 )1(2 xxx
则前一次 的点的试验，这一次可继续使用可节省一次试验。由 (2-3-6)式有
x?1
012 xx
61 8.02 51 x
0 2)618.0(382.0?618.0 1
§ 2.4.4 在选优法上的应用这就是所谓的 0.618优选法。即若在区间上找单峰极大值时，可在
)1,0(
3 8 3 2.06 1 8,01,6 1 8.0 21 xx
点做试验。比如保留区间,由于
，故只要在
)618.0,0(
3 2 8.0)6 1 8.0( 2?
2 3 6.03 2 8.06 1 8.0
点作一次试验。
§ 2.4.4 在选优法上的应用优选法中可利用 Fibonacci数列，和 0.618法不同之点在于它预先确定试验次数，分两种情况介绍其方法。
(a) 所有可能试验数正好是某个 。nF
10 2?nF nF1?nF
§ 2.4.4 在选优法上的应用这时两个试验点放在 和 两个分点上，如果 分点比较好，则舍去小于 的部分；如果 点更好，则舍去大于 的部分。在留下的部分共 个分点，其中第 和第 二试验点，恰好有一个是刚才留下来的试验可以利用。
2?nF1?nF
1?nF 2?nF
2?nF 1?nF
1?nF 2?nF
3?nF
可见在 个可能试验中，最多用 n-1次试验便可得到所求的极值点 n
F
§ 2.4.4 在选优法上的应用
(b)利用 Fibonacci数列进行优选不同于
0.618法之点,还在于它适合于参数只能取整数数值的情况,如若可能试验的数目比 小,
但比 大时,可以虚加几个点凑成 个点，
但新增加的点的试验不必真做，可认定比其他点都差的点来处理。
nF
1?nF nF
§ 2.4.4 在选优法上的应用下面给出两个定理作为这一节的结束。
定理,测试 n次可将包含单峰极值点的区间缩小到原区间的,其中 是任意小的正整数，
1/1 nF?2?n
§ 2.4.4 在选优法上的应用证,对 n用数学归纳法。
n=2时，将区间 平分成 段。在分点（包括端点 a,b） 分别标上 。在 1点的两侧取,在 与 两点上测试，无论哪一点较优，保留下来的区间长度均为,命题成立。
),( ba 212F
2,1,0?
11
1
§ 2.4.4 在选优法上的应用假设对于 n-1,命题成立对于 n,将 平分成 段，对分点（包括端点 a,b） 依次标上 。先在 点与 点测试，无论哪一点较优，保留下来的区间均为 段。根据归纳假设，再做 n-1次测试
（内含前两次测试之一）可将含极值点的区间缩小到 段，即原区间 的 。
),( ba 1?nF
1,,1,0?nF? 1?nF
nF
nF
1 ),( ba1/1 nF
§ 2.4.4 在选优法上的应用因,当 n较大时，可将相继的两个测试点取在待测区间的
0.618及 1-0.618处。由
6 1 8.02/)15(/ 1nn FF
,2,)
2
15(1)
2
15( 1 n
F
n
n
n
可知,0.618法比 法最多多测试一次。 0.618 nF
§ 2.4.4 在选优法上的应用定理,设在给定区间内有单峰极值点。如果包含极值点在内的可测点为 个，则测试 n次必可找到极值点,。
12nF
2?n
证,对 n用数学归纳法。
n=2时，,命题成立 2122F
§ 2.4.4 在选优法上的应用下面证明对 n命题成立。设可测试点的标号依次是 。先在 点及 点测试。无论哪一点较优，保留下来的可测点都为 个。根据归纳假设，再测试 n-1
必可找到极值点。而在保留的 个可测试点中，有一点（ 或 ）的测试结果下一次比较好时正好用上，这样总测试次数为 n。
假设对于 n-1,命题成立
1,,,,,2,1 21 nnn FFF nF
1?nF 1
1nF 1
1nF
nF 1?nF
§ 2.5 线性常系数递推关系
§ 2.5 线性常系数递推关系定义 如果序列 满足na
,02211 knknnn aCaCaCa152
,,,,111100 kk dadada252
及 是常数，,则称为 的 阶常系数线性递推关系，
称为 的初始条件，
kCCC?,,21 110,,?kddd? 0?kC
152 na k
252 na
kkkk CxCxCxxC 111)(?
称为 的特征多项式na
§ 2.5 线性常系数递推关系设 为 的母函数)(xG }{ na
nn xaxaaxG 10)(
根据 (2-5-1)，有
0)(
0)(
0)(
2211
11211
1
02211
knknnn
n
kkkk
k
kkkk
k
aCaCaCax
aCaCaCax
aCaCaCax
§ 2.5 线性常系数递推关系将这些式子两边分别相加，得到
0
1
0
2
0
1
xGxC
xaxGxCxaxG
k
k
k
i
k
i
i
i
i
i
即
1
0
1
0
2
211
k
j
jk
i
i
i
j
j
k
k xaxCxGxCxCxC?
其中 10?C
§ 2.5 线性常系数递推关系令,多项式 的次数不大于 。
特征多项式
1
0
1
0
k
j
jk
i
i
i
j
j xaxCxPxP
1?k
kkk CxCxxC11
§ 2.5 线性常系数递推关系因此,k
k
k xCxC
xCx
11
1
是 次多项式，我们知道 在复数域中有 个根。设
k
k
0?xC
kkkk
axaxaxxC
i
k
i
kk i
21
21
21
§ 2.5 线性常系数递推关系则
ikikk
k
k
k
xaxaxa
xCxC
x
Cx
111
1
1
21
21
1
于是xPxGxCxC kk11
k
k xCxC
xPxG
11
)452( 111 21 21 ikikk xaxaxa
xP
§ 2.5 线性常系数递推关系
(2-5-3)式是有理式，且分子的次数低于分母的次数，有分项表示，即：
t
t
k
t
tk
t
t
t
t
k
k
k
k
x
A
x
A
x
A
x
A
x
A
x
A
x
A
x
A
x
A
xG
)1()1(1
)1()1(1
)1()1(1
)(
2
21
2
2
2
2
22
2
21
1
1
2
1
12
1
11
2
2
1
1
§ 2.5 线性常系数递推关系承上页,)452(
)1(1 1
t
i
k
j
j
i
ij
i
x
A
)(xG
的系数是 。 是常数。
nx
n
i
t
i
k
j
ijn an
nj
Aa
i
1
1 1
ij
A
§ 2.5 线性常系数递推关系定理,设 是有理分式，多项式的次数低于 的次数。则 有分项表示，
且表示唯一
)(
)(
xQ
xP
)(xP
)(xQ )(
)(
xQ
xP
§ 2.5 线性常系数递推关系证明,设 的次数为 n,对 n用数学归纳法。
)(xQ
n=1时,是常数，命题成立。)(xP
假设对小于 n的正整数，命题成立。
下面证明对正整数 n命题成立。设 是的 重根，
)(xQ
k
0)( ),()()( 11 xQxQxxQ k?
§ 2.5 线性常系数递推关系不妨设 与 互素，设)(xP )(xQ
)()(
)(
)()(
)(
1
1
xQx
xP
x
A
xQ
xP
kk
0)(/)(
)()()()(
1
11
xQPA
xPxPxxAQ
)/()]()([)( 11 xxAQxPxP
§ 2.5 线性常系数递推关系的次数低于 。根据归纳假设，)(xP )(xQ
)()(
)(
1
1
xQx
xP
k
可分项表示。因此，
)(
)(
xQ
xP
可分项表示。 由 (2-5-6)式及 (2-5-7)式可知表示是唯一的 。
§ 2.5 线性常系数递推关系以下分别各种情况讨论具体计算的问题。
（ 1）特征多项式 无重根设可见化为
xC
kaxaxaxxC21
452
k
i i
i
k
k
xa
A
xa
A
xa
A
xa
A
xG
1
2
21
1
1
1
111
852
§ 2.5 线性常系数递推关系的系数是nx?
k
i
n
iin aAa
1
952
kAAA,,,21?可由线性方程组
daAaAaA
daAaAaA
dAAA
k
kk
kk
kk
k
11
22
1
11
12211
021
1052
解出。
§ 2.5 线性常系数递推关系的系数矩阵的行列式是 Vander
mond 行列式
1052
11
2
1
1
21
1 1 1
k
k
kk
k
aaa
aaa
1152
ji
ii aa 0
不难看出 有唯一解。?1052
§ 2.5 线性常系数递推关系
（ 2）特征多项式 有共轭复根设 是 的一对共轭复根。21,aa
xC
xC
)s i n(c o s,s i nc o s 121 iaaia
中 的系数是 xa
A
xa
A
2
2
1
1
11?
nx
§ 2.5 线性常系数递推关系
nBnA
nAAinAA
ninAninA
iAiA
AA
nn
nn
nn
nnnn
nn
s i nc o s
s i n)(c o s)(
)s i n( c o s)s i n( c o s
)s i n( c o s)s i n( c o s
2121
21
2
1
1
2211
§ 2.5 线性常系数递推关系其中 )(,2121 AAiBAAA
在具体计算时，可先求出各对共轭复根，再求待定系数 A,B,避免中间过程的复数运算。
（ 3）特征多项式 有重根设 是 的 重根，则 (2-5-4)可简化为? )(xC k
)(xC
k
i
i
i
x
A
1 )1(?
§ 2.5 线性常系数递推关系的系数 。其中nx
n
k
j
jn an
nj
Aa?
1
1
1
11
j
nj
n
nj
是 n的 j-1次多项式。因此,是 与 n的 k-1次多项式的乘积。
na n?
§ 2.5 线性常系数递推关系为了简化计算，下面引入一些记号，介绍几个命题。
设 x是任意变量,n是非负整数，令
n
x
{
,0,1 是当?n
,1,! )1()1( 时当 nn nxxx?
§ 2.5 线性常系数递推关系不难证明，多项式可用 唯一线性表示。其中是常数
0111)( axaxaxaxf nnnn
n
xxx
,
1
,
0 ka
)0( nk
§ 2.5 线性常系数递推关系设 是给定序列，令称为 的 阶差分。
)(,11 nknknnn aaaaa
}{ na
nka? na k
不难证明，如果对任意的 n有,则有
0 nra
0)1(
0
irn
r
i
i a
i
r
因而序列 的特征多项式为}{ na rxxC )1()(
§ 2.5 线性常系数递推关系不难证明，如果 是 n的 r次多项式，则是 n的 r+1次多项式。
na?
na
以上几个命题作为习题，请读者自己证明。
§ 2.5 线性常系数递推关系总之：
(1)若特征多项式 有 n个不同零点则递推关系 (2-5-1)的解
)(xC,,,,
11 naaa?
knnkkk alalala2211
其中 是待定系数，有初始条件
(2-5-2)来确定。
,,,,11 nlll?
§ 2.5 线性常系数递推关系
(2)若特征多项式 有不同的复根，
可依照 (1)的办法处理。不过任意复数可写为 形式，设是 的一个零点，其共轭复根为
)s i n( c o s1 ie i
)(xC bia?
ie
)(xC
)s i n( c o s2 ie i
§ 2.5 线性常系数递推关系
kllikll
kikl
kiklll
kk
k
kkk
s i n)(c o s)(
)s i n( c o s
)s i n( c o s
2121
2
12211
和 仍然是待定常数。即有一对共轭复根 和 时，递推关系 (2-5-1)的解有对应的项
21 ll? )( 21 lli? 0)(?xC
ie?1 ie2
kBkA kk s i nc o s?
其中 A,B是待定常数。
§ 2.5 线性常系数递推关系
(3)若 k重根。不妨设 是 k的重根。
则递推关系 (2-5-1)的解对应于的项为其中 是 k个待定常数。
nkk nAnAA 11110 )(
)(xC 1?
110,,,?kAAA?
§ 2.5 线性常系数递推关系例 1,求下列 n阶行列式 的值。nd
20
01210
00121
00012
n
d
§ 2.5 线性常系数递推关系根据行列式性质
3,2,02 2121 ddddd nnn
对应的特征方程为
1
0)1(12
21
22
mm
mmm
故 是二重根1?m
BnABnAd nn )1)((
§ 2.5 线性常系数递推关系时有1?n 21 BAd
时有2?n 322 BAd
1
32
2
BA
BA
BA
即 1 nd n
§ 2.5 线性常系数递推关系例 2,求?
n
k
n kS
0
1321
1321
1
nS
nnS
n
n
nSS nn 1
同理 121 nSS nn
相减得 12 21 nnn SSS
§ 2.5 线性常系数递推关系同理 12 321 nnn SSS
3,1,0
033
210
321
SSS
SSSS nnnn
对应的特征方程为
0)1(133 323 mmmm
§ 2.5 线性常系数递推关系是三重根1?m
22 )1)(( CnBnACnBnAS nn
0,00 AS
0,11 CBS
0,342,32 CBCBS
即 )1(2
1
2
1
2
1 2 nnnnS
n
)1(21321 nnn?这就证明了
§ 2.5 线性常系数递推关系例 2,求?
n
k
n kS
0
2
222
1
2222
)1(321
)1(321
nS
nnS
n
n
21 nSS nn
同理 221 )1( nSS nn
相减得 122 21 nSSS nnn
§ 2.5 线性常系数递推关系同理 1)1(22 321 nSSS nnn
14,5,1,0
0464
3210
4321
SSSS
SSSSS nnnnn
对应的特征方程为
0)1(1464
01464
4234
234
rrrrr
mmmm
相减得 233 321 nnnn SSSS
同理 233 4321 nnnn SSSS
§ 2.5 线性常系数递推关系是四重根1?r
nn DnCnBnAS )1)(( 32
依据 得关于 A,B、
C,D的连立方程组：
14,5,1,0 3210 SSSS
142793
5842
1
0
DCB
DCB
DCB
A
§ 2.5 线性常系数递推关系
12
2793
842
111
6
1
27914
845
111
2
1
B
§ 2.5 线性常系数递推关系已知 是 n的 3次式，故不妨令nS
)2)(1(!31)1(!21 nnDnnCnBnAS n
确定待定系数时，比较方便，无需解一联立方程组。
例如 0,0 0 ASn 时
1,1,1 1 BBASn 时
3,52,2 2 CCBSn 时
2,1433,3 3 DDCBSn 时
§ 2.5 线性常系数递推关系
)12)(1(
6
1
)2)(1(
3
1
)1(
2
3
nnn
nnnnnnS
n
§ 2.5 线性常系数递推关系例 4,求 333 21 nS n
解,是 n的 3次多项式，因此 是满足递推关系：
31 )1( nSSS nnn
nS
0510105 54321 nnnnnn SSSSSS
设
4321 4321
n
A
n
A
n
A
n
AS n
§ 2.5 线性常系数递推关系
6
,4126741100436
12,
2
3
7313639
7,
1
2
1921
1
4
4
3
4
33
3
3
22
33
2
11
A
AS
AAS
AAS
AS
§ 2.5 线性常系数递推关系
4
6
3
12
2
7
1
nnnn
S n
以 n=5对上面的结果验证一下
2 2 551 0 0 35S
25 53012 0705
4
5
6
3
5
12
2
5
7
1
5
§ 2.5 线性常系数递推关系例 5,求中 的 系数。
)1)(1()1(
1)(
323 xxxxG
nx na
解,的特征多项式是}{ na
)1)(1()1( 23 xxxx
§ 2.5 线性常系数递推关系是 3重根1?x
是 1重根1x
的根是 012 xx
32,1,2 31 3
2
iei
§ 2.5 线性常系数递推关系因此可设
3
2
si n
3
2
c o s
)1(
2
nFE
D
n
CBnAa
n
n
§ 2.5 线性常系数递推关系通过做长除法，求得
876
5432
6542
323
1087
54321
1
1
)1)(1()1(
1
)(
xxx
xxxxx
xxxxx
xxx
xG
§ 2.5 线性常系数递推关系可知
,1,1,1
,1,1,1,1,1,1
876
543210
aaa
aaaaaa
利用 的值解得。
故
543210,,,,,aaaaaa
FEDCBA,,,,,
3
2
si n
3
2
c o s)1(
2
nF
ED
n
CBnAa
n
n
§ 2.5 线性常系数递推关系通过上式，计算得 与用长除法得到的结果相同。
,10,8,7 876 aaa
§ 2.6 整数的拆分和 Ferrers图像
§ 2.6.1 问题举例所谓整数拆分即把整数分解成若干整数的和，相当于把 n个无区别的球放到 n个无标志的盒子，盒子允许空着，也允许放多于一个球。整数拆分成若干整数的和，办法不一，不同拆分法的总数叫做拆分数。
§ 2.6.1 问题举例例 1,若有 1克,2克,3克,4克的砝码各一枚，问能称出那几种重量？有几种可能方案？
10987
65432
74332
432
1
)1)(1(
)1)(1)(1)(1(
xxxx
xxxxxx
xxxxxx
xxxx
§ 2.6.1 问题举例从右端的母函数知可称出从 1克到 10克，
系数便是方案数。例如右端有 项，即称出 5克的方案有 2
52x
41325
同样，
432110
243216
故称出 6克的方案有 2，称出 10克的方案有 1
§ 2.6.1 问题举例例 2,求用 1分,2分,3分的邮票贴出不同数值的方案数。
因邮票允许重复，故母函数为
)1(
)1)(1()(
63
422
xx
xxxxxG
以其中为例，其系数为 4，即 4拆分成 1、
2,3之和的拆分数为 4，即
223121111114
§ 2.6.1 问题举例例 3,若有 1克砝码 3枚,2克砝码 4枚,4
克砝码 2枚的砝码各一枚，问能称出那几种重量？各有几种方案？
§ 2.6.1 问题举例
191817161514
1312111098
765432
841110987
65432
84
864232
2233
445555
4433221
)1)(222
222221(
)1(
)1)(1()(
xxxxxx
xxxxxx
xxxxxxx
xxxxxxx
xxxxxx
xx
xxxxxxxxG
§ 2.6.1 问题举例例 4,整数 n拆分成 1,2,3,…,m的和，
并允许重复，求其母函数。如若其中 m至少出现一次，其母函数如何？
若整数 n拆分成 1,2,3,…,m的和，
并允许重复，其母函数为：
)1(
)1)(1()(
2
422
1
mm xx
xxxxxG
§ 2.6.1 问题举例
)1()1)(1(
1
1
1
1
1
1
1
)1(
)1)(1()(
2
2
2
422
1
m
m
mm
xxx
xxx
xx
xxxxxG
§ 2.6.1 问题举例若拆分中 m至少出现一次，其母函数为：
)1()1)(1(
)(
)1)(1()(
2
2
422
2
m
m
mm
xxx
x
xx
xxxxxG
§ 2.6.1 问题举例显然有
)162(
)1()1)(1(
1
)1()1)(1(
1
)(
12
22
m
m
xxx
xxx
xG
等式 (2-6-1)的组合意义：即整数 n拆分成 1到
m的和的拆分数减去拆分成 1到 m-1的和的拆分数，即为至少出现一个 m的拆分数。
§ 2.6.1 问题举例例 1,若有 1,2,4,8,16,32克的砝码各一枚，问能称出那几种重量？有几种可能方案？
63
0
632
64
32
64
16
32
8
16
4
8
2
42
32
16842
)1(
1
1
1
1
1
1
1
1
1
1
1
1
1
1
)1(
)1)(1)(1)(1)(1( )(
k
k
xxxx
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
xxxxxxG
§ 2.6.1 问题举例从母函数可以得知，用这些砝码可以称出从 1克到 63克的重量，而且办法都是唯一的。
这问题可以推广到证明任一十进制数 n，
可表示为
0,10,2
0
kaan k
k
k
k
而且是唯一的。
§ 2.6.2 拆分数估计式定理,设 为整数 n的拆分数，则np
n
n ep
3
20
证,令 2210)( xpxppxG
一个整数 n拆分成若干整数的和，在拆分中每个整数允许重复出现。故
)1)(1)(1(
1)(
32 xxxxG
§ 2.6.2 拆分数估计式
)1l n (
)1l n ()1l n ()(ln
3
2
x
xxxG
32 3121)1l n ( xxxx
6422 3121)1l n ( xxxx
§ 2.6.2 拆分数估计式
)262(
13
1
12
1
1
)
3
1
2
1
(
)
3
1
2
1
(
)
3
1
2
1
()(ln
3
3
2
2
642
642
32
x
x
x
x
x
x
xxx
xxx
xxxxG
§ 2.6.2 拆分数估计式
12
1
111?
n
n
n
n
xxx
x
x
x
x
x
由于,1 32 nxxxx
11321 nn nxxxxx?
)362( 111 xxnxx n
n
§ 2.6.2 拆分数估计式把 (2-6-3)式代入 (2-6-2)式得
)
3
1
2
1
1(
1
13
1
12
1
1
)(ln
22
22
x
x
x
x
x
x
x
x
xG
由于
2
1
1
2
1
1
4
1
11
2
2
nnn
n
§ 2.6.2 拆分数估计式因而
)46(2
13
5
)(ln
3
5
2
1
2
1
1
3
1
2
1
1
2
1
1
)1(
11
22
22
x
x
xG
n
nn
§ 2.6.2 拆分数估计式设,有 )1,0(?x
)562(
1
ln)(lnln
lnln)(ln
)(
2
210
x
nxGp
xnpxG
xp
xpxpxppxG
n
n
n
n
n
n
§ 2.6.2 拆分数估计式把 (2-6-4)式代入 (2-6-5)式得
)662( 1ln1 2ln xnxxp n
曲线 是上凸，故曲线位于曲线的切线下方，点 的切线为
yz ln? yz ln?
)0,1(
1 yz
故有 1ln yy
§ 2.6.2 拆分数估计式
yz ln?
)0,1(0 x
y
图 (2-6-1)
§ 2.6.2 拆分数估计式
1- 1 1ln xx?
以上式代入 (2-6-5)式得：
)762(
)1(
)1(3
5
)1
1
(
)1(3
5
ln
x
xn
x
x
x
n
x
x
p
n
§ 2.6.2 拆分数估计式不等式 (2-6-7)的左端 是常数，右端是 的函数,即不等式对于 成立。
右端函数取极小值时将给出较好的上界值。
令
nplnx
)1,0(?x
x
xn
x
xy )1(
)1(3
5
求导得
22)1(3
5
x
n
xy
§ 2.6.2 拆分数估计式令,得0y
036)53( 2 nnxxn
解方程，得
53
153
n
nnx
)1,0(53 3,153 153 21 n nxn nnx
§ 2.6.2 拆分数估计式因为 0,2
)1(
1
3
10
233
xyx nxy
所以 是极小值。以 的值代入,得2x 2x y
ny 320?
n
n ep
3
20
§ 2.6.2 拆分数估计式利用,上式可改进为 62
1
2
11 2
22
n
n ep
3
20
§ 2.6.3 Ferrers图像一个从上而下的 n层格子,为第 层的格子数，当,
即上层的格子数不少于下层的格子数时，
称之为 Ferrers图像，如图 (2-6-2)示。
im i )1,2,1(,
1 nimm ii?
图 2-6-2
§ 2.6.3 Ferrers图像
Ferrers图像具有如下性质：
1.每一层至少有一个格子。
2.第一行与第一列互换，第二行于第二列互换,…，即图 (2-6-3)绕虚线轴旋转所得的图仍然是 Ferrers图像。两个 Ferrers
图像称为一对共轭的 Ferrers图像。
§ 2.6.3 Ferrers图像利用 Ferrers图像可得关于整数拆分的十分有趣的结果。
(a)整数 n拆分成 k个数的和的拆分数，
和数 n拆分成个数的和的拆分数相等。
因整数 n拆分成 k个数的和的拆分可用一 k行的图像表示。所得的 Ferrers图像的共轭图像最上面一行有 k个格子。例如：
§ 2.6.3 Ferrers图像
24=6+6+5+4+3
5个数，最大数为 6
24=5+5+5+4+3+2
6个数，最大数为 5
图 (2-6-3)
§ 2.6.3 Ferrers图像
(b)整数 n拆分成最多不超过 m个数的和的拆分数，和 n拆分成最大不超过 m的拆分数相等。
理由和 (a)相类似。
因此，拆分成最多不超过 m个数的和的拆分数的母函数是
)1()1)(1(
1
2 mxxx
§ 2.6.3 Ferrers图像拆分成最多不超过 m-1个数的和的拆分数的母函数是
)1()1)(1(
1
12 mxxx?
所以正好拆分成 m个数的和的拆分数的母函数为
§ 2.6.3 Ferrers图像所以正好拆分成 m个数的和的拆分数的母函数为
)1()1)(1(
)1()1)(1(
1
)1()1)(1(
1
2
12
2
m
m
m
m
xxx
x
xxx
xxx
§ 2.6.3 Ferrers图像
(c)整数 n拆分成互不相同的若干奇数的和的的拆分数,和 n拆分成自共轭的
Ferrers图像的拆分数相等,
设,)12()12()12( 21 knnnn?
其中 。 knnn21
构造一个 Ferrers图像，其第一行，第一列都是 格，对应于,第二行，
第二列各 格，对应于 。以此类推。由此得到的 Ferres图像是共轭的。反过来也一样。
11?n 12 1?n
12?n 12 2?n
§ 2.6.3 Ferrers图像例如 35917
对应为 Ferrers图像为
9+5+3=17
图 (2-6-4)
§ 2.7 指数型母函数
§ 2.7.1 问题提出设有 n个元素，其中元素 重复了 次，
元素 重复了 次,…,重复了 次，
从中取 r个排列，求不同的排列数
1a 1n
2a 2n ka kn
knnnn21
如果,则是一般的排列问题。
121 knnn?
§ 2.7.1 问题提出现在由于出现重复，故不同的排列计数便比较复杂。先考虑 个元素的全排列，
若 个元素没有完全一样的元素，则应有种排列。若考虑 个元素 的全排列数为
，则真正不同的排列数为
n
n !n
in ia!
in
!!!
!
21 knnn
n
§ 2.7.2 解的分析先讨论一个具体问题：若有 8个元素，
其中设 重复 3次,重复 2次,重复 3次。
从中取 r个组合，其组合数为,则序列的母函数为
1a 3a2a
rc
76543210,,,,,,,cccccccc
8765432
325432
32232
369109631
)1( )23321(
)1)(1)(1()(
xxxxxxxx
xxxxxxxx
xxxxxxxxxG
§ 2.7.2 解的分析从 的系数可知，这 8个元素中取 4个组合，其组合数为 10。这 10个组合可从下面展开式中得到
4x
)1(
])()(
)()(1[
)1)(1)(1(
3
3
2
33
2
2
3
1
2
2
2
12
3
1
2
212
2
1
3
1
2
221
2
121
3
3
2
33
2
22
3
1
2
11
xxx
xxxxxxxxxxx
xxxxxx
xxxxxxxx
§ 2.7.2 解的分析
)
()
()
()1( 1
2
2
2
1
3
3
13
2
2132
2
13
3
1
2
3
2
2
2
321
2
3
2
1
3
32
3
31
3
3
2
32
2
313
2
2
3213
2
1
2
212
2
1
3
1
3
332
31
2
221
2
1321
xx
xxxxxxxxxxxxxxx
xxxxxxxxxxxxx
xxxxxxxxxxxxx
xxxxxxxxx
承前页
§ 2.7.2 解的分析其中 4次方项有
)272( 222133132213221
3
3
1
2
3
2
2
2
321
2
3
2
1
3
32
3
31
xxxxxxxxxx
xxxxxxxxxxxxx
(2-7-2)表达了从 8个元素 ( 各 3个,
2个 )中取 4个的组合。例如 为一个,3
个 的组合,为两个,两个 的组合，
以此类推。
31,aa 2a
331xx 1a
3a 2321 xx 3a1a
§ 2.7.2 解的分析若研究从中取 4个的不同排列总数，以对应的两个两个的不同排列为例，其不同排列数为
2321 xx
6!2!2 !4?
即六种。同样,1个 3个的不同排列数为
,3311 aaaa,1331 aaaa,3131 aaaa,1313 aaaa
,1133 aaaa,3113 aaaa 1a
3a 4
!3
!4?
§ 2.7.2 解的分析即以此类推。故从 (2-7-2)式可得问题的解，
其不同的排列数为
,3331 aaaa,1333 aaaa,3133 aaaa,3313 aaaa
70361816
!3!2!2
!3!23!33!2!24
!4)
!2
3
!2!2
3
!3
4
(!4
)
!2!2
1
!1!3
1
!1!2!1
1
!1!1!2
1
!1!3
1
!2!2
1
!2!1!1
1
!2!2
1
!3!1
1
!3!1
1
(!4
§ 2.7.3 指数型母函数为了便于计算，利用上述特点，形式地引进函数
)
!3!2!1
1(
)
!2!1
1)(
!3!2!1
1()(
32
232
xxx
xxxxx
xG
e
§ 2.7.3 指数型母函数
)372(
72
1
72
8
72
35
12
17
12
35
3
14
2
9
31
)
6
1
2
1
1(
)
12
1
12
5
6
7
22(1 )(
876
5432
32
5432
xxx
xxxxx
xxx
xxxxxxG
e
承上页
§ 2.7.3 指数型母函数从 (2-7-3)式计算结果可以得出：取一个的排列数为,取两个的排列数为取 3个的排列数为,取 4个的排列数为,如此等等。把 (2-7-
3)式改写成下面形式便一目了然了 。
3,92/92
283/14!3
7012/35!4
)472(
!8
560
!7
560
!6
350
!5
170
!4
70
!3
28
!2
9
1!
3
1! )(
876
5432
xxx
xxxxxxG
e
§ 2.7.3 指数型母函数定义,对于序列,函数?,,,210 aaa
kk
e
x
k
a
x
a
x
a
x
a
axG
!
!3!21!
)(
33221
0
称为是序列 得指数型母函数?,,,210 aaa
§ 2.7.3 指数型母函数综合上述可得如下两个结论：
(a) 若元素 有 个，元素 有 个，
……，元素 有 个，由此；组成的 n个元素的排列，不同的排列总数为
1a 1n 2a 2n
knka
!!!
!
21 knnn
n
其中 knnnn21
§ 2.7.3 指数型母函数
(b) 若元素 有 个，元素 有 个，
……，元素 有 个，由此；组成的 n个元素中取 r个排列，设其不同的排列数为 。则序列 的指数型母函数为
1a 1n 2a 2n
knka
rp
nppp?,,10
)
!!21!
1( )
!!21!
1(
)
!!21!
1( )(
2
2
2
1
2
2
1
k
nn
n
e
n
xxx
n
xxx
n
xxx
xG
k
§ 2.7.3 指数型母函数与 (2)中所用的方法相比，可以看出指数型母函数在解决有重复元素的排列时的优越性。
§ 2.7.4 举例例 1,求由两个,1个,2个 组成的不同排列总数。
a b c
根据结论一，不同的排列总数为
30!1!2!2 !5n
§ 2.7.4 举例例 2,由 1,2,3,4四个数字组成的五位数中，要求数 1出现次数不超过 2次，但不能不出现； 2出现次数不超过 1次； 3出现次数可达 3次，也可以不出现； 4出现次数为偶数。求满足上述条件的数的个数。
§ 2.7.4 举例设满足上述条件的 r位数为,序列的指数型母函数为
ra
1021,,aaa?
)
144488
1
24
7
3
2
1)(
2
1
2
3
(
)
!4!2
1(
)
!3!2!1
1)(1)(
!21!
( )(
76
54
3232
42
322
xx
xx
xxxxxx
xx
xxx
x
xx
xG
e
§ 2.7.4 举例
10987
65432
288
1
48
1
288
1
48
17
48
43
24
43
3
8
3
2
5
xxxx
xxxxxx
!10
12 60 0
!9
76 50
!8
140
!7
17 85
!6
645
!5
215
!4
64
!3
18
!2
5
!1
10987
65432
xxxx
xxxxxx
由此可见满足条件的 5位数共 215个。
§ 2.7.4 举例例 3,求 1,3,5,7,9五个数字组成的 位数的个数，要求其中 3,7出现的次数为偶数，
其他 1,5,9出现次数不加限制。
设满足条件的 位的个数为,则序列对应的指数型母函数为
r
n
ra
,,,321 aaa
)!3!21()!4!21()(
32
2
42
xxxxxxG e
§ 2.7.4 举例由于 ),!3!21
32
xxxe x
).(21!4!21
42
xx eexx
xxx
xxx
e
eee
eeexG
322
32
)2(
4
1
)(
4
1
)(
§ 2.7.4 举例
).1325(
4
1
.
!
)1325(
4
1
)
!!
3
2
!
5
(
4
1
)2(
4
1
0
0 00
35
nn
n
n
n
n
n
n n
nnn
n
n
n
xxx
a
n
x
n
x
n
x
x
n
eee
§ 2.8 母函数和递推关系应用举例
§ 2.8 母函数和递推关系应用举例例 1,下图是一逻辑回路，符号 D是一延迟装臵，即在时间 t输入一个信号给延迟装臵 D,在 t+1时刻 D将输出同样的信号，符号表示加法装臵?
D D D
输入 u
输出 v
图 2-8-1
§ 2.8 母函数和递推关系应用举例若在 时刻，输入信号求相同时刻的输出信号 。
,2,1,0?t,,,10?uu
,,10 vv
显然，,,,12201100 uuvuuvuv
。,0233 uuuv
一般的有,3,31 nuuuv nnnn
§ 2.8 母函数和递推关系应用举例若信号输入的序列 的母函数为,输出的信号序列 的母函数为,则
,,,10?uu
)(xU,,,10?vv
)(xV
)()()()1()( 3 xUxPxUxxxV
其中 31)( xxxP
被装臵（图 2-8-1）的特性所确定，可以看作是该装臵的传递函数，如图 2-8-2
)(xU )(xV)(xP
§ 2.8 母函数和递推关系应用举例例 2,由红球两个，白球、黄球各一个，
试求有多少种不同的组合方案。
设 r,w,y分别代表红球，白球，黄球。
ywrry wwryr
ywrwryrwyr
ywwyrr
ywrr
222
2
2
2
)(
)()(1
)1)(1(
)1)(1)(1(
§ 2.8 母函数和递推关系应用举例由此可见，出一个球也不取的情况外，有：
（ a） 取一个球的组合数为三，即分别取红，白，黄，三种。
（ b） 取两个球的组合数为四，即两个红的，一红一黄，一红一白，一白一黄。
（ c） 取三个球的组合数为三，即两红一黄，两红一白，一红一黄一白。
（ d） 取四个球的组合数为一，即两红一黄一白。
§ 2.8 母函数和递推关系应用举例令取 r的组合数为,则序列的母函数为
rc 43210,,,,ccccc
432
22
3431
)1)(1()(
xxxx
xxxxG
共有 1+3+4+3+1=12种组合方式。
§ 2.8 母函数和递推关系应用举例例 3,n个完全一样的球放到 m个有标志的盒子中，不允许有空盒，问共有多少种不同的方案？其中 mn?
由于不允许有空盒，令 n个球放到 m个有标志的盒子的方案数为,序列 对应的母函数为 。则
na }{ na)(xG
m
m
x
x
xxxxxxxG
)1(
)())(()( 222
§ 2.8 母函数和递推关系应用举例因
3
2
!3
)2)(1(
!2
)1(
1)1(
x
mmm
x
mm
mxx
m
故二项式 中 项系数为mx )1( mnx?
)!(
)1()1(
)!(
)1()1(
mn
nmm
mn
mnmmm
§ 2.8 母函数和递推关系应用举例即
)1,1(
),1(),1)((
mnC
mnnCmnmnmC
§ 2.8 母函数和递推关系应用举例例 4,某单位有 8个男同志,5个女同志，
现要组织一个有数目为偶数的男同志和数目不少于 2的女同志组成的小组，试求有多少种组成方式。
令 为从 8位男同志中抽取出 n个的允许组合数。由于要男同志的数目必须是偶数，
故
。
na
,28)2,8(,1,0 207531 Caaaaaa
1,28)6,8(,70)4,8( 864 aCaCa
§ 2.8 母函数和递推关系应用举例故数列 对应一母函数 8210,,,,aaaa?
8642 2870281)( xxxxxA
类似的方法可得女同志的允许组合数对应的母函数位
5432 51010)( xxxxxB
§ 2.8 母函数和递推关系应用举例
131211
10987
65432
5432
8642
538
150350630728
8402812851010
)51010(
)2870281(
)()()(
xxx
xxxx
xxxxx
xxxx
xxxx
xBxAxC
§ 2.8 母函数和递推关系应用举例中 项的系数 为符合要求的 个人组成的小组的数目，总的组成方式数目为
)(xC kx kc k
3 3 2 815381 5 03 5 0
6 3 07 2 88 4 02 8 12 8 51010
§ 2.8 母函数和递推关系应用举例例 5,10个数字（ 0到 9）和 4个四则运算符 组成的 14个元素。求由其中的
n个元素的排列构成一算术表达式的个数。
),,,(
因所求的 n个元素的排列是算术表达式，
故从左向右的最后一个符号必然是数字。而第 n-1位有两种可能，一是数字，一是运算符。如若第 n-1位是十个数字之一，则前 n-1
位必然构成一算术表达式。
§ 2.8 母函数和递推关系应用举例如若不然，即第 位是 4个运算符之一，
则前 位必然是算术表达式。根据以上分析，令 表 个元素排列成算术表达式的个数。则
1?n
2?n
na n
.1 2 0,10
1)-8-(2,4010
21
21
aa
aaa nnn
指的是从 0到 99的 100个数，以及1202?a,0?
.9,,1
§ 2.8 母函数和递推关系应用举例利用递推关系,得特征多项式 。它的根是
)182(,2
1
0?a
40102 xx
,)655()655(
.655
nn
n BAa
x
解方程
,10)655()655(
,
2
1
BA
BA
§ 2.8 母函数和递推关系应用举例得
.654/)6515(
,654/)6515(
B
A
].)655)(6515(
)655)(6515[(
654
1
n
n
na
§ 2.8 母函数和递推关系应用举例例 6,设有 n条封闭的曲线，两两相交于两点，任意三条封闭曲线不相交于一点。求这样的 n条曲线把平面分割成几个部分？
设满足条件的 n条封闭曲线所分割成的域的数目为
，其中 条封闭曲线所分割成的域的数目为 图 2-8-3
na 1?n
1?na
§ 2.8 母函数和递推关系应用举例第 n条封闭曲线和这些曲线相交于 个点，这 个点把第 n条封闭曲线截成条弧，每条弧把 个域中的每个域一分为二。故新增加的域数为
)1(2?n
)1(2?n
)1(2?n )1(2?n
).1(2?n
2)-8-(2,2 ),1(2 11 anaa nn
利用递推关系 得 2)-8-(2,20?a
§ 2.8 母函数和递推关系应用举例设
.
2
22
,2,24
,0,22
2
,
2
222
111
00
210
n
a
AAa
AAa
Aa
n
AnAAa
n
n
§ 2.8 母函数和递推关系应用举例另解：利用欧拉公式点数 +域数 -边数 =2
点数 =,
边数 = 点数域数 =
2
2
n
2
.
2
222
2
2
2
4?
nnn
§ 2.8 母函数和递推关系应用举例例 7,平面上有一点 P,它是 n个域的共同交界点，见图 现取 k种颜色对这 n个域进行着色，
要求相邻两个域着的颜色不同。
试求着色的方案数。
令 表示这 n个域的着色方案数。无非有两种情况：
1D
2D
3D
1?nD
nD
P?
图 2-8-4
nDDD,,,21?
482
na
§ 2.8 母函数和递推关系应用举例
（ 1） 和 有相同的颜色；（ 2） 和 所着颜色不同。第一种情形,域有 种颜色可用，即 域所用颜色除外；而且从到 的着色方案，和 个域的着色方案一一对应。后一种 域有 种颜色可供使用；而且从 到 的每一个着色方案和 个域的着色方案一一对应。
1D
1D
1D1D
11,?nDD
1?nD
1?nD1?nD 1?k
2?nD 2?n
nD 2?k
1?n
§ 2.8 母函数和递推关系应用举例利用 得的特征方程为
).2)(1( ),1(
3)-8-(2,)1()2(
32
21
kkkakka
akaka nnn
3)-8-(2
3)-8-(2,,0 01 kaa
.)1()1(
.1,1
,0)1()2(
21
2
nn
n BkAa
xkx
kxkx
§ 2.8 母函数和递推关系应用举例解方程
.0)1(
,
BAk
kBA
)482(
得
,
.2,)1)(1()1(
.1
,1
1
ka
nkka
kB
A
nn
n
§ 2.8 母函数和递推关系应用举例例 8,求下列行列式（ n行 n列 ）
行nd
n
1 1 0 0 0 0
0 0 1 1 1 0
0 0 0 1 1 1
0 0 0 0 1 1
§ 2.8 母函数和递推关系应用举例利用行列式展开法，沿第一行展开得利用 式得
5)-8-(2,0,1,2121 ddddd nnn
5)-8-(2 1,0?d
特征方程是解方程，得
012 xx
.2 31 3 ieix
§ 2.8 母函数和递推关系应用举例设
,3s i n3c o s nBnAd n
解方程
1)
2
3
()
2
1
(
1)
3
0s i n ()
3
0c o s (
BA
BA
§ 2.8 母函数和递推关系应用举例得
.1,
3
s i n
3
1
3
c o s
3
1
1
nnnd
B
A
n
§ 2.8 母函数和递推关系应用举例例 9,求 n位 2进制最后三位出现 010图象的数的个数。
对于 n位 2进制数 从左而右进行扫描，一当出现 010图象，便从这图象后面一位从头开始扫描，例如对 11位 2进制数
00101001010从左而右的扫描结果应该是 2-
4,7-9位出现 010图象，即
nbbb?21
10010100100
§ 2.8 母函数和递推关系应用举例而不是 4-6,7-9位出现的 010图象，即不是为了区别于前者起见，我们说 4-6,9-11
位是 010，但不是“出现 010图象”，这作为约定。
为了找出关于数列 的第推关系，需对满足条件的数的结构进行分析。由于 n位中除了最后三位是 010已确定，其余 位可取 0或 1：
0 1 0010 1 00 0 1
na
3?n
§ 2.8 母函数和递推关系应用举例故最后 3位是 010的 n位 2进制数的个数是 。
其中包含最后 3位出现 010图象的以及在 位到第 位出现 010图象，而在最后 3位并不出现 010图象的两类数，后一种数为
00 1
32?n
4?n
2?n
01010
§ 2.8 母函数和递推关系应用举例故有
2.,1
,5,2
43
3
2
aa
naa nnn
6)-8-(2
利用 推得特征方程为
6)-9-(2,2
1,0,0
012 aaa
.,2
.0)1)(2(
2
3,21
2
i
exx
xx
§ 2.8 母函数和递推关系应用举例设
,2)2s i n ()2c o s ( nn CnBnAa
解方程组
.04
,02
,
2
1
CA
CB
CA
§ 2.8 母函数和递推关系应用举例得
.
10
1
,
5
1
,
5
2
C
B
A
.3,210 1)2s i n (51)2c o s (52 nnna nn
§ 2.8 母函数和递推关系应用举例例 10,求 n位的 2进制数中最后三位才第一次出现 010图象的数的个数。
即求对 n位 2进制数 从左而右扫描，第一次在最后三位出现 010图象的数的个数。自然，最后三位除外任取连续三个都不会是 010的。
设 表满足条件的 n位数个数，和前例类似，最后三位是 010的 n位 2进制数共 个，
nbbb?21
na
32?n
§ 2.8 母函数和递推关系应用举例对这 个数分析如下。
（ a） 包含了在最后三位第 1次出现 010图象的个数，其个数为,排除了在第 到第位第 1次出现 010图象的可能。
（ b）包含了在第 到第 位第 1次出现
010图象的数，其个数为
32?n
na
)4(?n
)4(?n
)2(?n
)2(?n
.2?na
00 1 1 0
§ 2.8 母函数和递推关系应用举例
（ c） 包含了在第 位到第 位第 1
次出现 010图象的数，其个数是,3?na
)5(?n )3(?n
00 1 1 00
§ 2.8 母函数和递推关系应用举例
（ d） 包含了在第 位到第 位第 1
次出现 010图象的数，其个数是,因在第 位（打 *号的格）可以取 0或 1两种状态。
)6(?n )4(?n
42?na
3?n
00 1 1 00?
§ 2.8 母函数和递推关系应用举例一般可以归纳为对,从第 位到第 位第一次出现 010图象的数，其数目为 。从第 位到第 位中间的 位可以取 0,1两种值，故有 种状态。
3?k )2( kn
kn?
knk a32 kn? 3?n3?k
32?k
00 1 1 00
§ 2.8 母函数和递推关系应用举例故得递推关系如下：
7)-8-(2,3,2,1
6,222
543
3
3
6
432
aaa
naaaaa nnnnnn?
时有下面几种状态：
排除了 01010，因从左而右扫描时 01010属于前三位出现 010图象的。
5n?
.11010,10010 00010,
§ 2.8 母函数和递推关系应用举例请注意，递推关系 式不是常系数递推关系。
.3,2,1 543 aaa
7)-8-(2
故 时有时有其它依此类推。
6n?
.58,2 3473346 aaaaaa
7n?
.9216,22 345743457 aaaaaaaa
§ 2.8 母函数和递推关系应用举例令 47362321)( xaxaxxxA
5
3
2
4568
5
4
3457
4
3
346
3
222:
22:
2:
aaaaax
aaaax
aaax
)
.212)()22(
]1)([]321)([
335243
22
xxxAxxx
xAxxxxA
§ 2.8 母函数和递推关系应用举例整理得
.
21
1
21
84412
)(
21
221
.421
21
2
)()
21
1(
32233332
2
333
2
x
x
xxxx
xA
x
xxxx
xx
x
x
xA
x
x
x
§ 2.8 母函数和递推关系应用举例
,49,28,16,9
,5,3,2,1
4928169
5321
21
1
)(
10987
6543
7654
32
32
aaaa
aaaa
xxxx
xx
xxx
xA
§ 2.8 母函数和递推关系应用举例例 11,解图 电路网络中的设其中
582,jv
.,,2,1,0 nj,)( vtv?
2 2 2 2 2 2 2
4 4 4 4 4 4 0v1v2vjv1?jv2?jv1?nv 2?nvnv
2)(tv
§ 2.8 母函数和递推关系应用举例图 根据欧姆定律有
2
1?ji ji jv1?jv2?jv
22
1 4
图 2-8-5
582
.4
,4
1
121
jjj
jjj
vvi
vvi
§ 2.8 母函数和递推关系应用举例由于各点的电流代数和为零，
).(
4
1
)882( ),(
4
1
1
121
jjj
jjj
vvi
vvi
9)-8-(2,21 11 jjj vii
§ 2.8 母函数和递推关系应用举例代入 得递推关系
)1082(,04141 12 jjj vvv
)882( 9)-8-(2
或,2,,2,1,0,04 12 njvvv jjj?
由 点的电流代数和为零，可得
.3
,
2
1
)(
4
1
01
001
vv
vvv
0v
§ 2.8 母函数和递推关系应用举例特征方程是,0142 xx
设解方程组
32x
,)32()32( nnn BAv
.3)32()32(
,
0
0
vBA
vBA
§ 2.8 母函数和递推关系应用举例得
].)32)(31(
)32)(31[(
32
)31(
32
1
)31(
32
1
0
0
0
n
n
n
v
v
vB
vA
§ 2.8 母函数和递推关系应用举例例 12,求图 2-8-6所示的 n级网络的等效电阻 。nR
所谓等效电路，相当于图 2-8-6中虚线所包围的块用一电阻 取代，使在两端点之间的效果一样。
nRn n?
n
n?
R R R R
R R R R
R R R R R R
图 2-8-6
n
n? nR
§ 2.8 母函数和递推关系应用举例可以作为由 等效电阻如图 所示的方式串并联构成的,
1?nR
R
R
R
图 2-8-7
nR 1?nR 782
§ 2.8 母函数和递推关系应用举例得递推关系如下
.
)2(
3
)2(
2
2
111
1
1
1
1
1
n
n
n
n
nn
RRR
RR
RRR
RRR
RRRR
.
4
3
,
11)-8-(2
3
)2(
21
1
1
RRRR
RR
RRR
R
n
n
n
§ 2.8 母函数和递推关系应用举例令
,1,,11 bRa
b
aR
n
n
n,
3
2
3
)2(
11
11
2
1
1
1
1
nn
nn
n
n
n
n
n
n
aRb
RabR
b
a
R
b
a
RR
b
a
因此
§ 2.8 母函数和递推关系应用举例令 )1282(
.3
,2
11
11
2
nnn
nnn
aRbb
RabRa
将 代入得到
11 3 nnn Rbba,2 112 nnn RabRa
.0,4
.04
),3(23
02
1
2
1
11
2
1
bRb
bRRbb
RbbRbRRbb
nnn
nnnnn
§ 2.8 母函数和递推关系应用举例解方程组特征方程是 04 22 RRxx
.])32()32([
,)32(
nnn
n RBAb
Rx
.1)32()32(
,0
RBA
BA
§ 2.8 母函数和递推关系应用举例得
.
32
1
,
32
1
R
B
R
A
nnn
nn
n
n
Rbba
R
b
3
],)32()32[(
32
1
1
§ 2.8 母函数和递推关系应用举例
].)32)(13(
)32)(13[(
32
n
n
nR
,)13(
)32()32(
)32)(13()32)(13(
RR
b
a
n
nn
nn
n
n
§ 2.8 母函数和递推关系应用举例例 13,设有地址从 1到 n的单元，用以纪录一组信息。这个信息的每个元素都占用两个单元，而且存放的地址是完全随机的，因而可能出现两个存放信息单元之间留下一个空单元无法存放其他信息，求这 n各单元留下空单元的平均数。
§ 2.8 母函数和递推关系应用举例设这个平均数为 。na
1 2 i+1 i+2 n-1 n
存储单元如上图，设某一信息占用了第 i+1，
i+2两个单元，把这组单元分割成两个部分，
一是从 1到 i,另一从 i+3到 n。 由于用相邻两个单元的几率相等，
§ 2.8 母函数和递推关系应用举例
)],(
)()[(
1
1
02
3120
aa
aaaa
n
a
n
nnn
2
0
)1382( 2)1(
n
k
kn aan
（ 2-8-13）式是变系数递推关系，可改为
.0,1,0
,02)2()1(
210
21
aaa
aanan nnn
§ 2.8 母函数和递推关系应用举例设
,432)(
,)(
3
5
2
43
4
5
3
4
2
31
xaxaxaxG
xaxaxaaxG
)
,234,
,223,
,22,
345
3
234
2
123
aaax
aaax
aaax
___ _ _ _ _ _ _ _ _ __ _ _ _ _ _ _ _ _ _
.2)( xGGxxG
§ 2.8 母函数和递推关系应用举例
,2)1( xGGx
,1 221 2 xxxGG
,)1l n (2ln 2 CxxG
22 )1( xkeG x
.1,110 kaG x
§ 2.8 母函数和递推关系应用举例
5432
32
22
15
4
3
2
1
]
!3
)2(
!2
)2(
21[
)1(
xxxx
xx
x
xeG
x
§ 2.8 母函数和递推关系应用举例
.
!
)1(2
)1(
!
2
)1(
)2(
!3
2
)1(
!2
2
2)1(
0
32
1
k
kn
n
nnnna
kn
k
k
n
n
n
一般有
§ 2.9 排错问题
§ 2.9 排错问题
n个有序的元素应有 个不同的排列，
如若一个排列使得所有的元素在原来的位臵上，则称这个排列为错排；有的叫重排。
以 1,2,3,4四个数的错排为例，分析其结构，找出规律性的东西来。
!n
§ 2.9 排错问题即 12 3 2 1 33 13 2
1 2的错排是唯一的，即 2 1。
1 2 3的错排有 3 1 2,2 3 1。 这二者可以看作是 1 2错排,3分别与 1,2换位而得的。
§ 2.9 排错问题
1 2 3 4的错排有
4 3 2 1,4 1 2 3,4 3 1 2，
3 4 1 2,3 4 2 1,2 4 1 3，
2 1 4 3,3 1 4 2,2 3 4 1。
第一列是 4分别与 1,2,3互换位臵，其余两个元素错排，由此生成的。
§ 2.9 排错问题第 2列是 4分别与 3,1,2（ 123的一个错排）的每一个数互换而得到的。即
3 42 14 3 2 3 4 1 1 4
1 3 4 2 24
§ 2.9 排错问题第三列则是由另一个错排 231和 4换位而得到，即
1 3 4 2 24 1 2 4 3 3 4
3 2 4 1 14
§ 2.9 排错问题上面的分析结果，实际上是给出一种产生错排的结果。
设 n个数 1,2,…,n错排的数目为,
任取其中一数,数 分别与其他的 n-1个数之一互换，其余 n-2个数进行错排，共得个错排。另一部分位数 以外的
n-1个数进行错排，然后 与其中每个数互换得 个错排。
nDi i
2)1( nDn ii
1)1( nDn
§ 2.9 排错问题综合以上分析结果得递推关系
.1
1)-9-(2,1,0
),)(1(
0
21
21
D
DD
DDnD nnn
§ 2.9 排错问题
（ 2-9-1）是一非常系数的递推关系，下面提供一种解法。
)()1(
])2([)1(
])1([
01
1
32
2
211
DD
DnD
DnDnDD
n
nn
nnnn
由于 故得关于 得递推关系
,1,0 01 DD nD
)292(,)1(1 nnn nDD
§ 2.9 排错问题令
3322
10 !3!2)( x
DxDxDDxG
e
)1(
)1(
)1(
3
23
2
12
1
01
DD
DD
DD
§ 2.9 排错问题可得 x
ee exxGxG )()(
!)
!
1
!2
1
11(
).1/()
!2
1(
1
)(
`2
n
n
D
x
x
x
x
e
xG
n
x
e
§ 2.10 Stirling数
§ 2.10 Stirling数前面见到的递推关系都是一个参数的。 St
irling数问题则不然。它导出的递推关系式是两个参数的。
（ 1）多项式系数
n个有区别的球放到两个有区别的盒子里，
若要求第 1个盒子放 k个球，第二个盒子放 n-k
个球 方案数应是 中 ),,,2,1,0( nk nxx )( 21?
§ 2.10 Stirling数项的系数 依据加法法则有可把上面的讨论推广到 n个有区别的球放到 m
个有区别的盒子里，要求 m个盒子放的球数分别是 的情况，
其不同方案数用
knk xx?21 ).,( knC
.2),()1,()0,( nnnCnCnC
)(,,,2121 mm nnnnnnn
§ 2.10 Stirling数表示。
从 n个有区别的球中取出 个放到第 1个盒子里去，其选取方案数为 ；当第 1个盒子的 个球选定后，第 2个盒子里的 个
mnnn
n
21
1n
1n
n
2n 3n
§ 2.10 Stirling数球则是从 个中选取的，其方案数应为；第 3个盒子的 个球则是从中选取，其方案数为 ；依此类推，
根据乘法法则可得
1nn?
2
1
n
nn
21 nnn
3
21
n
nnn3n
§ 2.10 Stirling数
m
m
m
n
nnnn
n
nnn
n
nn
n
n
nnn
n
121
3
21
2
1
121
§ 2.10 Stirling数
.
!!!
!
!0!
!
)!(!
)!(
)!(!
)!(
)!(!
!
21
3213
21
212
1
11
mm
m
nnn
n
n
n
nnnnn
nnn
nnnn
nn
nnn
n
§ 2.10 Stirling数
n个有区别的球，放到 m个有标志的盒子的问题，也可以考虑把 n个有区别的球进行全排列。对于每一个排列依次取 个放到第 1个盒子里，取 个放到第 2个盒子里,…，最后个放到第 m个盒子里。然而，放到盒子里的球不考虑球的顺序，故得不同的方案数为
1n
2n 3n
§ 2.10 Stirling数结果和 式一致。
称 为多项式系数。
.
!!!
!
21 mnnn
n
mnnn
n
21
)1102(
§ 2.10 Stirling数
2)-10-(2 )(
)(
)()(
21
21
2121
m
m
m
n
m
xxx
xxx
xxxxxx
多项式 的展开式是由式右端的 n项中，每项各取一个元素相乘而得到的。
nmxxx )( 21
2)-10-(2
§ 2.10 Stirling数表达式 中共有 n个因子项，令第 i
个因子项对应于第 i个有标志的球，从第 i个因子项中取 对应于把第 i个有标志的球放到第 i个盒子。 式展开的一般项表示第一个盒子有 个球，第二个盒子有个球，等等。因此 式中
2)-10-(2
2)-10-(2
2)-10-(2
)( 2121 21 nnnnxxx mnmnn m
1n 2n
mnmnn xxx?21 21
§ 2.10 Stirling数项的系数应为
mnnn
n
21
即
)3102(,
)(
21
21
21
21
21
m
m
n
m
nn
nnnn m
n
m
xxx
nnn
n
xxx
§ 2.10 Stirling数定理,展开式的项数等于
，而且这些系数之和等于证明,展开式中的项 和从 m个元素 中取 n个作允许重复的组合一一对应。故得 展开式的
nmxxx )( 21
mnmnn xxx?21 21 )( 21 nnnn m
mxxx,,,21?
nmxxx )( 21
nmxxx )( 21
,
1
n
mn
nm
§ 2.10 Stirling数项数等于 。从 m个中取 n个作允许重复的组合的全体，对于每个球都有 m个盒子可供选择，根据乘法法则有 4)-10-(2,
21 21
n
nnnn m
m
nnn
n
m
n
mn 1
§ 2.10 Stirling数
(2)Stirling数只准备讨论其中的第二类 Stirling数,至于第一类的 Stirling数只准备给出它的定义和递推关系,
定义,
.),(
)2,()1,()0,(
)1()2)(1(][
2
n
n
xnns
xnsxnsns
nxxxxx
§ 2.10 Stirling数称 为第一类 Stirling数 ),(,),1,(),0,( nnsnsns
,)1,1(
)1,1()0,1(
)](),()1,()0,([][
1
1
n
n
n
xnns
xnsns
nxxnnsxnsnsx
显然有
)5102( ).,()1,(),1( knnsknskns
§ 2.10 Stirling数定义,n个有区别的球放到 m个相同的盒子中,要求无一空盒,其不同的方案数用表示,称为第二类 Stirling数,
例如红,黄,蓝,白四种颜色的球,放到两个无区别的盒子里,不允许有空盒,其方案有如下七种,
),( mnS
§ 2.10 Stirling数其中 r表红球,y表黄球,b表蓝球,w表白球,
1 2 3 4 5 6 7
第 1 盒子 r y b w ry rb Rw
第 2 盒子 ybw r b w r y w r y b bw yw yb
.7)2,4( S
§ 2.10 Stirling数定理,第二类 Stirling数 有下列性质,
),( knS
.1),( )(
),2,()1,( )(,12)2,( )(
,1)1,( )(,0)0,( )(
1
nnSe
nCnnSdnSc
nSbnSa
n
证明,公式 (a),(b),(e)是显然的,只证 (c),
(d).
§ 2.10 Stirling数
(c)设有 n个不相同的球 从中取出球,其余的 个球,每个都有与 同盒
,或不与 同盒两种选择,但必须排除一种情况,即全体与 同盒,因这时另一盒将是空盒,
故实际上只有 种方案,
即 12)2,(
1nnS
,,,,,321 nbbbb?
1b 1?n
12 1n
1b
1b
§ 2.10 Stirling数
(d)n个球放到 个盒子里,不允许有一空盒,故必有一盒有两个球,从 n个有区别的球中取 2个共有 种组合方案,
定理,第二类 Stirling数满足下面的递推关系,
1?n
)2,(nC
).1,1(
)6102(),1,1(),1(),(
mn
mnSmnmSmnS
§ 2.10 Stirling数证明,设有 n个有区别的球 从中取一个球设为,把 n个球放到 m个盒子无一空盒的方案的全体可分为两类。
（ a） 独占一盒，其方案数显然为
（ b） 不独占一盒，这相当于先将剩下的 个球放到 m个盒子，不允许空盒，共
,,,,21 nbbb?
1b
).1,1( mnS1
b
1b
1?n
§ 2.10 Stirling数共有 种不同方案，然后将 球放进其中一盒，从乘法法则得 不独占一盒的方案数应为
),1( mnS?
).,1( mnmS?
1b
1b
根据加法法则有上面证明递推公式 的过程，
也就是给出构造所有方案的办法。例如今将
).,1()1,1(),( mnmSmnSmnS
)6102(
§ 2.10 Stirling数红、黄、蓝、白、绿五个球放到无区别的两个盒子里。
故共有 15种不同的方案。
先把绿球取走，余下的四个球放到两个盒子的方案已见前面的例子。和前面一样用
r,y,b,w分别表示红，黄，蓝，白球，绿球用 g表示，故得表
,15172)1,4()2,4(2)2,5( SSS
1102
§ 2.10 Stirling数
g 不独占一盒 g 独占一盒第 1 盒子 第 2 盒子 第 1 盒子 第 2 盒子 第 1 盒子 第 2 盒子
rg
yg
bg
wg
r yg
r bg
r w g
ybw
r bw
r yw
r yb
bw
yw
yb
r
y
b
w
ry
rb
rw
yb w g
r bw g
r yw g
r yb g
bw g
yw g
ybg
g r yb w
表 2-10-1
§ 2.10 Stirling数
n个球放到 m个盒子里，依球和盒子是否有区别？是否允许空盒？共有 种状态。
其方案计数分别列于下表 。
823?
n个球有区别,m个盒子有区别，有空盒时方案计数为 nm
n个球有区别,m个盒子有区别，无空盒时方案计数为 ),(! mnSm
§ 2.10 Stirling数
n个球有区别,m个盒子无区别，有空盒时方案计数为
mn
nnSnSnS
mn
mnSnSnS
),,()2,()1,(
),,()2,()1,(
§ 2.10 Stirling数
n个球有区别,m个盒子无区别，无空盒时方案计数为 ),( nnS
n个球无区别,m个盒子有区别，有空盒时方案计数为 ),1( nmnC
§ 2.10 Stirling数
n个球无区别,m个盒子有区别，无空盒时方案计数为
)1,1(
),1(
),1)((
mnC
mnnC
mnmnnC
§ 2.10 Stirling数
n个球无区别,m个盒子无区别，有空盒时方案计数为
)1()1)(1(
1
)( 2 m
xxx
xG
的 项系数。nx
§ 2.10 Stirling数
n个球无区别,m个盒子无区别，无空盒时方案计数为
)1()1)(1(
)(
2 m
m
xxx
x
xG
的 项系数。nx
§ 2.10 Stirling数利用
，还可以如 Pascal三角形一样得到表 2-10-3。 表 2-10-3见书 119页。
),,1()1,1(),( mnmSmnSmnS
1),()1,( nnSnS
§ 2.11 Catalan 数
§ 2.11 Catalan 数这一节讨论 Catalan数,其递推关系是非线性的,许多有意义的计数问题都导致这样的递推关系,本节将举出一些,后面还将见到,
一个凸 n边形,通过不相交于 n边形的对角线,把 n边形拆分成若干三角形,不同拆分的数目用 表之,
nh
§ 2.11 Catalan 数例如五边形有如下五种拆分方案，故,5?nh
图 2-11-1
§ 2.11 Catalan 数
1.递推关系定理：
)2112( ),
(
2
)3( )(
)1112(,)(
3142
2413
21321
hhhh
hhhh
n
hnb
hhhhhhha
nn
nnn
nnnn
§ 2.11 Catalan 数证明,的证明：
如图 所示，
以 作为一个边的三角形,
将凸 边形分割成两部分，一部分是边形，
1v
2v
3v
kv
nv
1?nv
边形k
边形2 kn
图 2-11-2
)(a
1112
11?nvv
1?n
11?nkvvv
k
§ 2.11 Catalan 数另一部分是 边形,即点可以是 点中任意一点。依据加法法则有
2 kn,,,3,2 nk kv
nvvv,,,32?
,231132
2
21
hhhhhhhh
hhh
nnnn
n
k
knkn
§ 2.11 Catalan 数的证明：
如图 所示，
从 点向其它 个顶点可引出 条对角线。
对角线 把 边形分割成两个部分，因此
1v
2v
kv
nv
边形k
边形2 kn
图 2-11-3
)(b
3112
1v 3?n
},,,{ 143?nvvv?
kvv1
3?n
n
§ 2.11 Catalan 数以 对角线作为拆分线的方案数为可以是 中任一点，对所有这些点求和得以 取代 点也有类似的结果。但考虑到对角线有两个顶点，同一对角线在两个顶点分别计算了一次，
kvv1 2knk hh
kv 143,,,?nvvv?
.31422413 hhhhhhhh nnnn
nvvv,,,32? 1v
§ 2.11 Catalan 数作
)3112(),(2 31422413 hhhhhhhhn nnnn?
式并不就给出剖分数，无疑其中是有重复的。其重复度是由于一个凸 边形的剖分有 条对角线，而对其每一条边计数时该剖分都计数了一次，故重复了次即 式给出的结果是 的 倍。
)3112(
3?n
3?n
n
3112 nh 3?n
§ 2.11 Catalan 数式和 式都是非线性的递推关系。
),
(
2
)3(
3142
2413
hhhh
hhhh
n
hn
nn
nnn
)1112( )2112(
§ 2.11 Catalan 数
2.Catalan 数计算公式由 式及,故得)1112( 12?h
)2(
2
)(
2
)3(
.2
1
312413
314224131
nn
nnnn
nnnnnn
hh
n
hhhhhh
n
hn
hhhhhhhhhh
§ 2.11 Catalan 数由整理得令
),2(2)3( 1 nnn hhnhn
.2)3(2 1 nnn nhnhhn
.)64( 1 nn hnnh
,11 nn nhf
.
)1)(1(
)32)(22(
1
)3(2
1
)64(
1
n
n
n
n
f
nn
nn
f
n
n
n
f
nf
§ 2.11 Catalan 数即,1,)1)(1(
)32)(22(
22
1
hf
nn
nn
f
f
n
n
11
22
22
34
)2)(2(
)52)(42(
)1)(1(
)32)(22(
2
3
3
4
2
1
1
1
1
nn
nn
nn
nn
f
f
f
f
f
f
f
f
f
f
f
n
n
n
n
n
n
n
§ 2.11 Catalan 数
.
1
221
.
1
22
)!1()!1(
)!22(
1
1
n
n
n
h
nb
n
n
nn
n
n
n
§ 2.11 Catalan 数
3.母函数方法设,)( 2432 xhxhhxG
253443524
4
2433424
3
23324
2
:
,:
,:
hhhhhhhhhx
hhhhhhhx
hhhhhx
)
§ 2.11 Catalan 数
.)(
)(
)(
)(
)(1)(
3
4
2
323
3
4
2
322
2
32
2
4
2
323
3
4
2
32
xhxhxhxh
xhxhxhhx
xhxhxh
xhxhxh
xhxhhxxG
即,)]([1)( 2xGxxG,012GxG
§ 2.11 Catalan 数后面将看到只能取 才有意义,
由二项式定理
.2 411 x xG
x
xG
2
411
221
!2
)1
2
1
(
2
1
2
1
1)1( yyy
§ 2.11 Catalan 数
,
!3
)2
2
1
)(1
2
1
(
2
1
3
y
,4
!2
)32(7531
4
!32
311
4
!22
11
21)41(
33
3
22
2
21
kk
k
x
k
k
xxxx
§ 2.11 Catalan 数即 中 项的系数为 21)41( x? 1?nx
)12(531
)!1(
2
2
2
)12(31
)!1(
)1(
)4)(
2
1
()2
2
1
)(1
2
1
(2
)!1(
1
1
22
1
12
1
n
n
n
n
n
n
n
n
n
n
n
§ 2.11 Catalan 数的系数为正，而且得
.
2
1
2
)!)(1(
)!2(2
2
n
n
nnn
n
x
xxG
2
411)(
.
1
221
1
n
n
n
h n
§ 2.11 Catalan 数从递推关系 同样可推出
,1,)64( 21 hhnnh nn
x
xxG
2
411)(
令
)()(
,)(
1
3
4
2
32
2
432
xGxhxhxhxxG
xhxhhxG
§ 2.11 Catalan 数
,0)0(,1)(2)()41(
),(6)]([41)(
)
6343,
6242,
11
'
1
1
'
1
'
1
334
2
223
GxGxGx
xGxxGxG
hhhx
hhhx
，
，
§ 2.11 Catalan 数用 乘等式两端得 3)41(
1
x?
.
412
1
41
)(
,
)41(
1
41
)(
,
)41(
1
)41(
)(2
)(
41
1
1
3
1
33
1'
1
C
xx
xG
xx
xG
dx
d
xx
xG
xG
x
§ 2.11 Catalan 数即
.
2
411
)(
,
2
411
)(
,
2
1
,0)0(,
2
1
41)(
1
11
x
x
xG
x
xG
C
GxCxG
§ 2.11 Catalan 数
4.举例
§ 2.11 Catalan 数图 2-11-4
§ 2.11 Catalan 数例 1.,见图例 2,为 n个数的乘积,依据乘法的结合率,不改变其顺序,
只用括号表示成对的乘积,试问有几种不同的乘法方案?
14
4
8
5
1
6
h
4112
naaaaP?321? naaa,,,21?
§ 2.11 Catalan 数令 表示 n个数乘积的 对括号插入的不同方案数,
令 故得而且 故 即为 Catalan数
np 1?n
.1,21112211 ppppppppp nnnn?
,,,3,2,1,1 nkpp kk
,2311321 hhhhhhhhh nnnnn
.111 nn hh np 1?nh
§ 2.11 Catalan 数以 为例4?n,53
6
4
1
54
hp
4)-11-(2 )).)((())),(((
)),)(((),))(((),))(((
43214321
432143214321
aaaaaaaa
aaaaaaaaaaaa
Catalan数,下面建立 式中不同的乘法顺序和一个 5边形不同拆分的一一对应关系，如图 6112
4p 5h 4)-11-(2
§ 2.11 Catalan 数
2a
)))((( 4321 aaaa
1a 2a 3a 4a
0a
1a 3a
4a
))(( 321 aaa )(
32aa
)))(( ( 4321 aaaa
1a 2a 3a 4a
0a
1a
2a
3a
4a))((
321 aaa
)( 21aa
§ 2.11 Catalan 数
)))((( 4321 aaaa
1a 2a 3a 4a
0a
1a
2a
3a
4a
)( 21aa )( 43aa
)) )((( 4321 aaaa
1a 2a 3a 4a
0a
1a
2a
3a
4a))((
432 aaa )(
43aa
§ 2.11 Catalan 数
)))((( 4321 aaaa
1a 2a 3a 4a
0a
1a
2a
3a
4a))((
432 aaa)(
32aa
图 2-11-6
§ 2.11 Catalan 数运算用二分树表示，两片叶子分别表乘数和被乘数，分支点为运算符,如图
)( ba?
a b
图 2-11-5
ba?
5112
§ 2.11 Catalan 数例 3,n个 1和 n个 0组成一 2n位的 2进制数，要求从左到右扫描,1的累计数不小于 0的累计数，试求满足这条件的数有多少？
下面介绍两种算法。
解法 1,设 为这样所得的数的个数。在 2n
位上填入 n个 1的方案数为,不填 1的其余
np2
n
n2
§ 2.11 Catalan 数
n位自动填以数 0。从 中减去不符合要求的方案数即为所求。不合要求的数指的是从左而右扫描，出现 0的累计数超过 1的累计数的数。
不合要求的数的特征是从左而右扫描时，
必然在某一奇数 位上首先出现
n
n2
12?m 1?m
§ 2.11 Catalan 数个 0的累计数，和 m个 1的累计数。
此后的 位上有 个 1，
个 0。如若把后面这部分位,0与 1交换，使之成为 个 0，
个 1，结果得 1个由 个 0和 个 1组成的 2n位数，即一个不合要求的数对应于一个由 个 0和 个 1组成的一个排列。
1)(2 mn mn?
1 mn 1)(2 mn
mn? 1 mn
1?n 1?n
1?n1?n
§ 2.11 Catalan 数反过来，任何一个由 个 0,个 1组成的 2n位数，由于 0的个数多 2个,2n是偶数，
故必在某一个奇数位上出现 0的累计数超过 1
的累计数。同样在后面的部分，令 0和 1互换，
使之成为由 n个 0和 n个 1组成的 2n位数。即个 0和 个 1组成的 2n位数，必对应于一个不合要求的数。
1?n
1?n 1?n
1?n
§ 2.11 Catalan 数用上述方法建立了由 个 0和 个 1
组成的 2n位数，与由 n个 0和 n个 1组成的 2n位数中从左向右扫描出现 0的累计数超过 1的累计数的数一一对应。
例如 是由 4个 0和 4个 1组成的 8位 2
进制数。但从左而右扫描在第 5位（打 *号）
出现 0的累计数 3超过 1的累计数 2，它对应于
1?n 1?n
* 10100101
§ 2.11 Catalan 数由 3个 1,5个 0组成的 。10100010
反过来 对应于 。
因而不合要求的 2n位数与 个 0，
个 1组成的排列一一对应，故有
* 10100010 10100101
1?n 1?n
)!1()!1(
1
!!
1)!2(
1
22
2 nnnnnn
n
n
n
p n
§ 2.11 Catalan 数
.
2
1
1
!)!1(
)!2(
!)!1(!)!1(
1
)!2(
n
n
n
nn
n
nn
n
nn
n
n
§ 2.11 Catalan 数解法 2.这个问题可以一一对应于图中从原点 到 点的路径要求中途所经过的点 满足关系对应的办法是从 出发，对 2n位数从左而右扫描，若遇到 1便沿 y轴正方向走一格；
若遇到 0便沿 x轴正方向走一格。由于有 n个 0，
n个 1，故对应一条从 点到达 点的路)0,0(
)0,0(
),( nn
)0,0( ),( nn
),( ba
7112
ba?
§ 2.11 Catalan 数径，由于要求 1的累计数不少于 0的累计数，
故可以途经对角线 上的点，但不允许穿越过对角线。反过来，满足这条件的路径对应一满足要求的 2n位 2进制数。见图问题导致求从 出发，途经对角线及对角线上方的点到达 点的路径数。
OA
8112
)0,0(
),( nn
§ 2.11 Catalan 数
x
y
0
1
1
1
1
00
0
0
图 2-11-8
)0,0(O
)1,0('O
B
),( nnA
)1,('?nnA
x
y
图 2-11-7
§ 2.11 Catalan 数从一点到另一点的路径数的讨论见第 1章 § 3
例 1。见图,从 点出发经过 及上方的点到达 点的路径对应一条从点出发经过 及 上方的点到达 点的路径，这是显而易见的。
从 点出发途经 上的点到达 点的路径，故对应一点从 点出发穿越 到达
OA
OA
O
A
''AO ''AO 'O
7112
OA
OAO
'O 'A
'A
§ 2.11 Catalan 数点的路径，故对应一从 点出发穿越 到达点的路径。
所以从 点出发经过 及 以上的点最后到达 点的路径树，等于从 点出发到达 点的所有路径数，减去从 点出发路径上的点到达 点的路径数。即
O OA
A
O OA OA
A
'O'A
OA 'A
§ 2.11 Catalan 数
)!1()!1(
1
!!
1)!2(
1
22
2 nnnnnn
n
n
n
p n
.
2
1
1
!)!1(
)!2(
!)!1(!)!1(
1
)!2(
2?
n
h
n
n
n
nn
n
nn
n
nn
n
n
§ 2.11 Catalan 数例 4,由 n个 1,n个 0组成的 2n位二进制数，要求从左向右扫描前 位时 1的累计数大于 0
的累计数，求满足这样条件的数的个数。此问题可归结为图 中从 点出发只经过对角线 上方的点抵达 点，求这样的路径数。相当于求从 点不经过对角线,
抵达 点的路径数，于是便转换为
12?n
7112 O
OA A
)1,0('O OA
),1(' nnA?
§ 2.11 Catalan 数例 3的问题。
根据例 3的结果。从 点通过 的点，以及 上方的点到达 的路径数为
)1,0('O ''AO
''AO ),1(' nnA?
)!1(!
1
)!22(]
)!2(!
1
)!1()!1(
1
[)!22(
22
1
22
nn
nn
n
nn
nn
n
n
n
n
n
§ 2.11 Catalan 数
.
1
221
1
nh
n
n
n
