Exercise 2117Combinatorics › Counting principlesOlympiadAdded 3 Nov 2026
Catalan numbers
#Catalan numbers#paths#Dyck paths
Statement
Show that the number of Dyck paths from to staying weakly above the diagonal is the Catalan number .
Hint
Use the reflection principle: total paths minus "bad" paths that dip below.
Show solutionHide solution
Solution
Total. Number of paths with up-steps and down-steps: .
Bad paths. Reflect the initial segment up to the first dip below the axis: bijection with paths from to starting with up and down. Count: .
Conclusion. .
Example. .