Exercício 39: Prove, usando um argumento combinatório, que
Passo 1
O enunciado pede para provar, por contagem combinatória, a igualdade
O conteúdo é o de escolher subconjuntos de tamanhos dados, e a ideia é contar de duas maneiras o número de pares
tais que
, com
e
.
Passo 2
Contagem pela esquerda (LHS):
- Primeiro escolho um conjunto
de tamanho dentre elementos. Há jeitos. - Em seguida escolho um subconjunto
de tamanho dentro de . Há jeitos.
Logo, o número total de paresé
Passo 3
Contagem pela direita (RHS):
- Primeiro escolho o subconjunto
de tamanho dentre elementos. Há jeitos. - Depois, para formar
com e contendo , escolho exatamente elementos adicionais dentre os que não estão em . Isso pode ser feito de maneiras.
Portanto, o número total de paresé
Passo 4
Como ambas as contagens descrevem exatamente o mesmo conjunto de pares
, devemos ter
Resposta
A igualdade está provada por contagem dupla.