Liczba podzbiorów

Agata80 · Post autor: **Agata80** » 18 mar 2013, o 19:15

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

lokas · Post autor: **lokas** » 18 mar 2013, o 21:54

A ile jest takich co posiaają? Będzie łatwiej

norwimaj · Post autor: **norwimaj** » 18 mar 2013, o 22:24

Myślę że najłatwiej tu będzie najpierw napisać wzór rekurencyjny.

Agata80 · Post autor: **Agata80** » 19 mar 2013, o 05:38

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.

norwimaj · Post autor: **norwimaj** » 19 mar 2013, o 11:27

Agata80 pisze: \(\displaystyle{ 2 ^{n - 1} + 2^{n - 1} = 2^{2n - 2}}\)

Nie wiem, co liczysz, ale takiej równości nie ma.

Agata80 pisze:A wzory rekurencyjne nie za bardzo wie czym są.
Jeszcze wiem że to przypomina ciąg Fibonacciego.

Skoro wiesz, co to ciąg Fibonacciego, to na pewno też wiesz, co to wzór rekurencyjny. Co to jest 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.