Prove, usando um argumento combinatório, que

Passo 1

O enunciado pede para provar, por contagem combinatória, que
Cm^n;Cn^r ;=; Cm^r;Cm-r^,n-r
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 ,Cm^n,Cn^r:
  1. Primeiro escolhemos, de um conjunto de m elementos, um subconjunto S de tamanho n. Há Cm^n maneiras de fazer isso.
  2. Depois, dentro desse subconjunto S, escolhemos um subgrupo especial de tamanho r. Há Cn^r maneiras de escolher esses r elementos em S.
    Logo, o produto Cm^n,Cn^r conta o número de formas de primeiro pegar n elementos em m e depois marcar r deles.

Passo 3

Interpretação do lado direito ,Cm^r,Cm-r^,n-r:
  1. Primeiro escolhemos, de m elementos, diretamente os r que vão ser marcados. Há Cm^r modos de fazer isso.
  2. Em seguida, dos m-r restantes (que não foram marcados), escolhemos mais n-r para completar o grupo de n. São Cm-r^,n-r maneiras.
    Portanto, Cm^r,Cm-r^,n-r também conta as formas de marcar r e depois escolher o restante até totalizar n.

Passo 4

Como ambas as contagens enumeram exatamente as mesmas construções (escolher um grupo de n e, dentro dele, marcar r), temos
Cm^n;Cn^r ;=; Cm^r;Cm-r^,n-r

Resposta

Cm^n;Cn^r ;=; Cm^r;Cm-r^,n-r

Exercícios de Livros Relacionados