pessoal desculpe mas essa resposta está errada, pois haverão 3^n relações
possíveis só que algumas delas são equivalentes...
acho que dá para ficar assim:
como {(x,1),(y,2)...} é equivalente a {(x,2),(y,1),...}, logo para toda
relação existe uma outra completamente equivalente à ela,
fica
1. 3^n-1: exclui o caso em que todos são relacionados ao zero, não
formando conjuntos disjuntos.
2. (3^n-1)/2: exclui todas as relações equivalentes
logo N = (3^n-1)/2
acho que dessa vez tá tudo ok...
.:. Marcos Aurélio Almeida da Silva .:.
.:. e-mail: maas@cin.ufpe.br .:.
.:. site : http://cin.ufpe.br/~maas .:.
On Mon, 11
Nov 2002, Marcos Aurelio Almeida da Silva wrote:
bom, imagine um conjunto:
A = {a1, a2, ..., an}
imagine a seguinte relação que acossia a cada elemento do conjunto A um
valor:
R: A -> {0,1,2}
vamos formar os seguintes conjuntos:
B = { x / (x,1) pertence a R}
C = { x / (x,2) pertence a R}
D = { x / (x,0) pertence a R}
logo temos dois conjuntos disjuntos que são subconjuntos de A (B e C),
e o conjunto D que é formado pelos elementos que não entram em nenhum dos
outros dois conjuntos. Para contar o número de subconjuntos disjuntos é
só contar o número de relações, pois a cada par de subconjuntos
corresponde uma relação e a cada releção corresponde um par de conjuntos,
logo a resposta deve ser 3^n.
.:. Marcos Aurélio Almeida da Silva .:.
.:. e-mail: maas@cin.ufpe.br .:.
.:. site : http://cin.ufpe.br/~maas .:.
On Mon, 11 Nov 2002, cgmat 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.
=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
O administrador desta lista é <nicolau@mat.puc-rio.br>
=========================================================================