RE: [obm-l] Problemas com binomiais

["David M. Cardoso" <david-obm@xxxxxxxxxxxx>]

Cara.. muuuito obrigado..
perfeito mesmo!!! entendi. :D 

> -----Mensagem original-----
> De: owner-obm-l@mat.puc-rio.br 
> [mailto:owner-obm-l@mat.puc-rio.br] Em nome de claudio.buffara
> Enviada em: quinta-feira, 24 de junho de 2004 13:07
> Para: obm-l
> Assunto: Re:[obm-l] Problemas com binomiais
> 
> > Oi pessoal,
> > 
> > Gostaria da ajuda de voces com 2 questoes que não consigo fazer:
> > (qualquer comentario/ideia vai ajudar, eu não consigo sair do canto 
> > nessas
> > questoes)
> > 
> > http://www.suati.com.br/david/questao3.29.gif
>  
> O primeiro eh provar que n^k/k^k <= Binom(n,k) <= n^k/k!.
>  
> A segunda desigualdade eh mais facil:
> Binom(n,k) = n*(n-1)*...*(n-k+1)/k! <= n*n*...*n/k! = n^k/k!.
>  
> Com relacao a primeira, repare que se n = k, entao:
> n^k/k^k = Binom(n,k) = 1;
>  
> se n > k = 1, entao:
> n^k/k^k = Binom(n,k) = n;
>  
> finalmente, se n > k > 1, entao:
> n/k < (n-1)/(k-1) < (n-2)/(k-2) < .... < (n-k+2)/2 < (n-k+1)/1
>  
> Basta provar a primeira desigualdade desta sequencia:
> n > k ==>
> n-1 > k-1 ==>
> 1/(n-1) < 1/(k-1) ==>
> 1 + 1/(n-1) < 1 + 1/(k-1) ==>
> n/(n-1) < k/(k-1) ==>
> n/k < (n-1)/(k-1)
>  
>  
> > http://www.suati.com.br/david/questao3.32.gif
>  
> Binom(n,0) + 2*Binom(n,1) + 2^2*Binom(n,2) + ... + 2^n*Binom(n,n) =
> (1 + 2)^n = 3^n.
>  
> Uma demonstracao combinatoria seria a seguinte:
> Temos um cartao de loteria esportiva com n jogos, cada um dos 
> quais com 3 alternativas (vitoria de um time, vitoria do 
> outro ou empate).
> De quantas maneiras podemos preenche-lo?
>  
> Obviamente, a resposta eh 3^n.
>  
> Por outro lado, poderiamos raciocinar da seguinte forma:
> Para cada k (0 <= k <= n), podemos preencher o cartao com k 
> empates e os demais n-k jogos com vitoria de um dois dois 
> times. Assim, para cada k, teremos:
> 1) Escolha dos jogos em que marcaremos empate:
> isso pode ser feito de Binom(n,k) formas diferentes.
>  
> 2) Em cada um dos (n-k) jogos em que marcaremos vitoria de 
> algum time, poderemos escolher o time de 2 maneiras. Logo, 
> poderemos marcar vitoria de 2^(n-k) formas diferentes.
>  
> Somando de k = 0 ateh k = n, acharemos o numero total de 
> maneiras de preencher o cartao:
> Binom(n,0)*2^n + Binom(n,1)*2^(n-1) + ... + Binom(n,n-1)*2^1 
> + Binom(n,n)*1, ou, levando em conta que Binom(n,k) = Binom(n,n-k):
> Binom(n,0)*1 + Binom(n,1)*2 + ... + Binom(n,n-1)*2^(n-1) + 
> Binom(n,n)*2^n.
>  
> Mas sabemos que esse numero eh igual a 3^n.
> Logo, a identidade estah provada.
>  
> []s,
> Claudio.
>  
>  
> 


=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
=========================================================================