数列与Stirling数列的生成函数(共22页).doc

《数列与Stirling数列的生成函数(共22页).doc》由会员分享，可在线阅读，更多相关《数列与Stirling数列的生成函数(共22页).doc（22页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上教 案课程名称：组合数学 授课教师卢奕南所在单位计算机科学与技术学院课程类型讲授授课时间32学时授课对象本科生三年级教学内容提要时间分配及备注在第二章中，已解决了部分排列组合问题。但对于不尽相异元素的部分排列和组合，用第二章的方法是比较麻烦的，若改用生成函数方法，问题将显得容易多了。其次，在求解递推关系的解、整数分拆以及证明组合恒等式时，生成函数是一种非常重要的手段。本章通过例题的解答，显示了生成函数方法确实是组合数学中的基本而重要的方法，它是连接离散数学与连续数学的桥梁，而且组合数学中的问题能借助于生成函数的方法、原理，获得统一的处理和解决方式生成函数（母函数）。生

2、成函数方法的基本思想是把离散的数列同多项式或幂级数一一对应起来，从而把离散数列间的结合关系转换为多项式或幂级数之间的运算。本节主要讨论几类特殊的生成函数，即组合数序列、排列数序列、分拆数序列、组合分配数序列以及排列分配数序列的生成函数，以及Catalan数和第一类Stirling数的生成函数。5.1 生成函数的定义与性质5.1.1 生成函数的定义定义 5.1.1 设于一个有限或无限数列 做形式幂级数 ，称A（x）为序列的生成函数，并记为 例 5.1.1组合数序列，的生成函数是 通过对的运算，可能导出一系列组合数的关系式，例如： 由恒等式 可以推导出Vandermonde恒等式 例5.1.2 无

3、限数列的生成函数是例5.1.3 求数列的生成函数，其中是多重集的组合数的生成函数。解 该数列记作，它的生成函数是，则 （5.1.1）当时，这时数列为例5.1.2的无限数列，其生成函数为。当时，的组合数是，这时数列变成，而由（5.1.1）式有。例5.1.4 投掷一次骰子，出现点数1，2，6的概率均为，问连续投掷两次，出现的点数之和为10的概率有多少？ 解 一次投掷出现的点数有6种可能，连续两次投掷到的点数构成二元数组，共有种可能，由枚举法，两次出现的点数之和为10的有3种可能；（4，6），（5，5），（6，4），所以概率为 如果问题是连续投掷10次，其点数之和为30的概率有多少，这时就不那么简单

4、了，这是由于10个数之和为30的可能组合方式很多，难以一一列举，要解决这个问题，只能另辟新径。 我们用多项式 表示投掷一次可能出现点数1，2，6，观察 从两个括号中分别取出和，使 即是两次投掷分别出现点数，且，由此得出，展开式中的系数就是满足条件的方法数。 同理，连续投掷10次，其和为30的方法数为 中的系数，而 所以，的系数为 故所求概率为 5.1.2 生成函数的性质 生成函数与数列之间是一一对应的，因此，若两个生成函数之间存在某种关系，那么相应的两个数列之间也必然存在一定的关系；反之亦然。 设数列的生成函数为，数列的生成函数为，我们可以得到生成函数的如下一些性质： 性质1 若 则 证明 由

5、假设条件，有 性质2 若则 证明 类似于性质1的证明。 性质3 若，则 证明 给等式的两端都乘以，得 把以上各式的两边分别相加，得 性质4 若，则 这里，是收敛的。 证明 因为收敛，所以是存在的，于是有 把以上各式的两边分别相加，得 性质5 若，则 证明 由的定义知 性质6 若，则 证明 由假设条件，有 性质7 若，则 性质8 若，则 性质9 若，为常数，则。 性质7和性质8可以形式幂级数的数乘、加法及乘法运算的定义直接得出。 利用这些性质，我们可以某些数列的生成函数，也可以计算数列的和。下面列出几个常见的简单数列的生成函数，其中： （1） （2） （3） （4） （5） （6） （7） （8

6、） （9） 下面证明其中的几个：证明 （3）（5） （6）设 则所以 故 例5.2.1 求的生成函数例5.1.4 已知的生成函数为 求，解 用部分分式的方法得 而 所以有 例5.1.5 计算级数 的和。 解 由前面列出的第（5）个数列的生成函数知，数列的生成函数为 此处，令 则 由性质3即得数列的生成函数为 比较等式两边的系数，便得 5.2 组合数的生成函数我们在前面几章中讨论过三种不同类型的组合问题：（1） 求的组合数；（2） 求的组合数；（3） 求的10组合数。其中，问题（1）是普通集合的组合问题；问题（2）转化为不定方程的非负整数解的个数问题；问题（3）是第四章的例子，利用容斥原理来计数

7、。它们在解题方法上各不相同。下面我们将看到，引入生成函数的概念后，上述三类组合问题可以统一地处理。 定理 5.3.1 设多重集，且，则S的k可重组合数对应序列的生成函数为 其中，k可重组合数为展开式中的系数。 证明 令中各的项分别对应诸元素的某种可能取法。例如，对表示元素选取了次。依次类推。 显见展开式中的项具有一般形式 其中 对此方程的一非负整数解（在前提下），乘积就对应了诸元素的一种可重取法。合并同类项后，的系数就表示了多重集S中取出k个元素的所有可能的可重组合数。 推论5.2.1 设，若限定元素出现的次数集合为，则从S中取出k个元素的组合数对应序列的生成函数为 我们先从问题（2）开始，令

8、的组合数为，个形式幂级数的乘积就是序列的生成函数： =从而中的系数就是M的k组合数，因此为 这时，我们再次得到了第3章中多重集合M的k组合数的公式，只不过现在是用生成函数获得的。用生成函数方法解问题（3）尤为简单，将的k组合数记为，的生成函数就是 所以，的系数为 与第4章中用容斥原理得到的结果相同。在普通集合的组合中，或者出现或者不出现，故该集合的组合数序列的生成函数为 从而 例5.2.1 设，则S的每个元素至少取一次的k（无限）可重组合数对应序列的生成函数为 其组合数为展开式中的系数。这是由于 例5.2.2 求不定方程的解组数。其中，限制可取0，2，4；可取1，3，5；可取6，7；可取8，9

9、。 解 设不定方程的解组数目为，本例中。注意到对的限制，序列对应的生成函数为 由展开式中的系数知题给不定方程解组数目为。 例5.2.3设有5个红球和8个黄球，要求每次取出不少于2个红球和偶数个黄球，求所有的组合方式数。 解 组合方式数对应序列的生成函数为 因此，总的组合方式数为1+1+28+1+1=20。 例5.2.4 设有红球2个，黑、白球各1个，问 （1）共有多少不同的选取方法？试加以枚举。 （2）若每次从中任取3个，有多少种不同取法？ 解 （1）设用分别代表红、黑、白三种球，两个红球的取法与对应，即红球的可能取法与中r的各次幂一一对应，亦即表示不取红球，表示取1个红球，表示取2个红球。对

10、其它球，依此类推法，则不同选取方法数所形成序列对应的生成函数为 分析上式，不难发现 1：一个球都不取，仅有一种方案； ：取1个球的方案有3种，分别为红，黑，白； ：取2个球的方案有4种，分别为红红，红黑，红白，黑白； ：取3个球的方案有3种，即2红1黑，2红1白，三色球各取其一； ：取4个球的方案仅1种，即所有球全取。若令，即可求得所有不同的选取方案总数为 G（1，1，1）=1 + 3 + 4 + 3 + 1 = 12 （2）若只考虑每次取3个球的方案数，而不需枚举，则可令。写出 由的系数知所求方案为3种。例5.2.5 求不定方程x1+2x2=15的非负整数解的个数a15。解 设ar的生成函数

11、为A（y），则 ,。例5.2.6从n双互不相同的鞋子中取出r只（r=n), 要求其中没有任何两只是成对出现的，问有多少种不同的取法？解（）：令，但同类中的两个是不同的，故其r重组合的生成函数为： 即不同的取法为解（二）：用排列组合法。先从n双鞋中选取r双，共有，再从此r双中每双取出一只，由乘法原理，即得。 22 2 =解（三）：先取出k只左脚的鞋，再在其余双鞋中取出只右脚的鞋，用乘法原理得，则总的取法为：5.3 排列数的指数型生成函数当涉及到与排列有关的问题时，通常使用指数型生成函数。例如元集合的排列数为，按5.5.1小节中方法构成的生成函数为： 没有简单的解析表达式，但如果把基底函数改换成，

12、则 。这启发人们引入指数型生成函数的概念。 数列的指数型生成函数定义为形式幂级数 定理 5.3.1 若元素可重复次，元素可重复次，元素可重复次，则元集的这种可重排列数对应序列的生成函数为 事实上，上式右端等于 由多项式系数的组合学意义知，正是元素出现次，元素出现次，元素出现次的可重排列数。故按所有可能的求和，即得总的k排列数。 推论5.3.1 设，若元素重复出现的次数构成集合，则集S中元素的这种k可重排列数对应序列的生成函数为 k可重排列数为展开式中的系数。 推论5.3.2 设元多重集，且，则S的k可重排列数对应序列的指数型生成函数为 其中，k可重排列数为展开式中系数。 特别地，数列的指数型生

13、成函数具有与指数函数相似的性质： 这是因为 从而 例5.3.1 多重集合的排列数序列的指数型生成函数为 从而 例5.3.2 3个红球，2个黄球，3个蓝球，每次从中取出4个排成一旬，求排列方案数。 解 由推论5.4.2知 故知，从所给n色球取出4个的排列方案有70种。 例5.3.3 由1，2，3，4能组成多少个五位数？要求这些五位数中1出现2次或3次，2最多出现1次，4出现偶数次。 解 根据题意，有 由推论5.4.2知，该排列数的指数型生成函数为 所以的系数为 即满足题意的五位数有140个。 例5.3.4 求的排列中每个至少出现一次的排列数的指数型生成函数。 解 根据题意，有 由推论5.3.2知

14、，排列数序的指数型生成函数为 所以 满足本题条件的排列 可以看成是把个不同的球1，2，k放入n个不的盒子，并且每盒非空的一种放法，即球j放入盒子中，在第2章2.7节中我们知道共有 种放法，由此得出k元集合的n分划数的显式表达式 由此可知，的指数型生成函数为 5.4 Catalan数列与Stirling数列的生成函数 本节介绍Catalan数列和Stirling数列这两种数列的生成函数。5.4.1 Catalan数列的生成函数 Catalan数首先是由Euler在精确计算对凸n边形的不同的对角三角形剖分的个数问题时得到的，它经常出现在组合计数问题中。 例5.5.1在一个凸n边形中，可以用条不在内

15、部相交的对角线将其分成个三角形，问有多少种不同的分法？ 令表示分一个n + 1条边的凸多边形为三角形的方法数，并规定。 当n = 2时，n + 1边形就是三角形，不需要用对角线进行三角形剖分，故。 当，考虑一个凸n + 1边形，它的顶点分别用表示，如图5.5.1所示。取定多边形的一条边，任取多边形的顶点，将分别与之间连线，得三角形T，三角形T将凸n + 1边形分成，和三部分，其中，为k +1边形，为边形。因此，可以用种方法划分，可以用种方法划分，所以 （5.5.1）这正是Catalan数列的形式。TR2R1A1An+1Ak+2AkAk+1图 5.5.1例5.4.2 求n个数的乘积 其中，乘法不

16、满足结合律，不改变名数的顺序，只用括号表示成对的乘积，共有多少种不同的乘法方案？解 设对n个数的乘积有种方式。在的每个格式中，存在着最后的乘法（对应外层的圆括号）： （的格式）（的格式）关于的乘法格式可以有种方式选择，而的乘法格式有种方式选择，对k 取中的任一个，因此有则它与Catalan数满足同一个递推关系。 例题 3.4.1从（0，0）点到（n , n）点的除端点外不接触直线y = x的路径数为，其中，为Catalan数。那么如何求，本节用的生成函数来计算。解 设 解，得 利用牛顿二项式定理，有 因为，开方应该取负号，故舍去，得最后有 或 , 此即Catalan数。由生成函数的一般讨论即知

17、 或 5.4.2 Stirling数列的生成函数 在3.5中已介绍过第二类Stirling数，本节先介绍第一类Stirling数和它的性质，再讨论这两大类Stirling数的生成函数。设有多项式，它的展开式具有下面的形式： - + - ，不考虑各项系数的符号，我们把的系数记作，则上面的式子变成： ，我们称这些数为第一类Stirling数。 第一类Stirling数具有下面的性质。 1、。 证明 为项的系数，即多项式中的常数项，显然为0。 是x项的系数，各因式在相乘时分别贡献负数，从而得到x项。不考虑这些数的符号，它们之积是所以。 是项的系数，显然为1。 是项的系数，为了得到，n个因式中只能有一

18、个因式贡献常数，由加法法则提供常数的总和为 ，所以。 2、第一类Stirling数满足下面的递推关系： 证明 考虑多项式 ，上式两边同乘以得 ，即 ，比较上式两边的系数得 。理解第一类Stirling数的组合意义。 Fibonacci数列，Catalan数列及Stirling数列形成组合数学中三种典型的数列，实际应用中许多组合计数结果都同它们相同或相似。3学时教学目的及要求掌握生成函数的定义、性质、组合数的生成函数、排列数的生成函数、教学重点与难点生成函数方法在组合数和排列数的应用教学手段多媒体参考资料徐利治，蒋茂森，朱自强. 计算组合数学.上海：上海科学出版社，1987庄心谷.组合数学及其在计算机科学中的应用.西安：西安电子科技大学出版社，1989课后小结专心-专注-专业