在 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
在計算機裡做這道題
下面的連結直接開啟對應的計算機,並把這道題的數字填進屏幕——答案就是上面那一行,可以自己核對。