Напишите рекуррентную формулу для числа маршрутов между парой смежных вершин (неориентированного) цикла длины 5

задан 7 Апр 21:53

изменен 8 Апр 11:39

@KotikVacia: почему в тексте формула названа рекуррентной, а в заголовке она стала реККуРентной?

(7 Апр 22:57) falcao
10|600 символов нужно символов осталось
0

При n>=0 рассмотрим три последовательности: число a(n) путей длиной n в графе C5 из одной вершину в смежную ей (обе вершины фиксированы), число b(n) путей длиной n из данной вершины в данную не смежную ей, число c(n) путей длиной n из данной вершины в себя.

Ясно, что a(0)=b(0)=0, c(0)=1; a(1)=1, b(1)=0, c(1)=0.

Пусть n>=1. Легко видеть, что a(n)=b(n-1)+c(n-1); b(n)=a(n-1)+b(n-1); c(n)=2a(n-1). Тогда при n>=2 имеем b(n-1)=a(n)-c(n-1)=a(n)-2a(n-2), то есть из второго уравнения получается a(n+1)-2a(n-1)=a(n-1)+a(n)-2a(n-2). Итого a(n+3)=a(n+2)+3a(n+1)-2a(n) при n>=0, где a(2)=0.

Данное рекуррентное соотношение решается в явной форме. См., например, здесь.

ссылка

отвечен 8 Апр 0:20

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×1,699

задан
7 Апр 21:53

показан
60 раз

обновлен
8 Апр 11:39

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru