遞迴關係（七）（Recurrence relation-7）

遞迴關係（七）（Recurrence relation-7）
國立高雄大學應用數學系游森棚教授/國立高雄大學應用數學系游森棚教授責任編輯

連結：遞迴關係（六）

摘要：不同於前面幾篇，本篇文章介紹幾個基本的高維遞迴關係

目前為止介紹的都是單維的遞迴  — $$a_n$$ 只有一個足碼 $$n$$。但是在數學上，更高維的遞迴也很常見，事實上在高中數學就出現過了只是未強調遞迴的觀點。我們熟悉的巴斯卡三角形，就是一個二維遞迴。這篇文章介紹幾個基本的高維遞迴關係。

$$(1)$$  巴斯卡三角形與二項式係數

眾所周知，巴斯卡三角形的第 $$n$$ 列第 $$k$$ 項（$$n\geq 0$$，$$0\leq k\leq n$$）是二項式係數 $$C_k^n$$。

而且對任意 $$n\geq 0$$ 有 $$C_0^{n}=1,C_n^{n}=1$$ 及恆等式

$$C^n_k=C^{n-1}_{k-1}+C^{n-1}_{k}$$

即某列的相鄰兩項和等於下一列的一項。

以遞迴的觀點來看，這是一個簡單的二維的遞迴。即

$$a_{n,k}=a_{n-1,k-1}+a_{n-1,k}$$，初始值 $$a_{n,0}=1$$、$$a_{n,n}=1$$

巴斯卡三角形之中隱含了非常多有趣和不可預期的性質，份量足夠寫一本專書。高中課本中因篇幅關係完全沒有提到，是很可惜的事。比如，巴斯卡三角形中隱藏著費波那契數：如下圖，斜的求和，則這些和就是費波那契數！

至於證明，讀者覺得下列那個策略容易些？

$$(\mathrm{i})$$ 證明各線的和所成的數列 $$S_n$$ 滿足 $$S_n=S_{n-1}+S_{n-2}$$，$$S_0=S_1=1$$，

或是

$$(\mathrm{ii})$$ 直接證明 $$S_n$$ 就是那個充滿 $$\sqrt{5}$$ 的一般式？

當然 $$(\mathrm{i})$$ 才是可行的策略。這也再次說明了有時候遞迴式本身比一般式更有用。

$$(2)$$  第一類 $$\mathrm{Stirling}$$ 數

如果將二項式係數的二維遞迴關係式稍微改變一下如下，

$$a_{n,k}=a_{n-1,k-1}+(n-1)a_{n-1,k}$$，初始值 $$a_{n,0}=0~(n\ge 1)$$、$$a_{n,n}=1~(n\ge 0)$$

再配上相間的正負號，可以慢慢遞迴生成出一個類似巴斯卡三角形的表 $$(-1)^{n+k}a_{n,k}$$，如下圖。

$$(-1)^{n+k}a_{n,k}$$ 稱為(有號的)第一類  $$\mathrm{Stirling}$$  數。負號不計的 $$a_{n,k}$$ 稱為第二類 $$\mathrm{Stirling}$$ 數。

$$a_{n,k}$$ 剛好就是將 $$\{1,2,…,n\}$$ 分成 $$k$$ 個非空集合，且每個集合圍成一圈的方法數。

$$(3)$$  第二類 $$\mathrm{Stirling}$$ 數

如果將二項式係數的二維遞迴關係式如下稍微改變一下，

$$a_{n,k}=a_{n-1,k-1}+ka_{n-1,k}$$，初始值 $$a_{n,0}=0~(n\ge 1)$$、$$a_{n,n}=1~(n\ge 0)$$

也可以慢慢遞迴生成出一個類似巴斯卡三角形的表，如下圖。

這些數字稱為第二類 $$\mathrm{Stirling}$$ 數。$$a_{n,k}$$ 剛好就是將 $$\{1,2,…,n\}$$ 分成 $$k$$ 個非空集合的方法數。

二項式係數，第一類與第二類 $$\mathrm{Stirling}$$ 數是組合數學的支柱，到現在為止仍然不時有新的研究成果。

連結：遞迴關係（八）

參考文獻：

1. Tucker, Applied Combinatorics, 5th edition, Wiley.
2. Brualdi, Introductory Combinatorics, 5th Edition, Pearson.

延伸閱讀：

1. 教育部，高中課程綱要(99)，2010。
2. Aigner, A course in enumeration, 1st edition, Springer, 2007.