Matemática-Ideia 01 (Vandermonde)

Escrita por Brendon Borck:

Uma identidade pouco conhecida em combinatória, porém útil em contagem e necessária para finalizar alguns problemas sem criar grandes dores de cabeça é a seguinte expressão (identidade de Vandermonde):

${m+n \choose r} = \sum^{r}_{k=0} {m \choose k} {n \choose r-k}$

sendo $m,n,r \in \mathbb{N_0}$

Prova:

A igualdade acima pode ser transformada num outro problema e sua prova feita a partir disso:

Temos $n$ homens e $m$ mulheres e precisamos escolher $r$ dessas pessoas para fazer parte de um grupo seleto.

Há duas formas de selecionar essas pessoas.

A primeira consiste em utilizar o fato de que há $m+n$ pessoas e queremos escolher $r$, o que pode ser feito de ${m+n \choose r}$ maneiras.

A segunda consiste em olhar os homens e as mulheres separadamente. Há $r+1$ possíveis formas: escolher $1$ homem e $r-1$ mulheres ou $2$ homens e $r-2$ mulheres ou $3$ homens e $r-3$ mulheres e assim sucessivamente. Para cada uma dessas parcelas pegamos $k$ homens, para isso há ${n \choose r}$ maneiras, e $r-k$ mulheres, para isso há ${m \choose r-k}$ maneiras, o que totaliza por parcela: ${n \choose k}{m \choose r-k}$ jeitos de realizarmos essa escolha. Pronto! Agora só somar variando $k$ de $0$ a $r$,

Como ambas soluções são válidas, não há outro jeito: elas são iguais e obtemos a identidade do enunciado.

Problemas relacionados:

1. Calcule: $\sum^{n}_{k=0} {n \choose k} ^2$
2. Calcule: $\sum^{n}_{k=0} k {n \choose k} ^2$
3. Calcule: $\sum^{n}_{k=0} {n \choose k} {m \choose k}$, com $n \ge m$.
4. Calcule: $\sum^{n}_{k=0} {n \choose k} {n-k \choose m-k}$, com $m<n$.
5. Problema 6 do nosso simulado para OBMEP 2017.
6. Problema 10 da prova de matemática do IME 2014/2015.
7. Problema 3 do nosso material sobre somatórios e produtórios (mod p)