(2-8-11)
5
R( 2 R Rn 1 ) Rn 3R Rn 1
(2-8-11)
an Rn , a1 R, b1 1, bn an1 R(2 R ) 2 因此 a bn1 2 R bn1 Ran1 n . an1 bn 3 Rb a n 1 n 1 3R bn1 令 an 2 R 2bn1 Ran1 , ( 2 8 12) bn 3Rbn1 an1.
1 2 i+1 i+2 n-1 n
存储单元如上图，设某一信息占用了第i+1，i+2两 个单元，把这组单元分割成两个部分，一是从1到i， 另一从i+3到n。 9
1
2
i+1 i+2
n-1 n
由于用相邻两个单元的几率相等，
1 an [(a0 an2 ) ( a1 an3 ) n 1 ( an2 a0 )],
2 3
§2.8 解方程组
a n ( 3 1)( 2 3 ) ( 3 1)( 2 3 ) n R ( 3 1) R. n n bn (2 3) (2 3)
n n
8
§2.8
母函数和递推关系应用举例
例：设有地址从1到n的单元，用以纪录一组信息 。这个信息的每个元素都占用两个单元，而且存放的 地址是完全随机的，因而可能出现两个存放信息单元 之间留下一个空单元无法存放其他信息，求这n个单元 留下空单元的平均数。 设这个平均数为 an。
对应的特征方程为
三重根
a 0 2 A0 a1 2 2 A1 , A1 0, a 2 4 2 A2 , A2 2,
n . a n 2 2 2
15
计算机界的精灵
• 一个栈(无穷大)的进栈序列为1，2，3，… ，n，有多少个不同的出栈序列?
bn
4
bn1 4 Rbn R bn1 0.
2
b2 4 R, b0 0. 2 2 特征方程是 x 4 Rx R 0
x ( 2 3) R , bn [ A( 2 3) B ( 2 3) ]R .
n n n
7
母函数和递推关系应用举例 A 1 , 2 3R A B 0, 1 B ( 2 3) A ( 2 3) B 1 R. . n 1 2 3R R n n bn [(2 3) ( 2 3) ], 2 3 Rn [( 3 1)( 2 3 ) n ( 3 1)( 2 3 ) n ]. an bn1 3Rbn
C(n) = C(0)*C(n-1) + C(1)*C(n-2) + .......+ C(n-2)*C(1) + C(n-1)*C(0)
G' G
(1 x )G 2 xG ,
G 2x 2 2 , G 1 x 1 x ln G 2 x ln(1 x ) 2 C , G ke 2 x (1 x ) 2 G x 0 a1 1,
k 1.
G e 2 x (1 x ) 2 n 1 ( 2 x ) 2 ( 2 x )3 n 1 ( 2 x ) [1 2 x ( 1) ...](1 2 x 3 x 2 ... nx n 1 ...) 2! 3! ( n 1)! 2 4 1 x2 x3 x4 x5 3 15
历史回顾
• 1988年以及1999年的文献研究表明实际上最 初发现Catalan数的也不是Euler，
– 1753欧拉在解决凸包划分成三角形问题的时候 ，推出了Catalan数。 – 1730年我国清朝时期的明安图（蒙古人）比 Catalan更早使用了Catalan数，见《割圜密率捷 法》。后来他的学生在1774年将其完成发表。
令
6
an 2 R 2bn1 Ran1 , ( 2 8 12) a 3 bn 3Rbn1 an1. Rn n , R1 R, R2 R, a1 R, b1 1.
将 an1 bn 3 Rbn1 代入 an 2 R 2bn1 Ran1 , 2 得到 bn1 3Rbn 2 R bn1 R (bn 3Rbn1 ),
n 22 23 2 a n1 ( n 1) 2n ( n 1) ( n 2) ( 1) n 2! 3! n! k n k 2 ( n k 1) ( 1) . k! k 0
12 12
§2.8
母函数和递推关系应用举例
例6：设有n条封闭的曲线，两两相交于两 点，任意三条封闭曲线不相交于一点。求 这样的n条曲线把平面分割成几个部分？ 设满足条件的n条封闭 曲线所分割成的域的数目为 an ，其中 n 1 条封闭曲线 所分割成的域的数目为 an1
– 正n边形化分为不重叠的三角形有多少种方法？
C(n) = C(0)*C(n-1) + C(1)*C(n-2) + .......+ C(n-2)*C(1) + C(0)*C(n-1)
回顾历史
• 1758年，Johann Segner 给出了欧拉问题的 递推关系 • 1838年，研究热潮
– Gabriel Lame给出完整证明和简洁表达式 – Eugè ne Charles Catalan在研究汉诺塔时探讨了 相关问题, 解决了括号表达式的问题. – …… – 1900 Eugen Netto在著作中将该数归功于 Catalan.
Rn可以作为由Rn-1等效电阻如图2-8-7所示的 方式串并联构成的.
R R R
图 2-8-7
Rn1
2 R Rn1 R 1 1 1 Rn R 2 R Rn1 R( 2 R Rn1 ) 3 R Rn 1 . R( 2 R Rn1 )
递推关系
R (2 R Rn1 ) Rn 3R Rn 1 3 R1 R, R2 R. 4
a n a n 1 2( n 1) a n 1 a n 2 2( n 2 ) a n 2a n 1 a n 2 2 a n 1 2a n 2 a n 3 2 a n 3a n 1 3a n 2 a n 3 0
x : 2a3 a2 2a1 , x 2 : 3a4 2a3 2a2 , x : 4a5 3a4 2a3 ,
3
_ _)_ _ _ _ _ _ _ __ __ _______ __
G ( x ) xG 2 xG.
11
(ln x )'
1 x
(ln G )'
14
an an 1 2( n 1), a1 2.
a n 3a n 1 3a n 2 a n 3 0
(2 - 8 - 2)
m 3 3m 2 3m 1 ( m 1) 3 0 利用递推关系 (2 - 8 - 2) 得 a0 2.
n , a n A0 A1n A2 2
f(n) = f(0)*f(n-1) + f(1)*f(n-2) + .......+ f(n-2)*f(1) + f(n-1)*f(0)
• 假设f(0) = 1，那么f(1) = 1, f(2) = 2, f(3) = 5 。
Catalan数
• 1751年欧拉在与哥德巴赫的通信中提出一个问 题：
Catalan数
• 比利时的数学家欧仁· 查理· 卡塔兰 (1814– 1894)命名 • OEIS A000108 • 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, ...
1，2，3, 4
1
2
3
4
17
计算机界的精灵
• 一个栈(无穷大)的进栈序列为1，2，3，… ，n，有多少个不同的出栈序列?
第一次为空时进行分步？
第一次为空时有k个元素出栈，即1 出栈的序号; 将1~n的序列分成两个序列，其中 一个是1~k-1共k-1个元素 另外一个是k+1~n，共n-k个元素 设f(n)是n个元素的出栈序列数 f(n)= f(k-1)* f(n-k) k =1~n
3
§2.8 母函数和递推关系应用举例 例：求图2-8-6所示的n级网络的等效电阻 Rn。 所谓等效电路，相当于图2-8-6中虚线 所包围的块用一电阻 Rn 取代，使在两端点 n n 之间的效果一样。
n
R
R
R R R R
R R R 图 2-8-6
R R
n
Rn
4
§2.8
母函数和递推关系应用举例
母函数
定义2-1 对于序列a0, a1, a2…, 构造一函数 G(x)= a0+a1x+a2x2+…, 称G(x)为序列a0, a1, a2…的母函数。
母函数就是一列用来展示一串数字序列的挂衣架。 — 赫伯特·维尔夫
拉普拉斯 1812年
x0 a0
x1 a1
x2 a2
x3 a3
x4 a4
x5 a5
13
§2.8 母函数和递推关系应用举例 第n条封闭曲线和这些曲线相交于 2( n 1) 个 点，这 2( n 1) 个点把第n条封闭曲线截成 2( n 1) 条弧，每条弧把 2( n 1) 个域中的每 个域一分为二。故新增加的域数为2( n 1). an an 1 2( n 1), a1 2. (2 - 8 - 2)