Dyck Paths & Catalan Numbers
Explore lattice paths and the fascinating Catalan number sequence
Enter a value between 0 and 8
A Dyck path is a lattice path from (0,0) to (2n,0) consisting of steps (1,1) and (1,-1) that never goes below the x-axis. The number of Dyck paths of length 2n is the nth Catalan number.
Catalan Numbers form the sequence: 1, 1, 2, 5, 14, 42, 132, 429, 1430, ...
They count many combinatorial objects including:
- Dyck paths of length 2n
- Valid parentheses expressions with n pairs
- Binary trees with n internal nodes
- Ways to triangulate a convex (n+2)-gon
Formula: C(n) = (1/(n+1)) × C(2n,n) = (2n)!/((n+1)!×n!)
Visualization Legend:
- Red dashed line: x-axis boundary (valid paths never cross below)
- Teal path: valid Dyck path
- Red dot: start point (0,0)
- Teal dot: end point (2n,0)
What is a Dyck path?
A Dyck path is a lattice path from (0,0) to (2n,0) consisting of up-steps (1,1) and down-steps (1,-1) that never goes below the x-axis. Named after mathematician Walther von Dyck, these paths are fundamental objects in combinatorics with deep connections to many counting problems.
How are Dyck paths related to Catalan numbers?
The number of Dyck paths of length 2n equals the nth Catalan number C(n). This is one of many combinatorial interpretations of Catalan numbers. For example, there are C(3) = 5 Dyck paths of length 6, and C(4) = 14 Dyck paths of length 8.
What do Dyck paths represent in practice?
Dyck paths represent balanced parentheses (up = open, down = close), valid sequences of push/pop operations on a stack, and mountain ranges that start and end at ground level. They're used in parsing algorithms, analyzing recursive structures, and studying random walks.
Why can't Dyck paths go below the x-axis?
The x-axis constraint ensures the path represents a 'valid' structure. In terms of parentheses, going below would mean having more closing parentheses than opening ones at some point - an invalid expression. This constraint is what makes Dyck paths count meaningful combinatorial objects.