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