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 des 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é.
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:
hehe bem legal =P
Obrigada :)
Acho que da para fazer pelo triângulo de pascal,pois cada combinação vai criar todos os sub-conjuntos com determinado numero de elementos,somando todas as combinações de uma linha =somar o numero de conjuntos com 1,2,3,4.....n=somar uma linha no triangulo de pascal que vai ser igual a 2^n
Entendir nada.
obrigada! ajudou-me na resolução de um exercício que insistia em permanecer na minha cabeça...é bem mais simples do que parecia...
Postar um comentário