1、2.1 2.1 母函数母函数 母函数方法是一套非常有用方法，应用极广。这套方法系统叙述，最早见于Laplace在1812年名著概率解析理论。两个骰子掷出6点，有多少种选法？我们来看以下例子我们来看以下例子第1页我们也能够从另一角度来看，要使两个骰子掷出6点，第一个骰子除了6以外都可选，这有5种选法，一旦第一个选定，第二个骰子就只有一个可能选法，按乘法法则有51=5种。注意到，出现1，5有两种选法，出现2，4也有两种选法，而出现3，3只有一个选法，这些选法互斥且穷尽了出现6点一切可能选法，按加法法则，共有2+2+1=5种不一样选法。第2页 但碰到用三个或四个骰子掷出n点，上述两方法就不胜其烦了。
2、这就需要引进新方法。第3页若有两个骰子，则第4页这种对应把组合问题加法法则和幂级数t乘幂相加对应起来。故使两个骰子掷出6点方法数等价于求第5页母函数思想很简单 即:把离散数列和幂级数一一对应起来,把离散数列间相互结合关系对应成为幂级数间运算关系,最终由幂级数形式来确定离散数列结构.看下面例子.第6页中全部项包含 n个元素a1，a2，an中取两个组合全体；同理 x3 项系数包含了从 n个元素a1，a2，an中取3个元素组合全体。以这类推。若令a1=a2=an=1，在（2-1-1）式项系数中每一个组合有1个贡献,其它各项以这类推.第7页故有：另首先：第8页比较等号两端项对应系数，可得一等式第9页一
3、样对于（设）比较等式两端常数项，即得公式第10页又如在等式中令x=1 可得第11页(2-1-2)式等号两端对x求导可得：等式(2-1-5)两端令x=1，得：第12页 用类似方法还能够得到：第13页已可见函数还能够类似地推出一些等式，但经过上面一些例子关系时所起作用。对其它序列也有一样结果。现引进母函数概念以下：在研究序列称函数G(x)是序列母函数母函数定义：定义：对于序列结构一函数第14页 如若已知序列 则对应母函数G(x)便可依据定义给出。反之，如若以求得序列母函数G(x)，则该序列也随之确定。第15页 例例1 1：下列图是一逻辑回路，符号D是一延迟装置，即在时间t输入一个信号给延迟装置D，
4、在t+1时刻D将输出一样信号，符号表示加法装置DDD输入u输出v第16页显然，普通有若在时刻，输入信号求相同时刻输出信号第17页 若信号输入序列u0,u1,母函数为U(x)，输出信号序列v0,v1,母函数为V(x)，则其中被装置（图 2-12-1）特征所确定，能够看作是该装置传递函数，第18页 例例2 2：有红球两个，白球、黄球各一个，试求有多少种不一样组合方案。设r，w，y 分别代表红球，白球，黄球。第19页由此可见，除一个球也不取情况外，有：（a）取一个球组合数为3，即分别取红，白，黄。（b）取两个球组合数为4，即两个红，一红一黄，一红一白，一白一黄。（c）取三个球组合数为3，即两红一黄，
5、两红一白，一红一黄一白。（d）取四个球组合数为1，即两红一黄一白。第20页母函数为共有1+3+4+3+1=12种组合方式。令取r组合数为 ,则序列第21页 例例3 3：某单位有8个男同志，5个女同志，现要组织一个有数目为偶数男同志和数目不少于2女同志组成小组，试求有多少种组成方式？令an为从8位男同志中抽取出n个允许组合数。因为要男同志数目必须是偶数。故第22页对应一母函数类似可得女同志允许组合数对应母函数为 故数列第23页第24页2.2 2.2 母函数性质母函数性质第25页性质性质1:证证:若则第26页 例例.已知则第27页 性质性质2:则若第28页证：证：第29页 例例.第30页性质性质3
6、：若则第31页 ):1 2102102210100LLLLLLLLLLLLLLLL+=+=+=nnaaaabnxaaabxaabxab证：证：第32页 例例.已知第33页类似可得：第34页性质4则第35页证第36页第37页 例例则性质性质5 5若则第38页性质5和性质6结论是显而易见。性质性质6 6若则第39页性质性质7 7若则第40页证证:第41页已知例例.则第42页 所谓正整数拆分即把正整数分解成若干整数和，相当于把n个无区分球放到n个无标志盒子，盒子允许空着，也允许放多于一个球。整数拆分成若干整数和，方法不一，不一样拆分法总数叫做拆分数。拆分能够分为无序拆分和有序拆分；不允许重复拆分和允
7、许重复拆分。2.3 2.3 整数拆分整数拆分-2.3.12.3.1问题描述问题描述第43页2.3.2 2.3.2 问题举例问题举例例例1 1 若有1克、2克、3克、4克砝码各一枚，问能称出那几个重量？有几个可能方案？第44页从右端母函数知可称出从1克到10克，系数便是方案数。比如右端有 项，即称出5克方案有2一样，故称出6克方案有2，称出10克方案有1第45页例例2 2 求用1分、2分、3分邮票贴出不一样数 值方案数。解:因邮票允许重复，故母函数为 以其中x 为例，其系数为4，即4拆分成1、2、3之和拆分数为4，即4第46页例例3 3 若有1克砝码3枚、2克砝码4枚、4克砝 码2枚，问能称出那
8、几个重量？各有几个 方案？解:作母函数第47页第48页第49页第50页第51页例6 对N进行无序且允许重复剖分，使得剖分后正整数都是奇数，求这种剖分方案数P0(N)母函数G0(x).解解：这是把N剖分成1,3,5,且允许重复。类似于上例，我们有第52页例7 对N进行无序剖分，使得剖分后整数 都是2幂，求这种剖分方法数Pt(N)母 函数Gt(x).解解：这相当于把N剖分成1,2,4,8,16,但不允许重复，类似于(a)可得第53页例8 整数n拆分成1，2，3，m和，并允许重复，若其中m最少出现一次，其母函数怎样？若整数n拆分成1，2，3，m和，并允许重复，由(d)式，其母函数为：第54页若拆分中
9、m最少出现一次，其母函数则为：第55页等式(g)组合意义：即整数n拆分成1到m和拆分数减去拆分成1到m-1和拆分数，即为最少出现一个m拆分数。显然有第56页定理定理1 整数剖分成不一样数和剖分数等于剖分成奇数剖分数.证实：设bN表示N剖分成不一样正整数和剖分数，则序列bN母函数为第57页定理定理2 N剖分成其它数之和但重复数不超出2，其剖分数等于它剖分成不被3整除数和剖分数。证实：N剖分成其它数之和但重复数不超出2剖分数所组成序列母函数为第58页第59页定理定理3 N被剖分成其重复度不超出k次数和，其剖分数等于被剖分成不被k+1除尽数和剖分数。定理定理4 对一切N，有Pt(N)=1.第60页例9 若有1、2、4、8、16、32克砝码各一枚,问能称出那几个重量？有几个可能方案？第61页从母函数能够得知，用这些砝码能够称出从1克到63克重量，而且方法都是唯一。这问题能够推广到证实任一十进制数n可表示为而且是唯一。第62页
