-------- 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: | <[EMAIL PROTECTED]> |
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 <[EMAIL PROTECTED]>; 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 <[EMAIL PROTECTED]>; 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 <[EMAIL PROTECTED]>; Mon, 11 Nov 2002 12:34:10 -0200 (EDT) |
Message-ID: | [EMAIL PROTECTED]"><[EMAIL PROTECTED]> |
Date: | Mon, 11 Nov 2002 12:33:59 -0200 |
From: | Augusto César Morgado <[EMAIL PROTECTED]> |
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: | [EMAIL PROTECTED] |
Subject: | Re: [obm-l] subconjuntos |
References: | <001701c28934$42e713a0$f270bfc8@41a7ime526d044j> |
Content-Type: | multipart/alternative; boundary="------------050201010406050504070106" |
Sender: | [EMAIL PROTECTED] |
Precedence: | bulk |
Reply-To: | [EMAIL PROTECTED] |
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.