四步向上四步向右、不過對角線:70 條路裡只有 14 條合法

中心二項式係數數的是所有走法,加泰羅尼亞公式數的是合法走法。

統計與資料 · 難度: 經典結論 · 更新於 2026-11-10

在 4 × 4 的方格上,只許向上和向右、從左下角走到右上角的路線有 8!/(4!·4!) = 70 條——工作台印的就是第二個連結。多數人還會加一條規矩「不許越過對角線」,這時數目變成 8!/(4!·5!) = 14。兩個公式只差分母上一個 n + 1,這一處差別就是加泰羅尼亞修正的全部。

那 56 條非法路線不是散亂的:按反射論證,越過對角線的走法與「走到一個平移後的終點」的走法一一對應,而後者的數目是 8!/(3!·5!) = 56。於是 70 − 56 = 14,兩塊螢幕相互印證。同一串 1、2、5、14、42 還數得出一串因子可以怎麼加括號、凸多邊形可以怎麼三角剖分、合法的括號串有多少條——第三個連結是 C₅ = 10!/(5!·6!) = 42,即下一項,也就是七邊形的三角剖分數。

答案

14

口徑說明

工作台上的 C₄ = 8!/(4!·5!)。第二個連結是不受限制的 8!/(4!·4!) = 70,第三個是下一個加泰羅尼亞數 42。

出處

The Catalan numbers Cₙ = (2n)!/(n!(n+1)!) count monotone lattice paths that stay on one side of the diagonal; Euler used the sequence for polygon triangulations in 1751, the Chinese mathematician Ming'an derived the formula in the 1730s, and Eugène Catalan gave the name in 1838

在計算機裡做這道題

下面的連結直接開啟對應的計算機,並把這道題的數字填進螢幕——答案就是上面那一行,可以自己核對。

本站為獨立第三方工具站,與 Casio、Texas Instruments 及其代理商無隸屬、代理或授權關係。型號名與產品名為各權利人商標,僅用於識別機型。

手冊中的操作序列依據「本站線上計算機同源佈局資料 + 公開產品事實」獨立撰寫;規格與地區配置以實機與廠商最新資料為準。