Сколько существует путей и почему?
Если шагающий начинает из точки (0, 0) и переходит в точку (50, 75) и имеет такое ограничение, что каждый шаг идет либо на одну единицу вверх, либо на одну единицу вправо, сколько путей существует для такого ходуна... Сколько существует путей и почему?
Ответы (1 шт):
Можно очень просто - движение по горизонтали - пишем 0, по вертикали - пишем 1. В итоге у нас каждый путь - число из 125 знаков, в котором 50 нулей и 75 единиц. В общем случае - M нулей и N единиц.
Чтобы определить количество таких чисел, надо прикинуть, сколькими способами можно выбрать N единиц среди N+M знакомест. Первая единица - N+M способов, вторая - N+M-1 и так далее... Итого - (N+M)!/M! Но еще надо поделить на N!, так как порядок всех этих единиц не играет роли. Очевидно, что то же значение получается, если рассматривать M нулей.
Итого всего таких путей -
Ну, а само число - 249510749788530813877394729177487510