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

《组合数学第二章1母函数.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

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

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

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

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

5、对应的母函数分别为、不特别说明,下面假设、两个序列2.2母函数的性质2.2母函数的性质性质1:证:若则2.2母函数的性质例.已知则2.2母函数的性质性质2:则若2.2母函数的性质证：2.2母函数的性质例.2.2母函数的性质性质3：若则2.2母函数的性质)::::12102102210100LLLLLLLLLLLLLLLL+++++=++=+==nnaaaabnxaaabxaabxab2.2母函数的性质证：例.已知2.2母函数的性质类似可得：2.2母函数的性质性质4则2.2母函数的性质证2.2母函数的性质2.2母函数的性质例则性质5若则2.2

6、母函数的性质性质5和性质6的结论是显而易见的。性质6若则2.2母函数的性质性质7若则2.2母函数的性质证:2.2母函数的性质已知例.则2.2母函数的性质所谓正整数拆分即把正整数分解成若干整数的和，相当于把n个无区别的球放到n个无标志的盒子，盒子允许空着，也允许放多于一个球。整数拆分成若干整数的和，办法不一，不同拆分法的总数叫做拆分数。拆分可以分为无序拆分和有序拆分；不允许重复的拆分和允许重复的拆分。2.3整数的拆分--2.3.1问题描述2.3.2问题举例例1：若有1克、2克、3克、4克的砝码各一枚，问能称出那几种重量？有几种可能方案？从右端

7、的母函数知可称出从1克到10克，系数便是方案数。例如右端有项，即称出5克的方案有2同样，故称出6克的方案有2，称出10克的方案有12.3.2问题举例例2：求用1分、2分、3分的邮票贴出不同数值的方案数。解:因邮票允许重复，故母函数为2.3.2问题举例以其中x为例，其系数为4，即4拆分成1、2、3之和的拆分数为4，即4例3：若有1克砝码3枚、2克砝码4枚、4克砝码2枚的砝码各一枚，问能称出那几种重量？各有几种方案？2.3.2问题举例解:作目函数2.3.2问题举例2.3.2问题举例2.3.2问题举例2.3.2问题举例例6对N进行无序且允许重复的

8、任意剖分，设剖分数为P(N),求{P(N)}的母函数G(y)。2.3.2问题举例解这相当于把N无序剖分成1,2,3,..,n,…且允许重复，类似上例，我们有例7对N进行无序且允许