卡特蘭數

卡特蘭數，在各種記數問題中很常會出現的數列，一般項公式為


另一個表達形式為
遞迴形式表達式為

還有
組合數學中有各種記數範例可以描述卡特蘭數，例如從 n x n 座標中從左下角到右上角，每一部均為向上或向右，不超過對角線的走法有多少種


節點數為 n 的不同構二元樹有多少種


卡特蘭數有多種表達形式，在處理記數問題時，若是發現可以套用卡特蘭數，則可以用卡特蘭數其他的形式做計算，可以方便許多，例如發現該記數符合卡特蘭數的遞迴形式，則可以改用一般項形式計算