Catalan Ballot Paths

Lattice paths, ballot sequences, and the Catalan numbers — count paths that stay above the diagonal.

Lattice Path Grid

Parameters

C_n = (2n choose n) / (n+1)
C_n = Σ C_k · C_{n-1-k}
n = 5
Catalan C_n = 42
Total paths = 252
Ratio (C_n/total) = 16.7%
Paths shown = 0

A ballot path (Dyck path) from (0,0) to (n,n) uses steps R=(+1,0) and U=(0,+1), never going above the diagonal y=x. The count is the Catalan number C_n.


Equivalently: balanced parenthesizations, binary trees, triangulations of a polygon.

C₀=1, C₁=1, C₂=2, C₃=5
C₄=14, C₅=42, C₆=132, C₇=429
C₈=1430, C₉=4862...