Um círculo foi dividido em n(n \geqslant 2) setores. De quantos modos podemos colori-los, cada setor com uma só cor, se dispomos de k(k>2) cores diferentes e setores adjacentes não devem ter a mesma cor?

Passo 1

O enunciado pede o número de colorações próprias de um círculo dividido em n setores, usando k cores k>2, de modo que setores adjacentes nunca tenham a mesma cor. Podemos modelar isso como o problema de colorir o grafo ciclo C_{n} com k cores, sem arestas bichromáticas.

Passo 2

Se tirássemos a aresta que liga o setor n de volta ao setor 1, obteríamos um caminho de n vértices. Nesse caso, para colorir o caminho de forma que cada vértice difira do anterior basta:
— escolher a cor do primeiro vértice de k maneiras;
— para cada um dos n-1 vértices seguintes, escolher qualquer das k-1 cores diferentes da cor do vértice imediatamente anterior.
Logo, o número de colorações desse caminho é
P(P_{n},k)\;=\;k\,(k-1)^{\,n-1}.

Passo 3

Para fechar o ciclo precisamos ainda impor que o setor n tenha cor diferente do setor 1. O polinômio cromático de C_{n} (grafo ciclo com n vértices) é um resultado clássico e vale
P(C_{n},k)\;=\;(k-1)^{n}\;+\;(-1)^{n}\,(k-1).
Ele já incorpora tanto as restrições de adjacência sequencial quanto a restrição adicional entre os vértices 1 e n.

Resposta

\boxed{(k-1)^{n} \;+\;(-1)^{n}\,(k-1)}.

Exercícios relacionados