毕业论文-生成函数的理论与应用

xx大学毕业论文-I-摘要本文系统的论述了生成函数的理论及其在组合数学和计算数学中的应用.生成函数又称母函数，它是在幂级数和多项式理论的基础上建立的.生成函数可分为普通型生成函数和指数型生成函数，他们在计算问题中有各自的应用范围.本文首先介绍了生成函数的基本理论，包括基本概念、性质及其系数计算的一些技巧.其次介绍了普通型生成函数和指数型生成函数的基本模型及其应用范围.最后则具体讨论了生成函数法在求解递推关系和整数分拆中的应用.通过本文的总结，可以使人们对生成函数有一个比较清晰的认识，更加系统的掌握生成函数这一数学工具.关键词：生成函数；普通型生成函数；指数型生成函数；递推关系；整数分拆xx大学毕业论文-II-ABSTRACTInthispaper,thetheoryofgenerationfunctionandtheapplicationinthecombinatorialmathematicsisdiscussed.Thegenerationfunctionisalsoknownasgeneratingfunction,whichisbuiltonthetheoryofpowerseriesandpolynomial.Generationfunctionincludesordinary-sizedandexponentialtype,theyhavetheirownapplicationfieldsintheproblemofcalculations.Firstly,thispaperintroducesthebasictheoryofgeneratingfunction,includingbasicconcepts,natureandsomecalculatingskillsofgeneratingfunctionscoefficients.Secondly,introducesthebasicmodelsandapplicationfieldsofordinary-sizedandexponentialtypegenerationfunction.Finally,discussesthemethodsofgenerationfunctioninsolvingtherecursiverelationsandpartition.Bythesummaryofthispaper,formingamoreprofoundunderstandingonthegenerationfunction.andmoresystematicmasteringthemathematicaltool-generatingfunction.Keywords：generationfunction；ordinary-sizedgenerationfunction；exponentialtypegenerationfunction；recursiverelations；partitionxx大学毕业论文-III-目录摘要…………………………………………………………………………………………IABSTRACT………………………………………………………………………………..II1前言……………………………………………………………………………………….12基本知识………...…………………………………………………………………….….22.1基本概念………………………………………………………………………..…22.2基本性质…………………………………………………………………………32.3生成函数的计算………………………………………………………………….43普通型生成函数模型…….………………………………………………………………63.1问题的提出……………………………………………………………………….63.2普通型生成函数模型及其应用…………………………………………………..64指数型生成函数模型…………………………………………………………………….94.1问题的提出…………………………………………………………………94.2指数型生成函数模型及其应用....…………….………………...………………...94.3指数型生成函数系数的计算技巧…………………………….…………...…….115生成函数在递推关系中的应用………………………………………………………...135.1生成函数法在常系数线性齐次递推关系上的应用……………………………135.2生成函数法在常系数线性非齐次递推关系上的应用………...………………..156生成函数在整数分拆中的应用……………………….………………………….…….18结论….…………...………….………….……………………..….……...…..….………...20参考文献……….………………….…………………..….…..……………….………….21致谢……….…………………….……………………..…….…………..………….22xx大学毕业论文-1-1前言生成函数又称母函数，是计数问题中既简单又精巧的数学模型，也是组合数学的一个重要理论和工具.1720年前后DeMoivre首先使用了组合生成函数,通过使用生成函数得到斐波那契数的一个公式.1748年欧拉在他的著作中对分拆问题使用了生成函数，而他同时对概率生成函数的工作是18世纪后期发展起了的组合生函数理论的原始动力.最早提出生成函数的人是法国数学家LaplaceP.S.在其1812年出版的《概率的分析理论》中明确提出“生成函数的计算”，书中对生成函数思想奠基人—EulerL在18世纪对自然数的分解与合成的研究做了延伸与发展，生成函数的理论由此基本建立.曹汝成在生成函数中提出了车问题及其解法，AlanTucker在应用组合数学中提出了生成函数系数的具体解法及一个求和的算法，RichardA.Brualdi具体提出了生成函数与递推函数的关系等.每本著作中作者所提的概念、所引用的符号以及表述方法都有一些共同点和差异.本文主要是系统的总结生成函数的基本理论和应用问题，使人们对生成函数有一个清晰的认识，比较简便的学会生成函数这一数学工具.本文第二部分主要回顾了生成函数的基本概念及其性质，计算生成函数系数的一些技巧.在第三部分和第四部分中主要介绍了普通型生成函数和指数型生成函数的基本模型及其应用范围.第五部分和第六部分则具体讨论了生成函数在递推关系和整数分拆中的应用.xx大学毕业论文-2-2基本知识2.1基本概念计数问题是组合数学的一个重要内容，而生成函数又是解决计数问题的一个重要的一般性的处理方法.幂级数2210)(xaxaaxP是我们所熟悉的多项式，我们定义)(xP为数列},,,{210aaa的生成函数，通常记为}{naG[1].生成函数的中心思想是：首先使用多项式或幂级数把需要研究的数列合为一个整体，通过研究多项式或幂级数的性质以及使用合并同类项的方法，来研究数列的性质，从而得到相关的结论.例如数列,2,,2,2,2210n的生成函数是2210222)(xxxf这个生成函数的值为xxf211)(xxf211)(用了非常简洁紧凑的方式显示了上述数列的序列信息.下面列举了几个常见的生成函数[2].(1)2111xxx(2)32!3)2)(1(!2)1(111xnnnxnnnxxn(3)2210222211xxx(4)221011xaxaaax(5)kkxxxxx22211(6)kxkxxxxxx232222332111(7)kxkkxxxxx)1()43()32()21(12323xx大学毕业论文-3-(8)kxkkkxxxxx)2()1()543()432()321(16324(9)kxxkxxe!1!21!11122.2基本性质首先假定，序列{ia}，{jb}的生成函数分别为2210)(xaxaaxP2210)(xbxbbxQ因为生成函数与数列之间是一一对应的关系，所以研究两个数列之间的关系可以转化为研究其生成函数的关系，这样就给解题带来了许多便利.线性性质(1)若nncab，则)()(xcPxQ(2)若nnnbac，则)()()(xPxQxC乘积性质(3)若nc=niiniba1，则)()()(xPxQxC移位性质(4)若)(0ikaikbikk，则)()(xPxxQi(5)若iknab，则kikkixaxPxxQ10)((1)(）(6)若ikinab0，则)(xQ=xxP-1)((7)若ikinab，则)(xQ=xxxPP-1)()1(，其中ikia是收敛的换元性质(8)若nnnacb，则)()(cxPxQ求导与积分性质xx大学毕业论文-4-(9)若nnnab，则)()(xPxxQ(10)若1nabnn，则)(xQ=xdttPx0)(12.3生成函数的计算计算生成函数系数的方法是把比较复杂的生成函数化简为简单的二次式类型，或若干个二项式类型的生成函数的积，这样就比较容易得出所需的kx的系数.我们需要用到牛顿二项式定理及其生成函数的性质.牛顿二项式定理，设实数a，对一切yx,有iaaiiayxiayx0)(其中ia=!11nnaaa，当na时，变成我们所熟悉的二项式定理nxnnCxnCxnCx,2,1,1)+(12n特别的当na时，kknxkkn1110kx1xkknxnkn110kx1x例1求解52102)1)(1(xxxxx。解52102)1)(1(xxxxx=5111111xxx=61111)1(xx=)16216211611)(1(211kxkkxxx利用牛顿二项式求得生成函数的系数.xx大学毕业论文-5-例2已知}{)(3kGxA，求解)(xA的值.解}{3kG=}{2}{3)}2)(1({2kGkGkkkG=2341211316xxxxxxx)}2)(1({kkkG，}{2kG和}{kG在2.1中已注明，本题利用生成函数的加法运算及其性质求得.例312x在5432)(xxx中的系数，系数是多少kx？解5432)(xxx=5210)1(xxx=51011xx511x中2x的系数是2215即15，所以12x的系数是15.同理可得kx=10101015100kkkkxx大学毕业论文-6-3通型生成函数模型3.1问题的提出在现实生活中我们经常遇见类似于这样的问题：5个苹果，4个橘子，3个梨，从中选出4个水果的组合数，及其组合方案.当然，通过列举法可以来解决上述问题，但当水果的种类和数量变多时，应用列举法就困难许多.在本节，我们在组合问题中引入了生成函数法，使解题的过程更加简便.3.2普通型生成函数模型及其应用(1)求},,,,{210naaaa的k组合数，这是普通集合的组合问题.例1现在有n个不同的球，求从中选出三个球的组合数.解显然根据以前的学习，我们可以得到三个球的组合数为3n，一般的对于r组合数有