Liczba podzbiorów
-
- Użytkownik
- Posty: 20
- Rejestracja: 14 lut 2013, o 17:08
- Płeć: Kobieta
- Lokalizacja: Kraków
- Podziękował: 2 razy
Liczba podzbiorów
Ile podzbiorów, które nie zawierają dwóch kolejnych liczb całkowitych, posiada zbiór {1, 2, . . . , n}?
-
- Użytkownik
- Posty: 20
- Rejestracja: 14 lut 2013, o 17:08
- Płeć: Kobieta
- Lokalizacja: Kraków
- Podziękował: 2 razy
Liczba podzbiorów
Takich co posiadają?
Hmm...
\(\displaystyle{ 2 ^{n - 1} + 2^{n - 1} = 2^{2n - 2}}\)
A wzory rekurencyjne nie za bardzo wie czym są.
Jeszcze wiem że to przypomina ciąg Fibonacciego.
Hmm...
\(\displaystyle{ 2 ^{n - 1} + 2^{n - 1} = 2^{2n - 2}}\)
A wzory rekurencyjne nie za bardzo wie czym są.
Jeszcze wiem że to przypomina ciąg Fibonacciego.
-
- Użytkownik
- Posty: 5101
- Rejestracja: 11 mar 2011, o 16:31
- Płeć: Mężczyzna
- Lokalizacja: 52°16'37''N 20°52'45''E
- Podziękował: 4 razy
- Pomógł: 1001 razy
Liczba podzbiorów
Nie wiem, co liczysz, ale takiej równości nie ma.Agata80 pisze: \(\displaystyle{ 2 ^{n - 1} + 2^{n - 1} = 2^{2n - 2}}\)
Skoro wiesz, co to ciąg Fibonacciego, to na pewno też wiesz, co to wzór rekurencyjny. Co to jest ciąg Fibonacciego?Agata80 pisze:A wzory rekurencyjne nie za bardzo wie czym są.
Jeszcze wiem że to przypomina ciąg Fibonacciego.
Innym sposobem może być podzielenie na przypadki, w zależności od liczby elementów podzbioru. Nie wiem tylko, czy wtedy wynik się ładnie zwinie.