這可能是最通俗最詳細的生成函式講解了吧!!!

前言:

寫這篇文章的時候自己是個數學 f w fw fw

但其實生成函式,組合數學用到的數學都是 f w fw fw能學會的

堅持看下去一定能看懂的!!!

初識生成函式

生成函式是一個關于 x x x的多項式函式,用于表示一個數列.

比如一個數列 s s s=1,2,3,4,5,6,7…

那么 s s s對應的生成函式就是 1 + 2 x + 3 x 3 + 4 x 4 + 5 x 5 . . . 1+2x+3x^3+4x^4+5x^5... 1+2x+3x3+4x4+5x5...

其中 x i x^i xi的系數對應 s i s_i si?

其中 x x x的取值沒有任何意義,叫做形式冪級數.

生成函式有什么用??

舉個講生成函式都會提到的經典例子.

物品 A A A有 2 2 2個,物品 B B B有 2 2 2個,物品 C C C有 3 3 3個

取出 k k k個物品有多少種取法?

這種問題一般可用背包解,但其實背包也是在模仿很像生成函式.

物品 A A A的生成函式是 1 + x + x 2 1+x+x^2 1+x+x2

含義是:取出 0 , 1 , 2 0,1,2 0,1,2個物品都只有一種取法,所以系數是 1 1 1

物品 B B B的生成函式是 1 + x + x 2 1+x+x^2 1+x+x2

物品 C C C的生成函式是 1 + x + x 2 + x 3 1+x+x^2+x^3 1+x+x2+x3

將 A , B , C A,B,C A,B,C的生成函式相乘得到一個新的生成函式

1 + 3 x + 6 x 2 + 8 x 3 + 9 x 4 + 6 x 5 + 3 x 6 + x 7 1+3x+6x^2+8x^3+9x^4+6x^5+3x^6+x^7 1+3x+6x2+8x3+9x4+6x5+3x6+x7

此時 x i x^i xi的系數就是取 i i i個物品的方案數，

構造斐波那契通項

生成函式引入

前面說到生成函式一般用于表示一個無限數列

比如對于一個無窮項,每一項都是 1 1 1的數列,生成函式是

1 + x + x 2 + x 3 . . . . = ∑ i = 0 ∞ x i 1+x+x^2+x^3....=\sum\limits_{i=0}^{\infty}x^i 1+x+x2+x3....=i=0∑∞?xi

當 x ∈ ( ? 1 , 1 ) x\in(-1,1) x∈(?1,1)時,運用等比數列求和

∑ i = 0 inf ? x i = ( 1 ? x i n f ) 1 ? x = 1 1 ? x = 1 + x + x 2 . . . . . \sum\limits_{i=0}^{\inf}x_i=\frac{(1-x^{inf})}{1-x}=\frac{1}{1-x}=1+x+x^2..... i=0∑inf?xi?=1?x(1?xinf)?=1?x1?=1+x+x2.....

所以,對于所有項都是 1 1 1的無窮數列的生成函式是 1 1 ? x \frac{1}{1-x} 1?x1?

也就是 1 1 ? x \frac{1}{1-x} 1?x1?表示 1 , 1 , 1 , 1..... 1,1,1,1..... 1,1,1,1.....

兩邊乘一個 2 2 2得到新的生成函式 2 1 ? x \frac{2}{1-x} 1?x2?,表示 2 , 2 , 2 , 2 , 2.... 2,2,2,2,2.... 2,2,2,2,2....

兩邊乘一個 x x x得到 x 1 ? x \frac{x}{1-x} 1?xx?,表示 0 , 1 , 1 , 1 , 1... 0,1,1,1,1... 0,1,1,1,1...

兩邊乘一個 2 x 2x 2x得到 2 x 1 ? x \frac{2x}{1-x} 1?x2x?,表示 0 , 0 , 2 , 2 , 2... 0,0,2,2,2... 0,0,2,2,2...

兩邊同時求導得到 1 ( 1 ? x ) 2 \frac{1}{(1-x)^2} (1?x)21?,表示 1 , 2 , 3 , 4 , 5... 1,2,3,4,5... 1,2,3,4,5...

根據這樣的性質,就可以通過一些玄學鬼畜的方法求數列的通項

斐波那契生成函式

斐波那契的遞推式為 f [ i ] = f [ i ? 2 ] + f [ i ? 1 ] ( i > = 2 ) f[i]=f[i-2]+f[i-1]\ (i>=2) f[i]=f[i?2]+f[i?1] (i>=2)

其中 f [ 0 ] = f [ 1 ] = 1 f[0]=f[1]=1 f[0]=f[1]=1

那么斐波那契的生成函式記作 G G G

G = 1 + x + 2 x 2 + 3 x 3 + 5 x 4 + 8 x 5 . . . . G=1+x+2x^2+3x^3+5x^4+8x^5.... G=1+x+2x2+3x3+5x4+8x5....

x G = x + x 2 + 2 x 2 + 3 x 4 + 5 x 5 . . . . xG=\ \ \ \ \ x+x^2+2x^2+3x^4+5x^5.... xG= x+x2+2x2+3x4+5x5....

x 2 G = x 2 + x 3 + 2 x 4 + 3 x 5 . . . x^2G=\ \ \ \ \ \ \ \ \ \ \ \ x^2+x^3+2x^4+3x^5... x2G= x2+x3+2x4+3x5...

G ? x G ? x 2 G = 1 G-xG-x^2G=1 G?xG?x2G=1

G = 1 1 ? x ? x 2 G=\frac{1}{1-x-x^2} G=1?x?x21?

得到了這個簡潔的式子,然鵝沒什么亂用因為這樣看不出第 i i i項的系數

但是我們知道 1 1 ? x \frac{1}{1-x} 1?x1?的第 n n n項系數是 n n n

所以我們的目標就是把 G G G化成類似那種形式得到通項，

化簡生成函式得到通項

G G G的分母 1 ? x ? x 2 1-x-x^2 1?x?x2可以構造成如下形式

1 ? x ? x 2 = ( 1 ? ? 1 x ) ( 1 ? ? 2 x ) 1-x-x^2=(1-\phi_1x)(1-\phi_2x) 1?x?x2=(1??1?x)(1??2?x)

{ ? 1 + ? 2 = 1 ? 1 ? ? 2 = ? 1 \left\{ \begin{aligned} \phi_1+\phi_2=1\\ \phi_1*\phi_2=-1 \end{aligned} \right. {?1?+?2?=1?1???2?=?1?

聯立解得 ? 1 = 1 + 5 2 , ? 2 = 1 ? 5 2 \phi_1=\frac{1+\sqrt{5}}{2},\phi_2=\frac{1-\sqrt{5}}{2} ?1?=21+5 ??,?2?=21?5 ??

那么 G = 1 ( 1 ? ? 1 x ) ( 1 ? ? 2 x ) G=\frac{1}{(1-\phi_1x)(1-\phi_2x)} G=(1??1?x)(1??2?x)1?

對 G G G裂項得到

G = a 1 ? ? 1 x + b 1 ? ? 2 x G=\frac{a}{1-\phi_1x}+\frac{b}{1-\phi_2x} G=1??1?xa?+1??2?xb?

那么得到 a ( 1 ? ? 2 x ) + b ( 1 ? ? 1 x ) = 1 a(1-\phi_2x)+b(1-\phi_1x)=1 a(1??2?x)+b(1??1?x)=1

化簡 ( a + b ? 1 ) ? ( a ? 1 + b ? 2 ) x = 0 (a+b-1)-(a\phi_1+b\phi_2)x=0 (a+b?1)?(a?1?+b?2?)x=0

所以得到方程組

{ a + b ? 1 = 0 a ? 1 + b ? 2 = 0 \left\{ \begin{aligned} a+b-1=0\\ a\phi_1+b\phi_2=0 \end{aligned} \right. {a+b?1=0a?1?+b?2?=0?
解得 a = 1 5 ? 1 , b = ? 1 5 ? 2 a=\frac{1}{\sqrt{5}}\phi_1,b=-\frac{1}{\sqrt{5}}\phi_2 a=5 ?1??1?,b=?5 ?1??2?

于是 G = ? 1 5 ? 1 1 ? ? 1 x ? ? 2 5 ? 1 1 ? ? 2 x G=\frac{\phi_1}{\sqrt{5}}*\frac{1}{1-\phi_1x}-\frac{\phi_2}{\sqrt{5}}*\frac{1}{1-\phi_2x} G=5 ??1???1??1?x1??5 ??2???1??2?x1?

觀察一下 1 1 ? ? 1 x \frac{1}{1-\phi_1x} 1??1?x1?表示的數列不就是 ? 1 , ? 1 2 , ? 1 3 . . . . . . . . \phi_1,\phi_1^2,\phi_1^3........ ?1?,?12?,?13?........

那么 G G G的 x n x^n xn項的系數就是

? 1 n + 1 5 ? ? 2 n + 1 5 = 1 5 ? [ ( 1 + 5 2 ) n + 1 ? ( 1 ? 5 2 ) n + 1 ] \frac{\phi_1^{n+1}}{\sqrt{5}}-\frac{\phi_2^{n+1}}{\sqrt{5}}=\frac{1}{\sqrt{5}}*[(\frac{1+\sqrt{5}}{2})^{n+1}-(\frac{1-\sqrt{5}}{2})^{n+1}] 5 ??1n+1???5 ??2n+1??=5 ?1??[(21+5 ??)n+1?(21?5 ??)n+1]

至此,你是不是理解了玄妙的生成函式?

居然能把斐波那契的通項求出來!!

生成函式展開利器!!廣義二項式定理

普通的二項式定理

( 1 + x ) n = ∑ i = 0 n ( n i ) 1 n ? i x = ∑ i = 0 n ( n i ) x i (1+x)^n=\sum\limits_{i=0}^n{n \choose i}1^{n-i}x=\sum\limits_{i=0}^n{n \choose i}x^i (1+x)n=i=0∑n?(in?)1n?ix=i=0∑n?(in?)xi

擴展域:牛頓廣義二項式定理

( 1 + x ) n = ∑ i = 0 ∞ ( n i ) x i (1+x)^n=\sum\limits_{i=0}^{\infty}{n \choose i}x^i (1+x)n=i=0∑∞?(in?)xi

這個很好理解,當 i < = n i<=n i<=n時就是普通的二項式定理

當 i > n i>n i>n根據組合數的性質, ( n i ) {n \choose i} (in?)應該是為 0 0 0的,所以沒有影響

擴展指數為負數

為了推廣這個,我們需要推廣一下組合數

( n m ) = n ( n ? 1 ) ( n ? 2 ) . . . ( n ? m + 1 ) m ! { n \choose m}=\frac{n(n-1)(n-2)...(n-m+1)}{m!} (mn?)=m!n(n?1)(n?2)...(n?m+1)?

那么 ( 1 + x ) ? n = ∑ i = 1 ∞ ( ? n i ) x i (1+x)^{-n}=\sum\limits_{i=1}^{\infty}{-n \choose i}x^i (1+x)?n=i=1∑∞?(i?n?)xi

是不是很震驚??組合數還有負數?沒事,組合數定義我們已經推廣過

( ? n m ) = ( ? n ) ( ? n ? 1 ) ( ? n ? 2 ) . . . ( ? n ? m + 1 ) m ! {-n \choose m}=\frac{(-n)(-n-1)(-n-2)...(-n-m+1)}{m!} (m?n?)=m!(?n)(?n?1)(?n?2)...(?n?m+1)?

把分子所有項取反得到

( ? n m ) = ( ? 1 ) ? n ? ( ? n ? m + 1 ) + 1 ? n ( n + 1 ) ( n + 2 ) . . . ( n + m ? 1 ) m ! {-n \choose m}=(-1)^{-n-(-n-m+1)+1}*\frac{n(n+1)(n+2)...(n+m-1)}{m!} (m?n?)=(?1)?n?(?n?m+1)+1?m!n(n+1)(n+2)...(n+m?1)?

( ? n m ) = ( ? 1 ) m ( n + m ? 1 m ) {-n \choose m}=(-1)^m{n+m-1 \choose m} (m?n?)=(?1)m(mn+m?1?)

于是,當二項式定理指數為負數時,有

( 1 + x ) ? n = ∑ i = 0 ∞ ( ? 1 ) i ( n + i ? 1 i ) x i (1+x)^{-n}=\sum\limits_{i=0}^{\infty}(-1)^i{n+i-1 \choose i}x^i (1+x)?n=i=0∑∞?(?1)i(in+i?1?)xi

當括號內的加號變減號時

( 1 ? x ) ? n = ∑ i = 0 ∞ ( ? 1 ) i ( n + i ? 1 i ) ( ? x ) i (1-x)^{-n}=\sum\limits_{i=0}^{\infty}(-1)^i{n+i-1 \choose i}(-x)^i (1?x)?n=i=0∑∞?(?1)i(in+i?1?)(?x)i

= ∑ i = 0 ∞ ( n + i ? 1 i ) x i =\sum\limits_{i=0}^{\infty}{n+i-1 \choose i}x^i =i=0∑∞?(in+i?1?)xi

這個叫做廣義二項式定理的東西在化簡生成函式的時候會起大作用

對于生成函式 ( 1 ? x ) ? n (1-x)^{-n} (1?x)?n,很容易知道它的第 i i i項系數

進階!解決排列問題的指數型生成函式

引入問題

回顧一下上面說到的這樣一個問題

物品 A A A有 a a a個,物品 B B B有 b b b個,物品 C C C有 c c c個

取出 k k k個物品有多少種取法?(注意取出(AB)和(BA)屬于不同的取法)

如果不需要考慮順序,構造普通生成函式相乘, x k x^k xk系數就是答案.

但這是排列啊!!其實這個東西叫做多重集排列問題

若把物品 A , B , C A,B,C A,B,C拿來排列方案數是

( a + b + c ) ! a ! b ! c ! \frac{(a+b+c)!}{a!\ b!\ c!} a! b! c!(a+b+c)!?

這個很好理解, ( a + b + c ) ! (a+b+c)! (a+b+c)!是排列,但是同種物品需要去重

而普通生成函式系數計算的是組合的方案數,去重不就好了嗎?

所以,若物品 A A A有 a a a個,對應的指數生成函式為

1 + x 1 ! + x 2 2 ! + x 3 3 ! . . . . + x a a ! 1+\frac{x}{1!}+\frac{x^2}{2!}+\frac{x^3}{3!}....+\frac{x^a}{a!} 1+1!x?+2!x2?+3!x3?....+a!xa?

設物品 B B B有 b b b個,對應的指數生成函式為

1 + y 1 ! + y 2 2 ! + y 3 3 ! . . . . + y a a ! 1+\frac{y}{1!}+\frac{y^2}{2!}+\frac{y^3}{3!}....+\frac{y^a}{a!} 1+1!y?+2!y2?+3!y3?....+a!ya?

考慮這兩個多項式相乘得到的第 k k k項系數為 ∑ i = 0 k 1 i ! ( k ? i ) ! x i y k ? i \sum\limits_{i=0}^k\frac{1}{i!(k-i)!}x^iy^{k-i} i=0∑k?i!(k?i)!1?xiyk?i

那么就應該知道 1 i ! ( k ? i ) ! \frac{1}{i!(k-i)!} i!(k?i)!1?是為了給同種物品去重,乘上 k ! k! k!全排列就是方案數.

展開 e x 成 系 數 表 達 式 e^x成系數運算式 ex成系數表達式

而且有意思的是,指數型生成函式可以化簡為

∑ i = 0 ∞ x i i ! = e x \sum\limits_{i=0}^{\infty}\frac{x^i}{i!}=e^{x} i=0∑∞?i!xi?=ex

考慮對 e x e^x ex在 x 0 = 0 x_0=0 x0?=0處進行泰勒展開,得到

f ( x ) = f ( x 0 ) + f 1 ( x 0 ) ( x ? x 0 ) 1 ! + f 2 x 0 ( x ? x 0 ) 2 2 ! . . . . . . f(x)=f(x_0)+\frac{f^1(x_0)(x-x_0)}{1!}+\frac{f^2{x_0}(x-x_0)^2}{2!}...... f(x)=f(x0?)+1!f1(x0?)(x?x0?)?+2!f2x0?(x?x0?)2?......

那么 e x e^x ex在 x 0 = 0 x_0=0 x0?=0處的展開式就是

e x = 1 + x 1 ! + x 2 2 ! + x 3 3 ! + x 4 4 ! . . . . . . . . . . . . . e^x=1+\frac{x}{1!}+\frac{x^2}{2!}+\frac{x^3}{3!}+\frac{x^4}{4!}............. ex=1+1!x?+2!x2?+3!x3?+4!x4?.............

運用指數生成函式解決一些問題

POJ3734

一段長度為 n n n的序列，你有紅黃藍綠四種顏色的磚塊，一塊磚長度為 1 1 1,問你鋪磚的方案數,其中紅黃顏色之和必須為偶數，

可以看出這是一個排列問題,也就是從紅黃藍綠選若干塊組成 n n n

對于藍綠來說怎么選都可以,也就是

1 + x 1 ! + x 2 2 ! + x 3 3 ! . . . . . . . . . . = e x 1+\frac{x}{1!}+\frac{x^2}{2!}+\frac{x^3}{3!}..........=e^x 1+1!x?+2!x2?+3!x3?..........=ex

對于紅黃來說,只有偶數項,也就是

1 + x 2 2 ! + x 4 4 ! + x 6 6 ! . . . . . . = e x + e ? x 2 1+\frac{x^2}{2!}+\frac{x^4}{4!}+\frac{x^6}{6!}......=\frac{e^x+e^{-x}}{2} 1+2!x2?+4!x4?+6!x6?......=2ex+e?x?

那么總的方案數就是累乘變成

e 2 x ? e 2 x + e ? 2 x + 2 4 = 1 4 ? ( e 4 x + 2 e 2 x + 1 ) e^{2x}*\frac{e^{2x}+e^{-2x}+2}{4}=\frac{1}{4}*(e^{4x}+2e^{2x}+1) e2x?4e2x+e?2x+2?=41??(e4x+2e2x+1)

其中 e 4 x e^{4x} e4x的第 n n n項系數是 4 n n ! \frac{4^n}{n!} n!4n?

其中 2 e 2 x 2e^{2x} 2e2x的第 n n n項系數是 2 n + 1 n ! \frac{2^{n+1}}{n!} n!2n+1?

所以最后的答案乘以 n ! n! n!全排列就是 4 n ? 1 + 2 n ? 1 4^{n-1}+2^{n-1} 4n?1+2n?1,常數項 1 4 \frac{1}{4} 41?可以忽略