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