生成函数在组合计数中的应用

信息与计算科学毕业论文生成函数在组合计数中的应用【摘要】生成函数即母函数，是组合数学中尤其是计数方面的一个重要理论和工具。最早提出母函数的人是法国数学家LaplaceP.S.在其1812年出版的《概率的分析理论》中明确提出。生成函数有普通型生成函数和指数型生成函数两种，其中普通型用的比较多。生成函数的应用简单来说在于研究未知（通项）数列规律，用这种方法在给出递推式的情况下求出数列的通项，生成函数是推导Fibonacci数列的通项公式方法之一。另外生成函数也广泛应用于编程与算法设计、分析上，运用这种数学方法往往对程序效率与速度有很大改进生成函数在组合问题中的应用既灵活又具有一定的广泛性，掌握生成函数的构造方法可以帮助学生提高其数学思维能力及解决实际问题的能力，文章总结了生成函数在组合问题的几种常见用法。【关键词】组合问题递推关系拆分【前言】利用生成函数可以说是研究组合问题的一种最主要的常用的方法，生成函数的应用也是数学中“以退为进”思想的典型代表。生成函数这个名字看上去有点神秘，但其实它就是将一个数列转化成一个函数的方法。其基本思想为：为了获得一个序列{:k≥0}={……}的有关知识，我们引用一个幂级数g(x)==……来整体表示这个序列，即g(x)为序列{:k≥0}的生成函数。这样，一个序列和它的生成函数一一对应，给了序列便得知它的生成函数；反之，求得生成函数序列也信息与计算科学毕业论文随之而定，我们还可以通过对函数的运算和分析得到这个序列的很多性质。本文试图通过一些实例谈一谈生成函数在组合上的几种应用。1.利用生成函数证明组合恒等式组合恒等式的证明技巧性很强，解题方法独特，其中利用构造生成函数，比较等式两端对应项的系数，是证明组合恒等式的一种非常有效的方法。求证：2+3+4+…+n=可以看出，该组合恒等式左端比较复杂，不太可能利用组合公式去证明，观察后发现等式左端各项规律性较强。通过分析，设法将等式左端看作是某一函数中确定项的系数，由为中项的系数，所以我们构造生成函数：fn(x)=(1+x)+2+…+n(x≠-1)fn(x)中的系数即为2+3+4+…+n.同时,利用”错位相减法”易知:fn(x)=+.比较的系数即得所证结果从上面可以看出，根据题意，灵活地引入生成函数是证明组合恒等式的关键所在。2.生成函数在递推关系上的应用递推关系是计算中的一个强有力工具，而递推关系的求解一般比较困难．利用生成函数求解递推关系则是一种主要的、行之有效的方法。信息与计算科学毕业论文求n位十进制数中出现偶数个5的数的个数。令=n位十进制数中出现偶数个5的数的个数，=n位十进制数中出现奇数个5的数的个数。因此有关系:其中则，此关系为关于序列｛｝的递推关系，求解此递推关系是解决本问题的难点。我们可以考虑引进序列｛｝的生成函数A(x)．即：A(x)=，利用错位相加减的方法，即：A(x)=则(1-8x)A(x)=8+9x+9=,A(x)=再将A(x)展开成幂级数的形式：A(x)=(=因此递推关系的求解主要是利用递推关系求得生成函数的一种形式算法，生成函数确定了，相应的递推关系对应的结果就确定了，这样的例子还有很多，象着名的Hanoi塔问题，Fibonacci数列都是典型的利用生成函数解决递推关系的例子3.利用生成函数进行整数的拆分信息与计算科学毕业论文组合数学中有很多实际问题都可以理解为将某一(些)整数按照一定条件进行拆分，而求所有拆分的种类或方法，利用生成函数可以简单有效地解决这类问题中的某些问题求方程满足X1+X2+X3+X4=20满足1≤x1≤6，0≤x2≤7，4≤x3≤8，2≤x4≤6的整数解的个数。此问题仍可看成是拆分数的问题，把20拆分成满足条件的4个整数和的方法数问题，根据x所需条件，引入生成函数：g(x)中的系数即为所求的满足条件的整数解的个数。可以解得=96即为所求4.生成函数在组合计算上的应用生成函数的应用确实很广泛，利用生成函数还可以解决在排列组合中有关排法种数的问题:有红球两只，白球、黄球各一只，试求有多少种不同的组合方案。此问题不能看成是简单的组合问题，也不是可重复元素的组合数问题，若用r，w，y分别代表红球、白球、黄球，则不同的组合方案可有下面的式子给出:此结果可以看出,除一个球也不取的情况外,有:(a)取一个球的组合数为3，即分别取红、白、黄三种；信息与计算科学毕业论文(b)取两个球的组合数为4，即两个红的、一红一黄、一红一白、一黄一自；(c)取三个球的组合数为3，即两红一黄、二红一白、一红一白一黄；(d)取四个球的组合数为1，即两红一黄一白。若此问题只求不同的方案种数，则可直接利用生成函数。设取r个球的组合数为Cr(o≤r≤4)，则{Cr}的生成函数为：G(x)=(1+x+x2)(1+x)2=1+3x十4x2十3x3+x4。共有1+3+4+3+1=12种组合方式。设有n个物件，并设n(r)是由n个不同物件中可任意重复地取r个物件生成函数的组合数。这个组合问题的生成函数即是「xr之系数等于n(r)」之生成函数。对一个物件来说，我们可以不选取，选取一次，选取二次等等，其方法可用式子表示。对第二个，第三个等物件也有同样作法。故其生成函数是我们必须将它写成标准形式。因为信息与计算科学毕业论文故我们得令n(r)是由n个不同物件中可任意重复地取r个，并在每一选取中，每个物件必须至少包含一次的组合数。数列{n(r)}的生成函数是故得。显然如果rn，本问题无解。信息与计算科学毕业论文简单推广上述问题，若在每一选取中每个物件必须至少选取q次，则一般排列组合问题可以归纳成将球放入盒中的问题。其中可将球与盒子看成可区分的或不可区分的，而每一盒子又可被允许放最多一个球，或超过一个球而产生各种情况。组合问题可看成将不可区分的球放入可区分的盒中之问题。a的问题相当于要求出将r个相同的球放入n个不同盒中之方法个数，其中每一盒必须至少放一个球。放球入盒的各种情况可列表如下：abcd球不可区分(r)可区分(r)可区分(r)不可区分(n)盒可区分(n)可区分(n)不可区分(n)不可区分(r)典型问题组合排列集合之分割整数之分解其中n或r表示盒子的个数，或球的个数。下面我们将利用生成函数的方法讨论这四类问题。设将相同的球放置于n个不同盒中，其中每一盒至少放q个球，并至多放q+z-1个球。此问题之生成函数是信息与计算科学毕业论文使问题具体些。设有四人掷骰，每人各掷一次，问当所得点数之和为17时共有多少种可能方式。四人可看作四个相异的盒子，17点可看作17个相同的球。这问题是当n=4,r=17,q=1,z=6之特别情况。故答案为展开式中x13项之系数，即共104种。上面的例子虽然很不全面，但我们也可以看出，利用生成函数是解决组合问题的非常有效的方法，但在具体问题中要注意具体问题具体分析，多研究，多体会，只有这样，才能真正掌握生成函数应用的技巧，做到事半功倍。作为本文最后的一个例，我们利用组合问题与其生成函数之对应关系证明下面著名的Euler恒等式：其中，信息与计算科学毕业论文首先我们要有下面结果：设n是一正整数，令E(n)表示将n分解成偶数个部份均不等之分解个数；F(n)表示将n分解成奇数个部份均不等之分解个数，则我们有上式是利用Ferrers图示所产生的对应来证明。设某一n之部份相异之分解的图示有如下图（我们用23=7+6+5+3+2为例）：令b记作底线上方框个数，d记作45°斜线上方框个数。这里有三种情况：如果bd，则底线上b个方框可移至斜线上端如右图所示。这样n之分解中部份个数则减少了一个，且各部份仍保持相异。信息与计算科学毕业论文如果b=d，则底线方框仍可移至斜线上端，唯一例外是斜线和底线相交如下面左图：在这情况下，这分解有形式如果bd，则斜线上方框可移至底部而令分解之部份个增加一个并各部份仍保持相异，唯一例外是斜线和底线相交如上面右图且b=d+1在这情况下，这分解有形式当时，上面对应使E(n)与F(n)相等；当时，则k是偶数使E(n)比F(n)多一个；k是奇数使E(n)比F(n)少一个。。信息与计算科学毕业论文回到我们上面提到之Euler恒等式。它的左边是一无穷乘积，恰是数列{E(n)-F(n)}的生成函数.Generatingfunctionintheapplicationofcombinedcount【Abstract】Generatingfunctionthatisgeneratingfunction,isacombinationofmathematics,especiallyintermsofcountisanimportanttheoryandtools.GeneratingfunctionwasfirstproposedbyFrenchmathematicianwhoisLaplaceP.S.Inhis1812bookprobabilitytheoryclearly.Commontypeofgeneratingfunctionandtheexponentialgeneratingfunctionoftwogeneratingfunctions,whicharemorecommontypeused.Generatingfunctionissimplytheapplicationoftheunknown(generalterm)seriesoflawsgivenbythismethodinthecaseofrecursivetypethegeneraltermofsequenceobtained,generatingfunctionsarederivedFibonacciseriesoneofthe信息与计算科学毕业论文generalformula.Anothergeneratingfunctionisalsowidelyusedinprogrammingandalgorithmdesign,analysis,mathematicalmethodsoftenusethisprocedureconsiderablyimprovedtheefficiencyandspeedGeneratingfunctionintheapplicationofcombinatorialproblemsinflexibleandhasacertainuniversality,tomastertheconstructionofgeneratingfunctionmethodcanhelpstudentsimprovetheirmathematicalthinkingandtheabilitytosolvepracticalproblems,thearticlesummarizestheproblemofgeneratingfunctioninthecombinationofseveralcommonusage.【Keywords】Combinatorial;generatingfunctions【参考文献】《组合学与图论》作者：林翠琴出版社：清华大学出版社2009年4月书号:9787302192220引自:第三章生成函数和递推公式3.1.1生成函数的一般概念3.1.3生成函数的应用《离散数学》作者：屈婉玲、耿素云、张立昂出版社：清华大学出版社2008年出版书号:978-04-023125-0信息与计算科学毕业论文引自:第十三章递推方程与生成函数