生成函数的应用

北航软件学院生成函数的应用摘要生成函数方法是一种简单而又重要的方法，本文介绍了生成函数的定义，同时给出了生成函数在概率论、证明恒等式、求解递推关系及求递归数列的通项公式等方面的应用。关键字：生成函数；递推关系；恒等式；生成函数应用一、 生成函数的定义生成函数又叫做母函数。生成函数方法是离散数学的重要方法，是连接离散数学与连续数学的桥梁。在组合数学中，生成函数的典型作用主要体现在组合计数方面，是解决组合计数问题的强有力工具之一，其基本思想为：为了获得一个序列的有关知识，我们引用一个幂级数来整体表示这个序列，为序列的生成函数。这样，一个序列和它的生成函数一一对应，我们可以通过对生成函数的运算和分析得到这个序列的很多性质。18世纪，欧拉在研究正整数分拆时首先使用了母函数，19世纪初拉普拉斯在研究概率问题时得到进一步发展。母函数的一种自然推广，导致概率论中引进强有力的工具特征函数，它把随机变量的分布函数变换为它的特征函数，从而把对分布函数的研究转化为对对应的特征函数的研究，大大地推动了相互独立随机变量的和的极限理论的研究。一、 生成函数的应用21 生成函数在概率论中的应用例：在做抽样调查时，采访的男士有教师，医生，律师等不同的q个行业，女士也有不同的p个行业，假设我们在每一行业中至多选取2位男士和至多选取1位女士，问有多少种不同的方法取k个人的样本？解：要区分相同性别的人，当且仅当他们属于不同的范畴，现以选择k个人的方法数量做生成函数。在q种范畴的每一个中，我们或者选择0，1，2位男士做样本，因此每个范畴给出项，另外选择0或1位女士，所以p种范畴中的每一个给出(1+x)项。所以，因此选择k个人的方法数量是中的系数。例如时，所以，的系数是即在每一行业中选取2位男士和1位女士有48种不同的方法取四个人的样本。22 利用生成函数证明恒等式组合恒等式的证明技巧性很强，解题方法独特，其中利用构造母函数，比较等式两端对应项的系数，是证明组合恒等式的一种非常有效的方法。例：求证可以看出,该组合恒等式左端比较复杂，不太可能利用组合公式去证明，观察后发现等式左端各项规律性较强。通过分析，设法将等式左端看作是某一函数中确定项的系数，由为中项的系数，所以我们构造母函数： (1)中的系数即为。同时，利用“错位相减法”(1)式两边同时乘以得(1)-(2)得：，整理得到：，比较的系数即得所证结果。从上面这个例子可以看出，根据题意，灵活地引入母函数是证明组合恒等式的关键所在。23 用生成函数求解递推关系递推关系是计算中的一个强有力工具,而递推关系的求解一般比较困难,利用母函数求解递推关系则是一种主要的、行之有效的方法。例：求n位十进制数中出现偶数个5的数的个数。解：令是n位十进制数中出现偶数个5的数的个数,是n位十进制数中出现奇数个5的数的个数。因此有关系，其中。则此关系为关于序列的递推关系，求解此递推关系是解决本问题的难点。我们可以考虑引进序列的母函数，即利用错位相加减的方法，即：，再将展开成幂级数的形式：递推关系的求解主要是利用递推关系求得母函数的一种形式算法，母函数确定了，相应的递推关系对应的结果就确定了，这样的例子还有很多，想著名的Hanoi塔问题，Fibonacci数列都是典型的利用母函数解决递推关系的例子。24 用生成函数解递归数列的通项公式例：设且，求数列的通项。解：令 (1)则 (2)且 (3)(1)+(2)+(3)可得：，即，有，从而。二、 总结由于生成函数(形式幂级数)具有良好的性质，便于处理，因此它的应用较广泛。在组合分析、数论、概率论和图论等数学领域中有着广泛的应用。由于篇幅有限，本文只列举其中一小部分。参考文献1 王新渊.生成函数的性质和几个问题J青海大学学报,2000,18(1):46-492 王新渊.生成函数在数列研究中的应用J.青海大学学报,2000,18(3):44-453 冯素芬;刘永现.生成函数计数理论的应用及其最新进展J.北京工业职业技术学院学报,2008