卡特蘭數

參數方程

卡特蘭數 $C_n=\frac{1}{n+1}\left(\genfrac{}{}{0ex}{}{2n}{n}\right)$ 計數多種結構：$n$ 對括號的合法匹配、從 $(0,0)$ 到 $(n,n)$ 不越對角線的格路徑、凸 $n+2$ 邊形的三角剖分等。視覺化可在不同模型間切換同一 $C_n$。

遞迴：

互動說明

• 模型切換：括號序列／戴克格路徑／剖分三種視圖
• 階數 n：控制物件規模，$n>6$ 時三角剖分改為抽樣顯示，避免組合爆炸

觀察重點

• 「下一個」只換畫出的物件，$C_n$ 不變
• 戴克格路徑就是把括號序列逐一讀成格路徑上的步，且始終不越過對角線；括號視圖中的弧線連起互相配對的括號
• 三角剖分把凸 $(n+2)$ 邊形切成三角形；$n>6$ 時此視圖為抽樣，並非列出全部剖分

相關作品

• 帕斯卡三角形
• 組合的路徑計數
• 二項式展開的幾何意義

延伸閱讀

• 卡特蘭數（維基百科）