[PDF]数列的周期性研究
www.yau-awards.org/paper/.../E13.数列的周期性研究.pdf
轉為繁體網頁
“数林外传系列”之《周期数列》曹鸿德 - 科学网—博客
blog.sciencenet.cn/blog-502977-704946.html
轉為繁體網頁
一般生成函數之應用
張福春 · 曾介玫
摘要: 生成函數是利用冪級數中變數的係數來表達數列, 在組合數學上有廣泛的應 用。 本文中將介紹一般生成函數重要的性質並透過大量的例子說明他們在組合數學
上的應用。
關鍵詞: 一般生成函數、 二項式定理、 二項係數、 遞迴、 遞迴關係、 冪級數、 恆等式、 等比級數、 數學歸納法、 計數問題、 整數分割、 費伯那西、 分項分式、 摺積。
一. 前言
在數學的領域中常常遇到艱難的數列問題, 若能利用生成函數則會使得問題變為輕而易 舉。 生成函數是一種常被運用在離散數學上的進階計算技巧。 在數學中有很廣泛的應用, 常見 的有計數問題、 整數的分割、 解遞迴關係、 求數列和與 恆等式的證明。 西元十三世紀初, 義大利數學家費伯那西 (Fibonacci, 1175∼1250) 研究費伯那西 (Fibonacci) 數列 0,1,1,2,3,5,8,13,21,..., 得到遞迴關係為
Fn+2 = Fn+1 + Fn, n ≥ 0 F0 = 0, F1 = 1 直到西元1843年, 法國數學家棣美弗 (Jacques-Philippe-Marie Binet, 1786∼1856) 利用一 般生成函數才得到Fn一般解的式子,
Fn =
1 √5" 1 +√5 2 !n − 1−√5 2 !n#, n ≥ 0 在西元1748時, 尤拉 (Euler, 1707∼1783) 利用一般生成函數的技巧, 深入研究整數的 分割。 利用
P(x) =
1 1−x
1 1−x2
1 1−x3 ···=
∞ Y i=1
1 1−xi
,
12
一般生成函數之應用 13
我們得到p(0),p(1),p(2),... 的生成函數, 其中 p(n) 代表正整數 n 的不同分割數, p(0)定義 為1。 Wilf (1994) 介紹了生成函數的基本定義、 應用和離散數學上相關的例子。 Stanley (1999) 兩冊的書總共用了八百多頁詳細的介紹生成函數的性質及在計數組合學上 各方面的應用。 Grimaldi (2004) 討論到生成函數的運算技巧和提到生成函數的相關歷史。 黃子嘉 (2001) 收 錄許多台灣地區關於生成函數的研究所入學考題。 讀者若對生成函數有深入瞭解, 可參考上述 書目。 本文取材參考了上述文獻。 關於著名整數數列的生成函數及其相關性質, 請參閱網路整數數列百科全書 “The OnLine Encyclopedia of Integer Sequences” (Sloane, 2007)。 在2007年5月27號共蒐集 了130017 個數列, 每個數列包含: 1. 數列的名稱; 2. 數列前幾十項; 3. 數列的別名; 4. 參考 文獻; 5. 相關連結; 6. 生成函數; 7. Mathematica, Maple及一般程式的程式碼; 8. 相關數 列; 9. 關鍵字; 10. 作者。 生成函數可分為一般生成函數與指數生成函數, 指數生成函數主要是用於計算與排列有關 的計數問題, 限於篇幅大小, 這裡只討論一般生成函數。 本文的主要目的是要介紹單變數的一般生成函數的基本性質, 並透過大量的例子說明他們 在計數、 整數分割、 遞迴關係式、 數列和與恆等式上廣泛的應用。 一般生成函數更深入的應用, 如解數列的漸近公式與證明數列的單一性、 凸性和同餘性等, 有興趣的讀者若想更進一步了解 可參閱 Wilf (1994)。
二. 基本性質
生成函數 (generating function) 是藉由冪級數中的係數來呈現數列, 是研究數列性質非 常有用的工具。 他能用於解很多不同類型的計數 (組合) 問題, 像是選擇或分配不同種類物件的 方法數, 這些計數問題受制於各種限制。 應用於解遞迴關係中, 藉由轉換遞迴關係項成數列的項 到生成函數的方程式中。 這方程式能由找到生成函數的解得到答案, 從這個解, 能找到生成函數 的冪級數係數, 解出原來的遞迴關係式。 他也能應用於計算數列和與證明恆等式, 藉由相關地簡 單關係函數的優點, 此函數能轉換到包含數列的等式。 在生成函數的冪次的運算中使用到下面兩個重要的觀念:
(a) 藉由xn乘以 xm後能得到xm+n, 這呈現了個數相加與多項式相乘之間的關係。 (b) 多項式或冪級數中的係數提供了生成函數中所要包含的資訊。 這說明利用生程函數來解問 題的動機。
可由下面幾節的例子看見上述兩個理由是生成函數可以解多種應用問題的主要原因。
14 數學傳播 32卷3期 民97年9月
首先介紹一般生成函數的定義如下: 定義 2.1: 設 {ak}∞ 0 = {a0,a1,a2,...} 是一數列, 則函數 f(x) = a0 + a1x + a2x2 +···= ∞ X k=0
akxk (2.1)
稱為 {ak}∞ 0 的一般生成函數 (ordinary generating function)。 換言之, 一般生成函數是以 {ak}∞ 0 為係數之 x 的冪級數。 如果只有有限個 ak 6= 0, 則 {ak}∞ 0 的生成函數是一個多項式。 我們能定義有限項實數數 列的生成函數藉由令 an+1 = 0,an+2 = 0,... 來擴充有限的數列 a0,a1,...,an 成為無窮的 數列。 下面計算幾個常見數列的生成函數。 例 2.1: (常數數列的生成函數) 常數數列 {1}∞ 0 的生成函數是 f(x) = 1 + x + x2 + x3 +···= ∞ X k=0 xk 此為公比是 x 的等比級數, 若 |x| < 1, 則此等比級數會收斂, 其和為 1 (1−x) 。 例 2.2: (等比數列的生成函數) 等比數列 {rk}∞ k=0 的生成函數是 f(x) = 1 + rx + r2x2 + r3x3 +···= ∞ X k=0 rkxk 此為公比是 rx 的等比級數, 若 |rx| < 1, 則此等比級數會收斂, 其和為 1 (1−rx) 。 等比級數的生成函數在生成函數的應用中具有無比重要的地位, 例如利用它的生成函數可 以很容易的得到下列生成函數的冪級數 x2 3 + 2x = x2 3 1 1−−2 3x != 1 3 x2 − 2 3 x3 + 2 3 2 x4 +···! 例 2.3: (二項係數的生成函數) 令 n 為任意正整數, 二項係數n 0 ,n 1 ,n 2 ,...,n n 的生成 函數是 f(x) = n 0 + n 1 x + n 2 x2 +···+ n n xn = n X k=0 n k xk 根據二項式定理可知 f(x) = (1 + x)n。
後面章節可以看見二項係數的生成函數可用於求許多與二項係數相關的級數和。 接著討論 一些非常有用生成函數的基本性質。 定理 2.2: (一般生成函數的性質) 設 f(x) =P∞ n=0 anxn 和 g(x) =P∞ n=0 bnxn 分別 是數列 {an}∞ 0 和數列 {bn}∞ 0 的生成函數, 則
一般生成函數之應用 15
(a) (加法) rf(x) + sg(x) 為 {ran + sbn}∞ 0 的生成函數。 (b) (向後平移) 對於正整數 h, xhf(x) 為 0,0,...,0 | {z } h個 ,a0,a1,... 的生成函數。 (c) (向前平移) 對於正整數 h, f(x)−a0−···−ah−1xh−1 xh 為 ah,ah+1,... 的生成函數。 (d) (乘法、 摺積) f(x)g(x) 為 {Pn r=0 arbn−r}∞ 0 的生成函數。 (e) (轉換) f(cx) 為 {cnan}∞ 0 的生成函數。 (f) (微分) f′(x) 為 {(n + 1)an+1}∞ 0 的生成函數。 (g) (積分)Rx 0 f(t)dt 為 {an−1 n }∞ 1 的生成函數。 (h) (部分和) f(x) (1−x) 為 {Pn j=0 aj}∞ 0 的生成函數, 一般稱 1 1−x 為數列 {an}∞ 0 的求和算子。 證明: (a) 直接計算得 rf(x) + sg(x) = rP∞ n=0 anxn + sP∞ n=0 bnxn =P∞ n=0(ran + sbn)xn, 所以 rf + sg 為 {ran + sbn}∞ 0 的生成函數。 (b) xhf(x) = xhP∞ n=0 anxn =P∞ n=h an−hxn, xhf(x) 為 0,0,...,0,a0,a1,... 的生成 函數。 (c)Pn≥0 an+1xn = 1 xPm≥1 amxm = f(x)−f(0) x = f(x)−a0 x , 所以 f(x)−a0 x 為 {an+1}∞ 0 的 生成函數。Pn≥0 an+2xn = 1 xPn+1≥1 an+1xn = [(f(x)−a0)/x]−a1 x = f(x)−a0−a1x x2 , 因此 f(x)−a0−a1x x2 為 {an+2}∞ 0 的生成函數。 同理,f(x)−a0−a1x−···−ah−1xh−1 xh 為 {an+h}∞ 0 的生 成函數。
(d) 由冪級數的乘法規則得 f(x)g(x) = (a0 + a1x + a2x2 +···)(b0 + b1x + b2x2 +···) = a0b0 + (a0b1 + a1b0)x + (a0b2 + a1b1 + a2b0)x2 +···
=
∞ X n=0
(a0bn + a1bn−1 +···+ an−1b1 + anb0)xn
所以 f(x)g(x) 為 {Pn r=0 arbn−r}∞ 0 的生成函數。 (e) f(x) =P∞ n=0 anxn, 則 f(cx) =P∞ n=0 an(cx)n。 因此, f(cx) 為 a0,ca1,c2a2 ... = {cnan}∞ 0 的生成函數。
16 數學傳播 32卷3期 民97年9月 (f) f(x) =P∞ n=0 anxn, 兩邊對 x 微分得 f′(x) =P∞ n=1 nanxn−1, 則 f′(x) 是 a1,2a2, 3a3,... = {(n + 1)an+1}∞ 0 的生成函數。 (g) 直接計算得Rx 0 f(t)dt =Rx 0 P∞ n=0 antndt =P∞ n=0 anRx 0 tndt =P∞ n=1 an−1 n xn = {an−1 n }∞ 1 。 (h) 直接計算得
f(x) 1−x
= (a0 + a1x + a2x2 +···)(1 + x + x2 +···) = a0 + (a0 + a1)x + (a0 + a1 + a2)x2 +···
=
∞ X n=0 n X j=0
aj!xn
所以 f(x) 1−x
為 {Pn j=0 aj}n≥0 的一般生成函數。 定理 2.2 是後面幾節生成函數應用的主要工具。 表 1 為常見數列的一般生成函數。 若能熟悉表 1 對於我們解生成函數的問題有莫大的幫
助。
表 1. 常見數列的一般生成函數
數列 一般生成函數 1,1,1,1,1,... 1 1−x 1,1,...,1,0,0,...(n個1) 1−xn 1−x n 0 ,n 1 ,...,n n ,0,0,... (1 + x)n1 ,−1,1,−1,1,−1,... 1 1+x 1,0,1,0,1,... 1 1−x2 1,2,3,4,5,... 1 (1−x)2 1,4,9,16,25,... 1+x (1−x)3 1,r,r2,r3,r4,... 1 1−rx 0,r,2r2,3r3,4r4,... rx (1−rx)2
接著介紹如何利用基本性質求得常見數列的一般生成函數。
一般生成函數之應用 17
例 2.4: 求下列數列的生成函數:
(a) 1,2,3,4,...
(b) 0,1,2,3,4,...
(c) 12,22,32,42,...
(d) 02,12,22,32,42,...
解:
(a) 考慮等比級數
1 = (1−x)(1 + x + x2 + x3 + x4 +···)
所以
1 1−x
= 1 + x + x2 + x3 + x4 +···=
∞ X k=0
xk, |x| < 1
兩邊對 x 微分
d dx
1 1−x
=
d dx
(1 + x + x2 + x3 + x4 +···+ xn +···)
因此得
1 (1−x)2
= 1 + 2x + 3x2 + 4x3 +···+ nxn−1 +···
=
∞ X i=1
ixi−1 =
∞ X j=0
(j + 1)xj, |x| < 1
所以 1 (1−x)2
為數列 1,2,3,4,... 的生成函數。
(b) 兩邊同乘 x 得
x (1−x)2
= 0 + x + 2x2 + 3x3 + 4x4 +···+ nxn +···=
∞ X k=1
kxk =
∞ X k=0
kxk
所以 x (1−x)2
為數列 0,1,2,3,4,... 的生成函數。
(c) 兩邊再對 x 微分
d dx
x (1−x)2
=
d dx
(0 + x + 2x2 + 3x3 +···)
18 數學傳播 32卷3期 民97年9月
所以
x + 1 (1−x)3
= 12 + 22x + 32x2 + 42x3 +···=
∞ X i=1
i2xi−1
所以 (1+x)x (1−x)3
為數列 12,22,32,42,... 的生成函數。
(d) 兩邊再同乘 x
(1 + x)x (1−x)3
=
∞ X i=1
i2xi =
∞ X i=0
i2xi
所以 (1+x)x (1−x)3
為數列 02,12,22,32,42,... 的生成函數。
令 R = {x|−∞ < x < ∞} 表示實數的集合, 而 N0 = {0,1,2,...} 表示非負整數的 集合。 例 2.5: (廣義二項係數) 設 a ∈ R,k ∈ N0,a k = a(a−1)(a−2)···(a−k+1) k! ,a 0 = 1, 求 a 0 ,a 1 ,a 2 ,... 的生成函數。解 : 考慮 (1 + x)a 的馬克勞林展開 (1 + x)a = 1 + ax + a(a−1)x2/2! + a(a−1)(a−2)x3/3! +···
= 1 +
∞ X k=1
a(a−1)(a−2)···(a−k + 1) k!
xk, |x| < 1
所以 (1+x)a =a 0 +a 1 x+a 2 x2+···=P∞ k=0a k xk。 因此, (1+x)a 為a 0 ,a 1 ,a 2 ,...的生成 函數。 (1 + x)a =P∞ k=0a k xk稱為廣義二項式定理, 此為二項式定理的推廣, 後面章節中將利用 二項係數的生成函數求冪級數的係數, 對於求數列和、 計數、 整數的分割及解遞迴關係等應 用有很大的幫助。 註: 設 N = {1,2,...} 表示自然數的集合, 當 a = −m,m ∈ N 時 −m k = (−m)(−m−1)(−m−2)···(−m−k + 1) k! = (−1)k(m)(m + 1)(m + 2)···(m + k−1) k!
=
(−1)k(m + k−1)! (m−1)!k! = (−1)k m + k−1 k
一般生成函數之應用 19
接著我們來看兩個廣義二項式定理的應用。 例 2.6: 求 f(x) = (1−3x)−8 的馬克勞林展開中 x4 的係數。 解: 令 y = −3x, 利用 (1 + y)a =P∞ n=0a n yn, 所以 (1−3x)−8 = (1 + y)−8 = ∞ X n=0 −8 n yn = ∞ X n=0 −8 n (−3x)n 因此在 f(x) 中 x4 的係數為−8 4 (−3)4 = (−1)48+4−1 4 (81) =11 4 (81) = 26,730。 例 2.7: 求 f(x) = √1 + x 生成何種數列?
解:
√1 + x = (1 + x)1/2 = 1/2 0 1 + 1/2 1 x + 1/2 2 x2 +··· = 1 + 1 2 x + 1 2 · −1 2 2! x2 + 1 2 · −1 2 · −3 2 3! x3 +
1 2 · −1 2 · −3 2 · −5 2 4!
x4 +···
= 1 +
1 2
x−
1 8
x2 +
1 16
x3 −
5 128
x4 +···
所以 √1 + x 是數列 {1/2 n }∞ n=0 = {1, 1 2,−1 8, 1 16,− 5 128,...} 的一般生成函數。 接著是摺積性質的應用。 例 2.8: 試求數列 {n k + 2 n k−1 }∞ 1 的生成函數。 解: 設 ak =n k , 數列 {ak}∞ 0 的生成函數為 f(x) = n X k=0 akxk = n X k=0 n k xk = (1 + x)n 考慮 bk =n k + 2 n k−1 = ak + 2ak−1, 且設 g(x) 為 {bk}∞ 0 的生成函數, 則 g(x) = n X k=1 bkxk = n X k=1 (ak + 2ak−1)xk = (1 + 2x)(a0 + a1x +···+ anxn)−a0 = (a0 + b1x +···+ bnxn)−a0 = (1 + 2x)(1 + x)n −1
三. 計數
對於利用一般生成函數去解計數問題時, 可使用形式冪級數, 將忽略級數是否收斂。
20 數學傳播 32卷3期 民97年9月
定義: 3.1: 形式冪級數為
∞ X k=0
akxk = a0 + a1x + a2x2 +···+ anxn +···
其中常數 a0,a1,a2,... 叫做冪級數的係數。
我們先說明如何利用生成函數來解相異物組合的問題: 設有三種相異物 a,b,c 其中這三 個相異物是可以重複選取, a 最多可選三次, b 最多選二次, c 最多選一次。 因為 a 最多可選 取三次, 表示可選取 0,1,2 或 3 次, 所以可以用 (1 + ax + a2x2 + a3x3) 來表示, 同理 (1 + bx + b2x2) 表示 b 可選取 0,1 或 2 次, (1 + cx) 表示 c 可選取 0 次或 1 次。 當全部放 在一起得
(1 + ax + a2x2 + a3x3)(1 + bx + b2x2)(1 + cx) = 1 + (a + b + c)x + (a2 + b2 + ab + ac + bc)x2 + (a3 + a2b + ab2 + a2c + b2c + abc)x3 + (a3b + a2b2 + a3c + a2bc + ab2c)x4 + (a3bc + a3b2 + a2b2c)x5 + (a3b2c)x6
常數項1表示 a,b,c 都不選, x 的係數 a+b+c 表示選1個物品時可選 a,b 或 c。 x2 的係 數 ab+ac+bc+a2+a2c+b2 表示選兩個物品: ab 表 a,b 各選一次, ac 表 a,c 各選一次, bc 表 b,c 各選一次, a2 表 a 選二次, b2 表 b 選二次。 x3 的係數 a3 +a2b+ab2 +a2c+b2c+abc 表示選三個的物品, a3 表 a 選三次, a2b 表 a 選二次且 b 選一次, ab2 表 b 選二次且 a 選 一次, a2c 表 a 選二次且 c 選一次, b2c 表 b 選二次且 c 選一次, abc 表 a,b,c 各選一次。 同理 x4 的係數 a3b + a2b2 + a3c + a2bc + ab2c 表示選四個物品所有組合方式。 x5 的係數 a3bc + a3b2 + a2b2c 表示選五個物品所有組合方式。 x6 的係數 a3b2c 表示選六個物品所有組 合方式。 當只關心事件發生可能之個數, 而不在乎選取那些物品時, 我們令 a = b = c = 1 代入得 (1 + x + x2 + x3)(1 + x + x2)(1 + x) = 1 + 3x + 5x2 + 6x3 + 5x4 + 3x5 + x6。 多項式 中 x 的次方表示物品的個數, 而係數則為其相對應的方法數。 表示三個物品都不選時方法數有 1種, 選一個物品時方法數有3種, 選二個物品時方法數有5種, 選三個物品時方法數有6種, 選 四個物品時方法數有5種, 選五個物品時方法數有3種, 選六個物品時方法數有1種。 此為計數 問題的生成函數, 該問題的答案已具見於函數當中。
例 3.1: 將20顆相同的球分配到五個相異的箱子中, (a) 每個箱子至少有兩顆球, (b) 每個箱子至少有兩顆球但不超過7個,
一般生成函數之應用 21
求有幾種分配數。
解: (a) 每個箱子分配的可能性可利用生成函數 (x2 + x3 + x4 +···) 來表示, 因為有五個箱子, 所以可看成 f(x) =x2 + x3 + x4 +··· 5 = x101 + x + x2 +··· 5 = x10 (1−x)5 有20顆球要分配到五個箱子, 所以在 f(x) 中 x20 的係數可看成在 (1−x)−5 中 x10 的係 數, 設 [xn]f(x) 表示 f(x) 的冪級數中 xn 的係數。 x20 f(x) = x10 (1−x)−5 = x10 1− −5 1 x + −5 2 x2 − −5 2 x3 +··· = −5 10 因為−5 10 = (−1)105+10−1 10 =14 10 = 1,001, 所以總共有1,001種分配數。(b) 每個箱子分配的可能性可利用生成函數 (x2 + x3 + x4 +···+ x7) 來表示, 因為有五個箱 子, 所以可看成 g(x) =x2 + x3 + x4 +···+ x7 5 = x101 + x + x2 + x3 + x4 + x5 5 = x10 1−x6 1−x 5 有20顆球要分配到五個箱子, 所以在 g(x) 中 x20 的係數可 看成在 (1−x6)5(1−x)−5 中 x10 的係數, x20 g(x) = x10 1−x6 1−x 5 = x10 (1−x6)5(1−x)−5 = −5 10 (−1)10 − 5 1 −5 4 (−1)4 = 14 10 − 5 1 8 4 = 651
所以總共有651種分配數。
22 數學傳播 32卷3期 民97年9月
例 3.2: [重複組合]利用生成函數求 n 個相異物允許重複取 r 件組合的方法數有幾種? 解: 設 P(x) 為數列 {ar} 的生成函數, 其中 ar 代表 n 個物件中允許重複取 r 件組合的 方法數。 因此, P(x) =P∞ r=0 arxr。 因為我們能選擇任何 n 個物件的特別的元素, 當允許重複 取 r 件組合, 其對應的生成函數為 (1 + x + x2 + x3 +···)。 每一個物件對應到這個因子, 因 為每一個的選擇有可能是0次,1次,2次,3次以上。 因為在這個集合中有 n 個物件, 每個都是有 相同因子, 所以 P(x) = (1 + x + x2 +···)n 只要|x|< 1, 可以得到1 + x + x2 +···= 1/(1−x), 所以 P(x) = 1/(1−x)n = (1−x)−n 利用廣義的二項式定理,
(1−x)−n = (1 + (−x))−n =
∞ X r=0 −n r (−x)r n 個物件允許重複取 r 件組合的方法數是在加總中 xr 的係數 ar, 其中 r 為正整數。 我們得 到ar等於 −n r (−1)r = n + r−1 r 例 3.3: 請問函數 1 (1−x−x2−···−x6) 為何種數列的生成函數?
解: 由等比級數可知
1 (1−x−x2 −···−x6)
=
∞ X k=0 (x + x2 + x3 + x4 + x5 + x6)k (3.1) 由於投擲一個公平骰子的生成函數為 (x + x2 + x3 + x4 + x5 + x6), 因此P∞ k=0(x + x2 + x3 + x4 + x5 + x6)k 為不論投擲幾次骰子其點數和的次數的生成函數, 點數和剛好為 n 的次 數即為 xn 的係數。
例 3.4: 對於所有的整數 n, 證明 n 都能由
1,3,32,33,34,... 經由唯一的子序列作加或減運算得到。 例如: 10 = 1 + 32,73 = 34 −32 + 1。 證明: 令 fm(x) =Qm k=0(1+x3k +x−3k), 則 (1+x3k +x−3k) 其中 1 代表 3k 沒有使用, x3k 代表加 3k, x−3k 代表減3k。 因此, fm(x) 展開後 xn 的係數代表是用 1,3,32,33,34,...,
一般生成函數之應用 23
3m 的子序列作加減所組合出來等於 n 的方法數, 特別是 x0 的係數代表都不取時的方法數, 在 此狀況下只有一種。 當 m = 1 時,
f1(x) = (1 + x + x−1)(1 + x3 + x−3) = x−4 + x−3 + x−2 + x−1 + 1 + x + x2 + x3 + x4 包含 x−4 = x−1 ·x−3,x−3 = 1·x−3,...,x3 = 1·x3,x4 = x·x3, 且每一項的係數都為1, 所以從 −4 到4都有唯一的表示方法。 對任意的自然數 m, 則
fm(x) =
m Y k=0 (1 + x3k + x−3k) = (1 + x + x−1)(1 + x3 + x−3)(1 + x32 + x−32)···(1 + x3m + x−3m) = x2 + x + 1 x x6 + x3 + 1 x3 x18 + x9 + 1 x9 ··· x2·3m + x3m + 1 x3m
=
1 xx3x9···x3m x3 −1 x−1 x9 −1 x3 −1 x27 −1 x9 −1 ··· x3m+1 −1 x3m −1 !
=
1
x
3m+1 −1 2 x3m+1 −1 x−1 !
=
x3m+1−1 +···+ x + 1 x 3m+1 −1 2 = x 3 m+1 −1 2 +···+ x1 + 1 + x−1 + x−2 +···+ x− 3 m+1
−1
2
則 fm(x) 的冪次包含了從−3m+1−1 2
到3m+1−1 2
的整數。 因此, 當 m →∞ 時, 就可以得到下面
這個很漂亮的等式
∞ Y k=0 (1 + x3k + x−3k) =
∞ Xk =−∞
xk
因為 k 是任意的整數, 且 xk 的係數皆為1, 因此得證。
對於在計數組合學上各方面的應用可參考 Stanley (1999) 兩冊的書。
四. 整數分割
在整數的分割問題中可分為整數 (有序) 分割問題和整數 (無序) 分割兩種問題, 它們分別 對應著 「分配」 問題和 「組合」 問題。
24 數學傳播 32卷3期 民97年9月
整數的分割是指把正整數 n分割為若干個正整數, 各個正整數相加之和為 n, 問有多少種 不同分割法? 由於各部分無次序之分, 因此在列出某個正整數的各部分時, 把它們按遞增序排 列。 整數的有序分割可以加上限制條件, 例如: 各個部分大小的限制條件、 部分個數的限制條 件。 在處理整數的分割中常常利用排容原理, 但在這裡是利用生成函數法來解決這類型的問題。 對於某些計算處理上有困難, 若利用生成函數會變得較為容易。 先定義p(n) 代表對正整數 n分 割成各項皆不同的方法數, P(x) 為 p(n) 的生成函數。 表 2 為自然數 1,2,3,4,5 的整數分割:
表 2. 整數分割
n 分割的情況 分割方法數 p(n) 1 1 1 p(1) 2 2, 1+1 2 p(2) 3 3, 2+1, 1+1+1 3 p(3) 4 4, 3+1, 2+2, 2+1+1, 1+1+1+1 5 p(4) 5 5, 4+1, 3+2, 3+1+1, 2+2+1, 2+1+1+1, 1+1+1+1+1 7 p(5)
表 2 只要透過簡單的數學即可得到答案, 如果延伸到較大的的整數時就需要一項工具記 錄, 即生成函數中次方係數, 例如: 1 + x + x2 + x3 + x4 +··· xi 項中的 i 代表有 i 個1 1 + x2 + x4 + x6 +··· x2i 項中的 i 代表有 i 個2 1 + x3 + x6 + x9 +··· x3i 項中的 i 代表有 i 個3 . . . . . . 1 + xn + x2n + x3n +··· xni 項中的 i 代表有 i 個 n . . . . . .
把上式表示成生成函數, 可以寫成
P(x) =
1 (1−x)
1 (1−x2)
1 (1−x3)···
1 (1−xn)···=
∞ Y i=1
1 (1−xi)
p(n)相當於 P(x) 中 xn 的係數, 也等於
n Y i=1
1 (1−xi)
一般生成函數之應用 25
中 xn 的係數, 因為Q∞ i=n+1
1 (1−xi)
的冪級數中除了常數1以外, 其餘皆高於 n次。 此外, 在問 題討論中, 如無特別註明, 整數分割都是各部分下限為1, 且定義p(0) = 1。
例 4.1: 試求5的 「分割」 方法總數。
解: 其對應的生成函數為
P(x) =
∞ X n=0
p(n)xn =
∞ Y i=1
1 (1−xi)
(4.1)
p(5)即上式展開式中 x5 項的係數。 根據觀察, 從 (4.1) 前5個括弧中取以下數值時, 相乘會得 到x5 項:
1·1·1·1·x5+1·x2·x3·1·1+x·1·1·x4·1+x·x4·1·1·1+x2·1·x3·1·1+x3·x2·1·1·1+x5·1·1·1·1 由於以上7組數值的相乘結果均為 x5, 所以上式展開式中 x5 項的係數是7, 即 p(5) = 7, 5的 分割方法數有7種。
例 4.2: 證明將正整數分割成每一項不超過兩次以上的生成函數與正整數不被3整除的生 成函數是相同的。 證明: 表因每一項不超過兩次以上的分項, 因此令 f(x) =Q∞ i=1(1+xi +x2i)。 若不被3 整除則其生成函數可令 g(x) = 1 1−x 1 1−x2 1 1−x4 1 1−x5 1 1−x7 ···。 可以發現 f(x) = (1 + x + x2)(1 + x2 + x4)(1 + x3 + x6)(1 + x4 + x8)··· = 1−x3 1−x 1−x6 1−x2 1−x9 1−x3 1−x12 1−x4 1−x15 1−x5 1−x18 1−x6 ··· = 1 1−x 1 1−x2 1 1−x4 1 1−x5 1 1−x7 ···= g(x) 得證。
接下來這個例子為限制條件時的整數有序分割。 例 4.3: (限制條件的整數分割) 求 x1 + x2 + x3 = 100,x1 ≥ 0,x2 ≥ 3,0 ≤ x3 ≤ 9之 整數解個數。 解: x1 可選取的個數為 0,1,2,..., 其對應的生成函數為 (1 + x + x2 + ···); x2 可 選取的個數為 3,4,5,..., 其對應的生成函數為 (x3 + x4 + x5 + ···); x3 可選取的個數為 0,1,2,...,8,9, 其對應的生成函數為 (1+x+x2 +···+x8 +x9)。 因此 x1 +x2 +x3 = 100 生成函數為 A(x) = (1 + x+ x2 +···)(x3 +x4 + x5 +···)(1 + x+ x2 +···+ x9), 欲求
26 數學傳播 32卷3期 民97年9月
之整數解個數即為 A(x) 中 x100 的係數 A(x) = 1 1−x x3 1−x 1−x10 1−x = (x3 −x13) 1 (1−x)3 = (x3 −x13) ∞ X r=0 3 + r−1 r xr = ∞ X r=0 r + 2 r xr+3 − ∞ X r=0 r + 2 r xr+13 x100 的係數為97+2 97 −87+2 87 = 935。 五. 遞迴關係式
解遞迴關係式有多種方法, 其中生成函數是一個非常有效且系統化的方法。 生成函數可用 來個別或是同時地解遞迴關係, 這個技巧和用來解微分方程的 Laplace 轉換法是類似的。 欲解 一個 k 階常係數的遞迴關係 Ckan+k +···+ C0an = g(n),n≥ 0, 可使用以下的步驟 1. 在遞迴關係式兩邊同乘上 xn+k, 並加總其結果; 2. 得到此新的方程式, 利用生成函數 f(x) =P∞ n=0 anxn 的形式重新寫此方程式, 並且解 出 f(x), 而當 g(n) 是 {ni},{λn},{niλn},i = 0,1,2,... 的線性組合時, f(x) 的解 為 一有理多項式;
3. 利用分項分式展開, 將 f(x) 寫成x 的冪級數, 即可得到係數 an。
由下列例子說明如何由一般生成函數解出遞迴關係式的解。 例 5.1: 設遞迴關係式 an+1 −2an = 1,n≥ 0,a0 = 0, 利用生成函數法求 an。 解: 此遞迴關係式為一無窮多項的方程式集合 ,第0 項為 a1 −2a0 = 1, 第1 項為 a2 − 2a1 = 1, 第2 項為 a3 −2a2 = 1, ···。 在第一式乘上 x, 第二式乘上 x2, 以此類推, 我們可以 得到, 第0 項為 a1x−2a0x = x, 第1 項為 a2x2−2a1x2 = x2, 第2 項為 a3x3−2a2x3 = x3, ···。 把上述的式子加起來可得 ∞ X n=1 anxn −2 ∞ X n=1 an−1xn = ∞ X n=1 xn 設 A(x) =P∞ n=1 anxn, 所以遞迴關係式可寫成 (A(x) −a0)−2xA(x) = x 1−x, 將起始條 件a0 = 0 代入 (A(x)−0)−2xA(x) = x 1−x , 經化簡後得 A(x) = x (1−2x)(1−x), 利用分項分 式可得 A(x) = −1 1−x + 1 1−2x = − ∞ X n=0 xn + ∞ X n=0 (2x)n = ∞ X n=0 (−1 + 2n)xn
一般生成函數之應用 27 即 an = −1 + 2n,n≥ 0。 再舉一個例子說明生成函數的用途, 這個例子是費伯那西數列, 在這要強調倒不是數列本 身, 而是如何借助一般生成函數計算數列的指定項的值。 例 5.2: (費伯那西數列) 設 Fn 滿足遞迴關係式 Fn+1 = Fn + Fn−1, n ≥ 1, F0 = 0, F1 = 1, 求 Fn 的解。
解: 令
F(x) =X n≥0
Fnxn
將 Fn+1 = Fn + Fn−1 乘以 xn+1 且對 n ≥ 1 相加, 左式得到 F2x2 + F3x3 + F4x4 +···= F(x)−x 右式得到 F1x2 + F2x3 + F3x4 +··· +F0x2 + F1x3 + F2x4 +··· = xF(x) + x2F(x)所 以 F(x)−x = xF(x) + x2F(x) 我們可以得知此生成函數為 F(x) = x 1−x−x2 利用部份分式展開 x/(1−x−x2), 將會得到費伯那西的公式。 在此我們先分解二次因子, 我 們可以得到 1−x−x2 = (1−xr+)(1−xr−), r± = (1±√5)/2 所以
x 1−x−x2
=
x (1−xr+)(1−xr−)
=
1 (r+ −r−) 1 1−xr+ −
1 1−xr−
=
1 (r+ −r−)(∞ X n=0
rn +xn −
∞ X n=0
rn −xn)
利用等比級數, 我們可以很容易的辨認出 xn 的係數
Fn =
1 √5" 1 +√5 2 !n − 1−√5 2 !n#, n = 0,1,....
28 數學傳播 32卷3期 民97年9月
註: 利用生成函數解常係數的遞迴關係式, 會得到一個有理多項式的生成函數 f(x), 要將 f(x) 寫成冪級數時, 分項分式 (partial fraction)是一個不可或缺的工具。 請參閱微積分課本。
六. 數列和與恆等式
利用一般生成函數計算數列和常見的方法可分為下列三種: 考慮 (a) 二項式定理: {n k }n k=0 的生成函數 (b) 生成函數的微分與積分
(c) 摺積性質f(x)g(x) 的一般生成函數, 特別是求和算子 g(x) = 1 1−x (定理 2.2 (h))
例 6.1: (二項式定理求和) 設 n 為自然數, 計算 (a)n 0 +n 1 +n 2 +n 3 +···+n n (b) 1 2n 1 +1 2 2n 2 +1 2 3n 3 +1 2 4n 4 +···+1 2 nn n (c) n 1 −n 3 +n 5 −n 7 +···(d) n 0 −n 2 +n 4 −n 6 +··· 解:
(a) 考慮二項式定理
n X k=0 n k xk = (1 + x)n (6.1)
將 x = 1 代入得 (6.1)
n X k=0 n k = (1 + 1)n = 2n
(b) 將 x = 1 2
代入(6.1) 得
n X k=0 1 2 n n k = 1 + 1 2 n = 3 2 n (c) 將 x = i 代入 (6.1), 右式為 (1 + i)n = √2 cos π 4 + isin π 4 n = 2n/2 cos nπ 4 + i2n/2 sin nπ 4
一般生成函數之應用 29
利用生二項式展開, 左式為
n X k=0 n k ik = n 0 − n 2 + n 4 − n 6 +··· + i n 1 − n 3 + n 5 − n 7 +···
所以n 1 −n 3 +n 5 −n 7 +···= 2n/2 sinnπ 4 。(d) 由 (c) 小題知n 0 −n 2 +n 4 −n 6 +···= 2n/2 cosnπ 4 。 例 6.2: (自然數平方和) 依下列步驟求前 n 個自然數的平方和:
(a) 求數列 02,12,22,... 的生成函數。
(b) 求數列 02,02 + 12,02 + 12 + 22,... 的生成函數。 (c) 求 02 + 12 + 22 +···+ n2 的公式。
解:
(a) 由例 2.4 (d) 得數列 02,12,22,... 的生成函數為 (1+x)x (1−x)3
。
(b) 因為 (1+x)x (1−x)3
為數列 02,12,22,... 的生成函數, 則
(1 + x)x (1−x)3 ·
1 1−x
= (02 + 12x + 22x2 +···)(1 + x + x2 +···) = 02 + (02 + 12)x + (02 + 12 + 22)x2 +···
=
∞ X n=0
(02 + 12 + 22 +···+ n2)xn
所以 (1+x)x (1−x)3 · 1 1−x
為數列 02,02 + 12,02 + 12 + 22,... 的生成函數。 (c) 02 + 12 + 22 +···+ n2相當於 (1+x)x (1−x)3 · 1 1−x 中 xn 的係數 (1 + x)x (1−x)3 · 1 1−x = x + x2 (1−x)4 = (x + x2) ∞ X r=0 4 + r−1 r xr = ∞ X r=0 4 + r−1 r xr+1 + ∞ X r=0 4 + r−1 r xr+2
30 數學傳播 32卷3期 民97年9月
xn 的係數為 4 + (n−1)−1 n−1 + 4−(n−2)−1 n−2 = n + 2 n−1 + n + 1 n−2 = (n + 2)! 3!(n−1)! +
(n + 1)! 3!(n−2)!
=
1 6
[(n + 2)(n + 1)(n) + (n + 1)(n)(n−1)] =
n(n + 1)(2n + 1) 6
例 6.3: (微分、 積分求和) 試求 (a)n 1 + 2n 2 + 3n 3 +···+ nn n (b) 1 + 1 2n 1 + 1 3n 2 +···+ 1 n+1n n 解:
(a) 考慮
n X i=0 n i xi = (1 + x)n (6.2)
(6.2) 兩邊對 x 微分
n X i=0
i n i xi−1 = n(1 + x)n−1
x = 1 代入得
n X i=0
i n i = n2n−1
(b) (6.2) 兩邊對 x 積分
n X i=0 n i xi+1 i + 1
=
(1 + x)n+1 n + 1
+ C
當 x = 0 時, C = −1 (n+1), 再將 x = 1 代入得
n X i=0 n i 1 i + 1
=
1 n + 12n+1 −1
例 6.4: 試求
12 0!
+
22 1!
+
32 2!
+
42 3!
+···
一般生成函數之應用 31
解: 考慮
ex =
∞ X n=0
xn n!
, x ∈ R
兩邊同乘 x 得
xex =
∞ X n=0
xn+1 n!
兩邊對 x 微分
(1 + x)ex =
∞ X n=0
(n + 1)xn n!
, x ∈ R
兩邊同乘 x 得
(x + x2)ex =
∞ X n=0
(n + 1)xn+1 n!
兩邊對 x 微分
(1 + 3x + x2)ex =
∞ X n=0
(n + 1)2xn n!
, x ∈ R
x = 1 代入得
∞ X n=0
(n + 1)2 n!
= 5e
例 6.5: (積分求和) 試求無窮級數
1−
1 4
+
1 7 −
1 10
+···
解: 已知
1 1 + x3
= 1−x3 + x6 −x9 +··· , |x| < 1
兩邊對 x 積分
Z x 0
dx 1 + x3
= x−
x4 4
+
x7 7 −
x10 10
+··· , |x| < 1 (6.3) 由交錯級數定理知當 x = 1 時 (6.3) 右式收斂, 且將 (6.3) 左式進行分項分式及利用 Abel’s 的極限定理得 Z x 0 dx 1 + x3 = 1 3Z x 0 1 1 + x + 2−x 1−x + x2 dx = 1 3Z x 0 1 1 + x + −1 2(2x−1) 1−x + x2 + 3 2 1−x + x2 dx = 1 3 log 1 + x √1−x + x2 +√3 arctan 2x−1 √3 −arctan −1 √3
32 數學傳播 32卷3期 民97年9月
因此此無窮級數和為
1 3 log2 + π √3 例 6.6: ( 求和算子求和) 利用求和算子計算出Pn i=0 i(i−1) 的公式。 解: Pn i=0 i(i−1) 為數列 {i(i−1)}∞ i=0 的部分和, 令其生成函數為 f(x) = ∞ X i=0 i(i−1)xi, |x| < 1 考慮 1 1−x =P∞ i=0 xi, 兩邊對 x 微分二次得 2 (1−x)3 = ∞ X i=2 i(i−1)xi−2, |x| < 1 兩邊同乘以 x2 得 2x2 (1−x)3 = ∞ X i=2 i(i−1)xi = ∞ X i=0 i(i−1)xi, |x| < 1 因此可得 f(x) = 2x2 (1−x)3 。 利用求和算子知 2x2 (1−x)3 1 1−x = 2x2 (1−x)4 為數列 {Pn i=0 i(i−1)}∞ n=1 的 生成函數, 利用二項式定理 2x2 (1−x)4 = 2x2 ∞ X r=0 4 + r−1 r xr = 2 ∞ X r=0 r + 3 3 xr+2 且Pn i=0 i(i−1) 為 xn 的係數, 所以 n X i=0 i(i−1) = [xn] 2x2 (1−x)4 = 2 n−2 + 3 3 = 2 n + 1 3 = 1 3 n(n + 1)(n−1) 接下來介紹如何利用生成函數來證明恆等式, 這裡的證明使用到廣義的二項式定理, 下面 的例子說明如何用生成函數來證明恆等式。 例 6.7: (Vandermonde’s convolution) 設 n,m ∈ N,r ∈ N0, 利用生成函數證明下列 等式 r X i=0 n i m r−i = n + m r
一般生成函數之應用 33
解: {n 0 ,n 1 ,n 2 ,...,n n ,0,0,...} 對應的生成函數為 f(x)=(1+x)n=Pi≥0n i xi。同 理, {m 0 ,m 1 ,m 2 ,...,m m ,0,0,...} 對應的生成函數為 g(x)=(1+x)m=Pj≥0m j xj。將 f(x) 和 g(x)相乘得到 f(x)g(x) = n 0 m 0 + n 0 m 1 + n 1 m 0 x + n 0 m 2 + n 1 m 1 + n 2 m 0 x2 +··· = (1 + x)n(1 + x)m = (1 + x)n+m
觀察xr 的係數
r X i=0 n i m r−i = [xr]f(x)g(x) = [xr](1 + x)n(1 + x)m = [xr](1 + x)n+m = n + m r
註: 當 m = n,r = n 時, 即可得著名的組合恆等式
n X i=0 n i 2 = 2n n 下列是一些不錯的題目, 也許讀者有興趣試試, 為了方便讀者, 我們也將答案列入。 1. 求下列數列的一般生成函數 (答案: x2 1−x3)
0,0,1,0,0,1,0,0,1,0,0,1,...
2. 求下列數列的一般生成函數 (答案: 2x2 (1−x)3 )
0,0,2,6,12,...,k(k−1),...
3. 求 (x7 + x8 + x9 +···)6 中 x50 的係數。 (答案:13 8 = 1,287)4. 求 1 (x−3)(x−2)2 中 x8 的係數。 (答案: −1 3 9 −71 2 10)5. 計算Pn k=1n−1 k−1 n k 。 (答案:2n−1 n−1 )
34 數學傳播 32卷3期 民97年9月
6. 利用一般生成函數來解遞迴關係式: (答案: 1 2(10n) + 1 2(8n)) an = 8an−1 + 10n−1, n ≥ 2,a1 = 9
7. 利用一般生成函數解二階遞迴式 (答案: (−1)·4n + 4·2n) an = 6an−1 −8an−2, n ≥ 2,a0 = 3,a1 = 4
8. 對於任一自然數 n, 令
Sn =
n X k=0
(−1)k 2k + 1 n k = n 0 − 1 3 n 1 + 1 5 n 2 − 1 7 n 3 +···+ (−1)n 2n + 1 n n 證明: 對於所有自然數 n, Sn = 4n(n!)2 (2n+1)! 。
9. 證明
∞ X k=0
1 (k + 2)k!
= 1
10. 利用一般生成函數證明
∞ X k=0 n + k k 1 2k
= 2n+1
11. 對任何正整數 n, 證明
[n−1 2 ] X k=0 1− 2k n n k 2 = 1 n 2n−2 n−1 (6.4)
這裡 n−1 2 表示 n−1 2
的整數部分。
參考文獻
1. 黃子嘉 (2001), 離散數學 (上)。 台北: 鼎茂。 2. Grimaldi, R.P. (1999). Generating functions. In: Rosen, K.H. (Editor in Chief) Handbook of Discrete and Combinatorial Mathematics, Section 3.2. New York: CRC. 3. Grimaldi, R.P. (2004). Discrete and Combinatorial Mathematics, 5th edition. New York: Addison Wesley
No comments:
Post a Comment