Uma bandeira é formada de 7 listras, que devem ser pintadas de 3 cores diferentes. De quantas maneiras distintas será possível pintá-la de modo que duas listras adjacentes nunca estejam pintadas da mesma cor?
Passo 1
O enunciado pede para pintar
listras com
cores, de modo que duas listras adjacentes nunca tenham a mesma cor. Esse é um problema de contagem com restrição de cores adjacentes diferentes, que podemos resolver usando uma relação de recorrência (ou o princípio multiplicativo com restrição).
Passo 2
Seja
o número de maneiras de pintar
listras sob essa regra.
- Para a primeira listra temos
escolhas, logo - Para cada listra seguinte, como ela não pode repetir a cor da listra imediatamente anterior, temos
escolhas de cor. Assim, para ,
Passo 3
Aplicando a recorrência até
, obtemos