Qual é a interpretação combinatória fundamental do coeficiente binomial
?
Passo 1
O enunciado pergunta qual é a interpretação combinatória fundamental do coeficiente binomial
.
Informações dadas (pressupostas): e
são inteiros com
. Nenhuma outra hipótese foi fornecida.
Informações dadas (pressupostas):
Passo 2
Imagine que você tem um conjunto com
objetos distintos — por exemplo,
fichas coloridas todas diferentes. A pergunta que vamos fazer é: de quantas maneiras diferentes eu posso escolher exatamente
dessas fichas, quando não importa a ordem em que eu as pego (ou seja, só importa o conjunto escolhido, não a sequência)?
Passo 3
Antes de contar as escolhas sem ordem, vamos contar primeiro de quantas maneiras podemos escolher e ordenar
fichas (ou seja, sequências de
elementos sem repetição). Para a primeira posição da sequência há
opções, para a segunda restam
, para a terceira
, e assim por diante até a
-ésima que tem
opções. Portanto o número de sequências ordenadas (permissões) é
Essa expressão também pode ser escrita usando fatorial como
onde
(lê-se “
fatorial”) significa
.
Passo 4
Agora volte ao problema original: escolher
fichas sem considerar ordem. Note que para cada conjunto de
fichas há exatamente
sequências diferentes que correspondem a permutações dessas
fichas (porque podemos ordenar
objetos de
formas). Assim, cada subconjunto sem ordem foi contado
vezes no total de sequências da etapa anterior. Para obter o número de subconjuntos distintos devemos dividir pelo fator
. Logo
Passo 5
A definição padrão do coeficiente binomial é exatamente essa quantidade. Portanto
conta o número de maneiras de escolher
elementos distintos dentre
quando a ordem não importa e sem reposição. Em palavras curtas: é o número de subconjuntos de tamanho
de um conjunto com
elementos.
Passo 6
Exemplo rápido para fixar: para
e
,
Isso significa que, de um conjunto com 5 elementos distintos, existem 10 pares distintos (por exemplo, se os elementos forem
).)
Passo 7
Outras interpretações equivalentes (úteis na prova):
é também o número de palavras binárias de comprimento
com exatamente
uns (escolher as
posições onde aparecem os uns), e é o coeficiente de
na expansão do polinômio
. Essas são apenas formas diferentes de ver a mesma ideia combinatória — escolher
posições ou
elementos.