先來看看CATALAN數是怎么定義的。（http://www.ekany.com/wdg98/zhsx/2/2_11.htm）

2.11 Catalan 數 

    這一節討論Catalan數,其遞推關系是非線性的,許多有意義的計數問題都導致這樣的遞推關系.本節將舉出一些,后面還將見到. 

    一個凸n邊形,通過不相交于n邊形的對角線,把n邊形拆分成若干三角形,不同拆分的數目用h_n表示.例如五邊形有如下五種拆分方案，故h_n=5

        圖 2-11-1 

1.遞推關系 

    定理： 

    證明：

    （a）的證明： 如圖2－11－1所示， 以v₁v_n+1作為一個邊 的三角形 ， 將凸n+1邊形分割 成兩部分，一部分是 k邊形， 另一部分是n-k+2邊形，k=2,3,^...,n即v_k點可以是v₂,v₃,^...,v_n點中任意一點。依據加法法則有 

        圖 2－11－3 

    (b) 的證明： 如圖2－11－3所示， 從v₁點向其它n-3個頂點(v₃,v₄,^...,v_n-1)可引出n-3條對角線。對角線v₁v_k把n邊形 分割成兩個部分，因此 以v₁v_k對角線作為拆分線的方案數為h_kh_n-k+2。

   v_k可以是v₃,v₄,^...,v_n-1中任一點，對所有這些點求和得h₃h_n-1+h₄h_n-2+^...+h_n-2h₄+h_n-1h₃

   以v₂,v₃,^...,v_n取代 點也有類似的結果。但考慮到對角線有兩個頂點，同一對角線在兩個頂點分別計算了一次，作 

（2－11－3）式并不就給出剖分數，無疑其中是有重復的。其重復度是由于一個凸n邊形的剖分有n-3條對角線，而對其每一條邊計數時該剖分都計數了一次，故重復了n-3次即（2－11－3）式給出的結果是h_n的n-3倍。 

（2－11－1）式和（2－11－2）式都是非線性的遞推關系。 

2.Catalan 數計算公式 

    由（2－11－1）式及h₂=1故得 

由 

整理得 

令