卡特蘭數是什麼意思

卡特蘭數(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個變量的連通平面二項式代數的數量。

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