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

1、 信息与计算科学毕业论文生成函数在组合计数中的应用 【摘要】生成函数即母函数，是组合数学中尤其是计数方面的一个重要理论和工具。最早提出母函数的人是法国数学家LaplaceP.S.在其1812年出版的概率的分析理论中明确提出。 生成函数有普通型生成函数和指数型生成函数两种，其中普通型用的比较多。 生成函数的应用简单来说在于研究未知（通项）数列规律，用这种方法在给出递推式的情况下求出数列的通项，生成函数是推导Fibonacci数列的通项公式方法之一。 另外生成函数也广泛应用于编程与算法设计、分析上，运用这种数学方法往往对程序效率与速度有很大改进生成函数在组合问题中的应用既灵活又具有一定的广泛性，掌

2、握生成函数的构造方法可以帮助学生提高其数学思维能力及解决实际问题的能力，文章总结了生成函数在组合问题的几种常见用法。【关键词】组合问题 递推关系 拆分【前言】 利用生成函数可以说是研究组合问题的一种最主要的常用的方法，生成函数的应用也是数学中“以退为进”思想的典型代表。生成函数这个名字看上去有点神秘，但其实它就是将一个数列转化成一个函数的方法。其基本思想为：为了获得一个序列:k0=的有关知识，我们引用一个幂级数g(x)=来整体表示这个序列，即g(x)为序列:k0的生成函数。这样，一个序列和它的生成函数一一对应，给了序列便得知它的生成函数；反之，求得生成函数序列也随之而定，我们还可以通过对函数的

3、运算和分析得到这个序列的很多性质。本文试图通过一些实例谈一谈生成函数在组合上的几种应用。1. 利用生成函数证明组合恒等式组合恒等式的证明技巧性很强，解题方法独特，其中利用构造生成函数，比较等式两端对应项的系数，是证明组合恒等式的一种非常有效的方法。求证： 2+3+4+n=可以看出，该组合恒等式左端比较复杂，不太可能利用组合公式去证明，观察后发现等式左端各项规律性较强。通过分析，设法将等式左端看作是某一函数中确定项的系数，由为中项 的系数，所以我们构造生成函数：fn(x)=(1+x)+2+n (x -1)fn(x)中的系数即为2+3+4+n .同时,利用”错位相减法”易知:fn(x)=+.比较的

4、系数即得所证结果从上面可以看出，根据题意，灵活地引入生成函数是证明组合恒等式的关键所在。2. 生成函数在递推关系上的应用递推关系是计算中的一个强有力工具，而递推关系的求解一般比较困难利用生成函数求解递推关系则是一种主要的、行之有效的方法。求n位十进制数中出现偶数个5的数的个数。令 = n位十进制数中出现偶数个5的数的个数， =n位十进制数中出现奇数个5的数的个数。因此有关系: 其中则，此关系为关于序列的递推关系，求解此递推关系是解决本问题的难点。我们可以考虑引进序列的生成函数A(x)即：A(x)= ，利用错位相加减的方法，即：A(x)=则(1-8x)A(x)=8+9x+9= , A(x)= 再

5、将A(x)展开成幂级数的形式：A(x)=(=因此递推关系的求解主要是利用递推关系求得生成函数的一种形式算法，生成函数确定了，相应的递推关系对应的结果就确定了，这样的例子还有很多，象着名的Hanoi塔问题，Fibonacci数列都是典型的利用生成函数解决递推关系的例子3. 利用生成函数进行整数的拆分组合数学中有很多实际问题都可以理解为将某一(些)整数按照一定条件进行拆分，而求所有拆分的种类或方法，利用生成函数可以简单有效地解决这类问题中的某些问题求方程满足X1+X2+X3+X4=20满足1 x1 6，0 x 2 7，4 x3 8，2 x4 6的整数解的个数。此问题仍可看成是拆分数的问题，把20拆

6、分成满足条件的4个整数和的方法数问题，根据x所需条件，引入生成函数：g(x)中的系数即为所求的满足条件的整数解的个数。可以解得=96即为所求4. 生成函数在组合计算上的应用生成函数的应用确实很广泛，利用生成函数还可以解决在排列组合中有关排法种数的问题:有红球两只，白球、黄球各一只，试求有多少种不同的组合方案。此问题不能看成是简单的组合问题，也不是可重复元素的组合数问题，若用r，w，y分别代表红球、白球、黄球，则不同的组合方案可有下面的式子给出:此结果可以看出,除一个球也不取的情况外,有:(a)取一个球的组合数为3，即分别取红、白、黄三种；(b)取两个球的组合数为4，即两个红的、一红一黄、一红一

7、白、一黄一自；(c)取三个球的组合数为3，即两红一黄、二红一白、一红一白一黄；(d)取四个球的组合数为1，即两红一黄一白。若此问题只求不同的方案种数，则可直接利用生成函数。设取r个球的组合数为Cr (or4)，则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个物件生成函数的组合数。 這個組合問題的生成函數即是 x r之係數等於n ( r ) 之生成函數。这个组合问题的生成函数即是 x r之系数等于n ( r ) 之生成函数。

8、 對一個物件來說，我們可以不選取，選取一次，選取二次等等，其方法可用式子对一个物件来说，我们可以不选取，选取一次，选取二次等等，其方法可用式子表示。表示。 對第二個，第三個等物件也有同樣作法。对第二个，第三个等物件也有同样作法。 故其生成函數是故其生成函数是我們必須將它寫成標準形式。我们必须将它写成标准形式。 因為因为故故我們得我们得例a.5 設n ( r )是由n個不同物件中可任意重複地取r個，並在每一選取中，每個物件必須至少包含一次的組合數原編註2 。aaq 令n ( r )是由n个不同物件中可任意重复地取r个，并在每一选取中，每个物件必须至少包含一次的组合数。數列n( r )的生成函數是

9、数列n( r )的生成函数是故得故得 。 。 顯然如果r < n ，本問題無解。显然如果r < n ，本问题无解。簡單推廣上述問題，若在每一選取中每個物件必須至少選取q次，則简单推广上述问题，若在每一选取中每个物件必须至少选取q次，则一般排列組合問題可以歸納成將球放入盒中的問題。一般排列组合问题可以归纳成将球放入盒中的问题。 其中可將球與盒子看成可區分的或不可區分的，而每一盒子又可被允許放最多一個球，或超過一個球而產生各種情況。其中可将球与盒子看成可区分的或不可区分的，而每一盒子又可被允许放最多一个球，或超过一个球而产生各种情况。 組合問題可看成將不可區分的球放入可區分的盒中之問題

10、。组合问题可看成将不可区分的球放入可区分的盒中之问题。 例如例a.4 的問題相當於想求得將r個相同的球，可任意重複地放入n個不同盒中之方法個數。例a.5 的問題相當於要求出將r個相同的球放入n個不同盒中之方法個數，其中每一盒必須至少放一個球a a的问题相当于要求出将r个相同的球放入n个不同盒中之方法个数，其中每一盒必须至少放一个球。 放球入盒的各種情況可列表如下：放球入盒的各种情况可列表如下：a ab bc cd d球球不可區分( r )不可区分( r )可區分( r )可区分( r )可區分( r )可区分( r )不可區分( n )不可区分( n )盒盒可區分( n )可区分( n )可區

11、分( n )可区分( n )不可區分( n )不可区分( n )不可區分( r )不可区分( r )典型問題典型问题組合组合排列排列集合之分割集合之分割整數之分解整数之分解其中n或r表示盒子的個數，或球的個數。其中n或r表示盒子的个数，或球的个数。 下面我們將利用生成函數的方法討論這四類問題。下面我们将利用生成函数的方法讨论这四类问题。例a.6 設將相同的球放置於n個不同盒中，其中每一盒至少放q個球，並至多放q + z -1個球。 设将相同的球放置于n个不同盒中，其中每一盒至少放q个球，并至多放q + z -1个球。 此問題之生成函數是此问题之生成函数是使問題具體些。使问题具体些。 設有四人擲

12、骰，每人各擲一次，問當所得點數之和為17 時共有多少種可能方式。设有四人掷骰，每人各掷一次，问当所得点数之和为17 时共有多少种可能方式。 四人可看作四個相異的盒子，17 點可看作17 個相同的球。四人可看作四个相异的盒子，17 点可看作17 个相同的球。 這問題是當n =4 , r =17 , q =1 , z =6之特別情況。这问题是当n =4 , r =17 , q =1 , z =6之特别情况。 故答案為故答案为 展開式中x 13項之係數，即共104 種。展开式中x 13项之系数，即共104种。上面的例子虽然很不全面，但我们也可以看出，利用生成函数是解决组合问题的非常有效的方法，但在具

13、体问题中要注意具体问题具体分析，多研究，多体会，只有这样，才能真正掌握生成函数应用的技巧，做到事半功倍。作为本文最后的一个例，我们利用组合问题与其生成函数之对应关系证明下面著名的Euler 恒等式：其中，其中，首先我們要有下面結果：首先我们要有下面结果：例d.7 設n是一正整數，令E ( n )表示將n分解成偶數個部份均不等之分解個數； F ( n )表示將n分解成奇數個部份均不等之分解個數，則我們有设n是一正整数，令E ( n )表示将n分解成偶数个部份均不等之分解个数； F ( n )表示将n分解成奇数个部份均不等之分解个数，则我们有上式是利用Ferrers 圖示所產生的對應來證明。上式是

14、利用Ferrers 图示所产生的对应来证明。 設某一n之部份相異之分解的圖示有如左圖（我們用23=7+6+5+3+2為例）：设某一n之部份相异之分解的图示有如下图（我们用23=7+6+5+3+2为例）：令b記作底線上方框個數， d記作45°斜線上方框個數。令b记作底线上方框个数， d记作45°斜线上方框个数。 這裏有三種情況：这里有三种情况：如果b < d ， 則底線上b個方框可移至斜線上端如右圖所示。如果b < d ，则底线上b个方框可移至斜线上端如右图所示。 這樣n之分解中部份個數則減少了一個，且各部份仍保持相異。这样n之分解中部份个数则减少了一个，且各部份

15、仍保持相异。如果b = d ， 則底線方框仍可移至斜線上端，唯一例外是斜線和底線相交如下面左圖：如果b = d ，则底线方框仍可移至斜线上端，唯一例外是斜线和底线相交如下面左图：在這情況下，這分解有形式在这情况下，这分解有形式如果b > d ， 則斜線上方框可移至底部而令分解之部份個增加一個並各部份仍保持相異，唯一例外是斜線和底線相交如上面右圖且b = d +1在這情況下，這分解有形式如果b > d ，则斜线上方框可移至底部而令分解之部份个增加一个并各部份仍保持相异，唯一例外是斜线和底线相交如上面右图 且b = d +1在这情况下，这分解有形式當当 時，上面對應使E ( n )與F

16、 ( n )相等；當时，上面对应使E ( n )与F ( n )相等；当 時，則k是偶數使E ( n )比F ( n )多一個； k是奇數使E ( n )比F ( n )少一個。时，则k是偶数使E ( n )比F ( n )多一个； k是奇数使E ( n )比F ( n )少一个。 本例證畢。回到我們上面提到之Euler 恆等式。回到我们上面提到之Euler 恒等式。 它的左邊是一無窮乘積，恰是數列E( n )- F ( n )的生成函數。它的左边是一无穷乘积，恰是数列E( n )- F ( n )的生成函数. Generating function in the application of

17、 combined count【Abstract】Generating function that is generating function, is a combination of mathematics, especially in terms of count is an important theory and tools. Generating function was first proposed by French mathematician who is LaplaceP.S. In his 1812 book "probability theory"

18、clearly. Common type of generating function and the exponential generating function of two generating functions, which are more common type used. Generating function is simply the application of the unknown (general term) series of laws given by this method in the case of recursive type the general term of sequence obtained, generating functions are derived Fibonacci series one of the general formula . Another generating function is also widely used in programming and algorithm design, analysis, mathematical methods often use this procedure conside