Maths WorkshopMaths problems with full solutions
Exercise 2117Combinatorics › Counting principlesOlympiadAdded 3 Nov 2026

Catalan numbers

#Catalan numbers#paths#Dyck paths

Statement

Show that the number of Dyck paths from (0,0)(0,0) to (2n,0)(2n,0) staying weakly above the diagonal is the Catalan number Cn=1n+1(2nn)C_n=\frac{1}{n+1}\binom{2n}{n}.

Hint

Use the reflection principle: total paths minus "bad" paths that dip below.

Show solutionHide solution

Solution

Total. Number of paths with nn up-steps and nn down-steps: (2nn)\binom{2n}{n}.

Bad paths. Reflect the initial segment up to the first dip below the axis: bijection with paths from (0,−1)(0,-1) to (2n,0)(2n,0) starting with n+1n+1 up and n−1n-1 down. Count: (2nn+1)\binom{2n}{n+1}.

Conclusion. Cn=(2nn)−(2nn+1)=1n+1(2nn)C_n=\binom{2n}{n}-\binom{2n}{n+1}=\frac{1}{n+1}\binom{2n}{n}.

Example. C3=14(63)=204=5C_3=\frac{1}{4}\binom{6}{3}=\frac{20}{4}=5.