Escolha um subconjunto com k elementos, o que voce pode fazer de C(n,k) modos.
O outro subconjunto deve ser um subconjunto do complementar: como o complementar
eh de tamanho
n - k, este outro subconjunto pode ser escolhido de 2^(n-k) modos.
A resposta parece ser somatorio de C(n,k)*[2^(n-k)] com k variando de 0
a n. Essa soma vale (binômio de Newton) 3^n.
Mas ha dois problemas: Primeiro, uma contagem dupla. Por exemplo, para o
conjunto {1, 2, 3, 4}, o par {1}, {2,3} eh contado duas vezes: uma quando
se escolhe o {1} como subconjunto e o {2,3} eh escolhido como o outro subconjunto
e vice-versa.
Segundo, o par vazio vazio soh eh contado uma vez.
A resposta eh 1 + a metade de (3^n - 1) = metade de (3^n + 1)
Bonito problema, Carlos Gomes!
cgmat wrote:
001701c28934$42e713a0$f270bfc8@41a7ime526d044j">
Alô pessoal, será que alguém poderia de
dar uma dica na questão:
De quantas formas podemos
selecionar dois subconjuntos disjuntos a partir de um conjunto finito com
n elementos?