*14. Quantas permutações de 26 letras do alfabeto inglês não contêm qualquer uma das seqüências fish, rat ou bird?
Passo 1
O enunciado pede o número de permutações das 26 letras do alfabeto que não contenham nenhuma das sequências “fish” (4 letras), “rat” (3 letras) ou “bird” (4 letras) como bloco contíguo. Vamos usar o princípio da inclusão–exclusão, tratando cada sequência proibida como um “superbloco”.
Passo 2
Definimos:
A = permutações contendo “fish” como bloco,
B = permutações contendo “rat” como bloco,
C = permutações contendo “bird” como bloco.
A = permutações contendo “fish” como bloco,
B = permutações contendo “rat” como bloco,
C = permutações contendo “bird” como bloco.
Para contar
, unimos as 4 letras de “fish” num único objeto, ficando
objetos distintos. Logo
De modo análogo, unindo “rat” (3 letras) ficamos com
objetos, então
e unindo “bird” (4 letras) temos novamente 23 objetos, logo
Passo 3
Agora as interseções:
– : “fish” e “rat” não compartilham letras, então podemos tratar os dois como blocos independentes, totalizando
–
objetos, de modo que
–
: “fish” e “bird” têm em comum a letra
, não é possível formar ambas as sequências simultaneamente (não há sobreposição compatível), logo
–
: “rat” e “bird” compartilham a letra
sem permitir sobreposição válida, portanto
E obviamente
Passo 4
Pelo princípio da inclusão–exclusão, o total de permutações que contêm pelo menos uma sequência proibida é
Assim, o número de permutações que não contêm nenhuma das sequências é