四步向上四步向右、不过对角线: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 及其代理商无隶属、代理或授权关系。型号名与产品名为各权利人商标,仅用于识别机型。

手册中的操作序列依据「本站在线计算器同源布局数据 + 公开产品事实」独立撰写;规格与地区配置以实机与厂商最新资料为准。