Considere a sequência constituida de 10 quadradinhos (todos congruentes).
Cada quadradinho deve ser colorido usando-se uma das seguintes cores: azul ou vermelho. Quantas são as sequências de 10 quadradinhos, nas quais não há 2 quadrinhos adjacentes vermelhos?
Solução:
Note que a quantidade de quadradinhos azuis vai de 5 a 10. Como estratégia de conta, serão colocados espaços vazios entre duas casas azuis, espaços estes que podem ser ocupados por casas vermelhas.
Todos os 10 quadrados azuis: A_A_A_A_A_A_A_A_A_A_
C11,0
9 azuis e 1 vermelho:
8 azuis e 2 vermelhos: A_A_A_A_A_A_A_A
Cy.
7 azuis e 3 vermelhos: A_A_A_A_A_A_A
6 azuis e 4 vermelhos: A_A_A_A_A_A
C
5 azuis e 5 vermelhos: A_A_A_A_A
Total:
Solução:
Note que a quantidade de quadradinhos azuis vai de 5 a 10. Como estratégia de conta, serão colocados espaços vazios entre duas casas azuis, espaços estes que podem ser ocupados por casas vermelhas.
Todos os 10 quadrados azuis: A_A_A_A_A_A_A_A_A_A_
9 azuis e 1 vermelho:
8 azuis e 2 vermelhos: A_A_A_A_A_A_A_A
7 azuis e 3 vermelhos: A_A_A_A_A_A_A
6 azuis e 4 vermelhos: A_A_A_A_A_A
5 azuis e 5 vermelhos: A_A_A_A_A
Passo 1
Temos uma sequência de
quadradinhos, cada um podendo ser azul (B) ou vermelho (V), com a restrição de que não pode haver dois V consecutivos. Esse é um problema clássico de contagem sem adjacência, e vamos usar um argumento de “vazios entre azuis” (stars and bars) para contar as sequências.
Passo 2
Suponha que haja exatamente
quadradinhos vermelhos. Então haverá
quadradinhos azuis. Para evitar V consecutivos, cada V deve ficar em um “espaço” entre duas azuis (ou nas extremidades). Esses espaços são
no total. Como não pode haver mais de um V por espaço, estamos escolhendo
espaços dentre os
disponíveis. Logo, o número de arranjos com exatamente
vermelhos é
Passo 3
O valor máximo de
vem de
Portanto
varia de
a
, e o total de sequências é
Passo 4
Vamos calcular termo a termo:
Passo 5
Somando tudo: