青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

什么是catalan數(shù)？
在網(wǎng)上找了n久，各種關(guān)于catalan數(shù)列的資料都?xì)埲辈豢埃税胩觳爬斫馐裁词莄atalan數(shù)。所以干脆自己梳理一番。

原理：
令h(1)＝1，catalan數(shù)滿(mǎn)足遞歸式：
h(n)= h(1)*h(n-1) + h(2)*h(n-2) + ... + h(n-1)h(1) (其中n>=2)
該遞推關(guān)系的解為：h(n)=c(2n-2,n-1)/n (n=1,2,3,...)

我并不關(guān)心其解是怎么求出來(lái)的，我只想知道怎么用catalan數(shù)分析問(wèn)題。
我總結(jié)了一下，最典型的三類(lèi)應(yīng)用：（實(shí)質(zhì)上卻都一樣，無(wú)非是遞歸等式的應(yīng)用，就看你能不能分解問(wèn)題寫(xiě)出遞歸式了）
1.括號(hào)化問(wèn)題。

矩陣鏈乘： P=a1×a2×a3×……×an，依據(jù)乘法結(jié)合律，不改變其順序，只用括號(hào)表示成對(duì)的乘積，試問(wèn)有幾種括號(hào)化的方案？(h(n)種)

2.出棧次序問(wèn)題。
一個(gè)棧(無(wú)窮大)的進(jìn)棧序列為1,2,3,..n,有多少個(gè)不同的出棧序列?

類(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元出棧)

3.將多邊行劃分為三角形問(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ù)?

不過(guò)下面這個(gè)問(wèn)題似乎不好歸類(lèi)，它怎么來(lái)應(yīng)用這個(gè)catalan遞歸方程呢？你說(shuō)說(shuō)：n個(gè)結(jié)點(diǎn)可構(gòu)造多少個(gè)不同的二叉樹(shù)?

看的人倒是不少,愿意想一想的倒是不多,唉