卡特蘭數

卡特蘭數

卡特蘭數又稱卡塔蘭數,卡特蘭數是組合數學中一個常出現在各種計數問題中的數列。以比利時的數學家歐仁·查理·卡塔蘭 (1814–1894)的名字來命名

基本介紹

  • 中文名:卡特蘭數
  • 外文名:Catalan number
  • 又稱:卡塔蘭數
  • 解釋:出現在各種計數問題中出現的數列
  • 命名人:歐仁·查理·卡塔蘭
簡介,歷史,原理,套用,擴展,Java套用,C++套用,

簡介

卡特蘭數又稱卡塔蘭數,英文名Catalan number,是組合數學中一個常出現在各種計數問題中出現的數列。以比利時的數學家歐仁·查理·卡塔蘭 (1814–1894)的名字來命名,其前幾項為(從第零項開始) : 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, ...
卡特蘭數Cn滿足以下遞推關係:

歷史

·1758年,Johann Segner 給出了歐拉問題的遞推關係;
·1838年,研究熱潮:
–GabrielLame給出完整證明和簡潔表達式;
–EugèneCharlesCatalan在研究漢諾塔時探討了相關問題,解決了括弧表達式的問題。
–……
–1900年,EugenNetto在著作中將該數歸功於Catalan。
·1988年以及1999年的文獻研究表明實際上最初發現Catalan數的也不是Euler。
–1753歐拉在解決凸包劃分成三角形問題的時候,推出了Catalan數。
–1730年我國清朝時期的明安圖(蒙古人)比Catalan更早使用了Catalan數,見《割圜密率捷法》。後來他的學生在1774年將其完成發表。
最後由比利時的數學家歐仁·查理·卡塔蘭(1814–1894)命名。

原理

設h(n)為catalan數的第n+1項,令h(0)=1,h(1)=1,catalan數滿足遞推式:
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,...)
遞推關係的另類解為:
h(n)=c(2n,n)-c(2n,n-1)(n=0,1,2,...)

套用

實質上都是遞推等式的套用
括弧化
矩陣連乘: P=a1×a2×a3×……×an,依據乘法結合律,不改變其順序,只用括弧表示成對的乘積,試問有幾種括弧化的方案?(h(n)種)
出棧次序
一個棧(無窮大)的進棧序列為1,2,3,…,n,有多少個不同的出棧序列?
卡特蘭數
常規分析
首先,我們設f(n)=序列個數為n的出棧序列種數。(我們假定,最後出棧的元素為k,顯然,k取不同值時的情況是相互獨立的,也就是求出每種k最後出棧的情況數後可用加法原則,由於k最後出棧,因此,在k入棧之前,比k小的值均出棧,此處情況有f(k-1)種,而之後比k大的值入棧,且都在k之前出棧,因此有f(n-k)種方式,由於比k小和比k大的值入棧出棧情況是相互獨立的,此處可用乘法原則,f(n-k)*f(k-1)種,求和便是Catalan遞歸式。ps.author.陶百百)
首次出空之前第一個出棧的序數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(0)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,n-1)(n=0,1,2,……)。
最後,令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)。
類似問題 買票找零
有2n個人排成一行進入劇場。入場費5元。其中只有n個人有一張5元鈔票,另外n人只有10元鈔票,劇院無其它鈔票,問有多少種方法使得只要有10元的人買票,售票處就有5元的鈔票找零?(將持5元者到達視作將5元入棧,持10元者到達視作使棧中某5元出棧)
凸多邊形三角劃分
在一個凸多邊形中,通過若干條互不相交的對角線,把這個多邊形劃分成了若干個三角形。任務是鍵盤上輸入凸多邊形的邊數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=2,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。(因為我沒研究過卡特蘭數的由來,此處僅作劉摶羽的臆測)。
類似問題
一位大城市的律師在她住所以北n個街區和以東n個街區處工作。每天她走2n個街區去上班。如果她從不穿越(但可以碰到)從家到辦公室的對角線,那么有多少條可能的道路?
圓上選擇2n個點,將這些點成對連線起來使得所得到的n條線段不相交的方法數?
給定節點組成二叉搜尋樹
給定N個節點,能構成多少種不同的二叉搜尋樹
(能構成h(N)個)
(這個公式的下標是從h(0)=1開始的)
n對括弧正確匹配數目
給定n對括弧,求括弧正確配對的字元串數,例如:
0對括弧:[空序列] 1種可能
1對括弧:() 1種可能
2對括弧:()() (()) 2種可能
3對括弧:((())) ()(()) ()()() (())() (()()) 5種可能
那么問題來了,n對括弧有多少種正確配對的可能呢?
考慮n對括弧時的任意一種配對方案,最後一個右括弧有唯一的與之匹配的左括弧,於是有唯一的表示A(B),其中A和B也是合法的括弧匹配序列
假設S(n)為n對括弧的正確配對數目,那么有遞推關係S(n)=S(0)S(n-1)+S(1)S(n-2) +...+S(n-1)S(0),顯然S(n)是卡特蘭數。

擴展

對於在n位的2進制中,有m個0,其餘為1的catalan數為:C(n,m)-C(n,m-1)。證明可以參考標準catalan數的證明。
問題1的描述:有n個1和m個-1(n>m),共n+m個數排成一列,滿足對所有0<=k<=n+m的前k個數的部分和Sk > 0的排列數。 問題等價為在一個格點陣列中,從(0,0)點走到(n,m)點且不經過對角線x==y的方法數(x > y)。
考慮情況I:第一步走到(0,1),這樣從(0,1)走到(n,m)無論如何也要經過x==y的點,這樣的方法數為(( n+m-1,m-1 ));
考慮情況II:第一步走到(1,0),又有兩種可能:
a . 不經過x==y的點;(所要求的情況)
b . 經過x==y的點,我們構造情況II.b和情況I的一一映射,說明II.b和I的方法數是一樣的。設第一次經過x==y的點是(x1,y1),將(0,0)到(x1,y1)的路徑沿對角線翻折,於是唯一對應情況I的一種路徑;對於情況I的一條路徑,假設其與對角線的第一個焦點是(x2,y2),將(0,0)和(x2,y2)之間的路徑沿對角線翻折,唯一對應情況II.b的一條路徑。
問題的解就是總的路徑數 ((n+m, m)) - 情況I的路徑數 - 情況II.b的路徑數。
((n+m , m)) - 2*((n+m-1, m-1))
或:((n+m-1 , m)) - ((n+m-1 , m-1))
問題2的描述:有n個1和m個-1(n>=m),共n+m個數排成一列,滿足對所有0<=k<=n+m的前k個數的部分和Sk >= 0的排列數。(和問題1不同之處在於此處部分和可以為0,這也是更常見的情況) 問題等價為在一個格點陣列中,從(0,0)點走到(n,m)點且不穿過對角線x==y的方法數(可以走到x==y的點)。
把(n,m)點變換到(n+1,m)點,問題變成了問題1。
方法數為:
((n+m+1, m)) - 2*((n+m+1-1, m-1))
或:((n+m+1-1, m)) - ((n+m+1-1, m-1))

Java套用

import java.util.*; import java.math.BigInteger;  public class Catalan {  //求卡特蘭數    public static void main(String[] args){          int numberOfCatalan = 101; //要求多少個卡特蘭數       BigInteger[] digis = new BigInteger[numberOfCatalan];        digis = generateCatalan(numberOfCatalan);                Scanner scanner = new Scanner(System.in);                int number;        while(true) {              number = scanner.nextInt();              if(number == -1)                  break;              String answer = digis[number].toString();              System.out.println(answer);          }      }          static BigInteger[] generateCatalan(int numberOfCatalan) {   //產生卡特蘭數    BigInteger digis[] = new BigInteger[numberOfCatalan + 1];          BigInteger x = new BigInteger("1"); //第一個卡特蘭數為1        digis[1] = x;          int y = 0;        int z = 0;                  for(int counter = 2; counter <= numberOfCatalan; ++ counter) {              y = 4 * counter - 2;              z = counter + 1;              digis[counter] = digis[counter-1].multiply(new BigInteger("" + y));              digis[counter] = digis[counter].divide(new BigInteger("" + z));          }        return digis;    }}  使用遞歸的方式解決卡特蘭數public static double CatalanNumber(int n) {    if (n == 1) {         return 1;      }   else {     return CatalanNumber(n - 1) * 2 * (2 * n - 1) / (n + 1);          }         }          public static void main(String[] args) {              for (int i = 1; i <= 50; i++) {                   System.out.println(i + "'s Catalan Number is " + CatalanNumber(i));                   }                }

C++套用

void catalan() //求卡特蘭數{    int i, j, len, carry, temp;    a[1][0] = b[1] = 1;    len = 1;    for(i = 2; i <= 100; i++)    {        for(j = 0; j < len; j++) //乘法        a[i][j] = a[i-1][j]*(4*(i-1)+2);        carry = 0;        for(j = 0; j < len; j++) //處理相乘結果        {            temp = a[i][j] + carry;            a[i][j] = temp % 10;            carry = temp / 10;        }        while(carry) //進位處理        {            a[i][len++] = carry % 10;            carry /= 10;        }        carry = 0;        for(j = len-1; j >= 0; j--) //除法        {            temp = carry*10 + a[i][j];            a[i][j] = temp/(i+1);            carry = temp%(i+1);        }        while(!a[i][len-1]) //高位零處理        len --;        b[i] = len;    }}

相關詞條

熱門詞條

聯絡我們