Subconjuntos de um conjunto finito

Seja A = {a1, a2, a3, a4, ... , an}um conjunto finito com n elementos.Desejamos determinar o número total de subconjuntos (Ns) que podem ser formados a partir do conjunto A.
Ora, existem subconjuntos de A formados por um elemento, por dois elementos, por três elementos, ... , por n elementos e, também por zero elementos, que corresponde ao conjunto vazio.
Exemplos de subconjuntos possíveis de A:
{a1}, {a2}, ... , {an} – com um elemento.
{a5, a8}, {a1,a6}, etc – com dois elementos ,etc

Da Análise Combinatória poderemos escrever:
Número de subconjuntos com zero elementos: Cn,0
Número de subconjuntos com um elemento: Cn,1
Número de subconjuntos com dois elementos: Cn,2
Número de subconjuntos com três elementos: Cn,3
...............................................
...............................................
Número de subconjuntos com n elementos: Cn,n

Assim, o número total de subconjuntos de A, será dado por:
Ns = Cn,0 + Cn,1 + Cn,2 + Cn,3 + ... + Cn,n  

Para o cálculo do número Ns acima, o uso da fórmula seria muito trabalhoso, principalmente para valores elevados de n.

Vamos contornar esta dificuldade, utilizando o Princípio Fundamental da Contagem, visto na Análise Combinatória:
Observe que para um determinado elemento ai Î A , onde i pode assumir valores de 1 a n, existem duas possibilidades: ele poderá pertencer ou não pertencer a um subconjunto qualquer de A, não existindo outra hipótese.
Assim, pelo Princípio Fundamental da Contagem – PFC o número total de possibilidades (que neste caso é igual ao número total de subconjuntos de A) será dado por:
Ns = 2.2.2.2.2.2. ... .2 = 2n (um produto com n fatores iguais).
Logo,
Ns = 2n
onde n é o número de elementos do conjunto A.

Da análise anterior, concluímos então que:

Cn,0 + Cn,1 + Cn,2 + Cn,3 + ... + Cn,n = 2n

Exercícios resolvidos:
1 – Quantos subconjuntos possui o conjunto A = {1,2,3,6,7}?
Solução: Temos n = 5 elementos \ Ns = 25 = 32 subconjuntos.

2 - Resolva a equação: 
Cx,0 + Cx,1 + Cx,2 + ... + Cx,x = 128
Solução: Pelo que foi visto acima, poderemos escrever imediatamente: 2x = 128 = 27 \ x = 7.

Exercícios propostos:
1 – Quantos subconjuntos possui um conjunto com 10 elementos?
Resposta: 210 = 1024 subconjuntos.

2 – Calcule o valor da soma 
C10,0 + C10,1 + C10,2 + ... + C10,10 .
Resposta: 1024

Paulo Marques, 02 de junho de 2002 – Feira de Santana – BA.

VOLTAR