Znajdź wzór rekurencyjny dla ciągu

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
le3o
Użytkownik
Użytkownik
Posty: 22
Rejestracja: 10 lut 2009, o 22:10
Płeć: Mężczyzna
Podziękował: 16 razy

Znajdź wzór rekurencyjny dla ciągu

Post autor: le3o » 22 lip 2011, o 17:04

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

abc666

Znajdź wzór rekurencyjny dla ciągu

Post autor: abc666 » 22 lip 2011, o 19:19

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

Mores
Użytkownik
Użytkownik
Posty: 23
Rejestracja: 7 lip 2011, o 18:28
Płeć: Mężczyzna
Lokalizacja: Warszawa
Pomógł: 4 razy

Znajdź wzór rekurencyjny dla ciągu

Post autor: Mores » 22 lip 2011, o 19:32

\(\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}}\) !

abc666

Znajdź wzór rekurencyjny dla ciągu

Post autor: abc666 » 22 lip 2011, o 19:39

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

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

Awatar użytkownika
Inkwizytor
Użytkownik
Użytkownik
Posty: 4105
Rejestracja: 16 maja 2009, o 15:08
Płeć: Mężczyzna
Lokalizacja: Poznań
Podziękował: 1 raz
Pomógł: 427 razy

Znajdź wzór rekurencyjny dla ciągu

Post autor: Inkwizytor » 22 lip 2011, o 19:50

\(\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
Użytkownik
Użytkownik
Posty: 23
Rejestracja: 7 lip 2011, o 18:28
Płeć: Mężczyzna
Lokalizacja: Warszawa
Pomógł: 4 razy

Znajdź wzór rekurencyjny dla ciągu

Post autor: Mores » 22 lip 2011, o 20:04

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}}\)

Awatar użytkownika
Inkwizytor
Użytkownik
Użytkownik
Posty: 4105
Rejestracja: 16 maja 2009, o 15:08
Płeć: Mężczyzna
Lokalizacja: Poznań
Podziękował: 1 raz
Pomógł: 427 razy

Znajdź wzór rekurencyjny dla ciągu

Post autor: Inkwizytor » 22 lip 2011, o 20:16

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}\)

le3o
Użytkownik
Użytkownik
Posty: 22
Rejestracja: 10 lut 2009, o 22:10
Płeć: Mężczyzna
Podziękował: 16 razy

Znajdź wzór rekurencyjny dla ciągu

Post autor: le3o » 22 lip 2011, o 20:52

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

Awatar użytkownika
Inkwizytor
Użytkownik
Użytkownik
Posty: 4105
Rejestracja: 16 maja 2009, o 15:08
Płeć: Mężczyzna
Lokalizacja: Poznań
Podziękował: 1 raz
Pomógł: 427 razy

Znajdź wzór rekurencyjny dla ciągu

Post autor: Inkwizytor » 22 lip 2011, o 21:14

le3o pisze:To co tu jest porpawnym roziązaniem ziberze ktos to w całosc ?
Tzn? Co Ty tu jeszcze chcesz zbierać?

abc666

Znajdź wzór rekurencyjny dla ciągu

Post autor: abc666 » 22 lip 2011, o 23:30

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 -_-

ODPOWIEDZ