[obm-l] Combinatoria

[Helder Suzuki <heldersuzuki@xxxxxxxxxxxx>]

Duas questoeszinhas.

_ _ _ _ _ _ _ 1 2 ... n _
_|_| |_|_| |_|_|_|_|_|_|_
B   \_\ /_/      A
     \_|_/
      |_|
      |_|
      |_| C
      |o|

Imagine que o 'desenho' acima é uma linha férrea,
aonde o segmento B é extensão do segmento A e o
segmento C se conecta com ambos segmentos.
Os numeros no segmento A representam n vagões _soltos_
e enumerados.
Os vagoes podem se mover de A -> B, A -> C e C -> B,
mas nunca de C -> A nem B -> A.

De quantas formas eh possivel reagrupar os vagões no
segmento B?

(há espaço suficiente para n vagões tanto em A, quanto
em B e em C)


-------

Um conjunto A depende de um conjunto B se e somente se
B != A e B for subconjunto de A.

De quantas formas podemos ordenar todos subconjunto de
um conjunto com n elementos distintos tal que nenhum
desses subconjuto anteceda uma dependencia?

por exemplo:
os subconjunto {a, b, c} podem ser ordenado assim:
(}, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}

assim tambem:
{}, {a}, {b}, {a, b}, {c}, {a, c}, {b, c}, {a, b, c}

_______________________________________________________________________
Busca Yahoo!
O serviço de busca mais completo da Internet. O que você pensar o Yahoo! encontra.
http://br.busca.yahoo.com/
=========================================================================
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>
=========================================================================