Number of Paths on Graph along X-axis using Diagonal Steps

From ProofWiki
Jump to navigation Jump to search

Theorem

The number of different paths that can be taken on a Cartesian coordinate plane from the origin to $\tuple {2 n + 2, 0}$, using only diagonal steps, and never touching the $x$-axis except at the beginning and the end of the path, is the Catalan number $C_n$:


DiagonalStepsOnGraph.png


Proof


Sources