Как посчитать кол-во возможных исходов?

Question

[Александр]

Есть доска M на N клеток. Возможно ходить безконечно, но только вниз или вправо. Нужно пройти от левого верхнего края до правого нижнего
Задача: посчитать, сколько возможных исходов существует
Пример доски:
1 1 1 1
1 1 1 1
1 1 1 1

Answer 1

[Wataru]

Ответ - количество сочетаний по n-1 из (n+m-2), или сколько способов выбрать n-1 объект из n+m-2.

Это потому что нужно обязательно сделать n-1 шагов вниз и m-1 шагов вправо. Вопрос только, в каком порядке их делать. Всего будет сделано n-1+m-1 шагов и из них надо выбрать какие-то n-1 вниз, остальные будут шаги вправо. Вот и получаются сочетания.

Можно считать треугольником Паскаля, получится в точности то же, что описал poznavaka,
можно считать по формуле факториалов: (n+m-2)! / (n-1)! / (m-1)!

Для вашего примера, где N=3 и M=4 ответ будет 5!/2!/3! = 120/2/6 = 10.

Answer 2

[poznavaka]

Правый верхний угол задает кол-во ячеек вверх и вправо и означает кол-во проходов:

1 5 15  35  70
1 4 10  20  35
1 3  6  10  15
1 2  3   4  5
0 1  1   1  1

K(n,m) = K(n-1,m) + K(n,m-1)
K(n,m) = n*m, при n или m равное 2
K(n,m) = 1, при n или m равное 1  
K(n,m) = 0, при n и m равное 1

Это можно реализовать рекурсией, останавливая его при n или m равное 2.

Comments

[Александр]

Спасибо

Answer 3

[Griboks]

Нисколько. Прийти в правый Нижний угол невозможно.

Comments

[Александр]

Извиняюсь, не налево, а направо

Answer 4

[4iloveg]

Это же просто: 0 возможных исходов. Как указано в условии - из верхнего левого угла невозможно дойти до нижнего правого угла, так как доступен только ход вниз или влево.

Comments

[Александр]

Извиняюсь, не налево, а направо

Answer 5

[dmshar]

Ответ - 10.

Comments

[Александр]

Это я понимаю. Но мне нужен алгоритм, чтобы просчитывать это при разных значениях M N

[dmshar]

Mrsnek007, Открываем любой учебник по элементарной теории графов, ищем задачу "поиск количества путей в ациклическом ориентированном графе".
Читаем, вникаем, считаем.
P.S. Кстати, алгоритм - это не формула, если что.