Шляхи під діагоналлю

Порахуй усі шляхи, а потім за допомогою відбиття відніми ті, що торкаються забороненої прямої.

1. Без обмежень існує $\left(\genfrac{}{}{0ex}{}{12}{5}\right)=792$ шляхів.
2. Поганий шлях уперше торкається прямої $y=x+1$ у деякій точці; відбиття частини до цієї точки відносно прямої переносить початок у $(-1,1)$.
3. Отже, погані шляхи взаємно однозначно відповідають шляхам без обмежень від $(-1,1)$ до $(7,5)$, які мають $8$ кроків на схід і $4$ кроки на північ, тобто їх $\left(\genfrac{}{}{0ex}{}{12}{4}\right)=495$.
4. Відповідь дорівнює $792-495=297$.

Відповідь: $297$