05-1 第五章 生成函数1.pptx

第1页：封面

第五章生成函数5.1生成函数的定义和性质5.2组合数的生成函数5.3指数型生成函数与多重集的排列数5.4Catalan数列与Stirling数列的生成函数5.5分拆数的生成函数

第2页：生成函数最早应用在1720年前后

生成函数最早应用在1720年前后组合计数方法，将数列与形式幂级数联系起来，成为连接离散数学与连续数学的桥梁。

美国著名计算数学家Wilf曾将生成函数形象地比喻成“一根晾衣绳”，其上挂满了要展示的一列数。

第3页：多重集合的排列和组合递推关系

多重集合的排列和组合递推关系的求解正整数分拆组合恒等式证明

第4页：生成函数生成函数方法的基本思

生成函数生成函数方法的基本思想是把离散的数列同多项式或幂级数一一对应起来，从而把离散数列间的结合关系转换为多项式或幂级数之间的运算。

第5页：生成函数的定义

§5.1生成函数的定义与性质定义5.1.1设有一个有限或无限数列称G(x)为序列的生成函数，做形式幂级数并记为

第6页：例5.1.1 二项式系数的序列的生成函数

例5.1.1求二项式系数的序列的生成函数。

解：设要求的生成函数为G(x)，根据定义5.1.1，由二项式定理，

第7页：例5.1.2 设要求的生成函数为G(x)

例5.1.2无限数列{1,1,….,…}的生成函数。

解：设要求的生成函数为G(x)，根据定义5.1.1，由牛顿二项式定理的推论，生成函数的定义

第8页：例5.1.3 该数列记作{ak}，它的生

例5.1.3求数列的生成函数，其中ak是多重集的k-组合数解：该数列记作{ak}，它的生成函数是G(x)，则：

第9页：生成函数的性质

§5.1.2生成函数的性质设数列的生成函数为，数列的生成函数为，数列的生成函数为，

第10页：生成函数的性质

生成函数的性质（1）性质1若则证明根据已知条件，有

第11页：生成函数的性质

生成函数的性质（2）性质2若则证明根据已知条件，有

第12页：生成函数的性质

生成函数的性质（3）性质3若则证明等式的两端都乘以，得以上各式两边分别相加，得

第13页：生成函数的性质

生成函数的性质（4）性质4若则其中收敛证明因为收敛，所以是存在的，于是有以上各式两边分别相加，得

第14页：生成函数的性质

生成函数的性质（5）性质5若则证明由的定义知

第15页：生成函数的性质

生成函数的性质（6）性质6若则证明根据已知条件有

第16页：生成函数的性质

生成函数的性质（7）性质7若则证明根据已知条件有

第17页：生成函数的性质

生成函数的性质（8）性质8若则证明根据已知条件有

第18页：生成函数的性质

生成函数的性质（9）性质9若证明：

第19页：一些数列的生成函数19(1)

一些数列的生成函数19(1)(2)(3)(4)(5)(6)(7)(8)

第20页：例5.2.1 的生成函数20解方法1设则

例5.2.1求的生成函数20解方法1设则：所以故

第21页：方法22

方法221

第22页：例5.2.2 22解方法1：用多项式的长

例5.2.2已知的生成函数为求22解方法1：用多项式的长除法得则：所以有

第23页：方法2当k=0时

方法2当k=0时，ak=2；

当k=1时，ak=22+3=7；

当k>1时，ak=2k+1+3×2k-1-6×2k-2=2k+1；

23，，

第24页：例5.2.3 求前n个正整数的平方和24

例5.2.3求前n个正整数的平方和24解由前面列出的第（5）个数列的生成函数有，的生成函数为此处，令则由性质3得：的生成函数为再根据例5.1.3，

第25页：比较等式两边的系数

比较等式两边的系数，有：