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

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

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

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

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

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

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

7、與計(jì)算科學(xué)畢業(yè)論文(b)取兩個(gè)球的組合數(shù)為4，即兩個(gè)紅的、一紅一黃、一紅一白、一黃一自；(c)取三個(gè)球的組合數(shù)為3，即兩紅一黃、二紅一白、一紅一白一黃；(d)取四個(gè)球的組合數(shù)為1，即兩紅一黃一白。若此問題只求不同的方案種數(shù)，則可直接利用生成函數(shù)。設(shè)取r個(gè)球的組合數(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個(gè)物件，并設(shè)n ( r )是由n個(gè)不同物件中可任意重復(fù)地取r個(gè)物件生成函數(shù)的組合數(shù)。 這個(gè)組合問題的生成函數(shù)即是 x r之系數(shù)等于n ( r ) 之生成函數(shù)

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

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

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

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

12、( n )與F ( n )相等；當(dāng) 時(shí)，則k是偶數(shù)使E ( n )比F ( n )多一個(gè)； k是奇數(shù)使E ( n )比F ( n )少一個(gè)。 。信息與計(jì)算科學(xué)畢業(yè)論文回到我們上面提到之Euler 恒等式。 它的左邊是一無(wú)窮乘積，恰是數(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信息與計(jì)算科學(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