Prove, usando um argumento combinatório, que
Passo 1
O enunciado pede para provar, por contagem combinatória, que
O conteúdo aqui é interpretação de coeficientes binomiais como “números de maneiras de escolher” e comparar duas contagens do mesmo conjunto de escolhas.
Passo 2
Interpretação do lado esquerdo
:
- Primeiro escolhemos, de um conjunto de
elementos, um subconjunto de tamanho . Há maneiras de fazer isso. - Depois, dentro desse subconjunto
, escolhemos um subgrupo especial de tamanho . Há maneiras de escolher esses elementos em .
Logo, o produtoconta o número de formas de primeiro pegar elementos em e depois marcar deles.
Passo 3
Interpretação do lado direito
:
- Primeiro escolhemos, de
elementos, diretamente os que vão ser marcados. Há modos de fazer isso. - Em seguida, dos
restantes (que não foram marcados), escolhemos mais para completar o grupo de . São maneiras.
Portanto,também conta as formas de marcar e depois escolher o restante até totalizar .
Passo 4
Como ambas as contagens enumeram exatamente as mesmas construções (escolher um grupo de
e, dentro dele, marcar
), temos