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 diz: um círculo foi dividido em n setores ( n\geqslant 2). Queremos colorir cada setor com exatamente uma cor, usando um conjunto de k cores diferentes ( k>2), de modo que setores adjacentes tenham cores diferentes. A pergunta é: de quantos modos distintos podemos fazer essa coloração?
Informações relevantes que o enunciado dá:
  • O número de setores é n.
  • O número de cores disponíveis é k.
  • Setores adjacentes não podem ter a mesma cor.
  • Cada setor recebe exatamente uma cor.
  • Devemos contar todas as colorações possíveis que satisfaçam a restrição.

Passo 2

Vamos numerar os setores ao redor do círculo como 1,2,\dots,n no sentido horário. Assim, a restrição “adjacentes não têm a mesma cor” significa que, para cada i, a cor do setor i deve ser diferente da cor do setor i+1, com a convenção n+1\equiv 1 (ou seja, o setor n também não pode ter a mesma cor que o setor 1).
Uma técnica útil é “cortar” o círculo em algum ponto (por exemplo entre os setores n e 1) e considerar primeiro o caminho linear de 1 a n (onde 1 e n já não são obrigatoriamente diferentes); depois impomos a condição adicional que a cor de 1 deve ser diferente da cor de n. Assim, contaremos colorings de um caminho e extrairemos dali as colorings válidas para o ciclo.

Passo 3

Para organizar a contagem, fixo a cor do setor 1 (isso facilita porque depois multiplicamos pelo número de escolhas para a cor de 1). Seja c essa cor fixa. Para m\geqslant 1 considere os colorings do caminho de vértices 1,2,\dots,m com a cor de 1 igual a c e que respeitam a restrição de adjacência entre vértices consecutivos. Defino:
  • s_m = número de colorings do caminho 1,\dots,m (com cor de 1 = c) tais que a cor do vértice m é igual a c.
  • d_m = número de colorings do caminho 1,\dots,m (com cor de 1 = c) tais que a cor do vértice m é diferente de c.
Note que essas quantidades depend só de m e de k, não de qual cor específica c escolhemos, porque todas as cores são simétricas.
O número total de colorings do caminho 1,\dots,n com cor de 1 fixa é s_n + d_n. Mas as colorings do ciclo correspondem apenas àquelas do caminho cujo vértice n tem cor diferente de c (pois no ciclo n e 1 são adjacentes). Assim, para uma cor fixa c teremos d_n colorings válidas; como há k escolhas possíveis para c, o total de colorings do ciclo será k\cdot d_n. Logo nosso objetivo passa a ser determinar d_n.

Passo 4

Base inicial (casos pequenos), com cor de 1 fixa:
  • Para m=1: só o vértice 1 com cor c. Então s_1=1 e d_1=0.
  • Para m=2: o vértice 2 deve ter cor diferente de 1, então há k-1 escolhas. Assim s_2=0 e d_2=k-1.
Esses valores servirão para iniciar uma recorrência.

Passo 5

Vamos relacionar s_m e d_m com os termos anteriores, pensando em como construir colorings de tamanho m a partir de colorings de tamanho m-1.
  • Para obter um coloring de tamanho m com o vértice m igual a c (contador s_m), o vértice m-1 obrigatoriamente deve ter cor diferente de c. Portanto cada coloring contado em s_m corresponde a um coloring de tamanho m-1 contado em d_{m-1}, e a cor do m-ésimo vértice fica determinada como c. Logo
s_m = d_{m-1}.
  • Para obter um coloring de tamanho m com o vértice m diferente de c (contador d_m), existem duas possibilidades quanto à cor do vértice m-1:
    1. Se o vértice m-1 tem cor c (há s_{m-1} colorings assim), então o vértice m pode ser qualquer uma das k-1 cores diferentes de c. Contribuição: s_{m-1}\,(k-1).
    2. Se o vértice m-1 tem cor diferente de c (há d_{m-1} colorings assim), digamos que essa cor seja x\neq c; então o vértice m não pode ser x nem c, ficando k-2 escolhas. Contribuição: d_{m-1}\,(k-2).
Somando as duas contribuições:
d_m = s_{m-1}(k-1) + d_{m-1}(k-2).

Passo 6

Usando s_{m-1}=d_{m-2} (da relação acima aplicada com índice m-1), podemos eliminar s e obter uma recorrência apenas em d_m:
d_m = d_{m-2}(k-1) + d_{m-1}(k-2).
Reescrevendo:
d_m = (k-2)\,d_{m-1} + (k-1)\,d_{m-2},\qquad \text{para } m\geqslant 3,
com condições iniciais d_1=0 e d_2=k-1.

Passo 7

Agora resolvemos essa recorrência linear homogênea de ordem 2 com coeficientes constantes. A equação característica é
r^2 - (k-2)r - (k-1) = 0.
Calculando o discriminante e as raízes:
\Delta = (k-2)^2 + 4(k-1) = k^2,
logo as raízes são
r = \frac{(k-2)\pm k}{2}.
Isso dá as duas raízes simples
r_1 = k-1,\qquad r_2 = -1.
Portanto a solução geral da recorrência tem a forma
d_m = A\,(k-1)^m + B\,(-1)^m,
onde A e B são constantes a determinar a partir das condições iniciais.

Passo 8

Usamos d_1=0 e d_2=k-1 para achar A e B.
Para m=1:
0 = d_1 = A(k-1) + B(-1) = A(k-1) - B \quad\Rightarrow\quad B = A(k-1).
Para m=2:
k-1 = d_2 = A(k-1)^2 + B(+1) = A(k-1)^2 + B.
Substituindo B = A(k-1):
k-1 = A\bigl((k-1)^2 + (k-1)\bigr) = A(k-1)\,k.
Como k-1\neq 0, podemos dividir por k-1 e obter 1 = A k, portanto
A = \frac{1}{k},\qquad B = \frac{k-1}{k}.
Assim
d_m = \frac{1}{k}(k-1)^m + \frac{k-1}{k}(-1)^m.

Passo 9

Lembrando que o número total de colorings do ciclo é k vezes d_n (pois multiplicamos pelas k escolhas para a cor do vértice 1), obtemos:
\text{Número de colorings} = k\cdot d_n = k\left(\frac{1}{k}(k-1)^n + \frac{k-1}{k}(-1)^n\right) = (k-1)^n + (k-1)(-1)^n.ú

Passo 10

Uma checagem rápida para ganhar confiança: se n=3 (triângulo) e k=3 cores, a fórmula dá
(3-1)^3 + (3-1)(-1)^3 = 2^3 - 2 = 8-2=6,
que é o número conhecido de colorings próprios do triângulo com 3 cores (equivalente a permutações de 3 cores na roda), então faz sentido.

Resposta

(k-1)^n + (-1)^n (k-1)

Exercícios relacionados