2022年生成函数的应用知识 .pdf

《2022年生成函数的应用知识 .pdf》由会员分享，可在线阅读，更多相关《2022年生成函数的应用知识 .pdf（4页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、北航软件学院1 生成函数的应用摘要生成函数方法是一种简单而又重要的方法，本文介绍了生成函数的定义， 同时给出了生成函数在概率论、 证明恒等式、 求解递推关系及求递归数列的通项公式等方面的应用。关键字：生成函数；递推关系；恒等式；生成函数应用一、 生成函数的定义生成函数又叫做母函数。 生成函数方法是离散数学的重要方法，是连接离散数学与连续数学的桥梁。 在组合数学中， 生成函数的典型作用主要体现在组合计数方面，是解决组合计数问题的强有力工具之一，其基本思想为： 为了获得一个序 列kk 0a的 有 关 知 识 ， 我 们 引 用 一 个 幂 级 数 来 整 体 表 示 这 个k2k012k 0 xa

2、 xaa xa xG （ ）序列，xG （ ）为序列kk0a的生成函数。这样，一个序列和它的生成函数一一对应， 我们可以通过对生成函数的运算和分析得到这个序列的很多性质。18 世纪，欧拉在研究正整数分拆时首先使用了母函数，19 世纪初拉普拉斯在研究概率问题时得到进一步发展。母函数的一种自然推广， 导致概率论中引进强有力的工具特征函数， 它把随机变量的分布函数变换为它的特征函数，从而把对分布函数的研究转化为对对应的特征函数的研究，大大地推动了相互独立随机变量的和的极限理论的研究。一、生成函数的应用21 生成函数在概率论中的应用例：在做抽样调查时，采访的男士有教师，医生，律师等不同的q 个行业，女

3、士也有不同的 p 个行业，假设我们在每一行业中至多选取2 位男士和至多选取1 位女士，问有多少种不同的方法取k 个人的样本？解：要区分相同性别的人， 当且仅当他们属于不同的范畴，现以选择 k 个人的方法数量做生成函数。在q 种范畴的每一个中，我们或者选择0，1，2 位男士做样本，因此每个范畴给出2(x+x )1+项，另外选择 0 或 1 位女士，所以 p 种范畴中的每一个给出 (1+x)项。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 4 页 - - - - - - -

4、 - - 北航软件学院2 所以，2qp(x)(x+x ) (x)G1+1+因此选择 k 个人的方法数量是(x)G中kx的系数。例如pq34k，时，233(x)(x+x ) (x)G1+1+23(1)(1)xxx223(1)(1)xxx642242633333(1)(1)(1)(1)(1)(1)0123xxxxxxxxx6524463(1)3(1)3(1)(1)xxxxxxx所以，4x的系数是6543348420即在每一行业中选取2 位男士和 1 位女士有 48 种不同的方法取四个人的样本。22 利用生成函数证明恒等式组合恒等式的证明技巧性很强，解题方法独特， 其中利用构造母函数， 比较等式两端

5、对应项的系数，是证明组合恒等式的一种非常有效的方法。例：求证2222234(1) (1)(32)2+3+424nnn nnCCCnC可以看出 ,该组合恒等式左端比较复杂，不太可能利用组合公式去证明，观察后发现等式左端各项规律性较强。通过分析，设法将等式左端看作是某一函数中确定项的系数，由2nC 为(1)nx中2x项的系数，所以我们构造母函数：2( )(1)2(1)(1) (1)nnfxxxnxx(1) ( )nfx 中2x的系数即为22222342+3+4nCCCnC 。同时，利用“错位相减法”(1)式两边同时乘以(1)x得231(1)( )(1)2(1)(1)(1)(1)nnnx fxxxn

6、xnx(1)-(2)得：231( )(1)(1)(1)(1)(1)nnnxfxxxxxnx，整理得到：112(1)(1)(1)( )nnnxxn xfxxx，比较2x的系数即得所证结果。从上面这个例子可以看出， 根据题意，灵活地引入母函数是证明组合恒等式的关键所在。23 用生成函数求解递推关系名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 4 页 - - - - - - - - - 北航软件学院3 递推关系是计算中的一个强有力工具,而递推关系的求解一般比较困难,利用母函数

7、求解递推关系则是一种主要的、行之有效的方法。例：求 n 位十进制数中出现偶数个5 的数的个数。解：令na 是 n 位十进制数中出现偶数个5 的数的个数 ,nb 是 n 位十进制数中出现奇数个 5 的数的个数。因此有关系211119,9 10nnnnnnaabba，其中18a。则2189 10nnnaa此关系为关于序列 na的递推关系，求解此递推关系 是解决 本 问题 的难点 。我们 可 以考 虑引进 序 列 na的母 函数( )A x， 即2123( )A xaa xa x利用错位相加减的方法，即：231238( )888xA xa xa xa x229871(18 )( )899 1081

8、101 10 xxx A xxxxx871( )(18 )(110 )xA xxx，再将( )A x展开成幂级数的形式：201791( )(789 10 )2 181102nknnA xxxx递推关系的求解主要是利用递推关系求得母函数的一种形式算法，母函数确定了，相应的递推关系对应的结果就确定了，这样的例子还有很多，想著名的Hanoi 塔问题， Fibonacci数列都是典型的利用母函数解决递推关系的例子。24 用生成函数解递归数列的通项公式例：设011,2,aa且1256(2)nnnaaan，求数列 na的通项。解：令20120( )nnnnnf xa xaa xa xa x(1) 则201

9、15( )555nnxf xa xa xax(2) 且2230126( )666nnx f xa xa xax(3) (1)+(2)+(3)可得：2010(1 56) ( )(5)xxf xaaa x，即2(156)()17xxfxx，有21754( )1561213xf xxxxx005(2 )4(3 )nnnnxx0(524 3 )nnnnx，从而5243nnna。二、总结由于生成函数 (形式幂级数 ) 具有良好的性质， 便于处理，因此它的应用较广泛。在组合分析、数论、概率论和图论等数学领域中有着广泛的应用。由于篇幅有限，本文只列举其中一小部分。名师资料总结 - - -精品资料欢迎下载 -

10、 - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 4 页 - - - - - - - - - 北航软件学院4 参考文献 1 王新渊 . 生成函数的性质和几个问题J 青海大学学报 , 2000, 18( 1): 46- 49 2 王新渊 . 生成函数在数列研究中的应用 J. 青海大学学报 , 2000, 18( 3): 44-45 3 冯素芬 ; 刘永现 . 生成函数计数理论的应用及其最新进展J. 北京工业职业技术学院学报, 2008,7( 2): 62- 64 4 李中恢 ; 黄小洁 . 生成函数及应用J. 宁波教育学院学院学报, 2007,9( 2): 46-47 5 曹汝成 . 组合数学 M. 广州 : 华南理工大学出版社,2006. 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 4 页 - - - - - - - - -