Ciąg ternarny
-
- Użytkownik
- Posty: 63
- Rejestracja: 16 sty 2009, o 08:48
- Podziękował: 12 razy
Ciąg ternarny
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.
Ciąg ternarny
\(\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.
\{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.