Задача
COM-B2-M03-P013 Путь ниже диагонали
#13
★★★★☆ Уровень 4 из 5
Найдите число путей из \((0,0)\) в \((n,n)\), которые идут шагами \(R,U\) и никогда не поднимаются выше прямой \(y=x\).
Посчитайте все пути и вычтите плохие через отражение до первого нарушения.
Всего путей \(\binom{2n}{n}\). Плохой путь впервые попадает выше диагонали шагом \(U\), в точку с \(y=x+1\). Отразим начальную часть до этого шага относительно прямой \(y=x+1\). Получается биекция плохих путей с путями из \((-1,1)\) в \((n,n)\), которых \(\binom{2n}{n-1}\). Значит, хороших путей
\[\binom{2n}{n}-\binom{2n}{n-1}=\frac{1}{n+1}\binom{2n}{n}.\]
Это первый полноценный Catalan-подсчёт.