Найдите рекуррентное соотношение

Я новичок в рекуррентных отношениях, и мне трудно понять эту проблему:

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

Я придумал a(n)=2a(n-1)+2a(n-2), но я не уверен, что это правильно/на правильном пути.

Любая помощь будет здорово!


recurrence discrete-mathematics
person user3000731    schedule 28.04.2014    source источник
comment
Этот вопрос кажется не по теме, потому что он касается математики, которая более уместна на math.stackexchange.com.   -  person templatetypedef    schedule 20.05.2014

Ответы (1)


arrow_upward
0
arrow_downward

Во-первых, ваш ответ правильный:

  • Если n-я салфетка зеленая, то n-1-я салфетка может быть желтой или оранжевой, а другая n-2 салфетка может быть любой, поэтому получается 2*an-2.

  • Если n-я салфетка не зеленая, она может быть желтой или оранжевой, а другая n-1 салфетка может быть любой, так что это 2*an-1.

Таким образом, окончательный ответ: an = 2*an-2 + 2*an-1.

person Lrrr    schedule 11.12.2014