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 +,
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.
[obm-l] RE: [obm-l] Dúvidas em combinatória
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 +, 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.
[obm-l] Dúvidas em combinatória
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.
