《组合数学第三讲》由会员分享,可在线阅读,更多相关《组合数学第三讲(22页珍藏版)》请在金锄头文库上搜索。
组合数学组合数学 第三讲第三讲递推关系与母函数递推关系与母函数递推关系与母函数递推关系与母函数 2.1 递推关系递推关系 组合数学很重要的内容是计数,有许多计数问题化为递推关组合数学很重要的内容是计数,有许多计数问题化为递推关系来求解。系来求解。 看两个例子。看两个例子。母母 函函 数数 组合数学用的最多的工具是母函数,究竟什么是母函数呢?组合数学用的最多的工具是母函数,究竟什么是母函数呢? 例例2.4 对于河内塔问题利用母函数求递推关系的解对于河内塔问题利用母函数求递推关系的解Fibonacci序列的递推关系序列的递推关系 Fibonacci序列序列 的两个等式的两个等式优选法与优选法与Fibonacci序列的应用序列的应用优选法也可以用优选法也可以用Fibonacci数来数来完成。完成。母函数的性质母函数的性质 一个母函数和一组序列一一对应,利用母函数解递推关系必一个母函数和一组序列一一对应,利用母函数解递推关系必须要使从母函数到序列,或从序列到母函数的桥保持畅通,母须要使从母函数到序列,或从序列到母函数的桥保持畅通,母函数的性质就在于搭这样的桥。函数的性质就在于搭这样的桥。本本 讲讲 结结 束束