*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.
Para contar |A|, unimos as 4 letras de “fish” num único objeto, ficando 26-(4-1)=23 objetos distintos. Logo
|A| = 23!\,.
De modo análogo, unindo “rat” (3 letras) ficamos com 26-(3-1)=24 objetos, então
|B| = 24!\,,
e unindo “bird” (4 letras) temos novamente 23 objetos, logo
|C| = 23!\,.

Passo 3

Agora as interseções:
A\cap B: “fish” e “rat” não compartilham letras, então podemos tratar os dois como blocos independentes, totalizando
26-(4-1)-(3-1)=21
objetos, de modo que
|A\cap B| = 21!\,.
A\cap C: “fish” e “bird” têm em comum a letra i, não é possível formar ambas as sequências simultaneamente (não há sobreposição compatível), logo
|A\cap C| = 0.
B\cap C: “rat” e “bird” compartilham a letra r sem permitir sobreposição válida, portanto
|B\cap C| = 0.
E obviamente
|A\cap B\cap C| = 0.

Passo 4

Pelo princípio da inclusão–exclusão, o total de permutações que contêm pelo menos uma sequência proibida é
|A\cup B\cup C| = |A|+|B|+|C| - |A\cap B| - |A\cap C| - |B\cap C| + |A\cap B\cap C| = 23! + 24! + 23! - 21! - 0 - 0 + 0 = 24! + 2\cdot23! - 21!.
Assim, o número de permutações que não contêm nenhuma das sequências é
26! - \bigl(24! + 2\cdot23! - 21!\bigr).

Resposta

26! \;-\; 24! \;-\; 2\,23! \;+\; 21!

Exercícios de Livros Relacionados