Re: [obm-l] Combinatória.

[Johann Peter Gustav Lejeune Dirichlet <peterdirichlet2003@xxxxxxxxxxxx>]

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." <dopikas@uol.com.br> 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
=========================================================================