Matematyka dyskretna, zadanie nr 634

Autor	Zadanie / 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