卡塔蘭數 Catalan number

卡塔蘭數(Catalan number)是組合學中的概念。

Cn = (2n)! / [(n+1)!×n!]

 

前幾個Catalan number是:

1, 1, 2, 5, 14, 42, 132, 429

 

 

Catalan number其中一個應用是,Cn是將一個n+2邊形,切割成三角形的所有可能方法。

如下圖,是5邊形的切割方式。

圖片來源:mathforum.org

 

 

Catalan number的另一個應用,是在n×n的正方形棋盤上,從左下角走到右下角,不穿越對角線,也不走回頭路的所有可能方法。

如下圖,是3×3的走法。

圖片來源:mathforum.org

 

 

資料來源:http://mathforum.org/advanced/robertd/catalan.html

更多介紹:https://zh.wikipedia.org/wiki/卡塔蘭數

發表迴響