Problem
COM-B2-M03-P020 General Reflection
#20
★★★★★ Level 5 of 5
Let \(a\ge b\). Find the number of paths from \((0,0)\) to \((a,b)\), using \(R,U\), that never go above the diagonal \(y=x\).
Reflect bad paths up to the first step entering the region \(y=x+1\).
There are \(\binom{a+b}{b}\) paths in total. A bad path first violates the condition by stepping to the line \(y=x+1\). Reflect the initial segment up to this step in the line \(y=x+1\). This gives a path from \((-1,1)\) to \((a,b)\). Such a path must have \(a+1\) steps \(R\) and \(b-1\) steps \(U\), so the number of bad paths is \(\binom{a+b}{b-1}\). Therefore the number of good paths is
\[\binom{a+b}{b}-\binom{a+b}{b-1}=\frac{a-b+1}{a+1}\binom{a+b}{b}.\]
A strong generalisation of the Catalan count, good for closing the module.