Математическая задача

[Blade]

Приветствую.
Есть такой фигура:

Необходимо определить максимально возможное количество разных путей из точки А в противоположную точку, перемещаясь по направлениям, указанными стрелочками.
Фигура может иметь N ребер (в данном случаи N=3). Зная N нужно определить количество путей (для N=3 ответ 5)
В первоначальном варианте задача предполагает решение с помощью рекурсии, но мне кажется должно быть математическое решение в виде формулы (функции).
Мои рассуждения таковы: в данной задаче есть три вида точек
1. Точки, из которых можно двигаться только в одном направлении
2. Точки, из которых можно двигаться в двух направлениях
3. Точка, из который никуда нельзя двигаться (это самая последняя точка)
Количество первых и вторых точек всегда известно и равно соответственно 2N и P - 2N - 1, где P количество всех точек, которое тоже легко посчитать, зная N.
В случаи N=3, общее количество точек P=10, количество точек первого типа равно 6 и, соответственно, количество точек второго типа равно 3.
Зная это, наверняка, можно вывести формулу, по которой можно посчитать максимальное количество путей, но у меня пока не получилось
Есть у кого какие идеи?

[MyLastHit]

Фигура может иметь N ребер (в данном случаи N=3).

Нарисуй пожалуйста этот рисунок с N=4. Не пойму что имеется ввиду под словом "Ребра".
Строже задачу сформулировать нужно. Тут изображен Орграф, и он не имеет ребер, только дуги. Или имеются ввиду ребра в геометрическом смысле? Тогда как у Вас тут их только 3 штучки получилось?

UPD: Понял что имели ввиду под словом ребра.
Мне вот почему то кажется, что нужно выполнить преобразования орграфа и прийти к более простому виду, он есть.
Например для N = 3:

Этот тоже можно упростить. Сейчас нет времени больше думать, вечером освобожусь займусь

[veniside]

че-то я сомневаюсь, что эти ряды можно посчитать без рекурсии.. хотя, хз )

[Blade]

Нарисовал вариант для N=4, так-же отметил три типа точек, которые описал в первом посте, соответственно P1, P2 и P3





З.Ы. Извиняюсь за качество, рисовал и фоткал на скорую руку

[Utkin]

Суммируй все направления
1. 1
2. 1 + 2
3. 1 + 2 + 1 + 2 (это мы добрались до вершины
4. 1 + 2 + 1 + 2 + 1 + 2
5. 1 + 2 + 1 + 2 + 1 + 2 + 1 + 2
6. 1 + 2 + 1 + 2 + 1 + 2 + 1 + 2 + 1 = 13, если я ничего не пропустил

Надо номернуть точки, а то маршруты перед глазами разбегаются.

[ds.Dante]

Тупая индукция в помощь: посчитай вручную для N = 1, 2, 3, 4 и угадай закономерность.

[Blade]

Сообщение от ds.Dante

Тупая индукция в помощь: посчитай вручную для N = 1, 2, 3, 4 и угадай закономерность.

Дык, с этого начал
N=1 - 1
N=2 - 2
N=3 - 5
N=4 - 10 (скорее всего)

Закономерность не нашел

Добавлено
Для N=4 - 14

[veniside]

> Закономерность не нашел

посмотрите на мой листик выше, там вроде всё просто (стрелочки -- операция сложения)
Для N = 4 там 14 путей
(N указаны в столбике слева, количество путей обведено кружком)

(Сорри, просто не в плане поиска закономерности, а в плане алгоритма подсчёта вариантов )

[Utkin]

Здесь какая-то рекурсия. Я считал эмпирически - все варианты ветвления и будут решением задачи. В программу уложить на раз два - считай все стрелочки и добавь еще единицу или двойку (как коэффициент смещения) .

[Blade]

С рекурсией сделать не проблема, и алгоритм я напишу.
Просто мне интересно, можно ли вывести математическую формулу для решения, начал копать в сторону комбинаторики, пока не раскопал