组合数学第三讲-－金锄头文库

组合数学组合数学第三讲第三讲递推关系与母函数递推关系与母函数递推关系与母函数递推关系与母函数 2.1 递推关系递推关系组合数学很重要的内容是计数，有许多计数问题化为递推关组合数学很重要的内容是计数，有许多计数问题化为递推关系来求解。系来求解。看两个例子。看两个例子。母母函函数数组合数学用的最多的工具是母函数，究竟什么是母函数呢？组合数学用的最多的工具是母函数，究竟什么是母函数呢？例例2.4 对于河内塔问题利用母函数求递推关系的解对于河内塔问题利用母函数求递推关系的解Fibonacci序列的递推关系序列的递推关系 Fibonacci序列序列的两个等式的两个等式优选法与优选法与Fibonacci序列的应用序列的应用优选法也可以用优选法也可以用Fibonacci数来数来完成。完成。母函数的性质母函数的性质一个母函数和一组序列一一对应，利用母函数解递推关系必一个母函数和一组序列一一对应，利用母函数解递推关系必须要使从母函数到序列，或从序列到母函数的桥保持畅通，母须要使从母函数到序列，或从序列到母函数的桥保持畅通，母函数的性质就在于搭这样的桥。函数的性质就在于搭这样的桥。本本讲讲结结束束