Qual é a interpretação combinatória fundamental do coeficiente binomial \binom{n}{k} ?

Passo 1

O enunciado pergunta qual é a interpretação combinatória fundamental do coeficiente binomial \binom{n}{k}.
Informações dadas (pressupostas): n e k são inteiros com 0 \le k \le n. Nenhuma outra hipótese foi fornecida.

Passo 2

Imagine que você tem um conjunto com n objetos distintos — por exemplo, n fichas coloridas todas diferentes. A pergunta que vamos fazer é: de quantas maneiras diferentes eu posso escolher exatamente k 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 k fichas (ou seja, sequências de k elementos sem repetição). Para a primeira posição da sequência há n opções, para a segunda restam n-1, para a terceira n-2, e assim por diante até a k-ésima que tem n-k+1 opções. Portanto o número de sequências ordenadas (permissões) é
n\cdot (n-1)\cdot (n-2)\cdots (n-k+1).
Essa expressão também pode ser escrita usando fatorial como
\frac{n!}{(n-k)!},
onde n! (lê-se “ n fatorial”) significa n\cdot (n-1)\cdot\ldots\cdot 2\cdot 1.

Passo 4

Agora volte ao problema original: escolher k fichas sem considerar ordem. Note que para cada conjunto de k fichas há exatamente k! sequências diferentes que correspondem a permutações dessas k fichas (porque podemos ordenar k objetos de k! formas). Assim, cada subconjunto sem ordem foi contado k! vezes no total de sequências da etapa anterior. Para obter o número de subconjuntos distintos devemos dividir pelo fator k!. Logo
\text{número de subconjuntos de tamanho }k=\frac{\dfrac{n!}{(n-k)!}}{k!}=\frac{n!}{k!(n-k)!}.ú

Passo 5

A definição padrão do coeficiente binomial é exatamente essa quantidade. Portanto \binom{n}{k} conta o número de maneiras de escolher k elementos distintos dentre n quando a ordem não importa e sem reposição. Em palavras curtas: é o número de subconjuntos de tamanho k de um conjunto com n elementos.

Passo 6

Exemplo rápido para fixar: para n=5 e k=2,
\binom{5}{2}=\frac{5!}{2!\,3!}=\frac{120}{2\cdot 6}=10.
Isso significa que, de um conjunto com 5 elementos distintos, existem 10 pares distintos (por exemplo, se os elementos forem \{1,2,3,4,5\}\}, os pares são \(\{1,2\},\{1,3\},\dots,\{4,5\}).)

Passo 7

Outras interpretações equivalentes (úteis na prova): \binom{n}{k} é também o número de palavras binárias de comprimento n com exatamente k uns (escolher as k posições onde aparecem os uns), e é o coeficiente de x^k na expansão do polinômio (1+x)^n. Essas são apenas formas diferentes de ver a mesma ideia combinatória — escolher k posições ou k elementos.

Resposta

\binom{n}{k} é o número de maneiras de escolher k elementos distintos dentre n sem considerar a ordem (ou seja, o número de subconjuntos de tamanho k de um conjunto com n elementos).

Exercícios relacionados