组合数学第二章1母函数.ppt

《组合数学第二章1母函数.ppt》由会员分享，可在线阅读，更多相关《组合数学第二章1母函数.ppt（71页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、2.1 2.1 母函数母函数 母函数方法是一套非常有用的方法，应用极广。这套方法的系统叙述，最早见于Laplace在1812年的名著概率解析理论。两个色子掷出6点，有多少种选法？我们来看如下的例子我们来看如下的例子方法的引入我们也可以从另一角度来看，要使两个色子掷出6点，第一个色子除了6以外的都可选，这有5种选法，一旦第一个选定，第二个色子就只有一种可能的选法按乘法法则有5*1=5种注意到，出现1，5有两种选法，出现2，4也有两种选法，而出现3，3只有一种选法，这些选法互斥且穷尽了出现6点的一切可能的选法，按加法法则，共有2+2+1=5种不同选法。但碰到用三个或四个色子掷出n点，上述两方法就不

2、胜其烦了。这就需要引进新的方法。这种对应把组合问题的加法法则和幂级数的t的乘幂的相加对应起来。故使两个色子掷出6点的方法数等价于求母函数的思想很简单 即:把离散数列和幂级数一一对应起来,把离散数列间的相互结合关系对应成为幂级数间的运算关系,最后由幂级数形式来确定离散数列的构造.看下面的例子.2.1 2.1 母函数母函数中所有的项包括 n个元素a1，a2，an中取两个组合的全体；同理 x3 项系数包含了从 n个元素a1，a2，an中取3个元素组合全体。以此类推。若令a1=a2=an=1，在（2-1-1）式项系数中每一个组合有1个贡献,其他各项以此类推.2.1 2.1 母函数母函数故有：另一方面：

3、比较等号两端项对应系数，可得一等式2.1 2.1 母函数母函数用类似的方法可得等式：证法如下：同样对于（设）比较等式两端的常数项，即得公式(2-1-3)又如等式：令x=1 可得(2-1-2)式等号的两端对x求导可得：等式(2-1-5)两端令x=1，得：2.1 2.1 母函数母函数 用类似的方法还可以得到：2.1 2.1 母函数母函数已可见函数还可以类似地推出一些等式，但通过上面一些例子的关系时所起的作用。对其他序列也有同样的结果。现引进母函数概念如下：在研究序列称函数G(x)是序列的母函数母函数定义：定义：对于序列构造一函数。2.1 2.1 母函数母函数 如若已知序列 则对应的母函数G(x)便

4、可根据定义给出。反之，如若以求得序列的母函数G(x)，则该序列也随之确定。序列可记为2.22.2 母函数的性质母函数的性质 一个序列和它的母函数一一对应。给了序列便得知它的母函数；反之，求得母函数序列也随之而定。这种关系颇像数学中的积分变换，特别酷似离散序列的Z变换。如前的例子所示的那样，为了求满足某种递推关系的序列，可把它转换为求对应的母函数G(x)，G(x)可能满足一代数方程，或代数方程组，甚至于是微分方程。最后求逆变换，即从已求得的母函数G(x)得到序列an。关键在于要搭起从序列到母函数，从母函数到序列这两座桥。这一节便是以此为目的的。对应的母函数分别为、不特别说明,下面假设、两个序列2

5、.22.2 母函数的性质母函数的性质2.2 2.2 母函数的性质母函数的性质性质性质1:证证:若则2.22.2 母函数的性质母函数的性质 例例.已知则2.22.2 母函数的性质母函数的性质 性质性质2:则若2.22.2 母函数的性质母函数的性质证：证：2.22.2 母函数的性质母函数的性质 例例.2.22.2 母函数的性质母函数的性质性质性质3：若则2.22.2 母函数的性质母函数的性质 ):1 2102102210100LLLLLLLLLLLLLLLL+=+=+=nnaaaabnxaaabxaabxab2.22.2 母函数的性质母函数的性质证：证：例例.已知2.22.2 母函数的性质母函数的

6、性质类似可得：2.22.2 母函数的性质母函数的性质性质4则2.22.2 母函数的性质母函数的性质证2.22.2 母函数的性质母函数的性质2.22.2 母函数的性质母函数的性质 例例则性质性质5 5若则2.22.2 母函数的性质母函数的性质性质5和性质6的结论是显而易见的。性质性质6 6若则2.22.2 母函数的性质母函数的性质性质性质7 7若则2.22.2 母函数的性质母函数的性质证证:2.22.2 母函数的性质母函数的性质已知例例.则2.22.2 母函数的性质母函数的性质 所谓正整数拆分即把正整数分解成若干整数的和，相当于把n个无区别的球放到n个无标志的盒子，盒子允许空着，也允许放多于一个

7、球。整数拆分成若干整数的和，办法不一，不同拆分法的总数叫做拆分数。拆分可以分为无序拆分和有序拆分；不允许重复的拆分和允许重复的拆分。2.3 2.3 整数的拆分整数的拆分-问题描述问题描述2.3.2 2.3.2 问题举例问题举例例例1 1：若有1克、2克、3克、4克的砝码各一枚，问能称出那几种重量？有几种可能方案？从右端的母函数知可称出从1克到10克，系数便是方案数。例如右端有 项，即称出5克的方案有2同样，故称出6克的方案有2，称出10克的方案有12.3.2 2.3.2 问题举例问题举例例例2 2：求用1分、2分、3分的邮票贴出不同数值的方案数。解:因邮票允许重复，故母函数为2.3.2 2.3

8、.2 问题举例问题举例 以其中x 为例，其系数为4，即4拆分成1、2、3之和的拆分数为4，即4例例3 3：若有1克砝码3枚、2克砝码4枚、4克砝码2枚的砝码各一枚，问能称出那几种重量？各有几种方案？2.3.2 2.3.2 问题举例问题举例解:作目函数2.3.2 2.3.2 问题举例问题举例2.3.2 2.3.2 问题举例问题举例2.3.2 2.3.2 问题举例问题举例2.3.2 2.3.2 问题举例问题举例例 6 对N进行无序且允许重复的任意剖分，设剖分数为P(N),求P(N)的母函数G(y)。2.3.2 2.3.2 问题举例问题举例解 这相当于把N无序剖分成1,2,3,.,n,且允许重复，类

9、似上例，我们有例 7 对N进行无序且允许重复的剖分，使得剖分后的正整数都是奇数，求这种剖分方案数P0(N)的生成函数G0(y).2.3.2 2.3.2 问题举例问题举例解：这是把N剖分成1,3,5,且允许重复。类似于上例，我们有例 8 对N进行无序剖分,使得剖分后的整数各不相等,求这种剖分方案数Pd(N)的生成函数Gd(y)2.3.2 2.3.2 问题举例问题举例解：这相当于把N剖分成1,2,3,.,n,且不允许重复，类似于(b)式，有例 9 对N进行无序剖分，使得剖分后的整数都是2的幂，求这种剖分方法数Pt(N)的母函数Gt(y).2.3.2 2.3.2 问题举例问题举例解：这相当于把N剖分

10、成1,2,4,8,16,但不允许重复，类似于(a)可得例例10:整数n拆分成1，2，3，m的和，并允许重复，若其中m至少出现一次，其母函数如何？若整数n拆分成1，2，3，m的和，并允许重复，由(d)式，其母函数为：2.3.2 2.3.2 问题举例问题举例若拆分中m至少出现一次，其母函数则为：2.3.2 2.3.2 问题举例问题举例等式(g)的组合意义：即整数n拆分成1到m的和的拆分数减去拆分成1到m-1的和的拆分数，即为至少出现一个m的拆分数。2.3.2 2.3.2 问题举例问题举例显然有从以上例子可以归结如下的结论2.3.2 2.3.2 问题举例问题举例定理1 整数剖分成不同数的和的剖分数等

11、于剖分成奇整数的剖分数.2.3.2 2.3.2 问题举例问题举例证明：设bN表示N剖分成不同正整数和的剖分数，则序列bN的生成函数为定理 2 N剖分成其他数之和但重复数不超过2，其剖分数等于它剖分成不被3整除的数的和的剖分数2.3.2 2.3.2 问题举例问题举例证明：N剖分成其他数之和但重复数不超过2的剖分数所构成序列的母函数为2.3.2 2.3.2 问题举例问题举例2.3.2 2.3.2 问题举例问题举例定理 3 N被剖分成其重复度不超过k次的数的和，其剖分数等于被剖分成不被k+1除尽的数的和的剖分数。定理4 对一切N，有Pt(N)=1.2.3.2 2.3.2 问题举例问题举例定理 5 设

12、Pod(N)=N被剖分成奇数个不同正整数 的和的剖分数；Pev(N)=N被剖分成偶数个不同正整数 的和的剖分数，则2.3.2 2.3.2 问题举例问题举例定理6 对一切N，有例例11：若有1、2、4、8、16、32克的砝码各一枚,问能称出那几种重量？有几种可能方案？2.3.2 2.3.2 问题举例问题举例从母函数可以得知，用这些砝码可以称出从1克到63克的重量，而且办法都是唯一的。这问题可以推广到证明任一十进制数n,可表示为而且是唯一的。2.3.2 2.3.2 问题举例问题举例2.4 Ferrers2.4 Ferrers图像图像 一个从上而下的n层格子，mi为第i层的格子数，当 ，即上层的格子

13、数不少于下层的格子数时，称之为FerrersFerrers图像，如图(2-4-1)示。图 2-4-1 Ferrers图像具有如下性质：1.每一层至少有一个格子。2.第一行与第一列互换，第二行于第二列互换，即图(2-4-1)绕虚线轴旋转所得的图仍然是Ferrers图像。两个Ferrers 图像称为一对共轭的Ferrers图像。2.4 Ferrers2.4 Ferrers图像图像 利用Ferrers图像可得关于整数拆分的十分有趣的结果。(a)整数n拆分成k个数的和的拆分数，和数n拆分成最大数为k的拆分数相等。因整数n拆分成k个数的和的拆分可用一k行的图像表示。所得的Ferrers图像的共轭图像最上

14、面一行有k个格子。例如：2.4 Ferrers2.4 Ferrers图像图像 24=6+6+5+4+3 5个数，最大数为6 24=5+5+5+4+3+2 6个数，最大数为5图(2-4-2)2.4 Ferrers2.4 Ferrers图像图像(b)整数n拆分成最多不超过m个数的和的拆分数，和n拆分成最大不超过m的拆分数相等。理由和(a)相类似。因此，拆分成最多不超过m个数的和的拆分数的母函数是2.4 Ferrers2.4 Ferrers图像图像拆分成最多不超过m-1个数的和的拆分数的母函数是所以正好拆分成m个数的和的拆分数的母函数为2.4 Ferrers2.4 Ferrers图像图像2.4 Fe

15、rrers2.4 Ferrers图像图像(c)整数n拆分成互不相同的若干奇数的和的的拆分数,和n拆分成自共轭的Ferrers图像的拆分数相等.构造一个Ferrers图像，其第一行，第一列都是 格，对应于 ，第二行，第二列各 格，对应于 。以此类推。由此得到的Ferres图像是共轭的。反过来也一样。2.4 Ferrers2.4 Ferrers图像图像，。设其中例如对应为Ferrers图像为9+5+3=17图(2-4-3)2.4 Ferrers2.4 Ferrers图像图像利用Ferrers图像可以证明定理定理 4 正整数N剖分成不超过k个数的和的剖分数等于将N+k剖分成恰好k个数的剖分数2.4 Ferrers2.4 Ferrers图像图像