Problem
COM-B2-M03-P013 Path Below the Diagonal
#13
★★★★☆ Level 4 of 5
Find the number of paths from \((0,0)\) to \((n,n)\), using \(R,U\), that never go above the line \(y=x\).
Count all paths and subtract bad paths using reflection up to the first violation.
There are \(\binom{2n}{n}\) paths in total. A bad path first goes above the diagonal by a step \(U\), landing at a point with \(y=x+1\). Reflect the initial part up to this step in the line \(y=x+1\). This gives a bijection from bad paths to paths from \((-1,1)\) to \((n,n)\), of which there are \(\binom{2n}{n-1}\). Therefore the number of good paths is
\[\binom{2n}{n}-\binom{2n}{n-1}=\frac{1}{n+1}\binom{2n}{n}.\]
This is the first full Catalan count.