logowanie

matematyka » forum » forum zadaniowe - uczelnie wyższe » zadanie

Matematyka dyskretna, zadanie nr 634

ostatnie wiadomości  |  regulamin  |  latex

AutorZadanie / Rozwiązanie

natalia1992
postów: 26
2012-11-11 10:09:59

Ile podzbiorów, które nie zawierają dwóch kolejnych liczb całkowitych, posiada zbiór {1, 2, . . . , n}?


tumor
postów: 8070
2012-11-13 13:14:53

Zbiór pusty ma jeden podzbiór, który spełnia warunki zadania, oznaczmy $S_0=1$
Zbiór $\{1\}$ ma dwa podzbiory, z tego jeden podzbiór zawiera liczbę $1$, a drugi nie zawiera.
$S_1=2$

Jeśli chcemy dodać liczbę $2$, to możemy ją dodać tylko do tych podzbiorów, które nie zawierają liczby $1$.
Zatem $S_2=S_1+S_0$

Dla liczby $3$ mamy:
$S_3=S_2+S_1$, gdyż wszystkie zbiory, które spełniały warunek zadania dla n=2, spełniają też dla n=3, natomiast oprócz nich rozważamy jeszcze zbiory spełniające warunek zadania dla n=1 z dołączoną liczbą 3.

Dla kolejnych $n$:
$S_{n+2}=S_{n+1}+S_n$
co się nam słusznie kojarzy z ciągiem Fibonacciego, tylko
$S_1=2=F_3$.

$S_n=F_{n+2}$

strony: 1

Prawo do pisania przysługuje tylko zalogowanym użytkownikom. Zaloguj się lub zarejestruj





© 2019 Mariusz Śliwiński      o serwisie | kontakt   drukuj