Problem
COM-B1-M10-P023 Not Above the Diagonal
#23
★★★★☆ Level 4 of 5
How many paths from \((0,0)\) to \((4,4)\), using right and up moves, never go above the diagonal \(y=x\)?
List small values or use reflection at the first bad up-step.
There are \(\binom{8}{4}=70\) paths in total. Bad paths are those that first go above the diagonal after some up-step. Reflect the initial segment up to this step across the line \(y=x+1\); this gives a bijection with paths from \((-1,1)\) to \((4,4)\), requiring \(5\) right moves and \(3\) up moves. There are \(\binom{8}{3}=56\) such paths. Hence the number of good paths is \(70-56=14\).
Preview of Catalan numbers.