sábado, 29 de agosto de 2009

Quantos subconjuntos?

Esses dias andei pensando numa forma de explicar a resposta de um problema de matemática para uma pessoa (bem importante ;-)) e acabei tendo a ideia de fazer este post.

Dado um conjunto qualquer com elementos, quantos subconjuntos tem ?

Podemos formulá-lo de outra forma. Seja o conjunto das partes de (isto é, o conjunto que tem por elementos todos os subconjuntos possíveis de ). Quantos elementos tem ? Em outras palavras, qual é a cardinalidade de ?

Este é um problema bem simples, inclusive muitos de vocês já devem saber a resposta, mas que pode gerar um pouco de confusão em sua solução.

Vou tentar elucidar um método bem fácil de entender para resolvê-lo.

Primeiramente, vamos entender como vai funcionar a contagem com um caso particular. Fixe um subconjunto de de tamanho (cardinalidade) .

Liste todos os elementos de numa linha. Para cada elemento, devemos decidir se ele pertence ou não a . Se ele pertence a , indicaremos com um , se ele não pertence, com um . Então teríamos algo assim:



Isto é, os 2 primeiros elementos pertencem a , o terceiro não pertence, etc.

O passo fundamental é perceber que cada diferente sequência de s e s determina um único subconjunto de . Por exemplo, se atribuíssemos para todos os elementos da lista, isso indicaria o conjunto vazio. Se atribuíssemos para todos os elementos, indicaria o conjunto inteiro. E assim por diante.

Agora entra a combinatória. Se quisermos decidir quantos subconjuntos existem para um determinado conjunto , basta decidir quantos arranjos é possível obter com os elementos listados anteriormente.

Mas isto é fácil, pois para cada elemento da nossa lista, temos apenas 2 opções ( e ). Como temos elementos, então teremos arranjos possíveis.

Existem outros caminhos para resolver este problema, mas eu achei este o mais elegante (e fácil de entender). Se você souber um melhor, comente aí.

Até.





5 comentários: