Re: [obm-l] subconjuntos

[Augusto César Morgado <morgado@xxxxxxxxxxxxxxx>]

Os conjuntos sao disjuntos; nao sao necessariamente complementares.

Domingos Jr. wrote:

003501c2899f$79d20e90$2accfea9@gauss">

seja N = 2k + s, com s = {0, 1}

 

0) você pode formar um subconjunto vazio e outro com 2k+s elementos

1) um subconjunto com 1 elemento, outro com 2k+s-1

...

i) um com i elementos e outro com 2k+s-i

 

se i > k estamos contando alguns subconjuntos duas vezes,

logo pegamos i <= k

seja S a soma de i = 0 até k de Cn,i

 

se N for ímpar, temos

2*S = 2^n => S = 2^(n-1)

 

ex.

{1, 2, 3}, S = 2^2 = 4

{},{1, 2, 3} ; { 1},{2,3} ; {2},{1,3} ; {3},{1,2}

 

se N for par, temos

2*S + Cn,n/2 = 2^n

=>

2*S - n!/[(n/2)!]² = 2^n

 

S = 2^(n-1) + 0,5Cn,n/2

 

para N=4, temos S = 1 + 4 + 6 = 11 = 2^3 + 0,5*C4,2

 

 

----- Original Message -----

From: bruno lima

To: obm-l@mat.puc-rio.br

Sent: Monday, November 11, 2002 10:44 AM

Subject: Re: [obm-l] subconjuntos

Resposta bem grosseira: Divida o conjunto em dois subconjuntos um com k e outro com n-k elementos. Faca as combinações('N escolha K') e multiplique por n, pois K varia de 1 a n. 

 cgmat <cgmat@uol.com.br > wrote:

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?

Grato, C.Gomes.

---

Yahoo! GeoCities
Tudo para criar o seu site: ferramentas fáceis de usar, espaço de sobra e acessórios.