Proposição 2.4: A quantidade dos subconjuntos diferentes, quais contem
elementos, entre um conjunto, que contem
elementos é igual ao
.
Passo 1
O enunciado afirma que, dado um conjunto com
elementos, a quantidade de maneiras de escolher subconjuntos de exatamente
elementos é
O conteúdo aqui é combinatória: vamos usar o princípio fundamental da contagem e a relação entre permutações e combinações para chegar a essa fórmula.
Passo 2
Primeiro, conte de quantas formas podemos escolher e ordenar
elementos distintos dentre os
. Isso é uma permutação de
elementos tomados
a
, cujo número é
Aqui estamos escolhendo uma sequência ordenada de
elementos.
Passo 3
Observe que cada subconjunto de
elementos pode ser ordenado de
maneiras diferentes. Ou seja, as
sequências contam cada subconjunto
vezes (uma para cada permutação interna).
Passo 4
Para obter apenas o número de subconjuntos (sem importar a ordem interna), dividimos o total de sequências
por
. Assim,