[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[Fwd: Re: [obm-l] subconjuntos]

Estou reenviando porque parece que ninguem leu.

-------- Original Message --------
From: - Mon Nov 11 14:35:08 2002
X-UIDL: T=>!!RO>"![dc"!9g:"!
X-Mozilla-Status: 0011
X-Mozilla-Status2: 00000000
Return-Path: <owner-obm-l@sucuri.mat.puc-rio.br>
Received: from sucuri.mat.puc-rio.br (sucuri.mat.puc-rio.br [139.82.27.7]) by trex.centroin.com.br (8.12.5/8.12.1) with ESMTP id gABEfMfD009988 for <morgado@centroin.com.br>; Mon, 11 Nov 2002 12:41:22 -0200 (EDT)
Received: (from majordom@localhost) by sucuri.mat.puc-rio.br (8.9.3/8.9.3) id MAA19220 for obm-l-MTTP; Mon, 11 Nov 2002 12:34:29 -0200
Received: from trex-b.centroin.com.br (trex-b.centroin.com.br [200.225.63.136]) by sucuri.mat.puc-rio.br (8.9.3/8.9.3) with ESMTP id MAA19216 for <obm-l@mat.puc-rio.br>; Mon, 11 Nov 2002 12:34:23 -0200
Received: from centroin.com.br (du105c.rjo.centroin.com.br [200.225.58.105]) (authenticated bits=0) by trex-b.centroin.com.br (8.12.5/8.12.1) with ESMTP id gABEY5Dh002564 for <obm-l@mat.puc-rio.br>; Mon, 11 Nov 2002 12:34:10 -0200 (EDT)
Message-ID: 3DCFBFD7.1000400@centroin.com.br"><3DCFBFD7.1000400@centroin.com.br>
Date: Mon, 11 Nov 2002 12:33:59 -0200
From: Augusto César Morgado <morgado@centroin.com.br>
User-Agent: Mozilla/5.0 (Windows; U; Win98; en-US; rv:0.9.4.1) Gecko/20020508 Netscape6/6.2.3
X-Accept-Language: en-us
MIME-Version: 1.0
To: obm-l@mat.puc-rio.br
Subject: Re: [obm-l] subconjuntos
References: <001701c28934$42e713a0$f270bfc8@41a7ime526d044j>
Content-Type: multipart/alternative; boundary="------------050201010406050504070106"
Sender: owner-obm-l@sucuri.mat.puc-rio.br
Precedence: bulk
Reply-To: obm-l@mat.puc-rio.br
X-UIDL: T=>!!RO>"![dc"!9g:"!
Status: U


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?
Grato, C.Gomes.