Com k cores e n regiões dispostas em sequência, onde regiões adjacentes não podem ter a mesma cor, quantas colorações possíveis existem?

\(k(k-1)^{\,n-1}\)

Explicação:
Escolhe-se a cor da primeira região em \(k\) opções, cada região seguinte tem \(k-1\) opções por não poder repetir a cor da região imediatamente anterior, aplicando o princípio fundamental da contagem multiplicamos as escolhas.

Exemplo:
Se há 4 cores e 5 regiões em sequência, o total é
\(4\times(4-1)^{5-1}=4\times3^{4}=4\times81=324\).