卡特蘭數 catalan number

卡特蘭數 catalan number

卡特蘭數前幾項為 : 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, ...

原理

令h(0)=1,h(1)=1，catalan數滿足遞推式[1]：h(n)= h(0)*h(n-1)+h(1)*h(n-2) + ... + h(n-1)h(0) (n>=2) 　　

例如：h(2)=h(0)*h(1)+h(1)*h(0)=1*1+1*1=2 　　h(3)=h(0)*h(2)+h(1)*h(1)+h(2)*h(0)=1*2+1*1+2*1=5 　　

另類遞推式： 　　    h(n)=h(n-1)*(4*n-2)/(n+1); 　　

遞推關系的解為：     h(n)=C(2n,n)/(n+1) (n=0,1,2,3,...) 　　

遞推關系的另類解為： h(n)=C(2n,n)-C(2n,n+1)(n=0,1,2,3,...)

卡特蘭數的應用

應用1描述：n對括号有多少種比對方式？

      思路：n對括号相當于有2n個符号，n個左括号、n個右括号，可以設問題的解為f(2n)。第0個符号肯定為左括号，與之比對的右括号必須為第2i+1字元。因為如果是第2i個字元，那麼第0個字元與第2i個字元間包含奇數個字元，而奇數個字元是無法構成比對的。

      通過簡單分析，f(2n)可以轉化如下的遞推式 f(2n) = f(0)*f(2n-2) + f(2)*f(2n - 4) + ... + f(2n - 4)*f(2) + f(2n-2)*f(0)。簡單解釋一下，f(0) * f(2n-2)表示第0個字元與第1個字元比對，同時剩餘字元分成兩個部分，一部分為0個字元，另一部分為2n-2個字元，然後對這兩部分求解。f(2)*f(2n-4)表示第0個字元與第3個字元比對，同時剩餘字元分成兩個部分，一部分為2個字元，另一部分為2n-4個字元。依次類推。

      假設f(0) = 1，計算一下開始幾項，f(2) = 1, f(4) = 2, f(6) = 5。結合遞歸式，不難發現f(2n) 等于h(n)。

應用2描述：矩陣鍊乘： P=a1×a2×a3×……×an，依據乘法結合律，不改變其順序，隻用括号表示成對的乘積，試問有幾種括号化的方案？

      思路：可以這樣考慮，首先通過括号化，将P分成兩個部分，然後分别對兩個部分進行括号化。比如分成(a1)×(a2×a3.....×an)，然後再對(a1)和(a2×a3.....×an)分别括号化；又如分成(a1×a2)×(a3.....×an)，然後再對(a1×a2)和(a3.....×an)括号化。

      設n個矩陣的括号化方案的種數為f(n)，那麼問題的解為f(n) = f(1)*f(n-1) + f(2)*f(n-2) + f(3)*f(n-3) + f(n-1)*f(1)。f(1)*f(n-1)表示分成(a1)×(a2×a3.....×an)兩部分，然後分别括号化。

      計算開始幾項，f(1) = 1, f(2) = 1, f(3) = 2, f(4) = 5。結合遞歸式，不難發現f(n)等于h(n-1)。

應用3描述：一個棧(無窮大)的進棧序列為1，2，3，…，n，有多少個不同的出棧序列?

      思路：這個與加括号的很相似，進棧操作相當于是左括号，而出棧操作相當于右括号。n個數的進棧次序和出棧次序構成了一個含2n個數字的序列。第0個數字肯定是進棧的數，這個數相應的出棧的數一定是第2i+1個數。因為如果是2i，那麼中間包含了奇數個數，這奇數個肯定無法構成進棧出棧序列。

      設問題的解為f(2n)， 那麼f(2n) = f(0)*f(2n-2) + f(2)*f(2n-4) + f(2n-2)*f(0)。f(0) * f(2n-2)表示第0個數字進棧後立即出棧，此時這個數字的進棧與出棧間包含的數字個數為0，剩餘為2n-2個數。f(2)*f(2n-4)表示第0個數字進棧與出棧間包含了2個數字，相當于1 2 2 1，剩餘為2n-4個數字。依次類推。

應用4描述：n個節點構成的二叉樹，共有多少種情形？

      思路：可以這樣考慮，根肯定會占用一個結點，那麼剩餘的n-1個結點可以有如下的配置設定方式，T(0, n-1),T(1, n-2),...T(n-1, 0)，設T(i, j)表示根的左子樹含i個結點，右子樹含j個結點。

      設問題的解為f(n)，那麼f(n) = f(0)*f(n-1) + f(1)*f(n-2) + .......+ f(n-2)*f(1) + f(n-1)*f(0)。假設f(0) = 1，那麼f(1) = 1, f(2) = 2, f(3) = 5。結合遞推式，不難發現f(n)等于h(n)。

應用5描述：在圓上選擇2n個點，将這些點成對連接配接起來使得所得到的n條線段不相交的方法數？

      思路：以其中一個點為基點，編号為0，然後按順時針方向将其他點依次編号。那麼與編号為0相連點的編号一定是奇數，否則，這兩個編号間含有奇數個點，勢必會有個點被孤立，即在一條線段的兩側分别有一個孤立點，進而導緻兩線段相交。設選中的基點為A，與它連接配接的點為B，那麼A和B将所有點分成兩個部分，一部分位于A、B的左邊，另一部分位于A、B的右邊。然後分别對這兩部分求解即可。

      設問題的解f(n)，那麼f(n) = f(0)*f(n-2) + f(2)*f(n-4) + f(4)*f(n-6) + ......f(n-4)*f(2) + f(n-2)*f(0)。f(0)*f(n-2)表示編号0的點與編号1的點相連，此時位于它們右邊的點的個數為0，而位于它們左邊的點為2n-2。依次類推。f(0) = 1, f(2) = 1, f(4) = 2。結合遞歸式，不難發現f(2n) 等于h(n)。

應用6描述：求一個凸多邊形區域劃分成三角形區域的方法數？

      思路：以凸多邊形的一邊為基，設這條邊的2個頂點為A和B。從剩餘頂點中選1個，可以将凸多邊形分成三個部分，中間是一個三角形，左右兩邊分别是兩個凸多邊形，然後求解左右兩個凸多邊形。

      設問題的解f(n)，其中n表示頂點數，那麼f(n) = f(2)*f(n-1) + f(3)*f(n-2) + ......f(n-2)*f(3) + f(n-1)*f(2)。f(2)*f(n-1)表示三個相鄰的頂點構成一個三角形，那麼另外兩個部分的頂點數分别為2和n-1。

      設f(2) = 1，那麼f(3) = 1, f(4) = 2, f(5) = 5。結合遞推式，不難發現f(n) 等于h(n-2)。

應用7描述：有2n個人排成一行進入劇場。入場費5元。其中隻有n個人有一張5元鈔票，另外n人隻有10元鈔票，劇院無其它鈔票，問有多少中方法使得隻要有10元的人買票，售票處就有5元的鈔票找零？

     思路：可以将持5元買票視為進棧，那麼持10元買票視為5元的出棧。這個問題就轉化成了棧的出棧次序數。由應用三的分析直接得到結果，f(2n) 等于h(n)。

出棧次序

一個棧（無窮大）的進棧序列為1，2，3，…，n，有多少個不同的出棧序列？

正常分析

首先，我們設f(n)=序列個數為n的出棧序列種數。同時，我們假定第一個出棧的序數是k。 　　

第一個出棧的序數k将1~n的序列分成兩個序列，其中一個是1~k-1，序列個數為k-1，另外一個是k+1~n，序列個數是n-k。此時，我們若把k視為确定一個序數，那麼根據乘法原理，f(n)的問題就等價于：序列個數為k-1的出棧序列種數乘以序列個數為n-k的出棧序列種數，即選擇k這個序數的f(n)=f(k-1)×f(n-k)。而k可以選1到n，是以再根據加法原理，将k取不同值的序列種數相加，得到的總序列種數為：f(n)=f(o)f(n-1)+f(1)f(n-2)+……+f(n-1)f(0)。 看到此處，再看看卡特蘭數的遞推式，答案不言而喻，即為f(n)=h(n)= C(2n,n)/(n+1)= C(2n,n)- C(2n,2n-1)（n=1，2，3，……）。

最後，令f(0)=1，f(1)=1。

非正常分析

對于每一個數來說，必須進棧一次、出棧一次。我們把進棧設為狀态1，出棧設為狀态0。n個數的所有狀态對應n個1和n個0組成的2n位二進制數。由于等待入棧的操作數按照1‥n的順序排列，入棧的操作數b大于等于出棧的操作數a(a≤b)，是以輸出序列的總數目=由左而右掃描由n個1和n個0組成的2n位二進制數，1的累計數不小于0的累計數的方案種數。

在2n位二進制數中填入n個1的方案數為c(2n,n)，不填1的其餘n位自動填0。從中減去不符合要求（由左而右掃描，0的累計數大于1的累計數）的方案數即為所求。

不符合要求的數的特征是由左而右掃描時，必然在某一奇數位2m+1位上首先出現m+1個0的累計數和m個1的累計數，此後的2(n-m)-1位上有n-m個 1和n-m-1個0。如若把後面這2(n-m)-1位上的0和1互換，使之成為n-m個0和n-m-1個1，結果得1個由n+1個0和n-1個1組成的2n位數，即一個不合要求的數對應于一個由n+1個0和n-1個1組成的排列。反過來，任何一個由n+1個0和n-1個1組成的2n位二進制數，由于0的個數多2個，2n為偶數，故必在某一個奇數位上出現0的累計數超過1的累計數。同樣在後面部分0和1互換，使之成為由n個0和n個1組成的2n位數，即n+1個0和n-1個1組成的2n位數必對應一個不符合要求的數。

因而不合要求的2n位數與n+1個0，n－1個1組成的排列一一對應。顯然，不符合要求的方案數為c(2n,n+1)。由此得出輸出序列的總數目=c(2n,n)-c(2n,n+1)=c(2n,n)/(n+1)=h(n)。

凸多邊形三角劃分

在一個凸多邊形中，通過若幹條互不相交的對角線，把這個多邊形劃分成了若幹個三角形。現在的任務是鍵盤上輸入凸多邊形的邊數n，求不同劃分的方案數f（n）。比如當n=6時，f（6）=14。

分析 　　

如果純粹從f（4）=2，f（5）=5，f（6）=14，……，f（n）=n慢慢去歸納，恐怕很難找到問題的遞推式，我們必須從一般情況出發去找規律。 　　

因為凸多邊形的任意一條邊必定屬于某一個三角形，是以我們以某一條邊為基準，以這條邊的兩個頂點為起點P1和終點Pn（P即Point），将該凸多邊形的頂點依序标記為P1、P2、……、Pn，再在該凸多邊形中找任意一個不屬于這兩個點的頂點Pk（2<=k<=n-1），來構成一個三角形，用這個三角形把一個凸多邊形劃分成兩個凸多邊形，其中一個凸多邊形，是由P1，P2，……，Pk構成的凸k邊形（頂點數即是邊數），另一個凸多邊形，是由Pk，Pk+1，……，Pn構成的凸n-k+1邊形。 　　

此時，我們若把Pk視為确定一點，那麼根據乘法原理，f（n）的問題就等價于：凸k多邊形的劃分方案數乘以凸n-k+1多邊形的劃分方案數，即選擇Pk這個頂點的f（n）=f（k）×f（n-k+1）。而k可以選2到n-1，是以再根據加法原理，将k取不同值的劃分方案相加，得到的總方案數為：f（n）=f（2）f（n-2+1）+f（3）f（n-3+1）+……+f（n-1）f（2）。看到此處，再看看卡特蘭數的遞推式，答案不言而喻，即為f（n）=h（n-2） （n=3，4，……）。

最後，令f（2）=1，f（3）=1。此處f（2）=1和f（3）=1的具體緣由須參考詳盡的“卡特蘭數”，也許可從凸四邊形f（4）=f（2）f（3）+ f（3）f（2）=2×f（2）f（3）倒推，四邊形的劃分方案不用規律推導都可以知道是2，那麼2×f（2）f（3）=2，則f（2）f（3）=1，又f（2）和f（3）若存在的話一定是整數，則f（2）=1，f（3）=1。（因為沒研究過卡特蘭數的由來，此處僅作臆測）。 　

<a href="http://blog.csdn.net/wuzhekai1985/article/details/6764858">http://blog.csdn.net/wuzhekai1985/article/details/6764858</a>

<a href="http://baike.baidu.com/view/2499752.htm">http://baike.baidu.com/view/2499752.htm</a>

<a href="http://en.wikipedia.org/wiki/Catalan_number">http://en.wikipedia.org/wiki/Catalan_number</a>

    本文轉自阿凡盧部落格園部落格，原文連結：http://www.cnblogs.com/luxiaoxun/archive/2012/10/01/2709720.html，如需轉載請自行聯系原作者