Four steps up and four across without crossing the diagonal: 14 of the 70 paths

The central binomial coefficient counts all the routes; the Catalan formula counts the legal ones.

Statistics and data · Level: Classic result · Updated on 2026-11-10

On a 4 × 4 grid, the routes from the bottom-left corner to the top-right that only step up and right number 8!/(4!·4!) = 70 — the workbench prints that as the second link. Most people add the rule 'never go above the diagonal', and then the count is 8!/(4!·5!) = 14. The two formulas differ by one factor of n + 1 in the denominator, which is the whole of the Catalan correction.

The 56 illegal paths are not scattered: by the reflection argument, crossing the diagonal pairs them one for one with the routes to a shifted endpoint, and those count 8!/(3!·5!) = 56. So 70 − 56 = 14 and the two screens agree. The same sequence 1, 2, 5, 14, 42 counts the ways to insert parentheses into a string of factors, the triangulations of a convex polygon and the legal bracket strings — the third link is C₅ = 10!/(5!·6!) = 42, the next one up, which is the number of triangulations of a heptagon.

Answer

14

How to read it

C₄ as 8!/(4!·5!) on the workbench. The second link is the unrestricted count 8!/(4!·4!) = 70, and the third is the next Catalan number, 42.

Source

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

Work it in the calculator

These links open the right calculator with this problem's numbers already typed in. The line above is what the screen should show — check it yourself.

This is an independent third-party tool site. It is not affiliated with, sponsored by, or authorised by Casio, Texas Instruments or their distributors. Model names and product names are trademarks of their respective owners and appear here only to identify devices.

The keystroke sequences in these manuals were written from this site's own layout data — the same data the online calculator renders — plus publicly available product facts. Specifications and regional configurations are confirmed against the physical device and the manufacturer's most recent material.