1、生成函數(shù)在組合計(jì)數(shù)中的應(yīng)用【摘要】生成函數(shù)是組合數(shù)學(xué)特別是計(jì)算方面的重要理論和工具。第一個(gè)提出母艦首號(hào)的人是法國(guó)數(shù)學(xué)家拉普拉ep.s .在1812年出版的概率的分析理論中明確提出的。生成函數(shù)有兩種：一般型生成函數(shù)和金志洙生成函數(shù)，其中一般型使用較多。生成函數(shù)的應(yīng)用在于研究未知(一般)數(shù)列法則，如果提供遞歸，這是簡(jiǎn)單地推導(dǎo)斐波那契數(shù)列的一般公式方法之一，那么尋找數(shù)列的一般項(xiàng)目。生成函數(shù)還廣泛用于編程和算法設(shè)計(jì)、分析，使用此數(shù)學(xué)方法通?？梢燥@著提高程序效率和速度可以靈活多樣地將生成函數(shù)應(yīng)用于組合問題，掌握函數(shù)生成方法有助于學(xué)生提高數(shù)學(xué)思維能力和實(shí)際解決問題的能力，總結(jié)了組合問題中生成函數(shù)的一些常用

2、用法?！娟P(guān)鍵詞】組合問題遞歸關(guān)系劃分使用生成函數(shù)是研究組合問題最重要的常用方法之一，生成函數(shù)的應(yīng)用也可以說是數(shù)學(xué)中表示“后退”的常用方法。函數(shù)生成這個(gè)名稱看起來有點(diǎn)神秘，但實(shí)際上是將系列轉(zhuǎn)換為一個(gè)函數(shù)的方法。其基本想法是序列:k0=.為了獲取的知識(shí)，冪級(jí)數(shù)g(x)=.引用以整體表示此序列。也就是說，g (x)是序列: k 0的生成函數(shù)。這樣，序列對(duì)其生成函數(shù)一一對(duì)應(yīng)，使序列知道其生成函數(shù)。相反，生成函數(shù)序列也因此可以通過函數(shù)的運(yùn)算和分析得到此序列的很多特性。本文想舉例說明生成函數(shù)的組合。1.使用生成函數(shù)證明組合身份組合身份證明技術(shù)強(qiáng)，解決問題的方法獨(dú)特。在這里，使用構(gòu)造生成函數(shù)比較方程兩端對(duì)應(yīng)

3、項(xiàng)的系數(shù)是證明組合身份的非常有效的方法。證詞：2 3 4.n=可以看出這個(gè)組合恒等式的左端更復(fù)雜，使用組合公式證明的可能性不大，觀察表明等式的左端具有很強(qiáng)的規(guī)律性。通過分析，將公式的左端視為函數(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í)使用“前綴減法”容易知道：Fn(x)=。比較的系數(shù)就是證明的結(jié)果如上所述，根據(jù)問題的意義靈活引入生成函數(shù)是證明組合身份的關(guān)鍵。生成函數(shù)在遞歸關(guān)系中的應(yīng)用遞歸關(guān)系是計(jì)算的有力工具，求解遞歸關(guān)系通常更困難。使用生成函數(shù)求解遞歸關(guān)系是最重要、最有效的方法。尋找n位元十進(jìn)位中偶數(shù)5的

4、數(shù)字。順序=n位十進(jìn)制數(shù)中偶數(shù)5的個(gè)數(shù)，=n位十進(jìn)制數(shù)中奇數(shù)5的個(gè)數(shù)。與：有關(guān)此關(guān)系是對(duì)難以解決問題的序列的遞歸關(guān)系。我們可以考慮序列的生成函數(shù)a (x)。即：A(x)=，如何使用前綴加法和減法，即：A(x)=然后(1-8x)A(x)=8 9x 9=，A(x)=將A(x)展開為冪級(jí)數(shù)形式。A(x)=(=所以遞歸關(guān)系的求解主要使用遞歸關(guān)系來尋找生成函數(shù)的一種形式算法，生成函數(shù)決定，相應(yīng)遞歸關(guān)系的結(jié)果決定。例如，著名的河內(nèi)塔問題、Fibonacci系列等3.使用生成函數(shù)拆分整數(shù)組合數(shù)學(xué)中有很多實(shí)際問題，將特定(部分)整數(shù)理解為根據(jù)特定條件進(jìn)行劃分，如果要查找所有劃分的種類或方法，生成函數(shù)可以幫助您

5、簡(jiǎn)單有效地解決其中的一些問題X1 X2 X3 X4=20尋找滿足1x16，0x 27，4X38，2X46的整數(shù)解的個(gè)數(shù)。這個(gè)問題仍然可以看作是分割分?jǐn)?shù)的問題。將20除以滿足條件的四個(gè)整數(shù)和方法數(shù)，根據(jù)x所需的條件引入生成函數(shù)。G(x)的系數(shù)是滿足條件的整數(shù)解的數(shù)目?？山鉀Q=96是請(qǐng)求在組合計(jì)算中應(yīng)用生成函數(shù)“繁殖”函數(shù)使用得非常廣泛，使用“繁殖”函數(shù)還可以解決排序組合中種子數(shù)量的問題：2個(gè)紅球、白色球、1個(gè)黃球有幾種不同的組合方案。這個(gè)問題不能看作是簡(jiǎn)單的組合問題或可重復(fù)元素的組合數(shù)問題。如果r、w、y分別表示紅球、白球和黃球，則可以提供以下組合劑：這個(gè)結(jié)果表明，除了拿一個(gè)球渡邊杏外，還有：(

6、a)拿一個(gè)球的組合數(shù)是3個(gè)，即紅、白、黃。(b)兩個(gè)球體的組合數(shù)為4，即兩個(gè)紅色，一個(gè)紅色，一個(gè)紅色，一個(gè)白色，一個(gè)黃色。(c)取三個(gè)球的組合數(shù)3，即兩個(gè)紅色，一個(gè)紅色，一個(gè)紅色，一個(gè)紅色，一個(gè)黃色。(d)有4個(gè)球的組合數(shù)是1，即2個(gè)紅色和1個(gè)黃色和1個(gè)白色。如果此問題查找其他模式種子數(shù)，則可以直接使用生成函數(shù)。當(dāng)r球的組合數(shù)為Cr(or4)時(shí)，Cr的生成函數(shù)為：g(x)=(1 x x2)(1 x)2=1 3x 10 4x 2 10 3x 3 x4?？傆?jì)1 3 4 3 1=12種組合方式：設(shè)置具有n個(gè)對(duì)象的組合數(shù)，n (r)可以將r個(gè)對(duì)象生成函數(shù)用作n個(gè)徐璐其他對(duì)象中的任意迭代。此組合問題的生

7、成函數(shù)等于“x r的系數(shù)為n (r)”。此組合問題的生成函數(shù)等于“x r的系數(shù)為n (r)”。對(duì)于對(duì)象，可以使用渡邊杏選擇、一次選擇、兩次選擇等方法。對(duì)于對(duì)象，可以使用渡邊杏選擇、一次選擇、兩次選擇等方法表示。表示。這同樣適用于第二、第三等對(duì)象。這同樣適用于第二、第三等對(duì)象。生成函數(shù)包括：生成函數(shù)包括我們必須以標(biāo)準(zhǔn)形式寫它。我們必須以標(biāo)準(zhǔn)形式寫它。因?yàn)楦呔潲愇覀儽仨氉鍪纠齛.5 n (r)可以在n個(gè)其他對(duì)象中隨機(jī)重復(fù)使用r，每個(gè)選擇都具有組合數(shù)量的原始注釋2，其中每個(gè)對(duì)象至少必須包含一次。Aaq命令n (r)可以從n個(gè)徐璐的其他對(duì)象中隨機(jī)獲取r，并且每個(gè)選擇必須至少包含一次的組合數(shù)。序列n(r

8、 )的生成函數(shù)包括序列n(r )的生成函數(shù)所以得到了。即可從workspace頁面中移除物件。顯然，如果r n，這個(gè)問題就解決不了。顯然，如果r n，這個(gè)問題就解決不了。以上問題的簡(jiǎn)單推廣，如果在每個(gè)選擇區(qū)域中每個(gè)對(duì)象必須至少選擇q，則簡(jiǎn)單地宣傳上述問題，如果在每個(gè)選擇區(qū)域中每個(gè)對(duì)象必須至少選擇q一般的數(shù)組組合問題可以概括為把球放進(jìn)箱子的問題。一般的數(shù)組組合問題可以概括為把球放進(jìn)箱子的問題。其中球和長(zhǎng)方體可以分辨或不可分辨，每個(gè)長(zhǎng)方體最多可以放1個(gè)或1個(gè)以上的球，可能會(huì)發(fā)生各種情況。其中球和長(zhǎng)方體可以分辨或不可分辨，每個(gè)長(zhǎng)方體最多可以放1個(gè)或1個(gè)以上的球，可能會(huì)發(fā)生各種情況。組合問題可以看作是

9、把不可分辨的球放進(jìn)可分辨的箱子里的問題。組合問題可以看作是把不可分辨的球放進(jìn)可分辨的箱子里的問題。例如，示例a.4的問題相當(dāng)于要求r個(gè)相同的球，是n個(gè)不同的長(zhǎng)方體中可以隨機(jī)重新放入的方法的數(shù)量。示例a.5問題等于將r個(gè)相同的球放入n個(gè)不同的長(zhǎng)方體的方法數(shù)。其中，每個(gè)箱子必須至少放一個(gè)a的問題與把r個(gè)相同的球放在n個(gè)不同的箱子里的方法數(shù)相同。在這里，每個(gè)箱子必須至少放一個(gè)球。將球放入箱子時(shí)的列表如下：將球放入箱子時(shí)的列表如下：A aB bC cD d球分隔渡邊杏盒(r)分隔渡邊杏盒(r)可分辨(r)可分辨(r)可分辨(r)可分辨(r)分隔渡邊杏盒(n)分隔渡邊杏盒(n)箱子可分辨(n)可分辨(n

10、)可分辨(n)可分辨(n)分隔渡邊杏盒(n)分隔渡邊杏盒(n)分隔渡邊杏盒(r)分隔渡邊杏盒(r)典型問題典型問題組合組合組合排列陣列分割集合的分割集整數(shù)分解整數(shù)的分解解其中n或r表示長(zhǎng)方體的數(shù)量或球體的數(shù)量。其中n或r表示長(zhǎng)方體的數(shù)量或球體的數(shù)量。下面使用創(chuàng)建函數(shù)的方法討論這四種類型的問題。下面使用創(chuàng)建函數(shù)的方法討論這四種類型的問題。示例a.6將相同的球設(shè)置為放置在n個(gè)不同的長(zhǎng)方體中，每個(gè)長(zhǎng)方體包含最小q球和最大q z -1球。在n個(gè)不同的框中放置相同的球，每個(gè)框中放置最小q和最大q z -1個(gè)球。這個(gè)問題的生成函數(shù)是這個(gè)問題的生成函數(shù)。具體問題。具體問題。4人擲骰子，每人扔一次，并詢問在總

11、數(shù)為17時(shí)可能的方法有多少。4人擲骰子，每人扔一次，并詢問在總數(shù)為17時(shí)可能的方法有多少。4個(gè)人可以看作4個(gè)徐璐不同的箱子，17點(diǎn)可以看作17個(gè)相同的球。4個(gè)人可以看作4個(gè)徐璐不同的箱子，17點(diǎn)可以看作17個(gè)相同的球。此問題是n=4、r=17、q=1、z=6的特殊情況。此問題是n=4、r=17、q=1、z=6的特殊情況。答案是展開圖的13個(gè)系數(shù)，即總計(jì)104個(gè)。展開圖中13個(gè)料件的系數(shù)，即總計(jì)104個(gè)。上面的例子雖然不完整，但也可以看出利用生成函數(shù)是解決組合問題的非常有效的方法，但在具體問題上，必須對(duì)特定問題進(jìn)行具體的分析，多研究，多經(jīng)驗(yàn)，這樣才能真正掌握生成函數(shù)應(yīng)用程序的技術(shù)，做更多的工作。

12、在本文的最后一個(gè)示例中，使用組合問題與其生成函數(shù)之間的對(duì)應(yīng)關(guān)系來證明以下著名的歐拉身份：其中，首先，必須有以下結(jié)果：首先，必須有以下結(jié)果：示例d.7如果將n設(shè)置為正整數(shù)，則E (n)表示將n分解為偶數(shù)部分的分解數(shù)。F (n)表示將n分解為奇數(shù)部分的分解數(shù)。n是正整數(shù)，E (n)表示將n分解為偶數(shù)部分的分解數(shù)。F (n)表示將n分解為奇數(shù)部分的分解數(shù)常識(shí)使用Ferrers圖標(biāo)生成的映射進(jìn)行證明。常識(shí)使用Ferrers圖標(biāo)生成的映射進(jìn)行證明。設(shè)置n的一部分不同的分解圖標(biāo)，例如23=7 6 5 3 2，如左圖所示。設(shè)置n的一部分不同的分解圖標(biāo)，例如23=7 6 5 3 2。用下劃線中的框數(shù)表示b，用

13、45斜線中的框數(shù)表示d。用下劃線中的框數(shù)表示b，用45斜線中的框數(shù)表示d。這里有三種情況。這里有三種情況。如果是B d，下劃線中的b框?qū)⒁苿?dòng)到斜線頂部，如圖所示。如果是B d，下劃線中的b框?qū)⒁苿?dòng)到斜線頂部，如圖所示。這將n的分解中的部分?jǐn)?shù)減少一個(gè)，每個(gè)部分保持不同。這將n的分解中的部分?jǐn)?shù)減少一個(gè)，每個(gè)部分保持不同。當(dāng)B=d時(shí)，下劃線框可以繼續(xù)移動(dòng)到斜線頂部，但斜線和下劃線的交點(diǎn)除外，如下圖所示。如果b=d，則下劃線框仍可以移動(dòng)到斜線頂部。例外情況是斜線和下劃線相交，如下圖所示。在這種情況下，此分解具有形式。在這種情況下，此分解具有形狀如果是B d，則可以將斜杠上方的框移動(dòng)到底部，添加分解部分

14、的一部分，并保持每個(gè)部分不同。但是，如果正斜線和下劃線相交且b=d 1(如上圖所示)分解為b d，則可以將正斜線上方的框移動(dòng)到底部，以添加分解部分的一部分并保留另一部分。例外情況是斜線和下劃線相交(如上圖所示)，并且b=d 1Dangdang，上述匹配使E (n)和F (n)相等。當(dāng)時(shí)使E (n)和F (n)相等。如果k是偶數(shù)，則E (n)比F (n)多一個(gè)。k是奇數(shù)，E (n)比F (n)少一個(gè)。k是偶數(shù)，E (n)比F (n)多一個(gè)。k是奇數(shù)，E (n)比F (n)少一個(gè)。此示例已完成。即可從workspace頁面中移除物件?；氐轿覀兲岬降臍W拉身份?；氐轿覀兲岬降臍W拉身份。左邊是無限的乘積。這就是序列E(n )- F (n )的生成函數(shù)。左邊是無限的乘積。這就是序列E(n )- F (n )的生成函數(shù)。generating function in the application of combined countabstract gene rating function that is gene rating function，is a combination of mathematics，Especally in terms of count is an importation which are more common type used . ge