母函数整数拆分ppt课件.ppt

《母函数整数拆分ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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点的方法数等价于求母函数的思想很简单—即:把离散数列和幂级数一一对应起来,把离散数列间的相互结合关系对应成为幂级数间的运算关系,最后由幂级数形式来确定离散数列的构造.看下面的例子.中所有的项包括n个元素a1，a2，…an中取两个组合的全体；同理x3项系数包含了从n个元素a1，a2，…an中取3个元素组合全体。以此类推。若令a1=a2=…=an=1，在（2-1-1）式项系数中每一个组合有1个贡献,其

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

4、回路，符号D是一延迟装置，即在时间t输入一个信号给延迟装置D，在t+1时刻D将输出同样的信号，符号表示加法装置DDD输入u输出v显然，一般的有若在时刻，输入信号求相同时刻的输出信号若信号输入的序列u0,u1,…的母函数为U(x)，输出的信号序列v0,v1,…的母函数为V(x)，则其中被装置（图2-12-1）的特性所确定，可以看作是该装置的传递函数，例2：有红球两个，白球、黄球各一个，试求有多少种不同的组合方案。设r，w，y分别代表红球，白球，黄球。由此可见，除一个球也不取的情况外，有：（a）取一个球的组合数为3，即分别取红，白，黄。（b）

5、取两个球的组合数为4，即两个红的，一红一黄，一红一白，一白一黄。（c）取三个球的组合数为3，即两红一黄，两红一白，一红一黄一白。（d）取四个球的组合数为1，即两红一黄一白。的母函数为共有1+3+4+3+1=12种组合方式。令取r的组合数为,则序列例3：某单位有8个男同志，5个女同志，现要组织一个有数目为偶数的男同志和数目不少于2的女同志组成的小组，试求有多少种组成方式？令an为从8位男同志中抽取出n个的允许组合数。由于要男同志的数目必须是偶数。故对应一母函数类似可得女同志的允许组合数对应的母函数为故数列2.2母函数的性质性质1:证:若则例.

6、已知则性质2:则若证：例.性质3：若则)::::12102102210100LLLLLLLLLLLLLLLL+++++=++=+==nnaaaabnxaaabxaabxab证：例.已知类似可得：性质4则证例则性质5若则性质5和性质6的结论是显而易见的。性质6若则性质7若则证:已知例.则所谓正整数拆分即把正整数分解成若干整数的和，相当于把n个无区别的球放到n个无标志的盒子，盒子允许空着，也允许放多于一个球。整数拆分成若干整数的和，办法不一，不同拆分法的总数叫做拆分数。拆分可以分为无序拆分和有序拆分；不允许重复的拆分和允许重复的拆分。2.3整数

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

8、剖分后的正整数都是奇数，求这种剖分方案数{P0(N)}的母函数G0(x).解：这是把N剖分成1,3,5,…,且允许重复。类似于上例，我们有例7对N进行无序剖分，使得剖分后的整数都