Exercício 39: Prove, usando um argumento combinatório, que
\binom{n}{r}\binom{r}{m}=\binom{n}{m}\binom{n-m}{r-m} .

Passo 1

O enunciado pede para provar, por contagem combinatória, a igualdade
\binom{n}{r}\binom{r}{m} \;=\;\binom{n}{m}\binom{n-m}{r-m}.
O conteúdo é o de escolher subconjuntos de tamanhos dados, e a ideia é contar de duas maneiras o número de pares (R,M) tais que M\subseteq R\subseteq\{1,\dots,n\}, com \lvert R\rvert=r e \lvert M\rvert=m.

Passo 2

Contagem pela esquerda (LHS):
  1. Primeiro escolho um conjunto R de tamanho r dentre n elementos. Há \binom{n}{r} jeitos.
  2. Em seguida escolho um subconjunto M de tamanho m dentro de R. Há \binom{r}{m} jeitos.
    Logo, o número total de pares (R,M) é
\binom{n}{r}\,\binom{r}{m}.

Passo 3

Contagem pela direita (RHS):
  1. Primeiro escolho o subconjunto M de tamanho m dentre n elementos. Há \binom{n}{m} jeitos.
  2. Depois, para formar R com \lvert R\rvert=r e contendo M, escolho exatamente r-m elementos adicionais dentre os n-m que não estão em M. Isso pode ser feito de \binom{n-m}{r-m} maneiras.
    Portanto, o número total de pares (R,M) é
\binom{n}{m}\,\binom{n-m}{r-m}.

Passo 4

Como ambas as contagens descrevem exatamente o mesmo conjunto de pares (R,M), devemos ter
\binom{n}{r}\binom{r}{m} \;=\;\binom{n}{m}\binom{n-m}{r-m}.

Resposta

A igualdade está provada por contagem dupla.

Exercícios relacionados