先來看看CATALAN數(shù)是怎么定義的。（http://www.ekany.com/wdg98/zhsx/2/2_11.htm）
2.11 Catalan 數(shù)
這一節(jié)討論Catalan數(shù),其遞推關(guān)系是非線性的,許多有意義的計(jì)數(shù)問題都導(dǎo)致這樣的遞推關(guān)系.本節(jié)將舉出一些,后面還將見到.
一個(gè)凸n邊形,通過不相交于n邊形的對(duì)角線,把n邊形拆分成若干三角形,不同拆分的數(shù)目用hn表示.例如五邊形有如下五種拆分方案，故hn=5
圖 2-11-1
1.遞推關(guān)系
定理：
證明：
（a）的證明： 如圖2－11－1所示， 以v1vn+1作為一個(gè)邊 的三角形 ， 將凸n+1邊形分割 成兩部分，一部分是 k邊形， 另一部分是n-k+2邊形，k=2,3,...,n即vk點(diǎn)可以是v2,v3,...,vn點(diǎn)中任意一點(diǎn)。依據(jù)加法法則有
圖 2－11－3
(b) 的證明： 如圖2－11－3所示， 從v1點(diǎn)向其它n-3個(gè)頂點(diǎn)(v3,v4,...,vn-1)可引出n-3條對(duì)角線。對(duì)角線v1vk把n邊形 分割成兩個(gè)部分，因此 以v1vk對(duì)角線作為拆分線的方案數(shù)為hkhn-k+2。
vk可以是v3,v4,...,vn-1中任一點(diǎn)，對(duì)所有這些點(diǎn)求和得h3hn-1+h4hn-2+...+hn-2h4+hn-1h3
以v2,v3,...,vn取代 點(diǎn)也有類似的結(jié)果。但考慮到對(duì)角線有兩個(gè)頂點(diǎn)，同一對(duì)角線在兩個(gè)頂點(diǎn)分別計(jì)算了一次，作
（2－11－3）式并不就給出剖分?jǐn)?shù)，無(wú)疑其中是有重復(fù)的。其重復(fù)度是由于一個(gè)凸n邊形的剖分有n-3條對(duì)角線，而對(duì)其每一條邊計(jì)數(shù)時(shí)該剖分都計(jì)數(shù)了一次，故重復(fù)了n-3次即（2－11－3）式給出的結(jié)果是hn的n-3倍。
（2－11－1）式和（2－11－2）式都是非線性的遞推關(guān)系。
2.Catalan 數(shù)計(jì)算公式
由（2－11－1）式及h2=1故得
由
整理得
令
|