Re: [obm-l] somatorio

[Carlos Yuzo Shine <cyshine@xxxxxxxxx>]

Dá para calcular esse somatório com argumentos
combinatórios.

> O resultado final que nos interessa é:
> 
> \sum_{0 <= k <= r}  C(r-k,m) C(s+k,n) =
> C(r+s+1,m+n+1),
> onde inteiro n >= inteiro s >= 0,
>           inteiro m >= 0, inteiro r >= 0.

Veja só:

C(r+s+1, m+n+1) é o número de subconjuntos de m+n+1
elementos de {0;1;2;3;...;r+s}.

C(r-k,m) é o número de maneiras de escolhermos m
dentre r-k números;

C(s+k,n) é o número de maneiras de escolhermos n
dentre r-k números.

Fixe o m+1-ésimo elemento. Se ele for r-k, temos
C(r-m,m) maneiras de escolhermos m elementos entre 0 e
r-m-1 e C(s+k,n) maneiras de escolhermos os outros n
elementos, que junto com o r-k e os outros m
escolhidos formam um conjunto de m+n+1 elementos. O k
pode variar de r a 0, pois se k<0, temos que escolher
n dentre s+k < s elementos, o que é impossível. E se
k>r, o m+1-ésimo elemento é r-k<0, impossível. Não é
difícil ver que a partir de um conjunto de m+n+1
elementos podemos montar dois conjuntos de m e n
elementos e mais o elemento "do meio", estabelecendo
assim uma bijeção.

> Colocando r=n, s=0 e n=m, vem:
> 
> \sum_{0 <= k <= n}  C(n-k,m) C(k,m) = C(n+1,2m+1).
> 
> > C(n+1,2m+1)=som(de k=o ate n) C(n-k,m) C(k,m)
> 

Nesse caso particular, o negócio fica mais simples:

Considere o conjunto X={0;1;2;3;...;n}. Vamos mostrar
que o somatório acima é o número de subconjuntos de
2m+1 elementos de X. Para isso vamos construir uma
bijeção entre os subconjuntos de 2m+1 elementos e uma
tripla ordenada (A,B,c) formada por conjuntos A e B de
m elementos e um número inteiro c, 0<=c<=n, onde todo
elemento de A é menor que c e todo elemento de B é
maior que c (note que o somatório acima conta nada
mais, nada menos que esses ternos).

Claramente, A e B são disjuntos, e portanto associamos
a essa tripla um conjunto A u B u {c} com 2m+1
elementos (aqui u significa união). Observe que
(A,B,c) e (A',B',c') estão associadas a um mesmo
subconjunto se e somente se A = A', B = B' e c = c'.
Logo a associação feita é injetiva. E a cada
subconjunto de 2m+1 elementos está associada uma
tripla (A,B,c). Os primeiros m elementos são os que
pertencem a A, o m+1-ésimo elemento é c e os demais m
elementos pertencem a B. Logo a associação também é
sobrejetiva, sendo assim uma bijeção.

Portanto, o somatório dado é o número de triplas que é
igual ao número de subconjuntos de X com 2m+1
elementos, que é C(n+1,2m+1).

[]'s
Shine

__________________________________________________
Do You Yahoo!?
Sign up for SBC Yahoo! Dial - First Month Free
http://sbc.yahoo.com
=========================================================================
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>
=========================================================================