Главная Вход в систему Регистрация
Задать вопрос Консультации Пользователи Форум
О системе Помощь
Задать вопрос экспертам
Консультация № 172283
17.09.2009, 20:31
0.00 руб.
0 2 1
Образование
Здравствуйте, уважаемые эксперты.
У меня несложная задача на комбинаторику, не могу разобраться.

Рисунок:
http://s45.radikal.ru/i107/0909/bd/6bd2dc8d6fcb.jpg

Имеется пространство (пример не рисунке) M*N клеток.
Размер каждой клетки одинаков, но это не имеет значения.

Можно перемещаться только по горизонтали и по вертикали.
И нужно найти количество кратчайших ходов от точки А до точки В.

Ответ: (M + N)! / (N! * M!).

Подскажите, пожалуйста, как решить такую задачу, и как получается такой ответ?
Спасибо.

Обсуждение

давно
Roman Chaplinsky / Химик CH
Модератор
156417
2175
17.09.2009, 21:24
общий
это ответ
Здравствуйте, Иванов Андрей Владимирович.
Очевидно, что кратчайший путь это N шагов вниз и М шагов вправо (в произвольном порядке).
Обозначим шаги по вертикали V, а по горизонтали - H
таким образом, мы имеем N элементов V и M элементов H
M+N различных элементов можно рзместить PM+N=(M+N)! различными способами (перестановки)
Но так как среди элементов есть N одинаковых элементов V, взаимные перестановки которых (PN=N!) не изменяют получаемого маршрута (также как если в слове "оно" поменять местами 1-ю и 3-ю буквы), а также M одинаковых элементов H, взаимные перестановки которых (PM=M!) также не влияют на результат, то на каждый реально существующий маршрут приходится M!*N! изначально полученых перестановок.
То есть количество возможных кратчайших маршрутов (M+N)!/(N!*M!)
Неизвестный
18.09.2009, 10:52
общий
Спасибо, Химик CH
Ваш ответ помог мне разобраться с этой задачей.
Форма ответа