Otimo. E quase o quie eu pensei so que com um a
formulacao menos tosca...
Agora e so colocar isto na BC ou resolver a
recorrencia...
--- "Domingos Jr." <[EMAIL PROTECTED]> escreveu:
> Seja f(n, p) o n�mero de maneiras de pintar Z_n
> (inteiros m�dulo n) com
> p cores de forma que i e i+1 n�o recebem a mesma
> cor.
>
> Se o n � pequeno, fa�a as contas na m�o mesmo...
> Para n >= 4 j� podemos usar uma recorr�ncia:
>
> Imagine que queremos colorir Z_{n+1} com p cores da
> maneira enunciada.
> Essa colora��o vai induzir uma p-colora��o de Z_n
> (basta considerar as
> cores dadas aos elementos 0, ..., n-1). H� duas
> possibilidades:
> - a colora��o induzida � da maneira enunciada
> [sabemos que h� f(n, p)
> colora��es dessa forma]
> - a colora��o induzida � tal que n-1 e 0 tem a mesma
> cor, por�m cor(0)
> != cor(1) != cor(2) != ... != cor(n-2) != cor(n-1) =
> cor(0), mas ent�o a
> colora��o induzida em 0, ..., n-2 � da maneira
> enunciada para Z_{n-2},
> mas h� f(n-1, p) tais colora��es.
>
> No primeiro caso, a cor de n pode ser uma das p-2
> cores diferentes de
> cor(0), cor(n-1). No segundo caso, temos de evitar
> apenas cor(0) e
> portanto h� p-1 cores poss�veis.
>
> f(n, p) = (p-2) f(n-1, p) + (p-1) f(n-2, p) para n
> >= 4.
>
> Abra�os,
>
> Domingos.
>
> >Ol� a todos.
> >Como sou novo na lista, n�o sei se o problema que
> apresentarei j� foi
> >publicado aqui, mas se algu�m puder ajudar ficarei
> muito grato..
> >
> >"N casas id�nticas est�o dispostas ao longo de uma
> pra�a circular. Um
> >pintor disp�e de p cores diferentes para pintar as
> casas. De quantos
> >modos isso pode ser feito se casas adjacentes n�o
> podem ter a mesma
> >cor?"
> >Abra�os
> >Paulo Cesar
> >
>
>
=========================================================================
> 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
>
=========================================================================
>
_______________________________________________________
Yahoo! Acesso Gr�tis - Instale o discador do Yahoo! agora.
http://br.acesso.yahoo.com/ - Internet r�pida e gr�tis
=========================================================================
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
=========================================================================
