卡特蘭數是什麼意思

卡特蘭數（Catalan numbers）是一組在數學中多個領域都有套用的整數序列，特別是在組合數學、代數幾何、複分析、組合拓撲學和計算機科學中。它們以法國數學家歐仁·卡特蘭（Eugène Charles Catalan）的名字命名，他在19世紀研究了這些數字。

卡特蘭數的定義如下：

C_n = (1/(n+1)) (2n choose n) = (2n)! / ((n+1)! n!)

其中n是一個正整數，n!表示n的階乘，即n! = 1 2 3 ... n。卡特蘭數的這個公式表示的是，C_n是從一個點開始，到達另一個點的n條線段的所有可能路徑的數量，條件是這些線段不能交叉。

卡特蘭數有許多其他的組合解釋，例如：

1. 卡特蘭數是半平面交換圖的數量，這些圖形有n個頂點，其中每個頂點都有兩個分支。
2. 卡特蘭數是n個二元樹的數量，這些樹的根節點沒有子節點。
3. 卡特蘭數是n個變量的連通平面有向無環圖（DAG）的數量。
4. 卡特蘭數是n個變量的連通平面二項式代數的數量。

卡特蘭數的應用包括在計算機科學中的文法分析、編譯器設計、堆疊操作和二叉搜尋樹的統計等。它們還在數學的其他領域中出現，如幾何學中的多邊形分割問題和拓撲學中的映射類群。