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.