Matematyka.pl

Niech \(\displaystyle{ a _{n}}\) oznacza liczbę słów binarnych długosci \(\displaystyle{ n}\) w których nie ma trzech jedynek pod rząd Znajdź wzór rekurencyjny dla ciągu\(\displaystyle{ \left( a _{n} \right) ^{} ^{ \infty } _{n=0}}\)

Proszę o pomoc

Rozważ ciągi długości \(\displaystyle{ n-1}\) i możliwość dostawienia jedynki i zera z np. prawej strony.

\(\displaystyle{ a_{0}=0,
a _{1}=1,
a_{2}=4,
a_{3}=7}\)

Ustalmy \(\displaystyle{ n \ge 3}\).
Załóżmy, że obliczyliśmy ilość takich ciągów o długości \(\displaystyle{ n}\).

Ile będzie takich ciągów o długości \(\displaystyle{ n+1}\) ?

1) przypadek: na \(\displaystyle{ n}\) pozycji w ciągu o dł. \(\displaystyle{ n+1}\) stoi \(\displaystyle{ 0}\).

Ponieważ ustaliliśmy cyfrę na przedostatnim miejscu, takich ciągów będzie tylko \(\displaystyle{ a_{n}}\), gdyż możemy wybrać na ostatnie miejsce zero lub jeden.

2)przypadek: na \(\displaystyle{ n}\) pozycji w ciągu o dł. \(\displaystyle{ n+1}\) stoi \(\displaystyle{ 1}\).
a)
jeśli na \(\displaystyle{ n-1}\) pozycji stoi 0, to na ostatniej pozycji może stać zero lub jeden. Ilość takich ciągów: \(\displaystyle{ a_{n-1}}\).
b)
jeśli na \(\displaystyle{ n-1}\) pozycji stoi 1, to na ostatniej pozycji musi stać zero. Ilość takich ciągów: \(\displaystyle{ a_{n-2}}\).

Zliczamy wszytski przypadki i otrzymujemy wzór rekurencyjny:

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

\(\displaystyle{ a _{1}=1}\)

\(\displaystyle{ a_1=2}\)

dalej też masz błędy, a wzór jest zły.

\(\displaystyle{ a_{n+1}=2 \cdot a_{n} - a_{n-2}}\)-- 22 lip 2011, o 20:54 --jesli dostawiamy 0 na końcu to ilośc możliwych ciągów to \(\displaystyle{ a_n}\)
jeśli dostawiamy 1 na końcu to ilośc możliwych ciągów to to podobnie jak wyżej \(\displaystyle{ a_n}\) i teraz trzeba odjąć te które mają na końcu 2 jedynki: dowolny ciąg \(\displaystyle{ a_{n-2} + \{11 \}}\)

abc66 mądry jesteś to napisz prawidłowy wzór.
Inkwizytor nie pogrążaj się. Twój wzór nie działa nawet dla \(\displaystyle{ a_{4}}\)

Inkwizytor pisze:\(\displaystyle{ a_{n+1}=2 \cdot a_{n} - a_{n-2}}\)

-- 22 lip 2011, o 20:54 --

jesli dostawiamy 0 na końcu to ilośc możliwych ciągów to \(\displaystyle{ a_n}\)
jeśli dostawiamy 1 na końcu to ilośc możliwych ciągów to to podobnie jak wyżej \(\displaystyle{ a_n}\) i teraz trzeba odjąć te które mają na końcu 2 jedynki: dowolny ciąg \(\displaystyle{ a_{n-2} + \{11 \}}\)

Mores pisze:Inkwizytor nie pogrążaj się. Twój wzór nie działa nawet dla \(\displaystyle{ a_{4}}\)

Słusznie poprawka (ale byłem blisko ):
jeśli dostawiamy 1 na końcu to ilośc możliwych ciągów to to podobnie jak wyżej \(\displaystyle{ a_n}\) i teraz trzeba odjąć te które mają na końcu 1 zero i 2 jedynki: dowolny ciąg \(\displaystyle{ a_{n-3} + \{011 \}}\)
Czyli:
\(\displaystyle{ a_{n+1}=2 \cdot a_{n} - a_{n-3}}\)

-- 22 lip 2011, o 21:26 --

Wzór działa dla \(\displaystyle{ n \ge 4}\)

\(\displaystyle{ a_{0}=0, a _{1}=1, a_{2}=4, a_{3}=7, a_{4}=13}\)

To co tu jest porpawnym roziązaniem ziberze ktos to w całosc ?

le3o pisze:To co tu jest porpawnym roziązaniem ziberze ktos to w całosc ?

Tzn? Co Ty tu jeszcze chcesz zbierać?

abc66 mądry jesteś to napisz prawidłowy wzór.

Mores, co ty masz pięć lat? Po prostu napisałem ci, że masz błąd -_-