RES: [obm-l] somatorio

[Ralph Teixeira <RALPH@xxxxxx>]

	Eu tenho n+1 livros numa estante (volume 1,2,3,...,n+1). Eu quero
escolher uma coleção de 2m+1 livros da estante (pintando o livro do meio de
verde, se você desejar). Quantas maneiras eu tenho de escolher tal coleção?

	Se eu estiver sozinho, eu escolho 2m+1 livros dos n+1. Então, há
C(n+1,2m+1) possíveis coleções. Aí eu posso pintar o do meio de verde, mas
isso não faz diferença alguma no número de maneiras... :)

	Por outro lado, se eu tiver dois ajudantes Abreu e Beatriz, eu
começo escolhendo o livro do meio (dos 2m+1), pinto-o de verde e é esse que
eu vou carregar. Digamos que eu escolhi o volume k (k poderia ser 0, 1, ...,
n). Agora eu peço ao Abreu para escolher m livros à esquerda do livro verde
(há C(k,m) maneiras de ele fazer isso) e à Beatriz para escolher m livros à
direita do livro verde (há C(n-k,m) maneiras de ela escolher). Em suma, para
uma escolha fixa de k, há C(k,m).C(n-k,m) maneiras de escolher os outros 2m
livros (este número pode até ser zero se eu escolhi um livro muito na
ponta). No total, incluindo o livro verde, há Sum(k=0 a k=n) C(n-k,m).C(k,m)
maneiras de escolher 2m+1 livros a partir dos n iniciais.

	Note que para cada escolha dos 2m+1 livros há apenas uma maneira de
fazer este processo do Abreu e Beatriz.

	Como o resultado dos processos é idêntico (exceto talvez porque eu
fiquei menos cansado na segunda situação), e cada maneira de fazer um
corresponde a apenas uma maneira de fazer o outro, conclui-se que

	C(n+1,2m+1) = Sum (k=0 a k=n) C(n-k,m).C(k,m)

	Que tal?

	Abraço,
		Ralph

----Mensagem original-----
De: adr.scr.m [mailto:adr.scr.m@bol.com.br]
Enviada em: sábado, 6 de julho de 2002 14:29
Para: obm-l@mat.puc-rio.br
Assunto: [obm-l] somatorio


Alguem pode me ajudar nesse somatorio, 
 caiu no IME em 1980,

Prove a seguinte identidade
C(n+1,2m+1)=som(de k=o ate n) C(n-k,m) C(k,m)
onde n e m sao inteiros positivos e
C(n,m)=  n! /[ (n-m)! m! ] 
para n >= m   e C(n,m)=0 para n < m.
Obrigado.
Adriano.
=========================================================================
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
O administrador desta lista é <nicolau@mat.puc-rio.br>
=========================================================================