Условие
По сетке нужно пройти из (0;0) в (4;3), каждый шаг — на единицу вправо или вверх. Через точку (1;1) проходить нельзя. Сколько существует путей?
Подсказка
Всего 7 шагов, из которых 3 вверх. Выбираем их места: C(7,3)=35.
До (1;1) есть 2 пути. От неё остаются 3 шагов вправо и 2 вверх: C(5,2)=10. Запрещённых путей 2·10=20.
Показать ответ
15
Пошаговое решение
- Считаем все кратчайшие пути
Всего 7 шагов, из которых 3 вверх. Выбираем их места: C(7,3)=35.
- Считаем запрещённые пути
До (1;1) есть 2 пути. От неё остаются 3 шагов вправо и 2 вверх: C(5,2)=10. Запрещённых путей 2·10=20.
- Вычитаем
Каждый запрещённый путь проходит эту точку ровно один раз. Допустимых 35−20=15.
Ответ: 15