Задача
COM-B2-M03-P020 Обобщённое отражение
#20
★★★★★ Уровень 5 из 5
Пусть \(a\ge b\). Найдите число путей из \((0,0)\) в \((a,b)\), которые идут шагами \(R,U\) и никогда не поднимаются выше диагонали \(y=x\).
Плохие пути отразите до первого шага, попавшего в область \(y=x+1\).
Всего путей \(\binom{a+b}{b}\). Плохой путь впервые нарушает условие шагом в точку на прямой \(y=x+1\). Отразим начальную часть до этого шага относительно прямой \(y=x+1\). Получится путь из \((-1,1)\) в \((a,b)\). Такой путь должен иметь \(a+1\) шагов \(R\) и \(b-1\) шагов \(U\), поэтому плохих путей \(\binom{a+b}{b-1}\). Следовательно, хороших путей
\[\binom{a+b}{b}-\binom{a+b}{b-1}=\frac{a-b+1}{a+1}\binom{a+b}{b}.\]
Сильное обобщение Catalan-подсчёта, хорошо завершает модуль.