Quantos subconjuntos há de um conjunto com n elementos?
Solução:
Seja x_{n} o número de subconjuntos de um conjunto A com n elementos. Seja y um destes n elementos do conjunto A . Podemos formar todos os \mathrm{x}_{11} subconjuntos de duas maneiras:
i) os subconjuntos que nào contém y^{\prime} : x_{n-1} no total;
ii) os subconjuntos de contém y : para tanto basta acrescentar o elemento y em cada subconjunto do conjunto A-\{y\}, que possui n-1 elementos, ou seja, também existem x_{n-1} no total.
Desta forma: x_{n}=x_{n-1}+x_{n-1}=2 . x_{n-1}, que caracteriza uma PG. Logo x_{11}=x_{1} .2^{n-1}. Desde que x_{1}=2 (subconjuntos unitário e vazio), então $x_{n}=2^{\prime \prime}.

Passo 1

O enunciado pergunta: “Quantos subconjuntos tem um conjunto A com n elementos?”
Conteúdo: contagem de subconjuntos via princípio da contagem ou recorrência. Vamos definir uma sequência (x_n) que dá a quantidade de subconjuntos de um conjunto com n elementos e obter uma relação de recorrência.

Passo 2

Seja x_n o número de subconjuntos de um conjunto A de tamanho n. Escolha um elemento fixo y\in A. Todo subconjunto de A ocorre em exatamente uma destas duas situações:
  1. Não contém y.
  2. Contém y.
    No caso 1, o subconjunto é um subconjunto de A\setminus\{y\}, que tem n-1 elementos, logo há x_{n-1} desses.
    No caso 2, basta pegar cada subconjunto de A\setminus\{y\} e unir com \{y\}, também dando x_{n-1} possibilidades.

Passo 3

Da classificação acima segue a relação de recorrência
x_n \;=\; x_{n-1} + x_{n-1} \;=\; 2\,x_{n-1}.
Isso caracteriza uma progressão geométrica de razão 2. Para uma PG, o termo geral é
x_n \;=\; x_1 \cdot 2^{\,n-1}.
Como um conjunto de tamanho 1 tem exatamente 2 subconjuntos (o vazio e ele próprio), temos x_1=2. Substituindo:
x_n \;=\; 2\cdot 2^{\,n-1} \;=\; 2^n.

Resposta

O número de subconjuntos de um conjunto com n elementos é
2^n.

Exercícios de Livros Relacionados