Re: [obm-l] Combinatória.

["Domingos Jr." <dopikas@xxxxxxxxxx>]

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