在 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
在计算器里做这道题
下面的链接直接打开对应的计算器,并把这道题的数字填进屏幕——答案就是上面那一行,可以自己核对。