1、母 函数与递推关系递推关系是计数的一个强有力的工具，特别是在做算法分析时是必需的。递推关系的求解主要是利用母函数。当然母函数尚有其他用处，但这主要是介绍解递推关系上的应用。例如母 函数与递推关系1 母函数定义 ：给定序列 (a0,a1, an,) ， 记为 an.函数f(x)= a0+a1x+ anxn+称为该序列的普通母函数，简称母函数。例 常数列 (1,1,) 的母函数为f(x)= 1+x+ xn+=1/(1- x)数列 C(n,i),i=0,1,2, n的母函数为这里的母函数只是 “形式幂级数 ”，运算均按收敛幂级数进行。母 函数与递推关系母函数的组合意义：考察母 函数与递推关系其中：
2、x前的 系数为 a,b,c的所有可重 1-组合，x2前的系数为 a,b,c的所有可重 2-组合，一般地： xn前的系数为 a,b,c的所有可重 n-组合，在前式中取 a=b=c=1,则 xn前的系数为 a,b,c的所有可重 n-组合数 F(3,n).母 函数与递推关系所以，构造某组合问题的组合数 an的母 函数 f(x)的基本方法为：用一个乘积因子 (1+x+x2+) 来代表一个所选元素，若该元素可重复 n次，则因子中应出现 xn。例 设有 2个红球， 3个白球， 1个黑球和 1个黄球 .求从这些球中取出 5个的不同方案数。解：设从所给球中取出 i个的不同方案数为 ai,则由题设可得 ai的母
3、函数为母 函数与递推关系例 求用 1元和 2元的钞票支付 n元的不同方式数。解：设所求不同方式数为 an,则由题设可得 an的母函数为母 函数与递推关系于是母 函数与递推关系定义 ：给定序列 (a0, a1, an,) ， 记为 an.函数称为该序列的指数型母函数 ,简称指数母函数。例 常数列 (1,1,) 的母函数为例 从 n 个不同元素中取 r 个的排列数 P(n， r)指数母函数为：母 函数与递推关系例 n 个不同元素的可重 r-排列数 nr (r = 0, 1, 2, ) 的指数母函数为例 求用 1,2,3,4,5五个数字组成的 n位数的个数，要求 1出现的次数为偶数， 2 出现的次数为奇数，并且 3至少出现一次。解：设所求 n位数的个数为 an ，则由题设可得an的指数母函数为：母 函数与递推关系
