遞迴關係（八）（Recurrence relation-8）

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

連結：遞迴關係（七）

摘要：延續上篇的幾個基本高維遞迴關係，本篇反過來以遞迴的角度來探討這些數列。

利用遞迴關係解決問題時，思考模式是動態與局部的  —  關心的是從一項到另一項之間的變化，即使根本不知道整體看來一般項公式是什麼。這篇文章中我們利用前文的二項式係數，$$\mathrm{Stirling}$$ 第一類、第二類數，來介紹一下遞迴的思考方式。

$$(1)$$  二項式係數的遞迴

令 $$a_{n,k}$$ 表示 $$n$$ 個相異物品中取出 $$k$$ 個的方法數，在什麼資訊都沒有的情況下，如何推導出遞迴關係式呢？想法是這樣。令 $$n$$ 個相異物品為 $$\{1,2,…,n\}$$，現在要選出 $$k$$ 個。

所有的選法可分成兩類：$$(\mathrm{i})~~n$$ 有被選到  $$(\mathrm{ii})~~n$$ 沒有被選到。

在第一類中，剩下的 $$n-1$$ 個中還要再選 $$k-1$$ 個，故有 $$a_{n-1,k-1}$$ 種方法。

在第二類中，剩下的 $$n-1$$ 個中還要再選 $$k$$ 個，故有 $$a_{n-1,k}$$ 種方法。因此合起來就有

$$a_{n,k}=a_{n-1,k-1}+a_{n-1,k}$$

初始值 $$a_{n,0}=1$$、$$a_{n,n}=1$$ 是顯然的。

因此就得到遞迴關係了。接著用一些數學工具可以得到 $$\displaystyle a_{n,k}=C_k^n=\frac{n!}{k!(n-k)!}$$。

在組合數學（離散數學）的研究中，以上的模式是常常出現的  —  先想辦法找到遞迴式再說。而且通常因為通項公式不見得存在，所以找到遞迴式常是關鍵的突破口。

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

在上一篇文章中，我們說由 $$a_{n,k}=a_{n-1,k-1}+(n-1)a_{n-1,k}$$ 定義出來的第一類 $$\mathrm{Stirling}$$ 數 $$a_{n,k}$$ 表示將 $$\{1,2,…,n\}$$ 分成 $$k$$ 個非空集合，且每個集合圍成一圈的方法數。底下來說明為什麼。

將 $$n$$ 人分成 $$k$$ 個非空集合，且每個集合圍成一圈的所有方法，可以分成兩類：

$$(1)~~~n$$ 自己一個人孤獨成圈
$$(2)~~~n$$ 和其他人圍成一圈。

在第一類中，剩下的 $$n-1$$ 人要圍成 $$k-1$$ 圈。所以有 $$a_{n-1,k-1}$$ 種方法。在第二類中，先讓剩下的 $$n-1$$ 人圍成 $$k$$ 圈（有 $$a_{n-1,k}$$ 種方法），然後再讓 $$n$$ 加入  — $$n$$ 可以怎麼加入呢？他可以任選一個人，跟在他的背後。因此有 $$n-1$$ 個方法。換句話說，一共有 $$(n-1)\cdot a_{n-1,k}$$ 種方法。合併起來就得到遞迴式

$$a_{n,k}=a_{n-1,k-1}+(n-1)a_{n-1,k}$$

初始值 $$a_{n,0}=0(n\geq 1)$$、$$a_{n,n}=1(n\geq 0)$$ 是顯然的。因此，我們就解釋了為什麼這個量是 $$n$$ 人圍成 $$k$$ 圈方法數了。下圖說明 $$a_{4,2}=11$$

$$(3)$$  第二類 $$\mahtrm{Stirling}$$ 數的遞迴

接下來說明由 $$a_{n,k}=a_{n-1,k-1}+ka_{n-1,k}$$ 定義出來的第二類 $$\mathrm{Stirling}$$ 數 $$a_{n,k}$$ 表示將 $$\{1,2,…,n\}$$ 分成 $$k$$ 個非空集合方法數。所有方法，可以分成兩類：

$$(1)~~~n$$ 自己一個人成一集合
$$(2)~~~n$$ 和其他人在一起。

在第一類中，有 $$a_{n-1,k-1}$$ 種方法。在第二類中，先讓剩下的 $$n-1$$ 人分成 $$k$$ 個集合（有 $$a_{n-1,k}$$ 種方法），然後再讓 $$n$$ 任選一個集合加入，故有 $$k$$ 個方法。合併起來得到遞迴式

$$a_{n,k}=a_{n-1,k-1}+ka_{n-1,k}$$

初始值也是顯然的。因此，我們就解釋了為什麼這個量是 $$n$$ 人分成 $$k$$ 個非空集合的方法數了。下圖說明 $$a_{4,2}=7$$。

讀者一定會問，那一般項呢？很抱歉，第一類和第二類 $$\mathrm{Stirling}$$ 數都寫不出不含 $$\Sigma$$ 的一般項！但是有非常多的關係式，可搜尋網路資料。

遞迴的思考對於高中師生是非常不熟悉的，但是卻是科學工作者重要的素養。關於遞迴，還有許多有趣的題材，在這系列的短文中，刻意略去與教科書上的制式化解法，期能透過各種例子的介紹，使讀者體會遞迴關係的重要，解遞迴的困難，以及遞迴的思考模式。

參考文獻：

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.