Visualize Cₙ valid Dyck paths from (0,0) to (n,n) that never cross above the diagonal.
n = 4
Cₙ = 14
Path 1 / 14
Showing: all
Catalan numbers Cₙ = C(2n,n)/(n+1) count the valid lattice paths from (0,0) to (n,n) using unit East (→)
and North (↑) steps that never rise above the diagonal y=x. Equivalently: balanced parenthesizations, binary trees,
triangulations of polygons, non-crossing partitions. C₀=1, C₁=1, C₂=2, C₃=5, C₄=14, C₅=42, C₆=132, C₇=429.
Recurrence: Cₙ₊₁ = Σ CₖCₙ₋ₖ.