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