母函数与指数型母函数.ppt

第二章第二章 母函数与递推关系母函数与递推关系2.1 母函数与指数型母函数母函数与指数型母函数2.2 递推关系与递推关系与Fibonacci数列数列2.3 线性常系数递推关系线性常系数递推关系2.4 非线性递推关系举例非线性递推关系举例2.5 应用举例应用举例2.1 母函数与指数型母函数母函数与指数型母函数1.母函数母函数2.母函数的性质母函数的性质3.整数的拆分整数的拆分4.Ferrers 图像图像5.指数型母函数指数型母函数1.母函数母函数母函数方法是一套非常有用的方法，应用极广。这母函数方法是一套非常有用的方法，应用极广。这套方法的系统叙述，最早见于套方法的系统叙述，最早见于Laplace在在1812年的年的名著名著概率解析理论。概率解析理论。我们来看如下的例子我们来看如下的例子：两个骰子掷出两个骰子掷出6点，有多少点，有多少种选法？种选法？注意到，出现注意到，出现1，5有两种选法，出现有两种选法，出现2，4也有两也有两种选法，而出现种选法，而出现3，3只有一种选法，按加法法则，只有一种选法，按加法法则，共有共有2+2+1=5种不同选法。种不同选法。或者，第一个骰子除了或者，第一个骰子除了6以外都可选，有以外都可选，有5种选法，种选法，一旦第一个选定，第二个骰子就只有一种可能的选一旦第一个选定，第二个骰子就只有一种可能的选法，按乘法法则有法，按乘法法则有51=5种。种。但碰到用三个或四个骰子掷出但碰到用三个或四个骰子掷出n点，上述两方法就点，上述两方法就不胜其烦了。不胜其烦了。设想把骰子出现的点数设想把骰子出现的点数1,2,6和和t,t2,t6对应起来，对应起来，则每个骰子可能出现的点数与则每个骰子可能出现的点数与(t+t2+t6)中中t的各次的各次幂一一对应。幂一一对应。若有两个骰子，则若有两个骰子，则其中其中t6的系数为的系数为5，显然来自于，显然来自于这表明，这表明，掷出掷出6点的方法一一对应于得到点的方法一一对应于得到t6的方法的方法。故使两个骰子掷出故使两个骰子掷出n点的方法数等价于求点的方法数等价于求中中tn的系数。的系数。这个函数这个函数f(t)称为称为母函数母函数。母函数方法的基本思想：母函数方法的基本思想：把离散数列和幂级数一一对应起来，把离散数列间把离散数列和幂级数一一对应起来，把离散数列间的相互结合关系对应成为幂级数间的运算关系，最的相互结合关系对应成为幂级数间的运算关系，最后由幂级数形式来确定离散数列的构造。后由幂级数形式来确定离散数列的构造。再来看下面的例子：再来看下面的例子：若令若令a1=a2=an=1，则有，则有这就是二项式展开定理。这就是二项式展开定理。比较等号两端项对应系数，可以得到恒等式：比较等号两端项对应系数，可以得到恒等式：比较等式两端的常数项，可以得到恒等式：比较等式两端的常数项，可以得到恒等式：中令中令x=1 可得可得又如在等式又如在等式两端对两端对x求导可得：求导可得：再令再令x=1 可得可得类似还可以得到类似还可以得到还可以类似地推出一些等式，但通过上面一些例子还可以类似地推出一些等式，但通过上面一些例子已可见函数已可见函数(1+x)n在研究序列在研究序列C(n,0),C(n,1),C(n,n)的关系时所起的作用。的关系时所起的作用。定义定义：对于序列：对于序列a0,a1,a2,，函数，函数称为序列称为序列a0,a1,a2,的的母函数母函数。例如例如函数函数(1+x)n就是就是序列序列C(n,0),C(n,1),C(n,n)的的母函数。母函数。如若已知序列，则对应的母函数可根据定义给出。如若已知序列，则对应的母函数可根据定义给出。反之，如果已经求出序列的母函数反之，如果已经求出序列的母函数G(x)，则该序列，则该序列也随之确定。也随之确定。DDD输入输入u输出输出v例例1 下图是一逻辑回路，符号下图是一逻辑回路，符号D是一延迟装置，即是一延迟装置，即在时间在时间t输入一个信号给延迟装置输入一个信号给延迟装置D，在，在t+1时刻时刻D将将输出同样的信号，符号输出同样的信号，符号 表示加法装置。表示加法装置。若在若在t=0,1,2,时刻的输入为时刻的输入为u0,u1,u2,求在这些时求在这些时刻的输出刻的输出v0,v1,v2,显然，显然，一般的有一般的有若信号输入的序列若信号输入的序列u0,u1,的母函数为的母函数为U(x)，输出，输出的信号序列的信号序列v0,v1,的母函数为的母函数为V(x)，则，则其中其中被装置的特性所确定，称为该装置的传递函数。被装置的特性所确定，称为该装置的传递函数。设设r，w，y 分别代表红球，白球，黄球。分别代表红球，白球，黄球。例例2 有红球两个，白球、黄球各一个，试求有多少种有红球两个，白球、黄球各一个，试求有多少种不同的组合方案。不同的组合方案。(1)取一个球的组合数为取一个球的组合数为3，即分别取红，白，黄。，即分别取红，白，黄。(2)取两个球的组合数为取两个球的组合数为4，即两个红的，一红一黄，即两个红的，一红一黄，一红一白，一白一黄。一红一白，一白一黄。(3)取三个球的组合数为取三个球的组合数为3，即两红一黄，两红一白，即两红一黄，两红一白，一红一黄一白。一红一黄一白。(4)取四个球的组合数为取四个球的组合数为1，即两红一黄一白。，即两红一黄一白。共有共有1+3+4+3+1=12种组合方式种组合方式。令取令取r的组合数为的组合数为 ,则序列则序列的母函数为的母函数为令令an为从为从8位男同志中抽取出位男同志中抽取出n个的允许组合数。由个的允许组合数。由于要男同志的数目必须是偶数。故于要男同志的数目必须是偶数。故例例3 某单位有某单位有8个男同志，个男同志，5个女同志，现要组织一个女同志，现要组织一个由数目为偶数的男同志和数目不少于个由数目为偶数的男同志和数目不少于2的女同志的女同志组成的小组，试求有多少种组成方式？组成的小组，试求有多少种组成方式？因此序列因此序列a1,a2,a8对应的母函数为：对应的母函数为：类似可得女同志的允许组合数对应的母函数为类似可得女同志的允许组合数对应的母函数为其中其中xk的系数就是组成符合要求的的系数就是组成符合要求的k人小组的数目。人小组的数目。2.母函数的性质母函数的性质设序列设序列ak,bk对应的母函数分别为对应的母函数分别为A(x),B(x)。则下面的两个性质显然成立：则下面的两个性质显然成立：(1)A(x)=B(x)当且仅当当且仅当 ak=bk。(2)若若A(x)+B(x)=c0+c1x+c2x2+，则，则ck=ak+bk。性质性质1：若：若 则则 B(x)=xlA(x)。证证:则则例例4 已知已知性质性质2：若：若bk=ak+l，则，则则则例例5 已知已知性质性质3：若：若bk=a0+ak，则，则1:x:x2:xk:+)则则例例6 已知已知性质性质4：若：若bk=ak+ak+1+，则，则1:x:x2:+)性质性质5：若：若bk=kak，则，则性质性质6：若：若bk=ak/(1+k)，则，则则则例例7 已知已知性质性质7：若：若ck=a0bk+a1bk-1+ak-1b1+akb0，则，则1:x:x2:+)令令例例8 已知已知则则3.整数的拆分整数的拆分所谓正整数拆分即把正整数分解成若干正整数的和。所谓正整数拆分即把正整数分解成若干正整数的和。相当于把相当于把n个无区别的球放到个无区别的球放到n个无标志的盒子，盒个无标志的盒子，盒子允许空着，也允许放多于一个球。子允许空着，也允许放多于一个球。整数拆分成若干整数的和，办法不一，不同拆分法整数拆分成若干整数的和，办法不一，不同拆分法的总数叫做拆分数。的总数叫做拆分数。拆分可以分为拆分可以分为无序拆分无序拆分和和有序拆分有序拆分；不允许重复的不允许重复的拆分拆分和和允许重复的拆分允许重复的拆分。例例9 若有若有1克、克、2克、克、3克、克、4克的砝码各一枚，问能克的砝码各一枚，问能称出那几种重量？有几种可能方案？称出那几种重量？有几种可能方案？从右端的母函数知可称出从从右端的母函数知可称出从1克到克到10克，系数便是克，系数便是方案数。方案数。例如右端有例如右端有2x5项，即称出项，即称出5克的方案有克的方案有2种：种：5=2+3=1+4。类似的，称出类似的，称出6克的方案也有克的方案也有2种：种：6=2+4=1+2+3。例例10 求用求用1分、分、2分、分、3分的邮票贴出不同数值的方分的邮票贴出不同数值的方案数。案数。以以x4为例，其系数为为例，其系数为4，即，即4拆分成拆分成1，2，3之和的允之和的允许重复的拆分数为许重复的拆分数为4：4=1+1+1+1 =1+1+2 =1+3 =2+2。注意邮票允许重复，因此母函数为：注意邮票允许重复，因此母函数为：例例11 若有若有1克砝码克砝码3枚、枚、2克砝码克砝码4枚、枚、4克砝码克砝码2枚，枚，问能称出那几种质量？各有几种方案？问能称出那几种质量？各有几种方案？即可称出即可称出1至至19克的质量，不同的方案数即为对应项克的质量，不同的方案数即为对应项前面的系数。前面的系数。母函数为：母函数为：例例12 把整数把整数N无序拆分成整数无序拆分成整数a1,a2,an的和，且的和，且不允许重复，求不同的拆分数。不允许重复，求不同的拆分数。的不同解的个数。的不同解的个数。这个问题对应于求不定方程这个问题对应于求不定方程令令bN表示不同的拆分数，则其对应的母函数为：表示不同的拆分数，则其对应的母函数为：特殊的，当特殊的，当ai=i时，对应的母函数为：时，对应的母函数为：例例13 把整数把整数N无序拆分成整数无序拆分成整数a1,a2,an的和，允的和，允许重复，求不同的拆分数。许重复，求不同的拆分数。的不同解的个数。的不同解的个数。这个问题对应于求不定方程这个问题对应于求不定方程令令bN表示不同的拆分数，则其对应的母函数为：表示不同的拆分数，则其对应的母函数为：特殊的，当特殊的，当ai=i时，对应的母函数为：时，对应的母函数为：例例14 把整数把整数N无序拆分成奇整数的和，允许重复，无序拆分成奇整数的和，允许重复，求不同的拆分数。求不同的拆分数。这相当于在上例中把这相当于在上例中把ai取成奇数，因此拆分数对应取成奇数，因此拆分数对应的母函数为：的母函数为：例例15 把整数把整数N无序拆分成无序拆分成2的幂次的和，求不同的拆的幂次的和，求不同的拆分数。分数。这相当于把这相当于把N拆分成拆分成1,2,4,8,的和，但的和，但不允许重复不允许重复。因此拆分数对应的母函数为：因此拆分数对应的母函数为：例例16 把整数把整数N无序拆分无序拆分1,2,m的和，允许重复，求的和，允许重复，求不同的拆分数。若要求不同的拆分数。若要求m至少出现一次呢？至少出现一次呢？若无要求，由例若无要求，由例13可知其母函数为：可知其母函数为：若要求若要求m至少出现一次，则拆分数对应的母函数为：至少出现一次，则拆分数对应的母函数为：这个等式的组合意义很明显：整数这个等式的组合意义很明显：整数n拆分成拆分成1到到m的的和的拆分数减去拆分成和的拆分数减去拆分成1到到m-1的和的拆分数，即为的和的拆分数，即为至少出现一个至少出现一个m的拆分数。的拆分数。显然有显然有设设bN表示表示N剖分成不同正整数和的剖分数，则其对剖分成不同正整数和的剖分数，则其对应的母函数为：应的母函数为：定理定理1 整数剖分成不同整数的和的剖分数整数剖分成不同整数的和的剖分数(不允许重不允许重复复)等于剖分成奇数的剖分数等于剖分成奇数的剖分数(允许重复允许重复)。设设bN表示表示N剖分成剖分成重复数不超过重复数不超过2的的正整数之和的剖正整数之和的剖分数，则其对应的母函数为：分数，则其对应的母函数为：定理定理2 N剖分成其他数之和但重复数不超过剖分成其他数之和但重复数不超过2，其剖，其剖分数等于它剖分成不被分数等于它剖分成不被3整除的数的和的剖分数。整除的数的和的剖分数。定理定理3 N被剖分成一些重复次数不超过被剖分成一些重复次数不超过k次的整数的次的整数的和，其剖分数等于被剖分成不被和，其剖分数等于被剖分成不被k+1除尽的数的和的除尽的数的和的剖分数剖分数。定理定理4 对任意整数对任意整数N，它被无序剖分成，它被无序剖分成2的幂次的和的幂次的和的剖分方式一定唯一。的剖分方式一定唯一。例例17 若有若有1、2、4、8、16克的砝码各一枚，问能称克的砝码各一枚，问能称出那几种质量？有几种可能方案？出那几种质量？有几种可能方案？这说明用这些砝码可以称出从这说明用这些砝码可以称出从1克到克到31克的质量，而克的质量，而且方案都是唯一的。且方案都是唯一的。实际上这说明整数的实际上这说明整数的二进制表示是唯一二进制表示是唯一的。的。4.Ferrers图像图像一个从上而下的一个从上而下的n层格子组成的图像，层格子组成的图像，mi为第为第i层的层的格子数。格子数。当当mimi+1，即上层的格子数不少于下层的格子数时，即上层的格子数不少于下层的格子数时，称之为称之为Ferrers图像，如下图：图像，如下图：每一层至少有一个格子。每一层至少有一个格子。绕虚线轴旋转所得的图绕虚线轴旋转所得的图仍然是仍然是Ferrers图像。这图像。这样的两个样的两个Ferrers图像称图像称为一对为一对共轭共轭的的Ferrers图图像。像。(1)整数整数n拆分成拆分成k个数的和的拆分数，与数个数的和的拆分数，与数n拆分成拆分成最大数为最大数为k的拆分数相等。的拆分数相等。因为整数因为整数n拆分成拆分成k个数的和的拆分可以用一个个数的和的拆分可以用一个k行的行的图像表示。所得的图像表示。所得的Ferrers图像的共轭图像最上面一图像的共轭图像最上面一行有行有k个格子。例如：个格子。例如：利用利用Ferrers图像可以得到一些关于整数拆分的结果：图像可以得到一些关于整数拆分的结果：24=6+6+5+4+3 5个数，最大数为个数，最大数为6 24=5+5+5+4+3+2 6个数，最大数为个数，最大数为5理由和理由和(1)相类似。相类似。因此，拆分成最多不超过因此，拆分成最多不超过m个数的和的拆分数的母个数的和的拆分数的母函数是：函数是：(2)整数整数n拆分成最多不超过拆分成最多不超过m个数的和的拆分数，个数的和的拆分数，与与n拆分成最大不超过拆分成最大不超过m的拆分数相等。的拆分数相等。正好拆分成正好拆分成m个数的和的拆分数的母函数为个数的和的拆分数的母函数为(3)整数整数n拆分成互不相同的若干奇数的和的的拆拆分成互不相同的若干奇数的和的的拆分数，与分数，与n拆分成自共轭的拆分成自共轭的Ferrers图像的拆分数图像的拆分数相等。相等。设整数设整数n拆分为拆分为n=(2n1+1)+(2n2+1)+(2nk+1)，其，其中中n1n2nk。构造一个构造一个Ferrers图像，第一行第一列都是图像，第一行第一列都是n1+1格，格，对应于对应于2n1+1，第二行第二列都是，第二行第二列都是n2+1格，对应于格，对应于 2n2+1，依此类推。，依此类推。这样得到的这样得到的Ferrers图像一定是自共轭的。图像一定是自共轭的。反过来，自共轭的反过来，自共轭的Ferrers图像也可以对应到一些不图像也可以对应到一些不同奇数的和。同奇数的和。例如例如17=9+5+3对应的对应的Ferrers图像为：图像为：(4)正整数正整数n剖分成不超过剖分成不超过k个数的和的剖分数，等于个数的和的剖分数，等于将将n+k剖分成恰好剖分成恰好k个数的剖分数。个数的剖分数。不超过不超过k层的层的Ferrers图像的每一层加上一个格子，图像的每一层加上一个格子，一一对应到一个刚好一一对应到一个刚好k层的层的Ferrers图像。图像。5.指数型母函数指数型母函数考虑考虑n个元素组成的多重集，其中个元素组成的多重集，其中a1重复了重复了n1次，次，a2 重复了重复了n2次，次，ak重复了重复了nk次，次，n=n1+n2+nk。从中取从中取r个排列，求不同的排列数。个排列，求不同的排列数。若若r=n，即考虑，即考虑n个元素的全排列，则不同的排列数个元素的全排列，则不同的排列数为：为：但是对于一般的但是对于一般的r，情况就比较复杂了。，情况就比较复杂了。876543232543232232369109631)1()23321()1)(1)(1()(xxxxxxxxxxxxxxxxxxxxxxxxxG+=+=+=先看一个具体的问题：假设有先看一个具体的问题：假设有8个元素，其中个元素，其中a1重复重复3次，次，a2重复重复2次，次，a3重复重复3次。从中取次。从中取r个组合，其个组合，其组合数为组合数为cr，则其对应的母函数为：，则其对应的母函数为：从从x4的系数可知，从这的系数可知，从这8个元素中取个元素中取4个组合，不同个组合，不同的组合数为的组合数为10。这这10个组合可从下面的展开式中得到：个组合可从下面的展开式中得到：其中其中4次方项表示了所有从次方项表示了所有从8个元素中取个元素中取4个的组合方个的组合方案。案。例如例如 表示一个表示一个a1三个三个a3的组合，的组合，表示两个表示两个a1两个两个a3的组合，依此类推。的组合，依此类推。接下来讨论从这接下来讨论从这8个元素中取个元素中取4个的不同排列总数。个的不同排列总数。以以两个两个a1两个两个a3组合组合为例，不同排列数为为例，不同排列数为4!/(2!2!)。同样一个同样一个a1三个三个a3的不同排列数为的不同排列数为4!/(1!3!)。依此类推可以得到不同的排列总数为：依此类推可以得到不同的排列总数为：为了便于计算，利用上述特点，形式地引进函数为了便于计算，利用上述特点，形式地引进函数从右边很容易可以看出，取从右边很容易可以看出，取2个的排列数为个的排列数为9，取，取3个个的排列数为的排列数为28，取，取4个的排列数为个的排列数为70依此类推。依此类推。定义定义：对于序列：对于序列a0,a1,a2,，函数，函数称为序列称为序列a0,a1,a2,对应的对应的指数型母函数指数型母函数。这样，对于一个多重集，其中这样，对于一个多重集，其中a1重复重复n1次，次，a2 重复重复n2次，次，ak重复重复nk次，次，从中取从中取r个排列的不同排列个排列的不同排列数所对应的指数型母函数为：数所对应的指数型母函数为：例例18 求下列数列的指数型母函数：求下列数列的指数型母函数：例例19 由由1，2，3，4四个数字组成的五位数中，要求四个数字组成的五位数中，要求数数1出现次数不超过出现次数不超过2次，但不能不出现；次，但不能不出现；2出现次数出现次数不超过不超过1次；次；3出现次数最多出现次数最多3次，可以不出现；次，可以不出现；4出出现次数为偶数。求满足上述条件的数的个数。现次数为偶数。求满足上述条件的数的个数。设满足上述条件的设满足上述条件的r位数个数为位数个数为cr，则其对应的指数，则其对应的指数型母函数为：型母函数为：由此可见满足条件的由此可见满足条件的5位数共位数共215个。个。例例20 求由求由1，3，5，7，9五个数字组成的五个数字组成的n位数的个位数的个数，要求其中数，要求其中3，7出现的次数为偶数，其他出现的次数为偶数，其他1，5，9出现次数不加限制。出现次数不加限制。设满足上述条件的设满足上述条件的n位数个数为位数个数为cn，则其对应的指数，则其对应的指数型母函数为：型母函数为：因此因此例例21 7个有区别的球放进个有区别的球放进4个有标志的盒子里，要求个有标志的盒子里，要求1，2两个盒子必须有偶数个球，第两个盒子必须有偶数个球，第3个盒子有奇数个个盒子有奇数个球，求不同的方案个数。球，求不同的方案个数。这相当于从这相当于从1234这这4个数中取个数中取7个做允许重复的排列，个做允许重复的排列，即每个数字对应于每个球所放的盒子的序号。即每个数字对应于每个球所放的盒子的序号。这样的排列数所对应的指数型母函数为：这样的排列数所对应的指数型母函数为：因此因此例例22 r个有标志的球放进个有标志的球放进n个不同的盒子里，要求无个不同的盒子里，要求无一空盒，问有多少种不同的分配方案？一空盒，问有多少种不同的分配方案？这相当于从这相当于从1到到n这这n个数字中取个数字中取r个做允许重复的排个做允许重复的排列，即每个数字对应于每个球所放的盒子的序号。列，即每个数字对应于每个球所放的盒子的序号。这样的排列数所对应的指数型母函数为：这样的排列数所对应的指数型母函数为：要求无一空盒即相当于要求每个数字至少出现一次。要求无一空盒即相当于要求每个数字至少出现一次。因此因此