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

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

原理：
令h(1)＝1，catalan數(shù)滿足遞歸式：
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)心其解是怎么求出來的，我只想知道怎么用catalan數(shù)分析問題。
我總結(jié)了一下，最典型的三類應(yīng)用：（實質(zhì)上卻都一樣，無非是遞歸等式的應(yīng)用，就看你能不能分解問題寫出遞歸式了）
1.括號化問題。

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

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

類似：有2n個人排成一行進(jìn)入劇場。入場費5元。其中只有n個人有一張5元鈔票，另外n人只有10元鈔票，劇院無其它鈔票，問有多少中方法使得只要有10元的人買票，售票處就有5元的鈔票找零？(將持5元者到達(dá)視作將5元入棧，持10元者到達(dá)視作使棧中某5元出棧)

3.將多邊行劃分為三角形問題。
將一個凸多邊形區(qū)域分成三角形區(qū)域的方法數(shù)?

類似：一位大城市的律師在她住所以北n個街區(qū)和以東n個街區(qū)處工作。每天她走2n個街區(qū)去上班。如果他
從不穿越（但可以碰到）從家到辦公室的對角線，那么有多少條可能的道路？

類似：在圓上選擇2n個點,將這些點成對連接起來使得所得到的n條線段不相交的方法數(shù)?

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

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