Prove, usando um argumento combinatório, que
binomnmbinommk=binomnkbinomn-km-k para 0<k <= m <= n.

Passo 1

O enunciado pede para provar, por contagem combinatória, que
binomnmbinommk=binomnkbinomn-km-k
para 0<k<= m<= n.
O conteúdo aqui é a interpretação de coeficientes binomiais como número de formas de escolher subconjuntos de certos tamanhos numa coleção de n elementos. Vamos contar de duas maneiras o mesmo objeto combinatório: um par (S,T) tal que
Tsubseteq Ssubseteq [n], |S|=m, |T|=k

Passo 2

Contagem pelo lado esquerdo. Primeiro escolhemos um subconjunto S de tamanho m em [n] de binomnm maneiras. Em seguida, dentro de S, escolhemos um subconjunto T de tamanho k de binommk maneiras. Assim o número total de pares (S,T) é
binomnm;binommk

Passo 3

Contagem pelo lado direito. Primeiro escolhemos o subconjunto T de tamanho k em [n] de binomnk maneiras. Sobram n-k elementos em [n]setminus T; desses, escolhemos m-k para completar S a m elementos. Esse segundo passo é feito de binomn-km-k maneiras. Logo o total de pares (S,T) também é
binomnk;binomn-km-k

Passo 4

Como ambos os lados contam exatamente o mesmo conjunto de pares (S,T), concluímos que
binomnmbinommk ;=;binomnkbinomn-km-k

Resposta

boxedbinomnmbinommk=binomnkbinomn-km-k

Exercícios relacionados