组合数学第三讲.ppt

《组合数学第三讲.ppt》由会员分享，可在线阅读，更多相关《组合数学第三讲.ppt（22页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、组合数学第三讲 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life, there is hope。有生命必有希望。有生命必有希望递推关系与母函数递推关系与母函数 2.1 递推关系递推关系 组合数学很重要的内容是计数，有许多计数问题化为递推关组合数学很重要的内容是计数，有许多计数问题化为递推关系来求解。系来求解。 看两个例子。看两个例子。例例2.1 河内塔问题：有河内塔问题：有 n个圆盘依半径的大小，从大到小依下而上套在柱个圆盘依半径的大小，从大到小依下而上套在柱A 上。另提供有相同的柱上。另提供有相同的柱 B 和柱和柱 C。要

2、将柱。要将柱 A 上的圆盘全部移到柱上的圆盘全部移到柱 B（或柱（或柱 C）上，每次只允许移动一盘到）上，每次只允许移动一盘到 B 或柱或柱 C 上，而且不允许将半上，而且不允许将半径大的圆盘压在半径小的圆盘上， 请设计一种移动办法， 并估计要移动径大的圆盘压在半径小的圆盘上， 请设计一种移动办法， 并估计要移动的次数。的次数。 母母 函函 数数 组合数学用的最多的工具是母函数，究竟什么是母函数呢？组合数学用的最多的工具是母函数，究竟什么是母函数呢？ 将1021HH，2121HH，3221HH，.代入上式得： 201222012( )2 ()()nnnnnG xHH xH xH xx HH x

3、H xH xxxx 2( )1xxG xx 所以有：( )(1)(1 2 )xG xxx 例例2.4 对于河内塔问题利用母函数求递推关系的解对于河内塔问题利用母函数求递推关系的解Fibonacci序列的递推关系序列的递推关系 令令 Fibonacci 序列的母函数序列的母函数212( )nnG xFxF xF x 利用已知结果利用已知结果12nnnFFF，121FF代入上式得如下结果：代入上式得如下结果： 22( ) ( )( )G xxxx G xxx G x 3x：123FFF 4x：234FFF 5x：345FFF 6x：456FFF +） 。 。 。 故有：故有： 2( )1xG xx

4、x 作部分分式分解得：作部分分式分解得： 2111( )1515151122xG xxxxx 记记152，152，则有：，则有： 2221( )()()5G xxx 所以得：所以得： 5nnnF 由于由于1512，当，当n 时，时，0n，所以，所以n较大时较大时11525nnF。 1151.6182nnFF ， 11.618nnFF， 10.618nnFF Fibonacci序列序列 的两个等式的两个等式1221nnFFFF135212nnFFFFF优选法与优选法与Fibonacci序列的应用序列的应用设函数)(xfy 在区间),(ba内有单峰极大值点（或极小值点） ， 求。 优选法： 设函数

5、)(xfy 在区间),(ba内有单峰极大值点 在),(ba内取两点 1x，2x，21xx 。 （1）若)()(21xfxf，则),(2xa，可去掉区间 ),(2bx； （2）若)()(21xfxf，则),(1bx，可去掉区间 ),(1xa； （3）若)()(21xfxf，则),(21xx，可去掉区间 ),(1xa和 ),(2bx。 然后在剩余区间重新用上述方法。当剩余区间长度小于预设规定长度后算法结束。 令382. 01x，618. 02x（即2512x） 这就是所谓的 0.618 优选法。 优选法也可以用优选法也可以用Fibonacci数来完成。数来完成。母函数的性质母函数的性质 一个母函数和一组序列一一对应，利用母函数解递推关系必一个母函数和一组序列一一对应，利用母函数解递推关系必须要使从母函数到序列，或从序列到母函数的桥保持畅通，须要使从母函数到序列，或从序列到母函数的桥保持畅通，母函数的性质就在于搭这样的桥。母函数的性质就在于搭这样的桥。本本 讲讲 结结 束束