m(m 1)(m 2) x3 3!
故二项式 (1 x)m中 xnm 项系数为
m(m 1) (m n m 1) m(m 1) (n 1) (n 1)!
(n m)!
(n m)!
(m 1)!(n m)!
§4.8 母函数和递推关系应用举例
即 C(m (n m) 1, n m) C(n 1, n m) C(n 1, m 1)
即求对n位2进制数 b1b2 从左bn 而右扫描，
第一次在最后三位出现010图象的数的个数。 自然，最后三位除外任取连续三个都不会 是010的。
设 表a满n 足条件的n位数个数，和前例类似， 最后三位是010的n位2进制数共 个2，n3
§4.8 母函数和递推关系应用举例
对这 2n3个数分析如下。
（a）包含了在最后三位第1次出现010图象的
符 (,,组,)成的14个元素。求由其中的n个
元素的排列构成一算术表达式的个数。 因所求的n个元素的排列是算术表达式，
故从左向右的最后一个符号必然是数字。而 第n-1位有两种可能，一是数字，一是运算 符。如若第n-1位是十个数字之一，则前n1位必然构成一算术表达式。
§4.8 母函数和递推关系应用举例
0 1 0 0 1 0
§4.8 母函数和递推关系应用举例
（d）包含了在第(n 6) 位到第(n 4)位第
1
2an4
次出n 现3010图象的数，其个数是 ，因在
第 位（打*号的格）可以取0或1两种状态。
0 1 0 0 1 0
§4.8 母函数和递推关系应用举例
一般可以归纳为对 k 3 ，从第(n k 2)位 到第n k 位第一次出现010图象的数，其数 目为 2k3 a。nk从第 位n 到 k第 位中n 间3 的 k 位3 可以取0，1两种值，故有 2种k3状
故有
an an2 2n3, n 5,
a3 1, a4 2.
利用
推得 a2 0,
特征方程为
a1 0,
a0
1. 2
(x 2)(x2 1) 0.
i
x1 2, x2,3 e 2 .
§4.8 母函数和递推关系应用举例
设
an
Acos(n )
2
B sin(n )
2
C
2n,
解方程组
A
§4.8 母函数和递推关系应用举例
整理得
(1 x2 x3 ) A(x) 23 x3 1 2x 4x2.
1 2x
1 2x
1 2x x2 2x3 x3 A(x) 23 x3 1 4x2 4x2 8x3
1 2x
1 2x
1. 1 2x
§4.8 母函数和递推关系应用举例
A( x)
如若不然，即第n 1 位是4个运算符之一， 则前n 2 位必然是算术表达式。根据以 上分析，a令n n表 个元素排列成算术表达
式的个数。an则 10an1 40an2 , a1 10, a2 120.
a2 120 指的是从0到99的100个数，以及 0, 1,,9.
§4.8 母函数和递推关系应用举例
an
4
1 [(15 65
65)(5
65)n
(15 65)(5 65)n ].
§4.8 母函数和递推关系应用举例
例6：平面上有一点P，它是n个域D1, D2,, Dn
的共同交界点，见图 现
取k种颜色对这n个域进行着色， 要求相邻两个域着的颜色不同。
Dn D1
试求着色的方案数。
令an表示这n个域的着色
种不同的方案？其中n m
由于不允许有空盒，令n个球放到m个有
标志的盒子的方案数为a，n 序列 {a对n}应的母 函数为 。G则(x) G(x) (x x2 )(x x2 )(x x2 )
xm (1 x)m
§4.8 母函数和递推关系应用举例
因 (1 x)m 1 mx m(m 1) x2 2!
Dn1 P
D2 D3
方案数。无非有两种情况：
图
§4.8 母函数和递推关系应用举例
（1）D1和 Dn1有相同的颜色；（2）D1和Dn1所 着颜色不同。第一种情形， 域有k 1 种颜 色可用，即D1, Dn1域所用颜色除外；而且从 D1 到Dn2的着色方案，和 n 2 个域的着色 方案一一对应。后一种Dn 域有k 2 种颜 色可供使用；而且从D1 到Dn1 的每一个着 色方案和n 1 个域的着色方案一一对应。
黄一白。
§4.8 母函数和递推关系应用举例
令取r的组合数为c，r 则序列 c0 , c1, c2 , c3, c4
的母函数为
G(x) (1 x x2 )(1 x)2 1 3x 4x2 3x3 x4
共有1+3+4+3+1=12种组合方式。
§4.8 母函数和递推关系应用举例
例3：n个完全一样的球放到m个有标 志的盒子中，不允许有空盒，问共有多少
个数，其个数为 an，排除了在第 (n到 4第) (n 2)
位第1次出现010图象的可能。
（b）包含了在第(n 到4)第 (n位第2)1次出现 010图象的数，其个数为an2 .
0 1 0 1 0
§4.8 母函数和递推关系应用举例
（c）包含了在第(n 5)位到第 (n 3)位第1 次出现010图象的数，其个数是an3.
§4.8 母函数和递推关系应用举例
故数列 a0 , a1, a2 ,对应, a8一母函数 A(x) 1 28x2 70x4 28x6 x8
类似的方法可得女同志的允许组合数对应的母
函数位 B(x) 10x2 10x3 5x4 x5
§4.8 母函数和递推关系应用举例
C(x) A(x)B(x) (1 28x2 70x4 28x6 x8 ) (10x2 10x3 5x4 x5 ) 10x2 10x3 285x4 281x5 840x6 728x7 630x8 350x9 150x10 38x11 5x12 x13
其它依此类推。
§4.8 母函数和递推关系应用举例
令 A(x) 1 2x 3x2 a6x3 a7 x4 x3 : a6 a4 a3 23 x4 : a7 a5 a4 2a3 24
) x5 : a8a6a5 2a4 22 a3 25 [ A(x) 1 2x 3x2 ] x2[ A(x) 1] (x3 2x4 22 x5 ) A(x) 23 x3 1 2x.
§4.8 母函数和递推关系应用举例
例4：某单位有8个男同志，5个女同志， 现要组织一个有数目为偶数的男同志和数 目不少于2的女同志组成的小组，试求有多 少种组成方式。
令 为an从8位男同志中抽取出n个的允许组合数。
由于要男同志的数目必须是偶数，故
a1 a3 a5 a7 0, a0。 1, a2 C(8,2) 28, a4 C(8,4) 70, a6 C(8,6) 28, a8 1
C
1 2
,
B 2C 0,
A 4C 0.
§4.8 母函数和递推关系应用举例
得
A
2 5
,
B
1 5
,
C
1 10
.
an
2 cos(n )
5
2
1 sin(n )
5
2
1 2n,n 10
3.
§4.8 母函数和递推关系应用举例
例8：求n位的2进制数中最后三位才第一次 出现010图象的数的个数。
态。
0 1 0 0 1 0
§4.8 母函数和递推关系应用举例
故得递推关系如下： an an2 an3 2an4 2n6 a3 2n3, n 6
a3 1, a4 2, a5 3.
n 5 时有下面几种状态： 00010, 10010, 11010.
排除了01010，因从左而右扫描时01010属于 前
§4.8 母函数和递推关系应用举例
§4.8 母函数和递推关系应用举例
例1：下图是一逻辑回路，符号D是一延 迟装置，即在时间t输入一个信号给延迟装 置D，在t+1时刻D将输出同样的信号，符
号 表示加法装置
D
输入u
D
D
输出v
图
§4.8 母函数和递推关系应用举例
求相若同在时t 刻 0的,1,输2,出信时号刻v0,，v1,输入。信号u0,u1,, 显然，v0 u0 , v1 u1 u0 , v2 u2 u1, v3 u3 u2 u0 ,。
§4.8 母函数和递推关系应用举例
an (k 2)an1 (k 1)an2,
a2 k(k 1), a3 k(k 1)(k 2).
则
a1 0, a0 k.
的特征方程为
x2 (k 2)x (k 1) 0,
x1 k 1, x2 1. an A(k 1)n B(1)n.
§4.8 母函数和递推关系应用举例
被装置的特性所确定，可以看作是该装置 的传递函数，如图4-8-1
U (x)
P(x)
V (x)
§4.8 母函数和递推关系应用举例
例2：由红球两个，白球、黄球各一个， 试求有多少种不同的组合方案。
设r，w，y分别代表红球，白球，黄球。
(1 r r 2 )(1 w)(1 y) (1 r r 2 )(1 y w yw) 1 (r y w) (r 2 ry rw yw)
§4.8 母函数和递推关系应用举例
C中(x)项的xk系数 为符c合k 要求的 个人组k 成
的小组的数目，总的组成方式数目为
10 10 285 281 840 728 630 350 150 38 5 1 3328
§4.8 母函数和递推关系应用举例
例5：10个数字（0到9）和4个四则运算
三位出现010图象的。
§4.8 母函数和递推关系应用举例
请注意，递推关不是常系数递推关系。