[obm-l] NP complexo

["Henrique Lima Santana" <santanahenrique@xxxxxxxxxxx>]

Oi pessoal, tudo bem?
Bom, gostaria, se possível, da ajuda de vcs nesse problema (probabilidades):
Tem-se n áreas; deve-se, primeiramente, particionar n de todas as maneiras 
possíveis:
(a) (1,1,...,1) n 1´s
(b) (2,1,...,1) (n-2) 1´s
      .
      .
      .
(c)   (n)
E assim, contar as possibilidades, que seriam (de (a) , por exemplo) : 1 com 
1 com 1...com 1 ou A,B,... (onde A,B,...seriam as n áreas) . Total de 
possibilidades=1.  De (b) seria : 2 com 1 com 1... com 1 , ou seja : 
AB,C,D,... ; AC,B,D,... : total de possibilidades: ?    . A (c) seria 
ABC.... Total de possibilidades = 1
Façamos um caso de n pequeno : n=3
Teríamos:
*  (1,1,1) : 1 com 1 com 1 : A,B,C (sendo A,B e C as áreas) , total de      
possibilidades = 1 (como poderíamos calcular essa probabilidade? C3,0 ?)
*   (2,1) : 2 com 1 : AB,C ; AC,B e BC,A  . Total de possibilidades: 3 
(seria C3,2 * C1,1 ?? )
*   (3) : ABC . Total de possibilidades : 1 (C3,3 ?)
Assim, pro n=3 se teria : C3,0 + C3,2*C1,1 + C3,3 =5

É basicamente isso, como eu poderia generalizar o caso prum n qualquer??
Ainda tem um detalhe: essas seriam as possibilidades totais, mas precisa-se 
das possibilidades reais , i.e., apenas as possibilidades em que tivermos 
áreas adjacentes seriam válidas. As áreas seriam agrupadas de duas em duas 
(uma área urbana e outra rural de uma cidade qualquer, onde a área urbana 
fica dentro da rural --  poderíamos considerar 2 circunferência, uma dentro 
da outra) . Por exemplo, por caso n=3 consideraríamos  a cidade X com área 
urbana= A e área rural = B . E a cidade Y com área urbana =C . Assim, a 
possibilidade AC,B seria inválida já que A  e C não são adjacentes...assim, 
as possibilidades totais seriam 5 mas as reais seriam 4 ...
É isso, deu pra entender ? q:-]
Muito obrigado pela atenção dispensada.
[]´s
Henrique

_________________________________________________________________
MSN Messenger: converse online com seus amigos .  
http://messenger.msn.com.br

=========================================================================
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
=========================================================================