Problem z rekurencją

[Khaine]

Mam takie dwa zadanka:

1. Na ile sposobów można wytworzyć ciąg długości n z liczb 0,1,2 tak aby żadne dwie jedynki nie stały obok siebie.
2. Na ile sposobów można wytworzyć ciąg długości n z liczb 0,1,2 tak aby żadne dwie jedynki oraz żadne dwie dwójki nie stały obok siebie.

Przyjąłem takie rozumowanie rekurencyjne:

\(\displaystyle{ a_{0} = 1, a_{1} = 3}\)
Dla n=2
1. Jeśli na pierwszym miejscu mamy 0, to po 0 mogą być 3 cyfry, czyli an-1. Analogicznie sytuacja zachodzi dla 2, więc mamy a_{n-1} x 2. Gdy na pierwszym miejscu mamy 1 zachodzi sytuacja wyjątkowa, żeby warunek nam się dopełnił musimy zużyć jeszcze jeden element, żeby wykluczyć pojawienie się 1. Stąd n-2, bo musimy tam wsadzić jeszcze jedną cyfrę. Mamy więc 2 przypadki 10 oraz 12, w każdym z nich jest 1 możliwość na umieszczenie 0 oraz 2, więc \(\displaystyle{ a_{n-2}}\). Generalnie wynik zgadza się z wypisywaniem sobie poszczególnych wyrazów dla n=3 i dalej pewnie też.
Mamy ogółem \(\displaystyle{ a_{n} = 2*a_{n-1} + 2*a_{n-2}}\)

2. Jeśli na pierwszym miejscu mamy 0, to po 0 mamy 3 opcje, czyli \(\displaystyle{ a_{n-1}}\).
Jeśli na pierwszym miejscu mamy 1 musimy postąpić tak jak poprzednio - wsadzić 2 lub 0, co daje nam dwa przypadki i n-2. I tak samo musimy postąpić dla 2, stąd w sumie n-2 x 4.
Wychodzi niby \(\displaystyle{ a_{n} = a_{n-1} + 4*a_{n-2}}\)

No tylko problem w tym, że ten drugi wzór mi się nie zgadza z tym co wypisuję sobie na kartce jako wyrazy dla n=3. Wzór podaje 19 możliwości, zaś z wypisywania mam 17 jeśli czegoś nie pominąłem.

Gdzie jest błąd w rozumowaniu i jak go naprawić?

[jutrvy]

Ojejku, dlaczego rekurencyjnie? Poustawiaj sobie najpierw dwójki i trójki, a potem między nie "powtykaj" jedynki. Możesz w ciągu mieć do \(\displaystyle{ 0}\) do \(\displaystyle{ k}\) jedynek (właśnie wróciłem z imprezy - nie policzę). I w zależności od tego będziesz miał \(\displaystyle{ m}\) dwójek i \(\displaystyle{ n-m-k}\) trójek. Ostatecznie, jak to rozpiszesz, dostaniesz podwójną sumę (po \(\displaystyle{ k, n}\)) z jakimiśtam symbolami Newtona. Rąbnij sobie funkcję tworzącą, wylicz i masz.

[arek1357]

Hm twoja propozycja jest bardzo skomplikowana! Nawet przed imprezą bym jej nie rozkminił.
Ja jestem prosty i prosto myślę więc:
Moja propozycja do b). to:

\(\displaystyle{ a_{1}=3}\)

\(\displaystyle{ a_{3}=7}\)

\(\displaystyle{ a_{n+2}=2a_{n+1}+a_{n}}\)


Bo to proste wszystko przemnażasz przez dwa i dodajesz jeszcze te wcześniejsze gdzie na początku są zera. Bo co by nie stało na końcu to i tak w najgorszym przypadku możesz dopisać dwie możliwości.
A Tobie nie wychodziło bo liczyłeś pewne przypadki podwójnie!