生成函數(shù)在組合計數(shù)中的應(yīng)用

1、信息與計算科學(xué)畢業(yè)論文生成函數(shù)在組合計數(shù)中的應(yīng)用【摘要】生成函數(shù)即母函數(shù)，是組合數(shù)學(xué)中尤其是計數(shù)方面的一個重要理論和工具。最早提出母函數(shù)的人是法國數(shù)學(xué)家LaplaceP.S.在其1812年出版的概率的分析理論中明確提出。 生成函數(shù)有普通型生成函數(shù)和指數(shù)型生成函數(shù)兩種，其中普通型用的比較多。 生成函數(shù)的應(yīng)用簡單來說在于研究未知（通項）數(shù)列規(guī)律，用這種方法在給出遞推式的情況下求出數(shù)列的通項，生成函數(shù)是推導(dǎo)Fibonacci數(shù)列的通項公式方法之一。 另外生成函數(shù)也廣泛應(yīng)用于編程與算法設(shè)計、分析上，運用這種數(shù)學(xué)方法往往對程序效率與速度有很大改進(jìn)生成函數(shù)在組合問題中的應(yīng)用既靈活又具有一定的廣泛性，掌握生

2、成函數(shù)的構(gòu)造方法可以幫助學(xué)生提高其數(shù)學(xué)思維能力及解決實際問題的能力，文章總結(jié)了生成函數(shù)在組合問題的幾種常見用法?！娟P(guān)鍵詞】組合問題 遞推關(guān)系 拆分【前言】利用生成函數(shù)可以說是研究組合問題的一種最主要的常用的方法，生成函數(shù)的應(yīng)用也是數(shù)學(xué)中“以退為進(jìn)”思想的典型代表。生成函數(shù)這個名字看上去有點神秘，但其實它就是將一個數(shù)列轉(zhuǎn)化成一個函數(shù)的方法。其基本思想為：為了獲得一個序列:k0=的有關(guān)知識，我們引用一個冪級數(shù)g(x)=來整體表示這個序列，即g(x)為序列:k0的生成函數(shù)。這樣，一個序列和它的生成函數(shù)一一對應(yīng)，給了序列便得知它的生成函數(shù)；反之，求得生成函數(shù)序列也信息與計算科學(xué)畢業(yè)論文隨之而定，我們還

3、可以通過對函數(shù)的運算和分析得到這個序列的很多性質(zhì)。本文試圖通過一些實例談一談生成函數(shù)在組合上的幾種應(yīng)用。1. 利用生成函數(shù)證明組合恒等式組合恒等式的證明技巧性很強，解題方法獨特，其中利用構(gòu)造生成函數(shù)，比較等式兩端對應(yīng)項的系數(shù)，是證明組合恒等式的一種非常有效的方法。求證： 2+3+4+n=可以看出，該組合恒等式左端比較復(fù)雜，不太可能利用組合公式去證明，觀察后發(fā)現(xiàn)等式左端各項規(guī)律性較強。通過分析，設(shè)法將等式左端看作是某一函數(shù)中確定項的系數(shù)，由為中項的系數(shù)，所以我們構(gòu)造生成函數(shù)：fn(x)=(1+x)+2+n (x -1)fn(x)中的系數(shù)即為2+3+4+n .同時,利用”錯位相減法”易知:fn(x

4、)=+.比較的系數(shù)即得所證結(jié)果從上面可以看出，根據(jù)題意，靈活地引入生成函數(shù)是證明組合恒等式的關(guān)鍵所在。2. 生成函數(shù)在遞推關(guān)系上的應(yīng)用遞推關(guān)系是計算中的一個強有力工具，而遞推關(guān)系的求解一般比較困難利用生成函數(shù)求解遞推關(guān)系則是一種主要的、行之有效的方法。信息與計算科學(xué)畢業(yè)論文求n位十進(jìn)制數(shù)中出現(xiàn)偶數(shù)個5的數(shù)的個數(shù)。令= n位十進(jìn)制數(shù)中出現(xiàn)偶數(shù)個5的數(shù)的個數(shù)， =n位十進(jìn)制數(shù)中出現(xiàn)奇數(shù)個5的數(shù)的個數(shù)。因此有關(guān)系: 其中則，此關(guān)系為關(guān)于序列的遞推關(guān)系，求解此遞推關(guān)系是解決本問題的難點。我們可以考慮引進(jìn)序列的生成函數(shù)A(x)即：A(x)= ，利用錯位相加減的方法，即：A(x)=則(1-8x)A(x)=

5、8+9x+9= ,A(x)=再將A(x)展開成冪級數(shù)的形式：A(x)=(=因此遞推關(guān)系的求解主要是利用遞推關(guān)系求得生成函數(shù)的一種形式算法，生成函數(shù)確定了，相應(yīng)的遞推關(guān)系對應(yīng)的結(jié)果就確定了，這樣的例子還有很多，象著名的Hanoi塔問題，F(xiàn)ibonacci數(shù)列都是典型的利用生成函數(shù)解決遞推關(guān)系的例子3. 利用生成函數(shù)進(jìn)行整數(shù)的拆分信息與計算科學(xué)畢業(yè)論文組合數(shù)學(xué)中有很多實際問題都可以理解為將某一(些)整數(shù)按照一定條件進(jìn)行拆分，而求所有拆分的種類或方法，利用生成函數(shù)可以簡單有效地解決這類問題中的某些問題求方程滿足X1+X2+X3+X4=20滿足1 x1 6，0 x 2 7，4 x3 8，2 x4 6的

6、整數(shù)解的個數(shù)。此問題仍可看成是拆分?jǐn)?shù)的問題，把20拆分成滿足條件的4個整數(shù)和的方法數(shù)問題，根據(jù)x所需條件，引入生成函數(shù)：g(x)中的系數(shù)即為所求的滿足條件的整數(shù)解的個數(shù)?？梢越獾?96即為所求4. 生成函數(shù)在組合計算上的應(yīng)用生成函數(shù)的應(yīng)用確實很廣泛，利用生成函數(shù)還可以解決在排列組合中有關(guān)排法種數(shù)的問題:有紅球兩只，白球、黃球各一只，試求有多少種不同的組合方案。此問題不能看成是簡單的組合問題，也不是可重復(fù)元素的組合數(shù)問題，若用r，w，y分別代表紅球、白球、黃球，則不同的組合方案可有下面的式子給出:此結(jié)果可以看出,除一個球也不取的情況外,有:(a)取一個球的組合數(shù)為3，即分別取紅、白、黃三種；信息

7、與計算科學(xué)畢業(yè)論文(b)取兩個球的組合數(shù)為4，即兩個紅的、一紅一黃、一紅一白、一黃一自；(c)取三個球的組合數(shù)為3，即兩紅一黃、二紅一白、一紅一白一黃；(d)取四個球的組合數(shù)為1，即兩紅一黃一白。若此問題只求不同的方案種數(shù)，則可直接利用生成函數(shù)。設(shè)取r個球的組合數(shù)為Cr (or4)，則Cr的生成函數(shù)為：G(x) = (1+x +x2 )(1 + x)2 = 1+3x十4x2 十3x3 +x4。共有1+3+4+3+1 =12種組合方式。設(shè)有n個物件，并設(shè)n ( r )是由n個不同物件中可任意重復(fù)地取r個物件生成函數(shù)的組合數(shù)。 這個組合問題的生成函數(shù)即是 x r之系數(shù)等于n ( r ) 之生成函數(shù)

8、。 對一個物件來說，我們可以不選取，選取一次，選取二次等等，其方法可用式子表示。 對第二個，第三個等物件也有同樣作法。 故其生成函數(shù)是我們必須將它寫成標(biāo)準(zhǔn)形式。 因為信息與計算科學(xué)畢業(yè)論文故我們得令n ( r )是由n個不同物件中可任意重復(fù)地取r個，并在每一選取中，每個物件必須至少包含一次的組合數(shù)。數(shù)列n( r )的生成函數(shù)是故得 。 顯然如果r<n ，本問題無解。信息與計算科學(xué)畢業(yè)論文簡單推廣上述問題，若在每一選取中每個物件必須至少選取q次，則一般排列組合問題可以歸納成將球放入盒中的問題。 其中可將球與盒子看成可區(qū)分的或不可區(qū)分的，而每一盒子又可被允許放最多一個球，或超過一個球而產(chǎn)生各

9、種情況。 組合問題可看成將不可區(qū)分的球放入可區(qū)分的盒中之問題。 a的問題相當(dāng)于要求出將r個相同的球放入n個不同盒中之方法個數(shù)，其中每一盒必須至少放一個球。 放球入盒的各種情況可列表如下：其中n或r表示盒子的個數(shù)，或球的個數(shù)。 下面我們將利用生成函數(shù)的方法討論這四類問題。設(shè)將相同的球放置于n個不同盒中，其中每一盒至少放q個球，并至多放q + z -1個球。 此問題之生成函數(shù)是信息與計算科學(xué)畢業(yè)論文使問題具體些。 設(shè)有四人擲骰，每人各擲一次，問當(dāng)所得點數(shù)之和為17 時共有多少種可能方式。 四人可看作四個相異的盒子，17 點可看作17 個相同的球。 這問題是當(dāng)n =4 , r =17 , q =1

10、, z =6之特別情況。 故答案為中x13項之系數(shù)，即共104種。展開式上面的例子雖然很不全面，但我們也可以看出，利用生成函數(shù)是解決組合問題的非常有效的方法，但在具體問題中要注意具體問題具體分析，多研究，多體會，只有這樣，才能真正掌握生成函數(shù)應(yīng)用的技巧，做到事半功倍。作為本文最后的一個例，我們利用組合問題與其生成函數(shù)之對應(yīng)關(guān)系證明下面著名的Euler 恒等式：其中，信息與計算科學(xué)畢業(yè)論文首先我們要有下面結(jié)果：設(shè)n是一正整數(shù)，令E ( n )表示將n分解成偶數(shù)個部份均不等之分解個數(shù)； F ( n )表示將n分解成奇數(shù)個部份均不等之分解個數(shù)，則我們有上式是利用Ferrers 圖示所產(chǎn)生的對應(yīng)來證明

11、。 設(shè)某一n之部份相異之分解的圖示有如下圖（我們用23=7+6+5+3+2為例）：令b記作底線上方框個數(shù)， d記作45°斜線上方框個數(shù)。 這里有三種情況： 如果b<d ，則底線上b個方框可移至斜線上端如右圖所示。 這樣n之分解中部份個數(shù)則減少了一個，且各部份仍保持相異。信息與計算科學(xué)畢業(yè)論文如果b = d ，則底線方框仍可移至斜線上端，唯一例外是斜線和底線相交如下面左圖：在這情況下，這分解有形式如果b>d ，則斜線上方框可移至底部而令分解之部份個增加一個并各部份仍保持相異，唯一例外是斜線和底線相交如上面右圖 且b = d +1在這情況下，這分解有形式當(dāng) 時，上面對應(yīng)使E

12、( n )與F ( n )相等；當(dāng) 時，則k是偶數(shù)使E ( n )比F ( n )多一個； k是奇數(shù)使E ( n )比F ( n )少一個。 。信息與計算科學(xué)畢業(yè)論文回到我們上面提到之Euler 恒等式。 它的左邊是一無窮乘積，恰是數(shù)列E( n )- F ( n )的生成函數(shù).Generating function in the application of combinedcount【Abstract】Generating function that is generating function, is a combination of mathematics, especially in

13、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" clearly. Common type of generating function and the exponential generating function of two generating functions, which ar

14、e 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信息與計算科學(xué)畢業(yè)論文 general formula . Anot

15、her generating function is also widely used in programming and algorithm design, analysis, mathematical methods often use this procedure considerably improved the efficiency and speed Generating function in the application of combinatorial problems in flexible and has a certain universality, to master the construction of generating function method can help students improve their mathematical thinking and the ability to solve practical problems, the article summarizes the problem of generating function in the combination of se