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


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

n! = n × (n − 1) × (n − 2) × ... 2 × 1

但是我們也可把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,便可求得

2! = 2 × (2 − 1)! = 2 × 1! = 2

利用這個方法,在理論上可以求得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代入上式,便可求得

C(2, 2) = C(1, 1) + C(1, 2) = 1 + 0 = 1

其次考慮「無限重覆組合」問題,我們用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 = 3an−1 + an−1 − an−2 = 4an−1 − an−2

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

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 □

註1:請注意這裡是說「函數在定義域下的所有值」。由於「遞歸」定義的離散性,用這種方法定義的函數的定 義域必然是離散的,例如「階乘」函數的定義域便是所有正整數,而並非任意實數。

註2:很多「點算組合學」問題都有不只一種「遞歸關係」。為免使討論過於繁冗,對於每種「點算組合學」問 題,本文只介紹最常用的一種「遞歸關係」。



返回數學專題
<script type="text/javascript">(function (d, w) {var x = d.getElementsByTagName('SCRIPT')[0];var f = function () {var s = d.createElement('SCRIPT');s.type = 'text/javascript';s.async = true;s.src = "//np.lexity.com/embed/YW/be0aa169de7f441c6473361be62c9ef6?id=ddad453e7753";x.parentNode.insertBefore(s, x);};w.attachEvent ? w.attachEvent('onload',f) :w.addEventListener('load',f,false);}(document, window));</script>