Задача
COM-B1-M10-P023 Не выше диагонали
#23
★★★★☆ Уровень 4 из 5
Сколько путей из \((0,0)\) в \((4,4)\), состоящих из шагов вправо и вверх, никогда не поднимаются выше диагонали \(y=x\)?
Можно выписать малые значения или использовать отражение плохого первого подъема.
Всего путей \(\binom{8}{4}=70\). Плохие пути - те, которые впервые попали выше диагонали после некоторого шага вверх. Отразим начальный участок до этого шага относительно прямой \(y=x+1\); получается взаимно однозначное соответствие с путями из \((-1,1)\) в \((4,4)\), где нужно сделать \(5\) шагов вправо и \(3\) вверх. Их \(\binom{8}{3}=56\). Значит хороших путей \(70-56=14\).
Это предварительный выход к числам Каталана.