wyznaczyć liczbę podzbiorów

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
RudaMa?aWied?ma
Użytkownik
Użytkownik
Posty: 58
Rejestracja: 28 lut 2010, o 13:57
Płeć: Kobieta
Lokalizacja: warszawa
Podziękował: 3 razy

wyznaczyć liczbę podzbiorów

Post autor: RudaMa?aWied?ma » 24 cze 2010, o 13:49

wyznaczyć liczbę podzbiorów zbioru \(\displaystyle{ \{0,1...n\}}\), które nie zawierają żadnych dwóch kolejnych liczb. tylko tak z wytłumaczeniem proszę ;D
Ostatnio zmieniony 24 cze 2010, o 18:58 przez Anonymous, łącznie zmieniany 1 raz.
Powód: Nieczytelny zapis - brak LaTeX-a. Proszę zapoznać się z instrukcją: http://matematyka.pl/latex.htm .

Crizz
Gość Specjalny
Gość Specjalny
Posty: 4094
Rejestracja: 10 lut 2008, o 15:31
Płeć: Mężczyzna
Lokalizacja: Łódź
Podziękował: 12 razy
Pomógł: 805 razy

wyznaczyć liczbę podzbiorów

Post autor: Crizz » 13 lip 2010, o 22:09

Jeśli \(\displaystyle{ a_{n}}\) oznacza szukaną liczbę podzbiorów zbioru \(\displaystyle{ \{1,2,3,...,n\}}\), to \(\displaystyle{ a_{n}=a_{n-1}+a_{n-2}}\).

Dlaczego? Podzbiorów spełniających zadany warunek, niezawierających \(\displaystyle{ n}\), jest oczywiście \(\displaystyle{ a_{n-1}}\). Do tej liczby musimy dodać liczbę podzbiorów tego zbioru spełniających dany warunek i zawierających n. Wszystkie takie podzbiory tworzymy, dokładając liczbę n do każdego z \(\displaystyle{ a_{n-2}}\) spełniających warunek podzbiorów zbioru \(\displaystyle{ \{1,2,...,n-2\}}\) (bierze się to stąd, że podzbiory, do których dokładamy \(\displaystyle{ n}\), nie mogą zawierać \(\displaystyle{ n-1}\)).

Po rozwiązaniu tej rekurencji (uwzględniamy \(\displaystyle{ a_{0}=2,a_{1}=3}\)), otrzymujemy: \(\displaystyle{ a_{n}= \frac{2\sqrt{5}+5}{5} \cdot \left(\frac{1+\sqrt{5}}{2}\right)^{n} + \frac{5-2\sqrt{5}}{5} \cdot \left(\frac{1-\sqrt{5}}{2}\right)^{n}}\).

ODPOWIEDZ