Obrigado,Douglas.
Uma problema bem parecido: Uma escada tem n degraus.Voce sobe tomando um ou
dois a cada vez.De quantas maneiras voce pode subir?
Date: Mon, 11 Jun 2012 15:42:45 -0300
From: douglas.olive...@grupoolimpo.com.br
To: obm-l@mat.puc-rio.br
Subject: Re: [obm-l] Dúvidas em combinatória
Problema interessantíssimo, não tinha parado pra fazer até que percebi algo..
se voce for analisando a medida que os elementos crescem no conjunto perceba:
{}----> 1
{1}---> 2
{1,2}--->3
{1,2,3}--->5
{1,2,3,4}--->8
...
os números que aparecem são os de fibonacci e analisando a sua resolução, voce
mesmo chegaria no teorema de lucas f_n+1=Cn,0 + Cn-1,1 +Cn-2,2 +...Cn-j,j onde
j é o maior inteiro menor ou igual a n/2, o que responde sua pergunta sobre n/2.
logo é só montar a recorrência e escrever a fórmula de binet.
Espero ter ajudado.
Douglas Oliveira!!!
On Mon, 4 Jun 2012 13:38:50 +0000, marcone augusto araújo borges wrote:
1)Quantos subconjuntos do conjunto {1,2,...,n} não contêm dois inteiros
consecutivos?
O vazio seria um deles
Com 1 elemento:n subconjuntos
Com 2 elementos:Cn-1,2
Com 3 elementos:Cn-2,3
.
.
.
Com n/2 elementos(se n é par):???
Eu pensei C(n/2 + 1,n/2) = n/2 + 1...mas isso é muito estranho,pois,se n =
10,por exemplo,só há 2 subconjuntos de 5 elementos que não contêm dois inteiros
consecutivos...
è necessario mesmo separar em 2 casos,n par e n ímpar?
2)Qual o argumento combinatório para mostrar que Cn,2 + Cn+1,2 = n^2?
Desde já agradeço.
