Exercise 1715Combinatorics › Inclusion-exclusionOlympiadAdded 3 Nov 2026

Inclusion-exclusion in ballot problems

#IE#ballot#paths

Statement

Using IE, count paths from $(0,0)$ to $(n,n)$ that stay strictly below the diagonal (i.e. paths where at every step, the number of right steps is strictly greater than the number of up steps except at the end).

Hint

This is related to Catalan numbers via reflection.

Show solutionHide solution

Solution

Setup. Number of paths from $(0,0)$ to $(n,n)$ : $\binom{2n}{n}$ .

Bad paths. By reflection, paths crossing the diagonal correspond to paths from $(0,-1)$ to $(n,n)$ .

Count. $\binom{2n}{n}-\binom{2n}{n+1}=C_n$ .

Conclusion. Number of such paths is the Catalan number $C_n$ .

Inclusion-exclusion in ballot problems

Statement

Solution

More problems in Inclusion-exclusion