第七章、生成函数.pdfVIP

组合数学讲义(内部资料，严禁商用) 第七章、生成函数 2008-2009学年第二学期 第七章、生成函数 本章目次 7.1、引论 7.2、形式幂级数 7.3 生成函数的性质 7.4 用生成函数求解递推关系 7.4.1 用生成函数求解常系数线性齐次递推关系 7.4.2 用生成函数求解常系数线性非齐次递推关系 7.5 生成函数在计数问题中的应用 7.5.1 组合数的生成函数 7.5.2 排列数的指数型生成函数 7.5.3 分拆数的生成函数 7.5.4 组合型分配问题的生成函数 7.5.5 排列型分配问题的生成函数 7.5.6 有限制位置的排列及棋子多项式 7.1、引论 生成函数方法是一种既简单又有用的数学方法，它是在 19 世纪初出现的，对于组合计数 问题，生成函数方法是一种最重要的一般性处理方法。它的中心思想是：对于一个有限或无 限数列 a a a L ， { 0 , 1, 2 , } 用幂级数 A(x) a +a x +a x 2 +L 0 1 2 使之成为一个整体，然后通过研究幂级数A(x) ，导出数列{a , a , a , L} 的构造和性质。我 0 1 2 们称A(x) 为序列{a , a , a , L} 的生成函数，并记为G{a } 。 0 1 2 n 例如、组合序列 C0 C1 L Cn { n , n , , n } 第1页本章共45页 组合数学讲义(涉外学院数学本科用) 2008-2009学年第二学期 制作人 陈勇 的生成函数为 0 1 2 2 n n f (x) C +C x +C x +L+C x n n n n n 由二项式定理知 f n (x) (1+x)n 通过对(1+x)n 的运算，可以导出一系列组合数的关系式，例如 n ∑Ci 2n n i 0 n ∑iCi n ⋅2n −1 n i 0