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