wyznaczyć liczbę podzbiorów
-
RudaMa?aWied?ma
- Użytkownik
- Posty: 58
- Rejestracja: 28 lut 2010, o 13:57
- Płeć: Kobieta
- Lokalizacja: warszawa
- Podziękował: 3 razy
wyznaczyć liczbę podzbiorów
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 .
Powód: Nieczytelny zapis - brak LaTeX-a. Proszę zapoznać się z instrukcją: http://matematyka.pl/latex.htm .
-
Crizz
- Użytkownik
- 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
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}}\).
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}}\).