Ciąg ternarny

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
natalia2007
Użytkownik
Użytkownik
Posty: 63
Rejestracja: 16 sty 2009, o 08:48
Podziękował: 12 razy

Ciąg ternarny

Post autor: natalia2007 »

Wyznaczyć wzór rekurencyjny ciągu \(\displaystyle{ a _{n}}\) gdzie \(\displaystyle{ a _{n}}\) jest liczbą wszystkich ciągów ternarnych w których żadne dwie jedynki nie stoją obok siebie.
abc666

Ciąg ternarny

Post autor: abc666 »

\(\displaystyle{ a_1 = 3 \\
\{0,1,2\} \\
a_2 = 8 \\
\{00,01,02,10,12,20,21,22\}}\)

\(\displaystyle{ b_n}\)- liczba ciągów zakończonych jedynką
\(\displaystyle{ c_n}\) - liczba ciągów zakończonych nie-jedynką

\(\displaystyle{ a_n=b_n+c_n\\
b_n=c_{n-1} \mbox{ - jedynkę możemy dostawić tylko gdy na końcu jest nie-jedynka}\\
c_n=2a_{n-1} \mbox{ - zawsze możemy dostawić zero lub jedynkę} \\
b_n=2a_{n-2}\\
a_n=2(a_{n-1}+a_{n-2})}\)


Niech ktoś jeszcze sprawdzi.
ODPOWIEDZ