卡特蘭數(shù)

問(wèn)題：

n對(duì)括號(hào)有多少種合法的匹配方式？（卡特蘭數(shù)的常見(jiàn)應(yīng)用之一）

結(jié)論：

對(duì)于n對(duì)括號(hào)，合法的排列共有C（n,2n）-C（n+1,2n）

基本思路：

考慮n對(duì)括號(hào)，有n個(gè)（和n個(gè)），對(duì)于任意一個(gè)）其前面必定有一個(gè)（跟他對(duì)應(yīng)，如果沒(méi)有則是非法序列。也就是說(shuō)，對(duì)于），其前面的（的數(shù)量必須大于等于）的數(shù)量。假設(shè)（=1，）=-1。合法的序列是 1 -11 -1 1 -1，不合法的序列是1 -1 -1 1 1 -1。n對(duì)括號(hào)的全排列數(shù)為C（n，2n），減掉那些不合法的排列數(shù)就得到了合法的排列數(shù)，那么不合法的排列數(shù)怎么得到呢？觀察上面不合法的序列1 -1 -1 1 1 -1，從第3個(gè)數(shù)開始，）的個(gè)數(shù)比（大1，因此，后面的(的個(gè)數(shù)也會(huì)比)大1。我們把1到3的數(shù)翻轉(zhuǎn)一下，變成-1 1 1 1 1 -1，得到一個(gè)有n+1個(gè)1，n-1個(gè)-1的序列。這樣的序列總共有C（n-1，2n）或者C（n+1,2n）種，

我們可以得出這樣一個(gè)結(jié)論：對(duì)于所有有n+1個(gè)1，n-1個(gè)-1的序列，都存在一個(gè)轉(zhuǎn)折點(diǎn)k，在k之前1的數(shù)量比-1的數(shù)量大1，在k之后1的數(shù)量比-1的數(shù)量大1。我們只需要從第1個(gè)到第k個(gè)元素翻轉(zhuǎn)回去，就能變成對(duì)于有n個(gè)1，n個(gè)-1的情況下的非法排列。因此我們可以得到非法排列的個(gè)數(shù)為C（n，2n）-C（n+1，2n）。

卡特蘭數(shù)公式

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

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

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

遞推關(guān)系的另類解為：h(n)=c(2n,n)-c(2n,n-1)(n=0,1,2,...)

可以利用卡特蘭數(shù)解決的常見(jiàn)問(wèn)題：

一個(gè)棧(無(wú)窮大)的進(jìn)棧序列為1，2，3，…，n，有多少個(gè)不同的出棧序列?

在n*n的格子中，只在下三角行走，每次橫或豎走一格，有多少中走法？

將一個(gè)凸n+2邊形區(qū)域分成三角形區(qū)域的方法數(shù)？

圓上選擇2n個(gè)點(diǎn),將這些點(diǎn)成對(duì)連接起來(lái)使得所得到的n條線段不相交的方法數(shù)？

有2n個(gè)人排成一行進(jìn)入劇場(chǎng)。入場(chǎng)費(fèi)5元。其中只有n個(gè)人有一張5元鈔票，另外n人只有10元鈔票，劇院無(wú)其它鈔票，問(wèn)有多少中方法使得只要有10元的人買票，售票處就有5元的鈔票找零？

  ……

求卡特蘭數(shù)的代碼：

#include <stdio.h>#include<string.h>int a[105][1000];//大數(shù)運(yùn)算 int b[105]; //儲(chǔ)存對(duì)應(yīng)卡特蘭數(shù)有多少位 void catalan() //求卡特蘭數(shù){    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++) //處理相乘結(jié)果        {            temp = a[i][j] + carry;            a[i][j] = temp % 10;            carry = temp / 10;        }        while(carry) //進(jìn)位處理        {            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;    }}int main() {	catalan();	for(int i=1;i<=100;i++)	{		for(int j=b[i]-1;j>=0;j--)		{			PRintf("%d",a[i][j]);		}		printf("/n");	}}