|
|
原理 令h(1)＝1,h(0)=1，catalan數(shù)滿足遞歸式：
h(n)= h(0)*h(n-1)+h(1)*h(n-2) + ... + h(n-1)h(0) (其中n>=2)
另類(lèi)遞歸式：
h(n)=((4*n-2)/(n+1))*h(n-1);
該遞推關(guān)系的解為：
h(n)=C(2n,n)/(n+1) (n=1,2,3,...)
卡特蘭數(shù)的應(yīng)用
（實(shí)質(zhì)上都是遞歸等式的應(yīng)用）
括號(hào)化問(wèn)題
矩陣鏈乘： P=a1×a2×a3×……×an，依據(jù)乘法結(jié)合律，不改變其順序，只用括號(hào)表示成對(duì)的乘積，試問(wèn)有幾種括號(hào)化的方案？(h(n)種)
出棧次序問(wèn)題
一個(gè)棧(無(wú)窮大)的進(jìn)棧序列為1，2，3，…，n，有多少個(gè)不同的出棧序列?
分析：對(duì)于每一個(gè)數(shù)來(lái)說(shuō)，必須進(jìn)棧一次、出棧一次。我們把進(jìn)棧設(shè)為狀態(tài)‘1’，出棧設(shè)為狀態(tài)‘0’。n個(gè)數(shù)的所有狀態(tài)對(duì)應(yīng)n個(gè)1和n個(gè)0組成的2n位二進(jìn)制數(shù)。由于等待入棧的操作數(shù)按照1‥n的順序排列、入棧的操作數(shù)b大于等于出棧的操作數(shù)a(a≤b)，因此輸出序列的總數(shù)目=由左而右掃描由n個(gè)1和n個(gè)0組成的2n位二進(jìn)制數(shù)，1的累計(jì)數(shù)不小于0的累計(jì)數(shù)的方案種數(shù)。
在2n位二進(jìn)制數(shù)中填入n個(gè)1的方案數(shù)為c(2n,n),不填1的其余n位自動(dòng)填0。從中減去不符合要求（由左而右掃描，0的累計(jì)數(shù)大于1的累計(jì)數(shù)）的方案數(shù)即為所求。
不符合要求的數(shù)的特征是由左而右掃描時(shí)，必然在某一奇數(shù)位2m+1位上首先出現(xiàn)m+1個(gè)0的累計(jì)數(shù)和m個(gè)1的累計(jì)數(shù)，此后的2(n-m)-1位上有n-m個(gè) 1和n-m-1個(gè)0。如若把后面這2(n-m)-1位上的0和1互換，使之成為n-m個(gè)0和n-m-1個(gè)1，結(jié)果得1個(gè)由n+1個(gè)0和n-1個(gè)1組成的2n位數(shù)，即一個(gè)不合要求的數(shù)對(duì)應(yīng)于一個(gè)由n+1個(gè)0和n-1個(gè)1組成的排列。
反過(guò)來(lái)，任何一個(gè)由n+1個(gè)0和n-1個(gè)1組成的2n位二進(jìn)制數(shù)，由于0的個(gè)數(shù)多2個(gè)，2n為偶數(shù)，故必在某一個(gè)奇數(shù)位上出現(xiàn)0的累計(jì)數(shù)超過(guò)1的累計(jì)數(shù)。同樣在后面部分0和1互換，使之成為由n個(gè)0和n個(gè)1組成的2n位數(shù)，即n+1個(gè)0和n-1個(gè)1組成的2n位數(shù)必對(duì)應(yīng)一個(gè)不符合要求的數(shù)。
因而不合要求的2n位數(shù)與n＋1個(gè)0，n－1個(gè)1組成的排列一一對(duì)應(yīng)。
顯然，不符合要求的方案數(shù)為c(2n,n+1)。由此得出 輸出序列的總數(shù)目=c(2n,n)-c(2n,n+1)=1/(n+1)*c(2n,n)。
（這個(gè)公式的下標(biāo)是從h(0)=1開(kāi)始的）
類(lèi)似：有2n個(gè)人排成一行進(jìn)入劇場(chǎng)。入場(chǎng)費(fèi)5元。其中只有n個(gè)人有一張5元鈔票，另外n人只有10元鈔票，劇院無(wú)其它鈔票，問(wèn)有多少中方法使得只要有10元的人買(mǎi)票，售票處就有5元的鈔票找零？(將持5元者到達(dá)視作將5元入棧，持10元者到達(dá)視作使棧中某5元出棧)
凸多邊形的三角剖分問(wèn)題
求將一個(gè)凸多邊形區(qū)域分成三角形區(qū)域的方法數(shù)。
類(lèi)似：一位大城市的律師在她住所以北n個(gè)街區(qū)和以東n個(gè)街區(qū)處工作。每天她走2n個(gè)街區(qū)去上班。如果她從不穿越（但可以碰到）從家到辦公室的對(duì)角線，那么有多少條可能的道路？
類(lèi)似：在圓上選擇2n個(gè)點(diǎn),將這些點(diǎn)成對(duì)連接起來(lái)使得所得到的n條線段不相交的方法數(shù)?
用給定節(jié)點(diǎn)組成二叉樹(shù)的問(wèn)題
給定N個(gè)節(jié)點(diǎn)，能構(gòu)成多少種不同的二叉樹(shù)？
（能構(gòu)成h（N）個(gè)）
|