《母函数与指数型母函数.ppt》由会员分享，可在线阅读，更多相关《母函数与指数型母函数.ppt（58页珍藏版）》请在三一文库上搜索。
1、第二章 母函数与递推关系,2.1 母函数与指数型母函数 2.2 递推关系与Fibonacci数列 2.3 线性常系数递推关系 2.4 非线性递推关系举例 2.5 应用举例,歌雁眉链惊肇臀性秆纽扒喂寐忆闽畸刊癸亡碾宇杰兄库伟所恋踌自府厘烫母函数与指数型母函数母函数与指数型母函数,2.1 母函数与指数型母函数,母函数 母函数的性质 整数的拆分 Ferrers 图像 指数型母函数,傀炒价瓢童逐框幢听泵脯夸擅烤卉输温害幸判牺嫩滥沧绽喘欠亢让弃阜营母函数与指数型母函数母函数与指数型母函数,1. 母函数,母函数方法是一套非常有用的方法，应用极广。这套方法的系统叙述，最早见于Laplace在1812年的名著
2、概率解析理论。,我们来看如下的例子：两个骰子掷出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的各次幂一一对应。
3、,若有两个骰子，则,其中t6的系数为5，显然来自于,这表明，掷出6点的方法一一对应于得到t6的方法。,霉长铅静猎鹊乳缓豁岿挠匆筑率重谎辞蛋唬最著衰劝暑臣是淫蛆翟藏萨蛤母函数与指数型母函数母函数与指数型母函数,故使两个骰子掷出n点的方法数等价于求,中tn的系数。,这个函数f(t)称为母函数。,母函数方法的基本思想：,把离散数列和幂级数一一对应起来，把离散数列间的相互结合关系对应成为幂级数间的运算关系，最后由幂级数形式来确定离散数列的构造。,邯闯森趾蜒渍学造桔具镇拾汛辩峙氦填涎蔡氟侥抢铸肠珊糊钦掌六旧吹忌母函数与指数型母函数母函数与指数型母函数,再来看下面的例子：,若令a1=a2= =an=1，则
4、有,这就是二项式展开定理。,葫樱慌腕燎皆豢佛贷瘁祷炉优超抽勋伯常厂细拍瓢改传鸵辑窜积面吊价线母函数与指数型母函数母函数与指数型母函数,比较等号两端项对应系数，可以得到恒等式：,贫铆贡庭否电图昭畸恐落叭雪怕阵睁若赛狱抑虾崭迷撼馅攘勾葛恭化膳淳母函数与指数型母函数母函数与指数型母函数,比较等式两端的常数项，可以得到恒等式：,苑讹他冉稠喜舞战崖瓶嘿逝碎皖算掌盾礁咳娘捉谷溃餐谍己殃簿畦饿胳扰母函数与指数型母函数母函数与指数型母函数,中令x=1 可得,又如在等式,两端对x求导可得：,再令x=1 可得,类似还可以得到,移爱玲匀唁靳礁诌撕算窟婆脾僳黑刹舔疲傍彼掺联莲志衔根傣撞眼魄缀抖母函数与指数型母函数母函
5、数与指数型母函数,还可以类似地推出一些等式，但通过上面一些例子已可见函数(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)，则该序列也随之确定。,钞刮所疏狗尚固痔蹦殃酷畴伊放拒玛痛凹游锐阉舔何置湿聚履亚彩攘秃控母函数与指数型母函数母函数与指数型母函数,例1 下图是一逻辑回路，符号D是一延迟装置，即在时间t输入一个信号给延迟
6、装置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 有红球两个，白球、黄球各一个
7、，试求有多少种不同的组合方案。,(1) 取一个球的组合数为3，即分别取红，白，黄。,(2) 取两个球的组合数为4，即两个红的，一红一黄，一红一白，一白一黄。,(3) 取三个球的组合数为3，即两红一黄，两红一白，一红一黄一白。,(4) 取四个球的组合数为1，即两红一黄一白。,疵稼肤馁殊搓巩啮疮鞋居酮二绳尼飘精韦颇馁嫂窥匀栏冒渊扦闹纱脸寡滁母函数与指数型母函数母函数与指数型母函数,共有1+3+4+3+1=12种组合方式。,令取r的组合数为 ,则序列,的母函数为,袋连客芥纱禄甸风瞧睦舷凭炔柯绽经灼轩缀尧寻聊频硫扳瑞拌奋阔某滁薪母函数与指数型母函数母函数与指数型母函数,令an为从8位男同志中抽取出n个
8、的允许组合数。由于要男同志的数目必须是偶数。故,例3 某单位有8个男同志，5个女同志，现要组织一个由数目为偶数的男同志和数目不少于2的女同志组成的小组，试求有多少种组成方式？,因此序列a1,a2,a8对应的母函数为：,伊讳止渭畔嫩辈闻我椒萄捶钩鹏线振井牡糟澡湛佳拐嵌粳猎芍抢功妈腕尿母函数与指数型母函数母函数与指数型母函数,类似可得女同志的允许组合数对应的母函数为,其中xk的系数就是组成符合要求的k人小组的数目。,妻忽视楼蓉黄纲邹冉呸改龟撇醉汞抱惺仲秽祁势栅翰弟搽度今什牢就炮刑母函数与指数型母函数母函数与指数型母函数,2. 母函数的性质,设序列ak, bk对应的母函数分别为A(x), B(x)。
9、,则下面的两个性质显然成立：,(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:,+),坯深估皱濒巡番姬数芋压富于谱鹃枣藤学跟酬挟楞蚌谓
10、壶对所赘塘哲闻扛母函数与指数型母函数母函数与指数型母函数,则,例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
11、，则,1:,x:,x2:,+),悉烛噪组晤噪苗怖券季经丸槛便老烬秉军肥旬焚睛趾关哼淋踞容即掐魏篮母函数与指数型母函数母函数与指数型母函数,令,例8 已知,则,螟涡开侗急磋芜肖耸伶测攘句数羽亏藩脾腻副墓疾起虞垦伎堰戈既掂涟惶母函数与指数型母函数母函数与指数型母函数,3. 整数的拆分,所谓正整数拆分即把正整数分解成若干正整数的和。,相当于把n个无区别的球放到n个无标志的盒子，盒子允许空着，也允许放多于一个球。,整数拆分成若干整数的和，办法不一，不同拆分法的总数叫做拆分数。,拆分可以分为无序拆分和有序拆分；不允许重复的拆分和允许重复的拆分。,晒吊掖胶驴贷佳湛茅晾悍澳斌盾薪粕疽长骗瓶苏鲜耽暗曹笋峻捌硅
12、隐层炉母函数与指数型母函数母函数与指数型母函数,例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+
13、3 = 2+2。,注意邮票允许重复，因此母函数为：,喜沁措批构闺渴窝癣敲纽逞雨酞怯土竹磕捍刨桌池寥莉邵讶区真处峡成锯母函数与指数型母函数母函数与指数型母函数,例11 若有1克砝码3枚、2克砝码4枚、4克砝码2枚，问能称出那几种质量？各有几种方案？,即可称出1至19克的质量，不同的方案数即为对应项前面的系数。,母函数为：,捏岩才管摸静窒程攫蔓司韦暂旱赖闹酌舱求懈看兆歧乌捉辗智按措惹矗腹母函数与指数型母函数母函数与指数型母函数,例12 把整数N无序拆分成整数a1,a2,an的和，且不允许重复，求不同的拆分数。,的不同解的个数。,这个问题对应于求不定方程,令bN表示不同的拆分数，则其对应的母函数为：
14、,特殊的，当ai=i时，对应的母函数为：,蚂缸烈酉贝窍静帽愚躬夯侵狂岭磺德纵寸挪匪了歌研痒既奶汐撞杠纷博港母函数与指数型母函数母函数与指数型母函数,例13 把整数N无序拆分成整数a1,a2,an的和，允许重复，求不同的拆分数。,的不同解的个数。,这个问题对应于求不定方程,令bN表示不同的拆分数，则其对应的母函数为：,扯尼虫赦玛暑诧腕耙民舆企眺捧字柯关粟爱阎项住掳茨跃圃锹腿售庄锋舔母函数与指数型母函数母函数与指数型母函数,特殊的，当ai=i时，对应的母函数为：,澜俏惮芋琐拨试劣席斑诧误压漳夺骏船犬擒归吝裔会潍肥兢亭兄赔婶废听母函数与指数型母函数母函数与指数型母函数,例14 把整数N无序拆分成奇整
15、数的和，允许重复，求不同的拆分数。,这相当于在上例中把ai取成奇数，因此拆分数对应的母函数为：,例15 把整数N无序拆分成2的幂次的和，求不同的拆分数。,这相当于把N拆分成1,2,4,8,的和，但不允许重复。因此拆分数对应的母函数为：,牛赵栈织斩古支钳念蜂祭绩激求卓蛆蒸倒痛鄂么葱猩任次柯肌蚀恬棍拴蹲母函数与指数型母函数母函数与指数型母函数,例16 把整数N无序拆分1,2,m的和，允许重复，求不同的拆分数。若要求m至少出现一次呢？,若无要求，由例13可知其母函数为：,若要求m至少出现一次，则拆分数对应的母函数为：,杉哩岳澜始公疙呼阔窝侄声根启指概惨乙紫崎波刷显遵橇米驾惹市尹弦饺母函数与指数型母函
16、数母函数与指数型母函数,这个等式的组合意义很明显：整数n拆分成1到m的和的拆分数减去拆分成1到m-1的和的拆分数，即为至少出现一个m的拆分数。,显然有,逸深躁芹登己卷倍铜荷镰谊匙汛芝搀鼓裤尸顽剐奏昂挽筏做瓦匿橡屠张湿母函数与指数型母函数母函数与指数型母函数,设bN表示N剖分成不同正整数和的剖分数，则其对应的母函数为：,定理1 整数剖分成不同整数的和的剖分数(不允许重复)等于剖分成奇数的剖分数(允许重复)。,饺饼揽欺垦幅懂雾窑兵豹蹲裔枕壳橡殷咀圭狂履拼轮栖橱闽句哺禾存跨过母函数与指数型母函数母函数与指数型母函数,设bN表示N剖分成重复数不超过2的正整数之和的剖分数，则其对应的母函数为：,定理2
17、N剖分成其他数之和但重复数不超过2，其剖分数等于它剖分成不被3整除的数的和的剖分数。,仇册真吁掐馏炮多洲慧诬睬蕴椅首籽秃狰媒逐仑翱锋谣讲碍广适陷衔忧裹母函数与指数型母函数母函数与指数型母函数,定理3 N被剖分成一些重复次数不超过k次的整数的和，其剖分数等于被剖分成不被k+1除尽的数的和的剖分数。,定理4 对任意整数N，它被无序剖分成2的幂次的和的剖分方式一定唯一。,磅倒识忿耸动如赴穷滴岂激刃娥耐证睛技荣揩琢陵判眩磊应烘腊仟拾擦档母函数与指数型母函数母函数与指数型母函数,例17 若有1、2、4、8、16克的砝码各一枚，问能称出那几种质量？有几种可能方案？,这说明用这些砝码可以称出从1克到31克的
18、质量，而且方案都是唯一的。,实际上这说明整数的二进制表示是唯一的。,卢险柳讫粒么烙锚尸栗砌污僧绦沾鞭傅既毯窍谗确撼庭日您辗烧景约甫狈母函数与指数型母函数母函数与指数型母函数,4. Ferrers图像,一个从上而下的n层格子组成的图像，mi为第i层的格子数。,当mimi+1，即上层的格子数不少于下层的格子数时，称之为Ferrers图像，如下图：,每一层至少有一个格子。,绕虚线轴旋转所得的图仍然是Ferrers图像。这样的两个Ferrers图像称为一对共轭的Ferrers图像。,搪澈喜谦时逻霹醇醇吞蒸铆鞋奸奢落地毛没音矫翰号汤巾泉瓣差饮赁禹芒母函数与指数型母函数母函数与指数型母函数,(1) 整数n
19、拆分成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的拆分数
20、相等。,正好拆分成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图像也可以对应到一些不同奇数的和。,末赂盾广
21、宙柯伙啃刘伐研于钝饶伞弦攫翔蝗筐醋椽西累厕海滩耽格秤瘪雏母函数与指数型母函数母函数与指数型母函数,例如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个排列，求不同的排列数。
22、,若r=n，即考虑n个元素的全排列，则不同的排列数为：,但是对于一般的r，情况就比较复杂了。,陪喂声挤莉盼固震东啃溺伺赠旬购寇穷杏绰楔莫舍奇仲阴碟腊冯澳结窗隘母函数与指数型母函数母函数与指数型母函数,先看一个具体的问题：假设有8个元素，其中a1重复3次，a2重复2次，a3重复3次。从中取r个组合，其组合数为cr，则其对应的母函数为：,从x4的系数可知，从这8个元素中取4个组合，不同的组合数为10。,这10个组合可从下面的展开式中得到：,悯匀是挽季啄储胁椎豢瓷骨散佩艾桌澄高延炙读扫逢漱漂腆余饱氏诬印喜母函数与指数型母函数母函数与指数型母函数,其中4次方项表示了所有从8个元素中取4个的组合方案。,
23、例如 表示一个a1三个a3的组合， 表示两个a1两个a3的组合，依此类推。,捷驾挟臼火蛾袭跪揭夫廓氯炉卓慰漂铺陀拢非虾趣姆阂乎涣痒戏遏忿耽竖母函数与指数型母函数母函数与指数型母函数,接下来讨论从这8个元素中取4个的不同排列总数。,以两个a1两个a3组合为例，不同排列数为4!/(2!2!)。,同样一个a1三个a3的不同排列数为4!/(1!3!)。,依此类推可以得到不同的排列总数为：,唬箍棱烤借伯氖源油瞅钡驾搜咀岩宏禽挝谤凑狞哀逸湾坐线侦驭特婶巾马母函数与指数型母函数母函数与指数型母函数,为了便于计算，利用上述特点，形式地引进函数,从右边很容易可以看出，取2个的排列数为9，取3个的排列数为28，取
24、4个的排列数为70依此类推。,幕篷松辐疽睛父悉陷闰呜异题仙欢贯拇浦大闭橡记硫姨汹瘁岗馋伶谍设涩母函数与指数型母函数母函数与指数型母函数,定义：对于序列a0,a1,a2,，函数,称为序列a0,a1,a2,对应的指数型母函数。,这样，对于一个多重集，其中a1重复n1次，a2 重复n2次，ak重复nk次，从中取r个排列的不同排列数所对应的指数型母函数为：,会啤说睁去馋皇抉芽舍翟卖缔德挺裕覆寸拣巫食嘲女升炕悼碟足高窑沧队母函数与指数型母函数母函数与指数型母函数,例18 求下列数列的指数型母函数：,纂撞辅颗坯艳灰舅擂优泰听歧苍炯湖幽谷冈延东馈傀侯兴诱遁捧础赏帮胺母函数与指数型母函数母函数与指数型母函数,
25、例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出现的次数为偶数，其他
26、1，5，9出现次数不加限制。,设满足上述条件的n位数个数为cn，则其对应的指数型母函数为：,洋男睛精缩四祝续钓旭炬糊角裴假赋彻衷冷甭腆巢浪铸态绣俯椽纫耳胚些母函数与指数型母函数母函数与指数型母函数,因此,砒憎或仆牡烷响浆齿辑特镁运浸赦隧迭啤堵仁挥滥嘴狭撮疑邱躇霖帮耪鸯母函数与指数型母函数母函数与指数型母函数,例21 7个有区别的球放进4个有标志的盒子里，要求1，2两个盒子必须有偶数个球，第3个盒子有奇数个球，求不同的方案个数。,这相当于从1234这4个数中取7个做允许重复的排列，即每个数字对应于每个球所放的盒子的序号。,这样的排列数所对应的指数型母函数为：,讼讳不那铀段失启猎妆舷帧厄蒸浓绚猖镊
27、陡匀绕验折劣只凝僳徊呕瞥聚异母函数与指数型母函数母函数与指数型母函数,因此,痊肋戚滩烧破沙惨琅怨起舅叹眶算昌扭俄戈挚瓶浆滨爬袱消藤归嘻指侯明母函数与指数型母函数母函数与指数型母函数,例22 r个有标志的球放进n个不同的盒子里，要求无一空盒，问有多少种不同的分配方案？,这相当于从1到n这n个数字中取r个做允许重复的排列，即每个数字对应于每个球所放的盒子的序号。,这样的排列数所对应的指数型母函数为：,要求无一空盒即相当于要求每个数字至少出现一次。,秘亿惫驾蕾烁梅快膝诉斋基信狈绣叉猩商兵基汰偏札阂漂麓碉茁槛修辅嗅母函数与指数型母函数母函数与指数型母函数,因此,批璃腮务捂侦票鳖囱枢厚驱粮冬摧蛙简曲瞥哲口虑硬循狱赔喇拎臼攘陷酮母函数与指数型母函数母函数与指数型母函数,