Quantos subconjuntos há de um conjunto com
elementos?
Solução:
Seja
o número de subconjuntos de um conjunto
com
elementos. Seja y um destes n elementos do conjunto A . Podemos formar todos os
subconjuntos de duas maneiras:
i) os subconjuntos que nào contém
:
no total;
ii) os subconjuntos de contém
: para tanto basta acrescentar o elemento y em cada subconjunto do conjunto
, que possui
elementos, ou seja, também existem
no total.
Desta forma:
, que caracteriza uma PG. Logo
. Desde que
(subconjuntos unitário e vazio), então $x_{n}=2^{\prime \prime}.
i) os subconjuntos que nào contém
ii) os subconjuntos de contém
Desta forma:
Passo 1
O enunciado pergunta: “Quantos subconjuntos tem um conjunto
com
elementos?”
Conteúdo: contagem de subconjuntos via princípio da contagem ou recorrência. Vamos definir uma sequência que dá a quantidade de subconjuntos de um conjunto com
elementos e obter uma relação de recorrência.
Conteúdo: contagem de subconjuntos via princípio da contagem ou recorrência. Vamos definir uma sequência
Passo 2
Seja
o número de subconjuntos de um conjunto
de tamanho
. Escolha um elemento fixo
. Todo subconjunto de
ocorre em exatamente uma destas duas situações:
- Não contém
. - Contém
.
No caso 1, o subconjunto é um subconjunto de, que tem elementos, logo há desses.
No caso 2, basta pegar cada subconjunto dee unir com , também dando possibilidades.
Passo 3
Da classificação acima segue a relação de recorrência
Isso caracteriza uma progressão geométrica de razão
. Para uma PG, o termo geral é
Como um conjunto de tamanho
tem exatamente
subconjuntos (o vazio e ele próprio), temos
. Substituindo:
Resposta
O número de subconjuntos de um conjunto com
elementos é