點算的奧秘：點算問題的遞歸關係

「遞歸關係」(Recurrence Relation，亦譯作「遞推關係」或「遞迴關係」)是除了「容斥原理」、「母函數」和「伯恩賽德-波利亞定理」以外，另一求解「點算組合學」問題的重要工具。在數學上，「遞歸關係」可用來定義某些函數，最常見的例子就是「階乘」(Factorial)的定義。在《點算的奧秘：排列和組合基本公式》中，筆者把「n階乘」(n!)定義為

但是我們也可把n!定義為

以上就是n!的「遞歸」(Recursive)定義。請注意這個定義由兩部分組成，第一部分是「遞歸」部分，包含一個「遞歸關係」。所謂「遞歸關係」，是指在定義某函數時，該函數本身被應用於自己的定義中。當然為免出現循環定義的問題，該函數在「定義項」和「被定義項」中應分別以不同的值為輸入值。例如在上述定義中，「被定義項」n!以n為輸入值，而「定義項」中的(n − 1)!則以n − 1為輸入值。上述定義中的第二部分是「基礎」(Base)部分，它通常規定函數的某個或某些初值(Initial Value)。利用「遞歸」定義的兩個部分，我們便可以求得函數在「定義域」(Domain)下的所有值(註1)。例如把n = 2代入上面的「遞歸關係」，並利用1! = 1，便可求得

利用這個方法，在理論上可以求得n為任意正整數時，n!的值。

在「點算組合學」上，「遞歸關係」可用來表達某些點算問題。以下筆者將回顧以往介紹過的某些「點算組合學」問題，並把它們表述為「遞歸關係」。首先看「不可重覆的組合」問題。在《點算的奧秘：二項式定理和多項式定理》，筆者推導了「二項式系數」的「遞歸關係」，現複述如下(並補上「基礎」部分)(註2)：

我們可以從兩個角度解釋上式中的「基礎」部分，即C(n, 0) = 1。第一個角度是直接從C(n, 0)的定義出發。根據「組合」的定義，C(n, 0)代表從n類物件中不可重覆地抽0個出來的方法總數，這顯然只有一種方法，就是一個也不抽出來，因此C(n, 0) = 1。

其次，我們可以利用C(n + 1, 1)和C(n, 1)的值以及上式中的「遞歸」部分反推出C(n, 0)的值。根據「組合」的定義，容易看到C(n + 1, 1) = n + 1和C(n, 1) = n。舉例說，從n類物件中不可重覆地抽1個出來，這顯然共有n種方法，因此C(n, 1) = n。把此一結果代入上式中的「遞歸」部分：

上述兩種方法(「直接法」和「反推法」)都是求「遞歸關係」的「基礎」部分的有效方法。不過，由於「直接法」涉及點算問題在某些「極端」情況時的值，這需依賴我們的直觀，而直觀有時是不準確的，因此我們最還是用「反推法」驗證一下，看看用這兩種方法求得的值是否一致。如果兩者不一致，那麼應以「反推法」所求的值為準。在以下的討論中，筆者一般不會詳細解釋各個「遞歸關係」的「基礎」部分的理據，讀者可自行用「直接法」或「反推法」證實各「基礎」部分的合理性。

由於「二項式系數」就是「不可重覆的組合」問題的計算公式，所以上式也就是這類問題的「遞歸關係」。請注意C(n, r)含有兩個變項，因此上式是一個「二元遞歸關係」，其「基礎」部分也較為複雜。舉例說，把n = 2，r = 2代入上式，便可求得

其次考慮「無限重覆組合」問題，我們用E(n, r)代表這類問題的答案。根據《點算的奧秘：無限重覆的排列組合問題》，E(n, r) = C(n + r − 1, r)。利用此一關係以及公式(1)，可以求得

由此得到E(n, r)的「遞歸關係」如下：

接著考慮「不可重覆的排列」問題，即P(n, r)。根據《點算的奧秘：排列和組合基本公式》，P(n, r) = n! / (n − r)!。利用此一關係以及「階乘」的「遞歸關係」，可以求得

由此得到P(n, r)的「遞歸關係」如下：

接著考慮「無限重覆排列」問題，我們用U(n, r)代表這類問題的答案。根據《點算的奧秘：無限重覆的排列組合問題》，U(n, r) = n^r。由於此一問題簡單直觀，無需借助「遞歸關係」也容易求得答案。不過如果硬要寫出U(n, r)的「遞歸關係」，我們也可以利用關係式n^r = n(n^{r − 1})，得出以下「遞歸關係」：

請注意雖然U(n, r)含有兩個變項，但在上式中n的值是固定的，所以上式實際是一個「一元遞歸關係」。

接著考慮「不容許空集的集合劃分」問題，我們用P₁(r, n)代表這類問題的答案，也就是「點算組合學」上所稱的「第二類斯特林數」。具體地說，P₁(r, n)代表把r個元素劃歸n個非空子集的「劃分」方案總數。我們可以循以下思路推導這類問題的「遞歸關係」。我們任意選取其中一個元素(姑名之為a)。根據a是否被單獨劃歸其中一個子集，可以分為兩種情況。

在第一種情況下，a被單獨劃歸其中一個子集，即a所在的子集沒有其他元素，這樣我們尚要把r − 1個元素劃歸餘下的n − 1個子集。根據P₁的定義，這應共有P₁(r − 1, n − 1)種「劃分」法。在第二種情況下，a所在的子集尚有其他元素。我們暫不考慮a，首先把r − 1個元素劃歸n個子集，這應共有P₁(r − 1, n)種「劃分」法。接著我們把a劃歸這n個子集中的一個，這有n種選擇，所以在第二種情況下，共有n × P₁(r − 1, n)種「劃分」法。結合以上兩種情況，我們得到以下「遞歸關係」：

接著考慮含有《點算的奧秘：費雷爾斯圖》所稱的「第(2)類限制條件」的「不容許部分為0的整數分割」問題，我們用p(r, n)代表這類問題的答案。具體地說，p(r, n)代表把整數r分割為剛好n個非零部分的「分割」方案總數。類似「集合劃分」問題，我們根據在r的「分割」方案中是否包含1而把這個問題分為兩種情況。

在第一種情況下，r的「分割」方案包含1這個部分(可能不止一個部分為1，但我們只需考慮一個)，即r = 1 + ...。由於已確定了其中一個部分，餘下的就是把r − 1分割為n − 1個部分的「分割」方案。根據p的定義，應有p(r − 1, n − 1)種「分割」方案。在第二種情況下，r的「分割」方案有一個限制條件：所有部分都大於1。我們可以消除這個限制條件，方法是從r的「分割」方案中的各部分減去1，所得便是把r − n分割為n個非零部分，且各部分不一定都大於1的「分割」方案。舉例說，設r = 8，n = 3，並設給定一個各部分均大於1的「分割」方案：2 + 3 + 3，現在從各部分減去1，便得1 + 2 + 2，這是一個把8 − 3 = 5分割為3個部分的「分割」方案。總上所述，在第二種情況下，共有p(r − n, n)種「分割」方案。結合以上兩種情況，我們得到以下「遞歸關係」：

以上筆者介紹了四大「點算組合學」問題所滿足的「遞歸關係」。除了以上這些問題外，還有其他某些點算問題也可表述為「遞歸關係」。這些問題的特點是，如要直接求解，將頗為複雜。但如果把它們表述為「遞歸關係」，則使問題變得很容易。以下筆者用幾個例題展示以「遞歸關係」表述這些問題的方法。在以下例題中，所有「遞歸關係」都是一元函數的「遞歸關係」，而且這些函數都以非負整數集作為其「定義域」。由於以非負整數集作為「定義域」的函數等同於一個「序列」(Sequence)，以下筆者把這些「遞歸關係」的值表達為「序列」，以a₀、a₁ ... 表示。

例題1：用1、2、3、4這四個數字可以構造出多少個4位正整數，使得這些整數不含「22」這個部分？舉例說，3421便是符合本題規定的5位整數，而3221則不符合本題的規定，因為它含有「22」這個部分。

答1：我們用a_n代表符合本題規定的n位整數的數目，我們循以下思路推導a_n所滿足的「遞歸關係」。我們看如何構造出符合本題規定的n位整數。假設我們已有a_n−1個符合規定的n − 1位整數，那麼這些n − 1位整數都不含「22」這個部分，在這些n − 1位整數前加上1、3或4，便可構造出3a_n−1個n位整數，而且這些n位整數都必然不含「22」這個部分。舉例說，設有符合規定的3位整數421，在它前面加上3，便可得到符合規定的4位整數3421。至此我們找到了構造以1、3或4開首且符合規定的n位整數的方法，如何構造以2開首的n位整數呢？假設我們已有a_n−2個符合規定的n − 2位整數，那麼只要在這些n − 2位整數前加上21、23或24，便可構造出3a_n−2個符合規定的n位整數。舉例說，設有符合規定的2位整數21，在它前面加上21，便可得到符合規定的4位整數2121。綜合以上討論，我們找到a_n的「遞歸關係」為

本題答案就是a₄的值。利用以上「遞歸關係」，容易求得這個值。計算如下：

例題2：用1、2、3、4這四個數字可以構造出多少個4位正整數，使得這些整數不含「23」這個部分？

答2：本題在表面上跟上題非常相似，但其實在某一方面跟上題有很不同之處。雖然給定a_n−1個符合規定的n − 1位整數，我們可以透過在它們前面加上1、3或4來構造3a_n−1個符合規定的n位整數；可是，給定a_n−2個符合規定的n − 2位整數，我們卻不可以透過在它們前面加上21、22或24來構造n位整數，問題出在22上，因為假如給定的n − 2位整數是以3開首的，那麼在它前面加上22，便會得到不符合規定的n位整數，因此在這裡我們應採用「減」法來作出處理。對於前述那a_n−1個符合規定的n − 1位整數，我們首先剔除那些以3開首的n − 1位整數。這些以3開首的n − 1位整數可以看成是在所有符合規定的n − 2位整數的前面加上3而得來的，因此應共有a_n−2個。剔除了這a_n−2個n − 1位整數後，我們便可以在餘下的a_n−1 − a_n−2個n − 1位整數前面加上2，這樣便可保證所構造出來的n位整數不含「23」這個部分。綜合以上討論，我們應有

至此我們可以寫出本題的「遞歸關係」如下：

現在讓我們用上式求a₄。

例題3：現投擲某硬幣4次，並把4次的投擲結果(「正面」或「反面」，分別用H和T表示)記錄下來，問有多少種不同的投擲組合包含最少兩個「H」？舉例說，H-T-T-H便是一個符合本題規定的投擲組合，而T-T-H-T則不符合本題的規定。

答3：我們用a_n代表符合本題規定的n次投擲組合的數目。根據在進行第n次投擲之前是否已有最少兩個H，可以分為以下兩個情況。

情況1：在進行第n次投擲之前已有最少兩個H。此一情況相當於在進行了n − 1次投擲後，所得投擲組合包含最少兩個H。根據定義，這樣的投擲組合應有a_n−1個。由於在進行第n次投擲之前，我們已有符合規定的投擲組合，所以第n次投擲的結果不論是H還是T，我們最終都將得到符合規定的投擲組合。由於第n次投擲的結果有兩個，因此在此情況下，符合規定的投擲組合共有2a_n−1個。

情況2：在進行第n次投擲之前只有一個H。在此情況下，第n次投擲的結果只能是H，而另一個H則出現於第n次投擲之前，換句話說，另一個H可能出現於第1次投擲、第2次投擲 ... 第n − 1次投擲，即共有n − 1可能。因此在此情況下，符合規定的投擲組合共有n − 1個。

綜合以上討論，我們得到本題的「遞歸關係」：

本題答案就是a₄。現計算如下：

例題4：設有三種顏色(紅、黃、綠，分別用R、Y、G代表)的卡片。現要把4張卡片從左至右排列，使得至少有一張G置於至少一張R的左面(這兩張卡片不一定要緊貼在一起)。舉例說，G-Y-R-R是符合規定的排列法，而R-R-G-Y則不符合規定。問有多少種符合規定的排列法？

答4：我們用a_n代表符合本題規定的n張卡片的排列方案的總數。根據這n張卡片中的最左一張是否為G，可以分為以下兩個情況。

情況1：最左的一張卡片不是G (即為R或Y)。在此情況下，我們必須保證在餘下的n − 1張卡片中，至少有一張G置於至少一張R的左面，即餘下的n − 1張卡片要符合本題規定的排列方案。根據定義，這樣的排列方案應共有a_n−1種。因此在些情況下，符合規定的n張卡片的排列方案共有2a_n−1個。

情況2：最左的一張卡片是G。在此情況下，我們只需保證在餘下的n − 1張卡片中有至少一張R。容易看到，含有至少一張R的排列方案總數等於所有可能的排列方案總數減去不含任何R的排列方案總數。由於共有3種顏色和n − 1張卡片，所有可能的排列方案總數是3ⁿ⁻¹。不含任何R的排列方案總數則等於含有Y、G這兩種顏色的所有可能排列方案的總數，即2ⁿ⁻¹。因此，在此情況下，符合規定的n張卡片的排列方案共有3ⁿ⁻¹ − 2ⁿ⁻¹個。

綜合以上討論，我們得到本題的「遞歸關係」：

本題答案就是a₄。現計算如下：

返回數學專題