O Binômio de Newton contabiliza todas as possíveis permutações de uma sequência

up:: 064 MOC Estatística em Economia

Fonte: 4. Counting - YouTube.

Dado um conjunto de $n$ elementos, a quantidade de subconjuntos de $k\le n$ elementos é dada pelo binômio de Newton $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$.

Isso é equivalente do que obter todas as sequências possíveis¹ de $k$ elementos.

Por um lado, partindo de $n$ elementos, tem-se que a quantidade de possíveis sequências tais é

$$n\cdot (n-1)\dots (n-(k-1))=\frac{n!}{(n-k)!}$$

Partindo de $k$ elementos pré-selecionados (dentre todos os $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ conjuntos), tem-se que é simplesmente $k!$ possíveis permutações. Portanto, o total de tais permutações é $\left(\genfrac{}{}{0ex}{}{n}{k}\right)k!$.

Igualando ambos, temos que

$$\left(\genfrac{}{}{0ex}{}{n}{k}\right)=\frac{n!}{(n-k)!k!}$$

Exemplos numéricos

Dado conjunto $\{1,2,3,4\}$, temos:

• Possíveis conjuntos de 2 elementos $\left(\genfrac{}{}{0ex}{}{4}{2}\right)=6$
  • $\{1,2/3/4\}$, $\{2,3/4\}$, $\{3,4\}$
• Possíveis conjuntos de 3 elementos $\left(\genfrac{}{}{0ex}{}{4}{3}\right)=4$
  • $\{1,2,3/4\}$, $\{1,3,4\}$, $\{2,3,4\}$

---

References

• 4. Counting - YouTube

Footnotes

1. Independente da ordem dos elementos, isso é importante. ↩