De quantos modos podemos formar uma sequência de
elementos iguais a 1 e
elementos iguais a 0 se dois elementos iguais a zero não podem ser adjacentes?
Passo 1
O enunciado quer contar o número de sequências de comprimento
formadas por exatamente
uns e
zeros, sujeitas à restrição de que não apareçam dois zeros consecutivos. O conteúdo é contagem de sequências com restrição de adjacência, que vamos tratar com um argumento de “vãos” entre os uns.
Passo 2
Imagine colocar primeiro os
uns em fila. Entre esses uns e também antes do primeiro e depois do último há exatamente
vãos onde os zeros podem eventualmente ser inseridos. Para garantir que não haja dois zeros adjacentes, permitimos no máximo um zero em cada vão.
Passo 3
Como precisamos inserir precisamente
zeros e cada zero deve ficar num vão distinto, basta escolher quais
vãos dentre os
disponíveis vão receber um zero. O número de maneiras de escolher
vãos de um total de
é dado por
Passo 4
Portanto, o total de sequências procurado é
com a convenção de que se
então
, refletindo a impossibilidade de colocar mais zeros do que vãos.