第4章遞迴、生成函數與Catalan數

本章小節

4.1 先有初值，再比較生成函數的係數
4.2 四個例題
4.3 練習
4.4 完整解答

4.1 先有初值，再比較生成函數的係數

遞迴關係說明後項如何由前項決定；還要給足初值。例如 aₙ=aₙ₋₁+aₙ₋₂ 適用於 n≥2，a₀、a₁ 一旦給定，就能依序算出全部。公式相同但初值不同，答案可以不同。

合法括號字串有 n 個左括號與 n 個右括號，每個前綴的左括號不少於右括號。令 Cₙ 為其數量，空字串給 C₀=1。非空字串可寫成 (U)V，第一個使高度回到零的右括號，恰好結束外層括號。回零之前高度至少為 1，所以去掉外層後，U 的相對高度非負並回到零；V 從零開始，亦合法。反過來，兩個合法字串 U、V 接成 (U)V 時，外層的右括號就是首次回零。因此 Cₙ=Σ CᵢCₙ₋₁₋ᵢ（0≤i<n）。

至多有 2^(2n)=4ⁿ 個長度 2n 的括號字串，因此 C(t)=Σ Cₙtⁿ 在 |t|<1/4 絕對收斂，Cauchy 乘積給 C(t)=1+tC(t)²。Cₙ 是 Catalan 數，與二項係數 C(n,k) 的記號有別。

把左、右括號分別當作上升、下降一步。n≥1 時有 C(2n,n) 條回零路徑。不合法者先到高度 −1；把截至首次 −1 的步子上下對換。此前高度皆非負，反射後此前皆非正，而該點成了首次到 1。後續步子不動，故終點升到 2。

反過來，任何終點為 2 的路徑必先到高度 1；反射截至首次 1 的步子，會回到終點 0，且在對應點首次到 −1。兩次反射翻同一段，因此互為逆。終點為 2 的路徑有 n+1 次上升、n−1 次下降，共 C(2n,n+1) 條。相減並約分得 Cₙ=C(2n,n)/(n+1)；n=0 時此式亦給 1。

4.2 四個例題

例題1 三對括號的五種來自哪裡

C₁=C₀C₀=1，C₂=C₀C₁+C₁C₀=2。C₃ 依內部 0、1、2 對分類，為 1·2+1·1+2·1=5。分類由第一個配對右括號決定，不重不漏。

例題2 幾何級數的係數是等比數列

a₀=1、aₙ=2aₙ₋₁，得 aₙ=2ⁿ。當 |t|<1/2，A(t)=Σ(2t)ⁿ 絕對收斂。把 2tA(t) 從 A(t) 扣掉只剩 1，因此 A(t)=1/(1−2t)；t=1/2 不能由此宣布收斂。

例題3 從兩個初值推出生成函數

取 a₀=0、a₁=1，n≥2 時 aₙ=aₙ₋₁+aₙ₋₂。由初值及遞迴歸納得 0≤aₙ≤2ⁿ，故 |t|<1/2 可移項。把 n≥2 的遞迴乘上 tⁿ 加總：aₙ₋₁ 的和是 t(A(t)−a₀)，aₙ₋₂ 的和是 t²A(t)。因此 A(t)−t=tA(t)+t²A(t)，得 A(t)=t/(1−t−t²)。依遞迴前六項為 0、1、1、2、3、5。

例題4 Catalan 的兩個根只留一個

由 C=1+tC²，整理得 (1−2tC(t))²=1−4t。冪級數使 1−2tC(t) 在 |t|<1/4 連續，且在 t=0 等於 1。右側在這個實區間內嚴格為正，所以左側平方裡的量無法穿過零，必取正根。由此對 t≠0 得 C(t)=(1−√(1−4t))/(2t)=2/(1+√(1−4t))。後一式在 t=0 也等於 1。

4.3 練習

B10-C04-Q01 a₀=2，aₙ=aₙ₋₁+3，求 a₁ 到 a₄。
B10-C04-Q02 a₀=1，aₙ=3aₙ₋₁，求 a₃ 及 A(t)。
B10-C04-Q03 求 (1+t+t²)(1+2t) 的 t² 係數。
B10-C04-Q04 沿用例題3求 a₆、a₇。
B10-C04-Q05 用 Catalan 遞迴算 C₄。
B10-C04-Q06 「())(」左右括號一樣多，是合法括號字串嗎？
B10-C04-Q07 「(()())」的 (U)V 分解是什麼？
B10-C04-Q08 對例題3的二階遞迴，只知道 a₀=0，為何還不能決定所有項？
B10-C04-Q09 aₙ=n! 的普通生成函數有原點附近正的收斂半徑嗎？
B10-C04-Q10 為何 C(t)=1+tC(t)² 中有一個 t？

4.4 完整解答

Q01

逐次加 3，得 5、8、11、14。由每步差固定可寫 aₙ=2+3n。

Q02

逐次乘 3 得 a₃=27。係數是 3ⁿ，在 |t|<1/3 可用幾何級數得 A(t)=1/(1−3t)。

Q03

冪次 2 來自 t²·1 或 t·2t，前者 1、後者 2，合計 3。

Q04

a₆=a₅+a₄=5+3=8，a₇=a₆+a₅=8+5=13。

Q05

按 i=0、1、2、3，依序有 1·5、1·2、2·1、5·1，總數 14。

Q06

不是。前三個字元「())」已有 1 個左與 2 個右，前綴高度為 −1。最後回到零不能補救。

Q07

首次回零在最後一格，外面第一、末字元為一對，U=「()()」、V 為空字串。U 的兩對屬於外層內部。

Q08

a₁ 尚可自由選。比如 a₀=0，取 a₁=0 得全零；取 a₁=1 得 a₂=1，之後也不同。需要兩個初值。

Q09

沒有。任意 t≠0，級數項絕對值的相鄰比為 (n+1)|t|，終會大於 2，所以項不趨 0。形式符號可以記係數，但不能按本章當成解析函數。

Q10

配對的外層括號本身占一對。C² 中 t^(n−1) 給 U、V 共 n−1 對；乘 t 把這個係數放到 n 對。常數 1 對應空字串。

第4章 遞迴、生成函數與Catalan數