「遞歸關係」(Recurrence Relation,亦譯作「遞推關係」或「遞迴關係」)是除了「容斥原理」、「母函數」和「伯恩賽德-波利亞定理」以外,另一求解「點算組合學」問題的重要工具。在數學上,「遞歸關係」可用來定義某些函數,最常見的例子就是「階乘」(Factorial)的定義。在《點算的奧秘:排列和組合基本公式》中,筆者把「n階乘」(n!)定義為
但是我們也可把n!定義為
n! = n × (n − 1)! | ,若n > 1 |
1! = 1 |   |
以上就是n!的「遞歸」(Recursive)定義。請注意這個定義由兩部分組成,第一部分是「遞歸」部分,包含一個「遞歸關係」。所謂「遞歸關係」,是指在定義某函數時,該函數本身被應用於自己的定義中。當然為免出現循環定義的問題,該函數在「定義項」和「被定義項」中應分別以不同的值為輸入值。例如在上述定義中,「被定義項」n!以n為輸入值,而「定義項」中的(n − 1)!則以n − 1為輸入值。上述定義中的第二部分是「基礎」(Base)部分,它通常規定函數的某個或某些初值(Initial Value)。利用「遞歸」定義的兩個部分,我們便可以求得函數在「定義域」(Domain)下的所有值(註1)。例如把n = 2代入上面的「遞歸關係」,並利用1! = 1,便可求得
利用這個方法,在理論上可以求得n為任意正整數時,n!的值。
在「點算組合學」上,「遞歸關係」可用來表達某些點算問題。以下筆者將回顧以往介紹過的某些「點算組合學」問題,並把它們表述為「遞歸關係」。首先看「不可重覆的組合」問題。在《點算的奧秘:二項式定理和多項式定理》,筆者推導了「二項式系數」的「遞歸關係」,現複述如下(並補上「基礎」部分)(註2):
C(n, r) = C(n − 1, r − 1) + C(n − 1, r) | ,若n > 0,r > 0,n ≥ r |     (1) |
C(n, r) = 0 | ,若n < r | |
C(n, 0) = 1 | ,對任何非負整數n而言 |
我們可以從兩個角度解釋上式中的「基礎」部分,即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 + 1, 1) | = C(n, 0) + C(n, 1),即 |
n + 1 | = C(n, 0) + n |
C(n, 0) | = 1 |
上述兩種方法(「直接法」和「反推法」)都是求「遞歸關係」的「基礎」部分的有效方法。不過,由於「直接法」涉及點算問題在某些「極端」情況時的值,這需依賴我們的直觀,而直觀有時是不準確的,因此我們最還是用「反推法」驗證一下,看看用這兩種方法求得的值是否一致。如果兩者不一致,那麼應以「反推法」所求的值為準。在以下的討論中,筆者一般不會詳細解釋各個「遞歸關係」的「基礎」部分的理據,讀者可自行用「直接法」或「反推法」證實各「基礎」部分的合理性。
由於「二項式系數」就是「不可重覆的組合」問題的計算公式,所以上式也就是這類問題的「遞歸關係」。請注意C(n, r)含有兩個變項,因此上式是一個「二元遞歸關係」,其「基礎」部分也較為複雜。舉例說,把n = 2,r = 2代入上式,便可求得
其次考慮「無限重覆組合」問題,我們用E(n, r)代表這類問題的答案。根據《點算的奧秘:無限重覆的排列組合問題》,E(n, r) = C(n + r − 1, r)。利用此一關係以及公式(1),可以求得
E(n, r) = C(n + r − 1, r) | = C(n + r − 2, r − 1) + C(n + r − 2, r) |
  | = E(n, r − 1) + E(n − 1, r) |
由此得到E(n, r)的「遞歸關係」如下:
E(n, r) = E(n, r − 1) + E(n − 1, r) | ,若n > 0,r > 0 |     (2) |
E(0, r) = 0 | ,對任何正整數r而言 | |
E(n, 0) = 1 | ,對任何非負整數n而言 |
接著考慮「不可重覆的排列」問題,即P(n, r)。根據《點算的奧秘:排列和組合基本公式》,P(n, r) = n! / (n − r)!。利用此一關係以及「階乘」的「遞歸關係」,可以求得
  | n! |   | n(n − 1)! | |||
P(n, r) = | ----------- | = | ------------------------ | |||
  | (n − r)! |   | (n − r)(n − r − 1)! | |||
  |   |   | (n − r + r)(n − 1)! | |||
  |   | = | ----------------------------- | |||
  |   |   | (n − r)(n − r − 1)! | |||
  |   |   | (n − r)(n − 1)! |   | r(n − 1)! | |
  |   | = | ------------------------ | + | ------------------------ | |
  |   |   | (n − r)(n − r − 1)! |   | (n − r)(n − r − 1)! | |
  |   |   | (n − 1)! |   | r(n − 1)! | |
  |   | = | -------------------- | + | -------------------- | |
  |   |   | (n − r − 1)! |   | (n − r)! | |
  |   | = | P(n − 1, r) + rP(n − 1, r − 1) |
由此得到P(n, r)的「遞歸關係」如下:
P(n, r) = P(n − 1, r) + rP(n − 1, r − 1) | ,若n > 0,r > 0,n ≥ r |     (3) |
P(n, r) = 0 | ,若n < r | |
P(n, 0) = 1 | ,對任何非負整數n而言 |
接著考慮「無限重覆排列」問題,我們用U(n, r)代表這類問題的答案。根據《點算的奧秘:無限重覆的排列組合問題》,U(n, r) = nr。由於此一問題簡單直觀,無需借助「遞歸關係」也容易求得答案。不過如果硬要寫出U(n, r)的「遞歸關係」,我們也可以利用關係式nr = n(nr − 1),得出以下「遞歸關係」:
U(n, r) = nU(n, r − 1) | ,若r > 0 |     (4) |
U(n, 0) = 1 | ,對任何非負整數n而言 |
請注意雖然U(n, r)含有兩個變項,但在上式中n的值是固定的,所以上式實際是一個「一元遞歸關係」。
接著考慮「不容許空集的集合劃分」問題,我們用P1(r, n)代表這類問題的答案,也就是「點算組合學」上所稱的「第二類斯特林數」。具體地說,P1(r, n)代表把r個元素劃歸n個非空子集的「劃分」方案總數。我們可以循以下思路推導這類問題的「遞歸關係」。我們任意選取其中一個元素(姑名之為a)。根據a是否被單獨劃歸其中一個子集,可以分為兩種情況。
在第一種情況下,a被單獨劃歸其中一個子集,即a所在的子集沒有其他元素,這樣我們尚要把r − 1個元素劃歸餘下的n − 1個子集。根據P1的定義,這應共有P1(r − 1, n − 1)種「劃分」法。在第二種情況下,a所在的子集尚有其他元素。我們暫不考慮a,首先把r − 1個元素劃歸n個子集,這應共有P1(r − 1, n)種「劃分」法。接著我們把a劃歸這n個子集中的一個,這有n種選擇,所以在第二種情況下,共有n × P1(r − 1, n)種「劃分」法。結合以上兩種情況,我們得到以下「遞歸關係」:
P1(r, n) = P1(r − 1, n − 1) + nP1(r − 1, n) | ,若r > 0,n > 0,r ≥ n |     (5) |
P1(r, n) = 0 | ,若r < n | |
P1(0, 0) = 1 |   | |
P1(r, 0) = 0 | ,對任何正整數r而言 |
接著考慮含有《點算的奧秘:費雷爾斯圖》所稱的「第(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)種「分割」方案。結合以上兩種情況,我們得到以下「遞歸關係」:
p(r, n) = p(r − 1, n − 1) + p(r − n, n) | ,若r > 0,n > 0,r ≥ n |     (6) |
p(r, n) = 0 | ,若r < n | |
p(0, 0) = 1 |   | |
p(r, 0) = 0 | ,對任何正整數r而言 |
以上筆者介紹了四大「點算組合學」問題所滿足的「遞歸關係」。除了以上這些問題外,還有其他某些點算問題也可表述為「遞歸關係」。這些問題的特點是,如要直接求解,將頗為複雜。但如果把它們表述為「遞歸關係」,則使問題變得很容易。以下筆者用幾個例題展示以「遞歸關係」表述這些問題的方法。在以下例題中,所有「遞歸關係」都是一元函數的「遞歸關係」,而且這些函數都以非負整數集作為其「定義域」。由於以非負整數集作為「定義域」的函數等同於一個「序列」(Sequence),以下筆者把這些「遞歸關係」的值表達為「序列」,以a0、a1 ... 表示。
例題1:用1、2、3、4這四個數字可以構造出多少個4位正整數,使得這些整數不含「22」這個部分?舉例說,3421便是符合本題規定的5位整數,而3221則不符合本題的規定,因為它含有「22」這個部分。
答1:我們用an代表符合本題規定的n位整數的數目,我們循以下思路推導an所滿足的「遞歸關係」。我們看如何構造出符合本題規定的n位整數。假設我們已有an−1個符合規定的n − 1位整數,那麼這些n − 1位整數都不含「22」這個部分,在這些n − 1位整數前加上1、3或4,便可構造出3an−1個n位整數,而且這些n位整數都必然不含「22」這個部分。舉例說,設有符合規定的3位整數421,在它前面加上3,便可得到符合規定的4位整數3421。至此我們找到了構造以1、3或4開首且符合規定的n位整數的方法,如何構造以2開首的n位整數呢?假設我們已有an−2個符合規定的n − 2位整數,那麼只要在這些n − 2位整數前加上21、23或24,便可構造出3an−2個符合規定的n位整數。舉例說,設有符合規定的2位整數21,在它前面加上21,便可得到符合規定的4位整數2121。綜合以上討論,我們找到an的「遞歸關係」為
an = 3an−1 + 3an−2 | ,若n > 0 |
a0 = 1,a1 = 4 |   |
本題答案就是a4的值。利用以上「遞歸關係」,容易求得這個值。計算如下:
a2 = 3a1 + 3a0 = 3 × 4 + 3 × 1 = 15 |
a3 = 3a2 + 3a1 = 3 × 15 + 3 × 4 = 57 |
a4 = 3a3 + 3a2 = 3 × 57 + 3 × 15 = 216 □ |
例題2:用1、2、3、4這四個數字可以構造出多少個4位正整數,使得這些整數不含「23」這個部分?
答2:本題在表面上跟上題非常相似,但其實在某一方面跟上題有很不同之處。雖然給定an−1個符合規定的n − 1位整數,我們可以透過在它們前面加上1、3或4來構造3an−1個符合規定的n位整數;可是,給定an−2個符合規定的n − 2位整數,我們卻不可以透過在它們前面加上21、22或24來構造n位整數,問題出在22上,因為假如給定的n − 2位整數是以3開首的,那麼在它前面加上22,便會得到不符合規定的n位整數,因此在這裡我們應採用「減」法來作出處理。對於前述那an−1個符合規定的n − 1位整數,我們首先剔除那些以3開首的n − 1位整數。這些以3開首的n − 1位整數可以看成是在所有符合規定的n − 2位整數的前面加上3而得來的,因此應共有an−2個。剔除了這an−2個n − 1位整數後,我們便可以在餘下的an−1 − an−2個n − 1位整數前面加上2,這樣便可保證所構造出來的n位整數不含「23」這個部分。綜合以上討論,我們應有
至此我們可以寫出本題的「遞歸關係」如下:
an = 4an−1 − an−2 | ,若n > 0 |
a0 = 1,a1 = 4 |   |
現在讓我們用上式求a4。
a2 = 4a1 − a0 = 4 × 4 − 1 = 15 |
a3 = 4a2 − a1 = 4 × 15 − 4 = 56 |
a4 = 4a3 − a2 = 4 × 56 − 15 = 209 □ |
例題3:現投擲某硬幣4次,並把4次的投擲結果(「正面」或「反面」,分別用H和T表示)記錄下來,問有多少種不同的投擲組合包含最少兩個「H」?舉例說,H-T-T-H便是一個符合本題規定的投擲組合,而T-T-H-T則不符合本題的規定。
答3:我們用an代表符合本題規定的n次投擲組合的數目。根據在進行第n次投擲之前是否已有最少兩個H,可以分為以下兩個情況。
情況1:在進行第n次投擲之前已有最少兩個H。此一情況相當於在進行了n − 1次投擲後,所得投擲組合包含最少兩個H。根據定義,這樣的投擲組合應有an−1個。由於在進行第n次投擲之前,我們已有符合規定的投擲組合,所以第n次投擲的結果不論是H還是T,我們最終都將得到符合規定的投擲組合。由於第n次投擲的結果有兩個,因此在此情況下,符合規定的投擲組合共有2an−1個。
情況2:在進行第n次投擲之前只有一個H。在此情況下,第n次投擲的結果只能是H,而另一個H則出現於第n次投擲之前,換句話說,另一個H可能出現於第1次投擲、第2次投擲 ... 第n − 1次投擲,即共有n − 1可能。因此在此情況下,符合規定的投擲組合共有n − 1個。
綜合以上討論,我們得到本題的「遞歸關係」:
an = 2an−1 + n − 1 | ,若n > 1 |
a1 = 0 |   |
本題答案就是a4。現計算如下:
a2 = 2a1 + 2 − 1 = 2 × 0 + 1 = 1 |
a3 = 2a2 + 3 − 1 = 2 × 1 + 2 = 4 |
a4 = 2a3 + 4 − 1 = 2 × 4 + 3 = 11 □ |
例題4:設有三種顏色(紅、黃、綠,分別用R、Y、G代表)的卡片。現要把4張卡片從左至右排列,使得至少有一張G置於至少一張R的左面(這兩張卡片不一定要緊貼在一起)。舉例說,G-Y-R-R是符合規定的排列法,而R-R-G-Y則不符合規定。問有多少種符合規定的排列法?
答4:我們用an代表符合本題規定的n張卡片的排列方案的總數。根據這n張卡片中的最左一張是否為G,可以分為以下兩個情況。
情況1:最左的一張卡片不是G (即為R或Y)。在此情況下,我們必須保證在餘下的n − 1張卡片中,至少有一張G置於至少一張R的左面,即餘下的n − 1張卡片要符合本題規定的排列方案。根據定義,這樣的排列方案應共有an−1種。因此在些情況下,符合規定的n張卡片的排列方案共有2an−1個。
情況2:最左的一張卡片是G。在此情況下,我們只需保證在餘下的n − 1張卡片中有至少一張R。容易看到,含有至少一張R的排列方案總數等於所有可能的排列方案總數減去不含任何R的排列方案總數。由於共有3種顏色和n − 1張卡片,所有可能的排列方案總數是3n−1。不含任何R的排列方案總數則等於含有Y、G這兩種顏色的所有可能排列方案的總數,即2n−1。因此,在此情況下,符合規定的n張卡片的排列方案共有3n−1 − 2n−1個。
綜合以上討論,我們得到本題的「遞歸關係」:
an = 2an−1 + 3n−1 − 2n−1 | ,若n > 1 |
a1 = 0 |   |
本題答案就是a4。現計算如下:
a2 = 2a1 + 31 − 21= 2 × 0 + 3 − 2 = 1 |
a3 = 2a2 + 32 − 22= 2 × 1 + 9 − 4 = 7 |
a4 = 2a3 + 33 − 23= 2 × 7 + 27 − 8 = 33 □ |