De quantos modos podemos formar uma sequência de p elementos iguais a 2, q elementos iguais a 1 e r 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 p+q+r contendo exatamente p símbolos 2, q símbolos 1 e r 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 p símbolos 2 e os q símbolos 1, ignorando momentaneamente os zeros. O número de permutações desses p+q elementos repetidos é
(p+q)!p!,q!

Passo 3

Agora inserimos os r zeros sem deixá-los adjacentes. Uma disposição de p+q elementos cria p+q+1 lacunas (entre cada par de elementos e nas extremidades). Como não podemos pôr mais de um zero na mesma lacuna, escolhemos r lacunas dentre as p+q+1 disponíveis, o que pode ser feito de
binomp+q+1r
formas, desde que r<= p+q+1 (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:
(p+q)!p!,q!,binomp+q+1r

Resposta

(p+q)!p!,q!,binomp+q+1r

Exercícios de Livros Relacionados