生成函數與差分方程 1

哆啦ˇ

組合數學是一門有廣泛應用且頗引人入勝的數學分枝。研讀組合數學並不需要太多數學背景;在高中數學裏便已介紹了許多有趣且困難的排列組合問題。但在那裏所用的方法卻是初等的；有如解算術題，每一問題有各自思考方法與技巧。在本文中我們將討論一類排列組合問題，它們可以用列線性回歸方程 (linear recurrence) 的方法來求解，並用例題來說明兩種回歸方程求解的步驟。我們所作僅為一粗淺介紹，所選取的材料可為讀過微積分的讀者所接受。有興趣的讀者應進一步參閱本文後所列參考資料。 我們先用例題來說明回歸方程的數學意義和它與排列組合問題之關係。 [例1] 設有 n 個半徑遞增的圓環依大小套在一圓柱上，最大的環在最下面。我們要將這些環移置至另一圓柱上，另有第三個圓柱作暫時放置圓環用，但移置時規定大環永不可放在小環上面，每次移動一個環，問最少要移動幾次才可將 n 個環由一圓柱移至另一圓柱？這便是著名的「河內之塔」問題 (The tower of Hanoi problem)。顯見當 n=1 時，我們只需 1步；當 n=2 時，我們需要 3 步。但當 n 很大時，例如， n=64，問題的答案便不顯然了。設 an (n=1,2,3,…) 為移動 n 個環的最少次數，則 a1=1, a2=3。如果 n>2，我們可先用 an-1 步將第一柱上面之 n-1 個環移至第三柱上，然後將最大環移至第二柱，最後再用 an-1 步將第三柱上之 n-1 個環放在第二柱最大環之上面。這樣便完成以最少步數移置這 n 個環，故得

an	=		(1)
a1	=	1	(2)

數列 可看成是定義在正整數集上的函數。 (1)式表示了兩相連正整數間該函數值之關係，稱為回歸方程，又稱差分方程 (difference equation)。 (2)式稱為方程(1)之邊界條件 (boundary condition)。如所給 n 之值不大，我們可用邊界條件 (2)代入 (1)式之右邊而逐步得出 an之值。方程 (1)之解是一用 n 表達 an 的一般形式。我們先討論應用生成函數 (generating function) 的方法求滿足邊界條件(2)之方程 (1)的解。 我們先提出生成函數的定義。設 是一數列，則函數

稱為與數列 對應之生成函數。生成函數又稱形式冪級數 (formal power series)，是看成一代數對象，我們無需顧慮其收斂性。生成函數可以相加與相乘，也可以形式地求其導數與反導數 這些運算法則恰如冪級數的對應運算。設

是與數列 所對應之生成函數，則生成函數的相加與相乘是定義為

其中

生成函數 f(x) 之導數是

本文所考慮的生成函數均為整係數。如果由(3)給出之生成函數 f(x) 是整係數的且首項係數 a0 為 1，則 f(x) 還可以除另一整係數的生成函數，所得之商仍為一整係數生成函數。兩個生成函數相等僅當它們對應之係數均相等。我們將在例題中用實際計算來說明這些運算，不再在理論上作詳細說明，其理論基礎請參閱參考資料[3]。有關生成函數在組合數學中之其它應用可參閱[2,4]。 回到回歸方程(1)，顯見可令 a0=0而仍保持由式(1)及(2)所建立之關係。將滿足(1)與 (2)之各數用數列 記出，並設 g(x) 為與之對應的生成函數，則我們有

如將上面三個生成函數相加，則由式(1)及 a0 之定義可知所得之生成函數的係數由第二項起均為零；g(x) 下面的二生成函數便是依據此一原則所定出。故得

解出 g(x) 有

因得滿足邊界條件(2)之方程(1)的解為

當 n=64 時，移動 64 個環的最小步數 an=264-1 是個很大數字。 [例2] 在平面上畫 n 個橢圓，每兩個必恰好交於兩點，但每三個又不能交於同一點，問這些橢圓將平面分隔成多少區域? 設 an (n=1，2，…)為 n 個橢圓將平面分隔之區域個數，則顯見 a1=2, a2=4。當 時，用觀察法求 an 便有困難了。設在平面上有 n-1 個橢圓，將平面份為 an-1 個區域，如再在平面上畫入第 n 個橢圓，則它與原有 n-1 個橢圓中每一個均恰交於兩點。這 2(n-1) 個交點將第 n 個橢圓分成 2(n-1) 個弧段，而每一弧段又將所在的 2(n-1) 個原有區域一分為二，故得回歸方程

定義 a0=2 並設 g(x) 為數列 之生成函數，則

其中，上面第三個等式可由下法導出:

將上三式相加得

即

因為

故

最後得回歸方程(4)之解為

[例 3] 問在用整數 0 與 1 組成的 n 位數中，有多少不含兩個相連的 0? 顯見有 2 個一位數；3 個二位數：01,10 與 11。設 an 為由 0 與 1 所組成不含兩個相連的 0 之 n-1 位數之個數（其中 n 錯開一位是由於歷史上原因），則得回歸方程

這是因為在不含兩個相連的零之由 0 與 1 組成 n-1 位數中，最後一位數如是零，則最後第二位數就不能是零，這樣的數一共有 an-2 個；最後一位數如是 1，則前面 n-2 個數可任意選取 0 或 1，只要兩個零不相連便可，這樣的數一共有 an-1 個。式(5)給出三個相連的 an 之值關係，稱為 2 階回歸方程，需要 2 個邊界條件。由(5)我們可定義 a1=1, a0=1。依前法，令 g(x) 是數列 之生成函數，則得

故得

g(x)(1-x-x2) = 1

利用部分分式得

其中

故得回歸方程(5)之解是

實際上數列 的前幾項可很容易得出，由式 (5)知 a0=1， a1=1起後面每一項均等於其前面兩項之和，故該數列的前幾項是

這些數稱為 Fibonacci數，它們背後藏有一段歷史悠久且頗具趣味的數學故事。但這些已不在本文範圍內了。 前面我們提出了幾個簡單的回歸方程的例子，並說明用生成函數求解的過程。在下面我們將回歸方程看成是一種差分方程，並介紹另一種方程求解的方法。我們已提過一個數列 a=