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

第1页：封面

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

第2页：组合数的生成函数

§5.2组合数的生成函数2问题3确定多重集S={3·a,4·b,5·c}的10-组合数。

问题1求的k组合数

第3页：定理5.2.1 设多重集

定理5.2.1设多重集，则M的k-组合数ck对应序列{ck}的生成函数为其中，ck为展开式中的系数。

第4页：证明:令中各的项分别对应各个元素

证明:令中各的项分别对应各个元素的可能取法。

例如，对时x2表示元素a2选取了2次，其中依次类推。

展开式中的项xk具有一般形式其中对此方程的一非负整数解(满足条件下)，相应的就对应了M的一个k-组合因此合并同类项后，xk的系数就表示了M的k-组合数。

第5页：推论5.2.1 设，若限定在k-组合中元

推论5.2.1设，若限定在k-组合中元素出现的次数集合为，则从M的k-组合数对应序列的生成函数为

第6页：问题2例5.2.1利用生成函数方

问题2例5.2.1利用生成函数方法求的k-组合数。

第7页：解设的k-组合数

解设的k-组合数为，则数列{}的生成函数为：其中的系数就是M的k-组合数，这个结果显然与第三章中定理3.3.3是一致的。

第8页：例5.2.2 多重集合的10-组合数

例5.2.2用生成函数方法求多重集合的10-组合数。

问题3

第9页：解将的k-组合数记

解将的k-组合数记为，{}的生成函数是所以，的系数为与第4章中用容斥原理得到的结果相同。

第10页：问题1问题1求的k组合数解

问题1问题1求的k组合数解：在普通集合的k-组合中，或出现或不出现，故其k-组合数数列{ }的生成函数为从而

第11页：例5.2.3 的每个元素至少取一次的k-

例5.2.3求的每个元素至少取一次的k-组合数。

第12页：解设的每个元素至少取一次的k

解设的每个元素至少取一次的k-组合数对应数列的生成函数为为的系数。

第13页：例5.2.4 方程的整数解的个数

例5.2.4求方程的整数解的个数。

13解：设方程的整数解数为，数列对应的生成函数为我们所求的是为展开式中的系数

第14页：例5.2.5 方程x1+2x2=15的非

例5.2.5求方程x1+2x2=15的非负整数解的个数。

解设方程x1+2x2=k的非负整数解的个数为ak,{ak}的生成函数为因此，a15=8.

第15页：例5.2.6 假定有足够多的苹果

例5.2.6假定有足够多的苹果、香蕉、橘子和梨，用这4种水果装成由k个水果的构成水果袋，要求水果袋中苹果数为偶数，香蕉数是5的倍数，橘子最多有4个，梨的个数是0或者1，求可以有多少种不同的装法？

第16页：解设有ck种装法

解设有ck种装法，则数列{ck}对应的生成函数因此，有k+1种不同的装法。

第17页：排列数的指数型生成函数

§5.3排列数的指数型生成函数当涉及到与排列有关的问题时，需要引入指数型生成函数。

定义5.3.1数列的指数型生成函数定义为形式幂级数记为或者

第18页：定理5.3.1 设,考虑M的k-排列

定理5.3.1设,考虑M的k-排列中元素出现次数构成的集合为(1≤i≤n)，则k-排列数对应数列的生成函数为

第19页：证明根据和式的性质

证明根据和式的性质，上式右端等于由多项式系数的组合学意义知，正是元素出现次，元素出现次，元素出现次的k-排列数。

故按所有可能的求和，即得总的k-排列数。

第20页：例5.3.1 设要求的生成函数为Ge(x

例5.3.1求排列数数列{}的指数型生成函数，其中20解：设要求的生成函数为Ge(x)，根据定义5.1.1

第21页：例5.3.2 数列{bk}的指数型生成函

例5.3.2求多重集合的k-排列数bk.21解设数列{bk}的指数型生成函数为Ge{bk}，根据定理5.3.1有，从而，与第3章中的结果是一致的。

第22页：例5.3.3 计算M={4 r

• 例5.3.3计算M={4
• r, 5
• g, 6
• b}中r和g均出现奇数次的10-排列数。

第23页：解显然根据要求在所求的10-

解显然根据要求在所求的10-排列中r可能出现的次数为1或3，g出现的次数为1或3或5。

若设M的k-排列数为bk，数列{bk}的指数型生成函数为Ge{bk}，则有我们要求的是的系数，为9660.

第24页：例5.3.4 红色方格的个数是偶数且至少

例5.3.4用红、白、蓝三种颜色给1行k列棋盘涂色，并要求红色方格的个数是偶数且至少有一个方格为白色，求涂色方案数bk，其中k为正整数。

24解设数列{bk}的指数型生成函数为Ge{bk}，则有因此，

第25页：例5.3.5 排列方案数

例5.3.5有3个红球，2个黄球，3个蓝球，每次从中取出4个排成一行，求排列方案数。

25解设每次取出k个球的排列数为bk，数列{bk}的指数型生成函数为Ge{bk}，则有而我们所求的即为为的系数，则取出4个球的排列方案有70种。

第26页：Catalan数列的生成函数

§5.4.1 Catalan数列的生成函数26一、Catalan数列的通项公式二、Catalan数列的生成函数三、Catalan数列的应用

第27页：例5.4.1 在一个凸n+1边形

例5.4.1在一个凸n+1边形中，可以用(n-2)条不在内部相交的对角线将其剖分成(n-1)个三角形，问有多少种不同的分法？

一、Catalan数列的通项公式

第28页：28TR2R1A1An+1A

28TR2R1A1An+1Ak+2AkAk+1

第29页：解令表示将一个凸(n+1)边形剖

解令表示将一个凸(n+1)边形剖为三角形的方法数，规定。

当n= 2时，(n+1)边形就是三角形，不需剖分，故当考虑一个凸(n+1)边形，它的顶点分别用表示，如图5.4.1所示。

取边，任取顶点将分别与之间连线，得三角形T，三角形T将凸(n+1)边形分成T，R1和R2三部分，其中，R1为(k+1)边形，R2为(n-k+1)边形。

因此，R1可以用种方法剖分，R2可以用种方法剖分，所以这正是Catalan数列的通项公式。

第30页：那么如何求

那么如何求,本节用的生成函数来计算。

解得30二、Catalan数列的生成函数

第31页：利用牛顿二项式定理

利用牛顿二项式定理，有因为，开方应该取负号，故舍去显然一个凸n+1边形中有种不同的剖分方法。

第32页：三、Catalan数列的应用1.

三、Catalan数列的应用1.括号化问题。

矩阵链乘：P=a1×a2×a3×……×an，依据乘法结合律，不改变其顺序，只用括号表示成对的乘积，试问有几种括号化的方案？

(h(n)种)2.出栈次序问题。

一个栈(无穷大)的进栈序列为1,2,3,..n,有多少个不同的出栈序列?

第33页：3.给顶节点组成二叉树的问题

3.给顶节点组成二叉树的问题。

给定N个节点，能构成多少种形状不同的二叉树？

第34页：Stirling数列的生成函数

§5.4.2Stirling数列的生成函数在3.5节中介绍过第一类和第二类Stirling数。

本节中我们首先从另外一个角度介绍第一类Stirling数和它的性质，最后给出第二类Stirling数的生成函数。

设有多项式，它的展开式具有下面的形式：□-□+□-…，不考虑各项系数的符号，则的系数就是第一类Stirling数，上面的式子变成：我们称这些数为第一类Stirling数。

根据3.5节有，第一类Stirling数具有下面的性质，我们给出不同的证明方法。

第35页：证明为项的系数

证明为项的系数，即多项式中的常数项，显然为0。

是x项的系数，各因式在相乘时分别贡献负数-1，-2，…，-(n-1)，从而得到x项。

不考虑这些数的符号，它们之积是(n-1)!所以是项的系数，显然为1。

是项的系数，为了得到，n个因式中只能有一个因式贡献常数，由加法原理得出提供常数的总和为所以。

第36页：2.第一类Stirling数满足

2.第一类Stirling数满足下面的递推关系。

证明考虑多项式上式两边同乘以得即比较上式两边的系数得

第37页：定理5.4.1 序列的生成函数为并有证明

定理5.4.1序列的生成函数为并有证明：对递归关系两端同乘以，并对n求和，得即：令则有

第38页：故：从而等式右端展开后

故：从而等式右端展开后，各项的一般形式为

第39页：其中，，且

其中，，且。

合并同类项后的的系数为其中，是满足非负整数解，因此

第40页：作为验证

作为验证，我们计算，其中n=4，k=2，n-k=2，n1+n2=2的所有非负整数解为（0，2），（1，1），（2，0），因此根据第3章的知识，结果显然是正确的。