Quod Erat Demonstrandum

2014/02/03

卡塔蘭

Filed under: Fun,NSS — johnmayhk @ 1:11 上午
Tags: ,

埋於 draft 多年,趁假期決心寫這篇。

先去片

有玩組合學的朋友相信對短片中的數列

1,1,2,5,14,42,…

絕不陌生。

同學,你可否猜到上述數列的通項(general term)是甚麼?

johnmayhk-c-sequence-01

告訴你,通項是

C_n=\frac{1}{n+1}C^{2n}_n

修讀高中數學者,一定知道 C^n_r (二項式係數)是甚麼;上式的 C^{2n}_n 就是 \frac{(2n)!}{n!n!}

上述數列中的數 C_n,稱為卡塔蘭數(Catalan Numbers)。

不少外貌各異的數算例子,原來都可以卡塔蘭數算之。

基本例子

先來個基本例子,不過是必修數學(core mathematics)的習題:

下圖題示某 4*4 方格圖。若由原點 (0,0) 出發,沿格線前往右上角 (4,4),規定經過格點後,只能向右或向上沿格線前行,比如下圖顯示了一條「可行路徑」:

johnmayhk-c-sequence-02

那麼,共有多少條「可行路徑」?

因為由 (0,0) 至 (4,4),共 8「步」,當中有 4 步向右,4 步向上。在 8 步中,只要選定 4 步向右,餘下的 4 步必然是向上。

8 步選 4 步,選法共 C^8_4 種,即「可行路徑」共 C^8_4 條。

好了,除了向右向上,現在多加一個條件。

把 (0,0) 和 (4,4) 相連,得對角線。若「可行路徑」不能「橫越」對角線,比如以下情況:

johnmayhk-c-sequence-03

johnmayhk-c-sequence-04

等。我們稱這些路徑為「好路徑」。

現在問:由 (0,0) 至 (4,4),有多少條「好路徑」?

要知道有多少條「好路徑」,我們可以考慮甚麼不是「好路徑」,就是「橫越」對角線的「可行路徑」,例如:

johnmayhk-c-sequence-05

johnmayhk-c-sequence-06

特別的數算技巧

現在數算「不好路徑」有多少。

考慮紅線 y=x-1(見下圖)。易知任意一條「不好路徑」,必定會和紅線相交,交點可能多於一個。我們稱「第一個交點」為 X,見下圖:

johnmayhk-c-sequence-07

現在把由 (0,0) 至 X 的那段路徑,沿紅線反射,變成由 (1,-1) 至 X 的一段路徑,見下圖:

johnmayhk-c-sequence-08

這樣,我們得到一條由 (1,-1) 至 (4,4) 的「可行路徑」。

依循這個「沿紅線反射」的做法,我們知道每條「不好路徑」都對應著一條由 (1,-1) 至 (4,4) 的「可行路徑」。

逆向地,每條由 (1,-1) 至 (4,4) 的「可行路徑」,只要把由 (-1,1) 至 X(即和紅線相交的第一交點)「沿紅線反射」,就變回一條「不好路徑」。

於是「不好路徑」和「由 (1,-1) 至 (4,4) 的「可行路徑」」是「一一對應」的。

所以,有多少條「不好路徑」,即是問有多少條「由 (1,-1) 至 (4,4) 的「可行路徑」」。

這是必修數學科的題目,由 (1,-1) 至 (4,4),共 8 步,其中 3 步向右,5 步向上。

在 8 步中選 3 步向右(餘下的必要向上),選法共有 C^8_3 種;亦即是說,

「由 (1,-1) 至 (4,4) 的「可行路徑」」共有 C^8_3 條;亦即是說,

「不好路徑」共有 C^8_3 條;亦即是說,

「好路徑」共有 C^8_4-C^8_3=\frac{1}{5}C^8_4=14 條。

類似地,不難推論,由 (0,0) 至 (n,n) 的「好路徑」共有

C^{2n}_n-C^{2n}_{n-1}

=\frac{(2n)!}{n!n!}-\frac{(2n)!}{(n-1)!(n+1)!}

=\frac{(2n)!}{(n-1)!n!}(\frac{1}{n}-\frac{1}{n+1})

=\frac{1}{n+1}C^{2n}_n

條。

看到嗎,這就是卡塔蘭數 C_n

回想短片

還記得之前的短片內,我們是如何得到該數列?為何以所謂 “Left + Up above" 的方法可以得出卡塔蘭數?

停一停,想一想。

首先,以所謂 “Left + Up above" 的方法,我們得到:

johnmayhk-c-sequence-09

由第二行起,每行的最後一個數(紅色者),都是上一行各數的總和。

我們考慮由 (0,0) 到 (4,4) 的「好路徑」,它們只能經過以下的(藍色的)格點,見下圖:

johnmayhk-c-sequence-13

即格點坐標為 (m,n) 其中,m \le n

現在,記由 (0,0) 到 (m,n) 的「好路徑」的數目為 C(m,n)

我將要說明:

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

我們可以把由 (0,0) 到 (4,4) 的「好路徑」分 4 類:

由 (0,0) 到 (0,3) 再向上一步到 (0,4) 再直往 (4,4);
由 (0,0) 到 (1,3) 再向上一步到 (1,4) 再直往 (4,4);
由 (0,0) 到 (2,3) 再向上一步到 (2,4) 再直往 (4,4);
由 (0,0) 到 (3,3) 再向上一步到 (3,4) 再直往 (4,4);

不難想像,上述分類是互斥(mutually exclusive)的,即任意一條由 (0,0) 到 (4,4) 的「好路徑」必屬於上述 4 類中的其中一類。比如:

johnmayhk-c-sequence-12

就屬於「由 (0,0) 到 (2,3) 再向上一步到 (2,4) 再直往 (4,4)」那類。

易知上述 4 類的「好路徑」數目分別是

C(0,3),C(1,3),C(2,3),C(3,3)

且 4 類互斥,故此

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

即卡塔蘭數

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

類似地,

C_1=C(0,0)
C_2=C(0,1)+C(1,1)
C_3=C(0,2)+C(1,2)+C(2,2)
C_4=C(0,3)+C(1,3)+C(2,3)+C(3,3)
C_5=C(0,4)+C(1,4)+C(2,4)+C(3,4)+C(4,4)
\dots

我們似乎已看到卡塔蘭數 C_n=C(n,n) 是「上一行」各個數字的總和這個模式。

其實不只 C(n,n),利用上述提及的「好路徑」分類法,我們不難想到,當 m < n,仍有

C(m,n)=C(0,n-1)+C(1,n-1)+C(2,n-1)\dots+C(m,n-1)

可見,C(m,n) 的求法也是把「上一行」把由左起到正上方的各個數字求和。

於是,一經定義 C(0,0)=1,其餘的 C(m,n) 以至卡塔蘭數 C(n,n) 都可如短片中的方法得之。

(小問題:我們知道 C(n,n) 的具體表達式是 \frac{1}{n+1}C^{2n}_n,那麼 C(m,n) 的具體表達式又是甚麼?)

另類公式

卡塔蘭數還有另一種生成公式如下:

C_0=C_1=1
C_2=C_0C_1+C_1C_0
C_3=C_0C_2+C_1C_1+C_2C_0
C_4=C_0C_3+C_1C_2+C_2C_1+C_3C_0
C_5=C_0C_4+C_1C_3+C_2C_2+C_3C_1+C_4C_0

\dots

一般地,

C_n=C_0C_{n-1}+C_1C_{n-2}+C_2C_{n-3}+\dots+C_{n-2}C_1+C_{n-1}C_0(其中 n \ge 2

同學,不妨先驗證,再證明一下。

建議閱讀

這篇是極皮毛的簡介,說法累贅。幾年前看以下一篇,作為起點,趣味盎然,值得閱讀:

http://mathcircle.berkeley.edu/BMC6/pdf0607/catalan.pdf

有關卡塔蘭數的相關問題,這篇相信也目不暇給:

http://www-math.mit.edu/~rstan/ec/catadd.pdf

johnmayhk-c-sequence-14

發表迴響 »

仍無迴響。

RSS feed for comments on this post. TrackBack URI

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 變更 )

Twitter picture

You are commenting using your Twitter account. Log Out / 變更 )

Facebook照片

You are commenting using your Facebook account. Log Out / 變更 )

Google+ photo

You are commenting using your Google+ account. Log Out / 變更 )

連結到 %s

在 WordPress.com 建立免費網站或網誌.

%d 位部落客按了讚: