淺談生成函數之OGF

表示序列的一種有效方法就是生成函數，它把序列的項作為一個形式冪級數中變數的冪的係數。可以用生成函數求解許多類型的計數問題，例如在各種限制下選取或分配不同種類的物體的方式數，使用不同的面額的營比換一美元的方式數等。也可以用生成函數求解遞推關係。它先把關於序列的項的遞推關係轉換成涉及生成函數的方程，然後求解這個方程並找出關於這個生成函數的直接表達形式。從這個直接表達形式可以找到生成函數的冪級數的係數，從而求解原來的遞推關係。生成函數甚至可以利用函數之間的關係來證明組合恆等式，因為這些關係可以轉換成涉及序列的項的恆等式。

普通生成函數(OGF)

定義(OGF). 實數序列的普通生成函數是無窮級數 $G(x)=a_0+a_1x+dots+a_kx^k+dots=sum_{k=0}^infty a_kx^k$

來看一些基本的例子：

例1. 序列 ${a_k}(a_k=3,a_k=k+1,a_k=2^k)$ 的生成函數分別是 $sum_{k=0}^infty 3x^k, sum_{k=0}^infty(k+1)x^k,sum_{k=0}^infty2^kx^k$

特別地，我們可以通過設置 $a_{n+1}=0,a_{n+2}=0$ 這些項的係數，把一個有限序列, 擴充成一個無限序列，就可以定義一個實數的有限序列的生成函數。這個無限序列 ${a_n}$ 的生成函數是一個次多項式，因為當的時候沒有形如的項出現，即 $G(x)=sum_{i=0}^n a_ix^i$

例2. 序列的生成函數為。

右邊的式子看起來像等差數列求和？答案是 $frac{x^6-1}{x-1}$ ，那的時候豈不是沒有定義了？

注意我們一直把生成函數稱為形式冪級數，就是說它是一個形式，其實是不考慮它的解析意義的。在之後的討論中，對於一個冪級數我們也不再關心它的收斂性，並且對於一個封閉形式我們也只考慮它的麥克勞林級數。（也就是在處的泰勒展開）

例3. 函數 $f(x)=frac{1}{1-x}$ 是序列的生成函數。

進行麥克勞林展開有 $dfrac{1}{1-x}=1+x+x^2+cdots$

例4. $f(x)=frac{1}{1-ax}$ 是序列的生成函數。

進行麥克勞林展開有 $dfrac{1}{1-ax}=1+ax+a^2x^2+dots$

Mathematica驗證

知道了基本的例子之後，再來考慮以下定理：

定理. 令 $f(x)=sum_{k=0}^infty a_kx^k$ ， $g(x)=sum_{k=0}^infty b_kx^k$ ，那麼有 $f(x)+g(x)=sum_{k=0}^infty (a_k+b_k)x^k$ 和 $f(x)g(x)=sum_{k=0}^infty left ( sum_{j=0}^ka_jb_{k-j} ight)$

有啥用呢？請看這個例子。

例6. 設 $f(x)=frac{1}{(1-x)^2}$ ，求出它的冪級數。

當然可以對其直接麥克勞林展開，利用公式 $f ( x ) = frac { f left( x _ { 0 } ight) } { 0 ! } + frac { f ^ { prime } left( x _ { 0 } ight) } { 1 ! } left( x - x _ { 0 } ight) + frac { f ^ { prime prime } left( x _ { 0 } ight) } { 2 ! } left( x - x _ { 0 } ight) ^ { 2 } + ldots$

得到

現在想一下用剛才的定理怎麼做。把它看成是兩個 $g(x)=sum_{i=0}^infty x^i=frac{1}{1-x}$ 相乘，那麼有 $f(x)=g^2(x)=sum_{k=0} ^ infty left ( sum_{j=0}^k 1 ight)x^k=sum_{k=0}^infty(k+1)x^k$

定理(廣義二項式定理). 設，那麼 $(1+x)^u = sum_{k=0}^ infty inom{u}{k}x^k$

可以使用麥克勞林級數的理論證明定理2。有興趣的讀者可以查看相關資料。

例7. 設，，使用廣義二項式定理求 $(1+x)^{-n}$ 和 $(1-x)^{-n}$ 的生成函數。

由於有 $(1+x)^{-n}=sum_{k=0}^infty (-1)^k inom{n+k-1}{k}x^k$ ，於是用代替得到 $(1-x)^{-n}=sum_{k=0}^infty inom{n+k-1}{k}x^k$ 。

其中比較重要的一個生成函數是當時， $frac{1}{1-x^k}=sum_{i=0}^infty x^{ik}$ 。

下面一起來看一下如何用生成函數解決計數問題。

例8. 設，並設數列，其中代表方程的非負整數解的數目。

用簡單的的隔板法可得 $h_n=inom{n+k-1}{k-1}$ 。它的生成函數是 $g(x)=sum_{n=0}^infty inom{n+k-1}{k-1}x^n$ 。這個的封閉形式我們也早已瞭解，就是 $dfrac{1}{(1-x)^k}$ 。回憶一下，這個封閉形式其實可以用乘法表示為個 $frac{1}{1-x}$ 相乘的形式。寫成冪級數相乘就是 $dfrac{1}{(1-x)^k}=left ( sum_{e_1=0}^infty x^{e_1} ight)left ( sum_{e_2=0}^infty x^{e_2} ight)left ( sum_{e_3=0}^infty x^{e_3} ight)dots left ( sum_{e_k=0}^infty x^{e_k} ight)$ 。在上面的記法中， $x^{e_1}$ 是第一個因子的代表項， $x^{e_2}$ 是第二個因子的代表項，， $x^{e_k}$ 是第個因子的代表項。將這些代表項乘起來，得到 $x^{e_1}x^{e_2}x^{e_3}dots x^{e_k}=x^n$ ，當且僅當 .

於是上面的冪級數的展開式乘起來後的係數等於原方程的非負整數解的個數。

由此，生成函數的係數和方案數的關係也就更加明顯了。再來繼續看一個例子

例9. 確定蘋果、香蕉、橘子和梨的組合的個數，其中在每個組閤中蘋果的個數是偶數，香蕉的個數是奇數，橘子的個數在和之間，而且至少要有一個梨。

首先方案數等價於求出方程的非負整數解的個數，其中 , , , 。為每種類型的水果創建一個因子，其指數為該類型水果的組閤中所允許的數量：

注意到

$egin{aligned} 1+x^2+x^4+dots &= dfrac{1}{1-x^2} \ x+x^3+x^5+dots &= dfrac{x}{1-x^2} \ 1+x+x^2+x^3+x^4 &= dfrac{1-x^5}{1-x}\ x+x^2+x^3+dots &=dfrac{x}{1-x} end{aligned}$

因此 $g(x)=dfrac{1}{1-x^2}dfrac{x}{1-x^2}dfrac{1-x^5}{1-x}dfrac{x}{1-x}=dfrac{x^2(1-x^5)}{(1-x^2)^2(1-x)^5}$ ，這個函數的麥克勞林級數中第項的係數便為所求的答案。

Ex：有無限多的一分，五分，一角，兩角五分和五角的硬幣。試確定用這些硬幣湊成分錢的方法法數。

提示：作換元。

答案：生成函數為 $g(x)=dfrac{1}{1-x}dfrac{1}{1-x^5}dfrac{1}{1-x^{10}}dfrac{1}{1-x^{25}}dfrac{1}{1-x^{50}}$

這裡推薦一個視頻，講的非常清楚，如果不懂什麼意思的話強烈建議食用。

https://www.youtube.com/watch?v=bfFQLSIuQQk?

www.youtube.com

生成函數教程（侵刪） https://www.zhihu.com/video/1059077252406382592

到這裡不知到大家是否有一個疑問：生成函數用來求解數列相關的問題，那麼和數列的遞推式又有怎樣的聯繫？

例10. 求解遞推關係 $a_k=3a_{k-1},k=1,2,3,dots$ ，初始條件為

聰明的孩子（劃掉）正常人都能一眼看出來它的通項公式為。這裡從生成函數的角度加以分析：

設是序列 ${a_n}$ 的生成函數，即 $G(x)=sum_{k=0}^infty a_kx^k$ 。首先注意 $xG(x)=sum_{k=0}^infty a_k x^{k+1}=sum_{k=1}^infty a_{k-1}x^k$ ，利用遞推關係可以得到 $egin{aligned} G(x)-3xG(x)&=sum_{k=0}^infty a_kx^k-3sum_{k=1}^infty a_{k-1}x^k\ &=a_0+sum_{k=1}^infty (a_k-3a_{k-1})x^k\ &=2 end{aligned}$

所以有。求解，解得 $G(x)=dfrac{2}{1-3x}$ 。使用恆等式 $dfrac{1}{1-ax}=sum_{k=0}^infty a^kx^k$ ，有 $G(x)=2sum_{k=0}^infty 3^kx^k = sum_{k=0}^infty 2 imes 3^k x^k$ 。

於是。

是不是覺得非常妙？練習一下。

Ex：求解遞推式 $a_n=8a_{n-1}+10^{n-1}$ ，初始條件為。使用生成函數找出的顯示公式。

設 (擴充序列，方便推導)

用乘遞推關係的兩邊得 $a_nx^n=8a_{n-1}x^n+10^{n-1}x^n$ 。設 $G(x)=sum_{x=0}^infty a_nx^n$ 是序列的生成函數。從開始兩邊求和，得到 $egin{aligned} G(x)-1&=sum_{n=1}^infty a_n x^n=sum_{n=1}^infty (8a_{n-1}x^n+10^{n-1}x^n)\ &=8sum_{n=1}^infty a_{n-1}x^n+sum_{n=1}^infty10^{n-1}x^n\ &=8xsum_{n=1}^infty a_{n-1}x^{n-1}+xsum_{n=1}^infty10^{n-1}x^{n-1}\ &=8xsum_{n=0}^infty a_{n}x^{n}+xsum_{n=0}^infty10^{n}x^{n}\ &=8xG(x)+dfrac{x}{1-10x} end{aligned}$

解得 $G(x)=dfrac{1-9x}{(1-8x)(1-10x)}$ 。

下面怎麼做？似乎有些走投無路了？

這裡要用到一個技巧，就是展開為部分分式： $G(x)=frac{1}{2}left ( frac{1}{1-8x}+frac{1}{1-10x} ight)$

於是就可以輕鬆地得到： $G(x)=sum_{n=0}^infty frac{1}{2}left ( 8^n+10^n ight)x^n$ ，所以 $a_n=dfrac 12 (8^n+10^n)$

這麼愉快？下面來看幾道OI題吧！

BZOJ3028食物

BZOJ3028?

www.lydsy.com

明明這次又要出去旅遊了，和上次不同的是，他這次要去宇宙探險！
我們暫且不討論他有多麼NC，他又幻想了他應該帶一些什麼東西。理所當然的，你當然要幫他計算攜帶件物品的方案數。他這次又準備帶一些受歡迎的食物，如：蜜桃多啦，雞塊啦，承德漢堡等等當然，他又有一些稀奇古怪的限制：

每種食物的限制如下：
承德漢堡：偶數個可樂：個或個雞腿：個，個或個蜜桃多：奇數個雞塊：的倍數個包子：個,個,個或個土豆片炒肉：不超過一個。麵包：的倍數個注意，這裡我們懶得考慮明明對於帶的食物該怎麼搭配著喫，也認為每種食物都是以『個』為單位（反正是幻想嘛），只要總數加起來是就算一種方案。因此，對於給出的 ,你需要計算出方案數，並對取模。

直接寫式子了

$egin{aligned} G(x)&=(1+x^2+x^4+...)(1+x)(1+x+x^2)(x+x^3+x^5+...)\ &quad (1+x^4+x^8+...)(1+x+x^2+x^3)(1+x)(1+x^3+x^6+...)\ &={1-x^2over 1-x}·{1-x^2over 1-x}·{1-x^3over 1-x}·{1-x^4over 1-x}·{1over 1-x^2}·{xover 1-x^2}·{1over 1-x^4}·{1over 1-x^3}\ &={xover (1-x)^4}\ &=xsumlimits_{k=0}^{infty }inom{4+k-1}{k}x^k\ &=xsumlimits_{k=0}^{infty }inom{k+3}{k}x^k\ &=xsumlimits_{k=0}^{infty }inom{k+3}{3}x^k end{aligned}$