參考維基百科 Catalan數詳解
這里只是把常見的公式搬過來

設Catalan數的第n項為 hnhn，定義 h0=h1=1h0=h1=1 則有如下兩個常用遞推式

hn=h0hn?1+h1hn?2+...+hn?1h0,n>=2hn=h0hn?1+h1hn?2+...+hn?1h0,n>=2

hn=4n?2n+1hn?1,n>=1hn=4n?2n+1hn?1,n>=1

通項公式為

hn=Cn2nn+1,n>=0hn=C2nnn+1,n>=0 hn=Cn2n?Cn?12n,n>=0hn=C2nn?C2nn?1,n>=0

//Catalan數的前30項 h[0] = 1 h[1] = 1 h[2] = 2 h[3] = 5 h[4] = 14 h[5] = 42 h[6] = 132 h[7] = 429 h[8] = 1430 h[9] = 4862 h[10] = 16796 h[11] = 58786 h[12] = 208012 h[13] = 742900 h[14] = 2674440 h[15] = 9694845 h[16] = 35357670 h[17] = 129644790 h[18] = 477638700 h[19] = 1767263190 h[20] = 6564120420 h[21] = 24466267020 h[22] = 91482563640 h[23] = 343059613650 h[24] = 1289904147324 h[25] = 4861946401452 h[26] = 18367353072152 h[27] = 69533550916004 h[28] = 263747951750360 h[29] = 1002242216651368 h[30] = 3814986502092304

典型的應用問題

• 矩陣鏈乘： P=a1×a2×a3×……×an，依據乘法結合律，不改變其順序，只用括號表示成對的乘積，試問有幾種括號化的方案？
• 出棧次序問題，一個棧(無窮大)的進棧序列為1,2,3,..n,有多少個不同的出棧序列?
• 將一個凸多邊形區域分成三角形區域的方法數?
• 給定N個節點，能構成多少種形狀不同的二叉樹？
• ……

轉載于:https://www.cnblogs.com/wafish/p/10465232.html

總結

以上是生活随笔為你收集整理的Catalan数总结的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。