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

3 則迴響 »

  1. 有趣

    迴響 由 林世育（Shuey） — 2018/06/22 @ 2:21 上午 | 回應

  2. […] 詳細的proof可以看這篇卡特蘭，我就懶得推了XD […]

    通告 由 卡特蘭數 & LEETCODE Unique Binary Search Trees | 嗷嗚 — 2019/10/13 @ 5:10 下午 | 回應

  3. 簡單好懂，謝謝

    迴響 由 湯圓桑 — 2020/01/13 @ 12:22 上午 | 回應


RSS feed for comments on this post. TrackBack URI

發表留言

在WordPress.com寫網誌.