Seja D(n) esse número que você quer. Então:
D(0)=1 (vazio)
D(1)=1+1=2 (1 com 0 elementos, 1 com 1 elemento)
D(2)=1+2+0=3 (vazio e os subconjuntos unitários)
D(3)=1+3+1+0=5 (vazio, os unitários e {1,3}, mas com 3 elementos não dá)
Será que eu arrumo uma recorrência? Oras, os subconjuntos que eu arrumo em
{1,2,...,n} são de 2 tipos:
-- os que contém o último número n; então eles não podem ter o n-1! Assim,
eu tenho que escolher (e basta escolher!) um subconjunto de {1,2,...,n-2}
que não tenha dois inteiros consecutivos, o que pode ser feito de D(n-2)
jeitos;
-- os que não tem o ultimo número n; então eu tenho que escolher (e basta!)
um subconjunto de {1,2,...,n-1} corretamente, o que pode ser feito de
D(n-1) jeitos.
Assim, D(n)=D(n-1)+D(n-2) -- e a sequência dos D(n) é a sequencia de
Fibonacci, começando com 1,2,3,5,8,13,... Você agora pode arrumar uma
fórmula fechada para ela.
Abraço,
Ralph
2012/6/11 marcone augusto araújo borges <marconeborge...@hotmail.com>
> Quantos subconjuntos do conjunto {1,2,...,n} não contêm dois inteiros
> consecutivos?
>
