生成函数计数理论的应用及其最新进展

《 生成函数计数理论的应用及其最新进展》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、生成函数计数理论的应用及其最新进展生成函数计数理论的应用及其最新进展生成函数计数理论的应用及其最新进展生成函数计数理论的应用及其最新进展生成函数计数理论的应用及其最新进展生成函数计数理论的应用及其最新进展生成函数计数理论的应用及其最新进展生成函数计数理论的应用及其最新进展生成函数计数理论的应用及其最新进展生成函数计数理论的应用及其最新进展第7卷第2期2008年4月北京工业职业技术学院J0URNAL0FBEUINGPOLYTECHNICC0LLEGE№.2V01.7Apr.2008生成函数计数理论的应用及其最新进展冯素芬刘永现(1.首都师范大学,北京100037;2.北京工业职业技术学

2、院,北京100042;3.暨南大学,广州510632)摘要:生成函数方法是一种简单而又重要的方法,介绍了它在解决部分组合数学问题中的应用及其最新进展.关键词:生成函数;递推关系;整数的拆分;不定方程中图分类号:0157文献标识码:A文章编号:1671—6558(2008)O2—62一O2StudyApplicationandLatestDevelopmentofCreatingFunctionCountingTheoryFengSufen,LiuYongxian(1.CapitalNormalUniversity,Beijing100037,China;2.BeijingPolyte

3、chnicCoHege,Beijing100042,China;3.JinanUniversity,Guangzhou510632,China)Abstract:Creatingfunctionmethodissimplebutverysomeessentia1.Thisessayintroducestheapplicationandthelatestdevelopmentofthismethodinsolvingsomecombinatorialmathsproblems.Keywords:creating{luncti0n:deductiverelation;splitofint

4、eger;indefiniteequationO前言生成函数又叫做母函数.生成函数方法是离散数学的重要方法,是连接离散数学与连续数学的桥梁.在组合数学中,生成函数的典型作用主要体现在组合计数方面,是解决组合计数问题的强有力工具之一,其基本思想为:为了获得一个序列{:k≥O}=}a0,∞,a2….}的有关知识,我们引用一个幂级数g()=.∑’=0++2+…来整体表示这个序列,即g()为序列{:k≥O}的母函数.这样,一个序列和它的母函数一一对应,给了序列便得知它的母函数;反之,求得母函数序列也随之而定,我们还可以通过对函数的运算和分析得到这个序列的很多性质.1利用母函数证明组合恒等式组

5、合恒等式的证明技巧性很强,解题方法独特,其中利用构造母函数,比较等式两端对应项的系数,是证明组合恒等式的一种非常有效的方法.例1:求证:2c;+3c:+4c:+…+Jlc:=3n+2收稿日期:2008—03-03作者简介:冯素芬(1966一)女,首都师范大学数学科学院数学与应用数学专业毕业,首都师范大学数学科学院数学与应用科学专业在读硕士,副教授.第2期冯素芬,等:生成函数计数理论的应用及其最新进展63可以看出,该组合恒等式左端比较复杂,不太可能利用组合公式去证明,观察后发现等式左端各项规律性较强.通过分析,设法将等式左端看作是某一函数中确定项的系数,由c为(1+)中项的系数,所以我

6、们构造母函数:()=(1+)+2(1+)+…+n(1+)(≠一1)(1)L(x)中的系数即为2c+3C;+4C:+…+nC”.同时,利用”错位相减法”(1)式两边同时乘以(1慨)得(1+)’()=(1+)2+2(1+)+???+(n一1)(1+)+n(1慨)(2).(1)一(2)得:一()=(1慨)+(1慨)+(1慨)+…+(1慨)一n(1慨)整理得到:():二+“,比较的系数即得所证结果.从上面这个简单的例子可以看出,根据题意,灵活地引入母函数是证明组合恒等式的关键所在.2母函数在递推关系上的应用递推关系是计算中的一个强有力工具,而递推关系的求解一般比较困难,利用母函数求解递推关系

7、则是一种主要的,行之有效的方法.例2求T/,位十进制数中出现偶数个5的数的个数.令C/,是T/,位十进制数中出现偶数个5的数的个数,b是T/,位十进制数中出现奇数个5的数的个数.因此有关系:C/,=9a一1+b一1,b一1=9X10一C/,～1,其中C/,1=8.则C/,=8a一1+9X10此关系为关于序列{C/,}的递推关系,求解此递推关系是解决本问题的难点.我们可以考虑引进序列{C/,}的母函数A(),即:a(x)=C/,1+a2x+O,3X+…利用错