動機
計數問題常常在去掉對象的最後一部分之後變得更簡單。餘下的對象更小,因此這種分解給出一個遞推關係。遞推關係還未算是封閉形式的答案:它的初始值與適用範圍同樣重要。生成函數把整個數列打包起來,使下標的移位變成乘以一個形式變量。
定義
定義 3.1.1
(形式級數與遞推關係)
對於實數或複數上的數列 ,其普通生成函數是形式級數 。兩個形式級數相等,是指它們的每一個係數都相等。乘積採用有限卷積法則
階為 的常係數齊次線性遞推關係是指:當 時 ,並同時給定 。
「形式」的意思是:我們既不先取定 的數值,也不追問分析意義上的收斂性。乘積的每一個係數都只涉及有限多項。常數項非零的形式級數有唯一的乘法逆元,可以從零次項開始逐次向上求解各次係數,以遞歸方式得到。
定理/命題
定理 3.1.2
(初始值決定遞推關係的解)
具有上述形式的遞推關係與 個初始值恰好決定一個數列。它的生成函數滿足
特別地,它的生成函數作為形式級數是有理的。
定理 3.1.3
(兩個相異的特徵根)
若對 有 ,且 有相異的非零根 ,則存在唯一的常數 ,使得對每個 都有 。它們由 與 確定。
證明思路
證明
(存在性、唯一性與分子多項式)
遞推關係的解的存在性,由逐項依次定義下一項得到。若兩個解在首 項上一致,則由歸納法,它們在其後每一項上也一致,這就證明了唯一性。將 乘以分母多項式。對於次數 ,所得係數為 ;對於 ,它恰好是右邊的係數。分母的常數項為 ,所以它在形式意義下可逆。
證明
(構造線性組合,再援引唯一性)
至於特徵根定理,數列 與 各自由其定義二次方程而滿足該遞推關係。關於 的兩個方程,其行列式 非零。它們的線性組合具有正確的初始值,因此由唯一性可知它就等於所求數列。這個證明並沒有去猜測所有解都具有所示形式;它構造出一個解,再援引唯一性。
證明透視
相異根在哪裏用到
這個證明有兩個互相獨立的部分。第一,每個幾何數列都是遞推關係的解:對 ,
而遞推關係是線性的,所以每個組合 也是解。這部分完全沒有用到 。第二,必須能配合初始值:方程組 、 的行列式是 ,相異性只在這裏用到。行列式非零,對每組 都恰好給出一對 ;若兩對常數都表示該數列,它們在 處解同一個非奇異方程組,所以相等。論證最後不是靠計算更多項來完成,而是經由第一個定理:該組合與所給數列是首兩項相同的兩個解,因此對每個 都相等。
當兩個根重合時,兩個指數數列是同一個數列,上述論證便不再適用。例如,遞推關係 說明一階差分為常數,從而 。多出來的因子 來自一個真正不同的第二個解。
反例模式
重根使初始值無法配合
斷言:二階遞推關係的每個解,都是其特徵根之冪的線性組合。對 ,特徵多項式為 ,唯一的根是 ,而它的冪的任何組合都是常數 。初始值 、 要求同時有 與 ,這不可能。然而該遞推關係有解 ;例如 。此時行列式 為零,失效的正是這個假設。修正:若 是非零重根,即 、,則數列 是第二個解,因為 。對 ,初始條件為 與 ,這個方程組的行列式是 。
例題詳解
例題 3.1.4
(不含相鄰兩個 1 的二進制串)
設 為不含子塊 的長度為 的二進制串的個數。空串有一個,所以 ,並且 。對於 ,以 結尾的串,是在一個合乎要求的長度為 的串後面添上 得到的。以 結尾的串必定以 結尾,它們由合乎要求的長度為 的串得到。這兩種情形互不相交,並且涵蓋所有可能,所以 。於是 ,並且 。
例題 3.1.5
(一個非齊次遞推關係)
設 ,且對 有 。令 。則 且 ,所以 。檢驗 ,兩邊都給出 。這一代換消去了強迫項;齊次情形的特徵公式不能簡單地忽略該項。
例題 3.1.6
(在重複因子之後提取係數)
形式幾何級數滿足 。將它平方並利用卷積,得到 ,因為該係數計數的是和為 的非負整數對。因此,對 有 ,而常數項為 。
不依賴收斂性假設的形式代數
形式生成函數是對係數的一份記錄,起初並不是一個數值函數。使用無窮記號是合理的,因為和或積的每一個所需係數,都只由有限多個輸入確定。對於乘積,給定次數處的係數只用到次數相加等於該次數的那些次數對。因此,即使沒有任何一個變量的數值能使原來兩個級數同時收斂,卷積公式依然是良定的。
逆元的存在性可以用同樣的有限推理來證明。在零次項處,乘積方程迫使逆元的常數項確定下來。在一次項處,它迫使下一個係數確定,且只用到已經確定的係數。此後每一次項都給出一個線性方程,其首項純量相同且非零。於是逆元存在且唯一,整個過程沒有取任何分析意義上的極限。如果原級數的常數項為零,則零次項處的乘積不可能等於一,因此這樣的逆元不存在。
這一觀點解釋了遞推問題中出現的分母。它們的常數項是一,所以除法從一開始就在形式意義下成立。如果提出的是分析性問題,則之後可以再研究數值收斂性,但按係數計數的論證不應依賴於在某個數值點上未經證明的代入。
初始條件是下標移位的邊界項
將生成函數乘以變量,會使其係數數列後移一位,並在開頭插入零。遞推關係的移位並不會自動插入實際的初始值;它們必須另行處理。這正是分子多項式的來源,也說明了為甚麼兩個數列可以滿足同一個遞推關係,卻有不同的生成函數。
可靠的推導方法是:先在遞推關係成立的下標處把它乘上去,只對這些下標求和,並在化簡之前把每個截斷級數明確寫出。這樣,每一個被省略的初始項都清晰可見。一旦掌握了這種模式,定理中的一般公式便能高效地完成這項記賬工作。如果某個分子看起來出乎意料地簡單,應當把它的頭幾個係數與所給的初始值逐一核對,而不要假定所有邊界項都已消失。
這裏的棋盤鋪法序列計算以長度一和二的磚鋪板的方法:空板有一種鋪法,長度一亦有一種;移除最後一塊便給出相同的兩項遞推。
不含相鄰兩個 1 的數列與鋪磚數列正好說明了這一區別。它們滿足同一個二階遞推關係,但首項不同。因此它們的分母相同,分子卻不同。遞推關係描述的是更新規則;分子記錄的則是從這條更新規則的所有解中選取了哪一個解。單憑其中任何一部分,都無法確定這個計數數列。
有序組裝與無序選取
生成函數反映被計數對象的確切結構。假設一個整數總和由大小為一和二的部分構成,這些部分之間不附帶任何次序。大小為二的部分的個數唯一地確定了該對象,其餘的單位則是大小為一的部分。其生成函數是兩個級數的乘積:一個容許任意多個大小為一的部分,另一個容許任意多個大小為二的部分。它的分母是相應兩個幾何級數分母的乘積。
當總和為五時,這樣的無序選取有三種:使用零個、一個或兩個大小為二的部分。這與長度為五的板的八種鋪法不同,因為鋪法記錄了磚塊的次序。先放一塊長度為二的磚再放一塊長度為一的磚,與相反次序是不同的鋪法,儘管兩者每種磚的塊數相同。這種不一致並不是生成函數的失敗;它說明兩個模型計數的是不同的對象。
要直接提取無序情形的係數,可以在零到總和的一半(向下取整)之間選取大小為二的部分的個數。每一種選擇都恰好留下一個合法的大小為一的部分的個數。因此答案是該向下取整的一半再加一。這個係數計算是一個有限卷積,為乘法法則提供了另一種具體解釋。
由首次回歸得到的非線性遞推
並非每個有用的遞推關係都是線性的。考慮這樣的括號平衡串:左、右括號總數相等,且每個前綴中的左括號個數都不少於右括號個數。空串是容許的。非空的這類串以左括號開頭。與它配對的右括號,位於第一次回到平衡值零的位置,它把該串唯一地分成內部的一個平衡串與其後的一個平衡串。
若總共有固定數目的括號對,則選定內部的對數就決定了其後的對數。這兩個較小的串隨後可以獨立選取。對所有可能的分割大小,把它們的計數之積求和,便得到一個卷積型遞推關係,其中空串的計數等於一。這個分割是唯一的,因為它使用的是首次回到零的位置;若任意選取一個右括號,則得不到同樣明確的分解。
用生成函數的語言來說,該級數等於空串情形的一,加上非空情形的變量乘以它自身的平方。變量記錄最外層的那一對配對括號。這個方程以遞歸方式確定每一個係數:正次數處的係數只依賴於更早的係數。從一開始,零至三對括號的計數依次為一、一、二和五。若要得到封閉公式,還需要進一步的論證;而這一分解本身,無需封閉公式,就已經證明了該遞推關係及其含義。
若 計算有 對括號的串,而 ,則上述分解給出 ,以及對 有 ,從而 。
概念視角結構
乘積記錄了對象分成兩部分
乘積中的卷積係數考慮了將總大小分配給第一個對象與第二個對象的所有方式。只有當原對象能唯一地分解為這樣一個有序對時,組合意義上的乘積才有依據。同一個係數法則可以編碼兩段括號、兩個獨立的選取,或一個代數遞推關係,但在每種情形下都必須另行給出解釋。
封閉形式由存在性與唯一性來驗證
一個猜想的公式,可能來自巧妙的代換、特徵多項式,或生成函數的運算。驗證往往比發現簡單得多。檢查初始值,把所提出的表達式代入每一個有效下標處的遞推關係,再援引唯一性。即使啟發出這一公式的途徑並不嚴格,這三步論證也能證明該公式。
對於重複的特徵根,相異根定理的假設確實不成立。必須另外推導出一個解,或者回到生成函數;僅僅把同一個根賦給兩個常數,只會得到一個指數數列。對於非齊次遞推關係,在應用齊次情形的唯一性論證之前,必須先包含針對強迫項的一個特解。這是擴展該方法的兩個不同原因,因此不應把它們合併為一個含糊的例外。
最後,遞推關係的階並不一定是每個選定數列可能的最小階。特殊的初始值可能使封閉形式中的某一項消失,從而容許存在更低階的關係。所給出的遞推關係仍然正確地確定該數列。區分有效的遞推關係與最小的遞推關係,可以避免作出超出計算所能證明的斷言。
常見錯誤
常見錯誤
(在首個有效下標之前套用遞推關係)
從 起成立的遞推關係,不能代入 ,除非像 這樣的項已另行定義並給出理由。對不含 的串,若設 並在 處套用 ,會得到 ;但串 與 給出 。在生成函數的計算中保留初始多項式,可以避免這類下標錯誤。
常見錯誤
(沒有雙射就去掉最後一個符號)
組合遞推關係需要一個雙射的分解。如果容許的擴展方式的數目取決於餘下的串,那麼只說「去掉最後一個符號」是不夠的。在不含 的例子中,以 結尾的合乎要求的串只能再添 ,所以 並不等於 :已有 。把結尾 與結尾 分開,就使這種依賴關係變得明確。
常見錯誤
(把數值代入形式恆等式)
形式恆等式不會自動使在級數解析收斂域之外的數值代入變得合理。若在 處解讀形式恆等式 ,便會斷言 ,作為數值求和這毫無意義。該恆等式是關於係數的陳述;要代入數值,須另有收斂性論證。
總結
一個分解提供一個遞推關係及其初始值。形式生成函數把移位變成多項式乘法,初始項出現在分子中。唯一性則提供了一種清晰的方法,來驗證所提出的封閉形式。
練習
快速檢查
(計數用長度為一和二的磚塊鋪滿長度為 的板的鋪法數。求其生成函數,並求 時的計數。)
空板有一種鋪法。
解答 · 答案
設 。對於 ,去掉最後一塊長度為一或長度為二的磚,得到 ,其中兩種情形互不相交,且可以唯一地還原。因此 。數值 說明 。
快速檢查
(解 ,其中 、,並求其生成函數。)
利用一階差分,或利用一般的生成函數恆等式。
解答 · 答案
由遞推關係得 ,所以每個一階差分都是 。因此 。生成函數為 。分子也可以直接由 得到。
快速檢查
(已知 ,用 計算 ,並說明下標為 的項計數甚麼。)
解答 · 答案
取 ,得 。下標為 的項計數這樣的四對括號串:其第一對括號(在首次回到零處閉合)內含 對,其後跟著一個含其餘 對的平衡串。這四種情形互不相交且涵蓋每個串,所以把各乘積相加。