De quantos modos podemos formar uma sequência de
elementos iguais a
elementos iguais a 1 e
elementos iguais a 0 se dois elementos iguais a zero não podem ser adjacentes?
Passo 1
O enunciado pede o número de sequências de comprimento
contendo exatamente
símbolos 2,
símbolos 1 e
símbolos 0, sob a restrição de que não haja dois zeros adjacentes. Para resolver, vamos usar contagem de permutações com repetição e o método das lacunas (slots) para impor a não-adjacência dos zeros.
Passo 2
Primeiro, organizamos apenas os
símbolos 2 e os
símbolos 1, ignorando momentaneamente os zeros. O número de permutações desses
elementos repetidos é
Passo 3
Agora inserimos os
zeros sem deixá-los adjacentes. Uma disposição de
elementos cria
lacunas (entre cada par de elementos e nas extremidades). Como não podemos pôr mais de um zero na mesma lacuna, escolhemos
lacunas dentre as
disponíveis, o que pode ser feito de
formas, desde que
(caso contrário o número de sequências é zero).
Passo 4
Pelo princípio multiplicativo, o total de sequências é o produto dos resultados dos passos 2 e 3: