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_ \rightarrow C11,0 =1
9 azuis e 1 vermelho: A_{-} A_{-} A_{-} A_{-} A_{-} A_{-} A_{-} A_{-} A_{-} \rightarrow C_{10.1}=10
8 azuis e 2 vermelhos: A_A_A_A_A_A_A_A \rightarrow Cy. 2=36
7 azuis e 3 vermelhos: A_A_A_A_A_A_A \rightarrow \mathrm{C}_{8,3}=56
6 azuis e 4 vermelhos: A_A_A_A_A_A \rightarrow C 7.4=35
5 azuis e 5 vermelhos: A_A_A_A_A \rightarrow C_{6.5}=6
Total: 1+10+36+56+35+6=144

Passo 1

Temos uma sequência de 10 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 k quadradinhos vermelhos. Então haverá 10-k 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 (10-k)+1 no total. Como não pode haver mais de um V por espaço, estamos escolhendo k espaços dentre os 10-k+1 disponíveis. Logo, o número de arranjos com exatamente k vermelhos é
\binom{(10-k)+1}{k} \;=\;\binom{11-k}{k}.

Passo 3

O valor máximo de k vem de
11-k\ge k\quad\Longrightarrow\quad k\le5.
Portanto k varia de 0 a 5, e o total de sequências é
\sum_{k=0}^{5}\binom{11-k}{k}.

Passo 4

Vamos calcular termo a termo:
\binom{11}{0}=1,\quad \binom{10}{1}=10,\quad \binom{9}{2}=36,\quad \binom{8}{3}=56,\quad \binom{7}{4}=35,\quad \binom{6}{5}=6.

Passo 5

Somando tudo:
1 + 10 + 36 + 56 + 35 + 6 = 144.

Resposta

144 sequênciais.

Exercícios de Livros Relacionados