How many permutations of the English alphabet do not contain and of the strings "fish", "rat", or "bird"?
No repetition...obviously.
Hello, chickeneaterguy!
I have an imcomplete solution.
Maybe someone can finish it?
How many permutations of the English alphabet do not contain
any of the strings FISH, RAT, or BIRD?
No repetition . . . obviously.
There are $\displaystyle 26!$ permutations of the alphabet.
How many of these do contain FISH, RAT, or BIRD?
The permutation contains the string FISH.
FISH can appear in $\displaystyle 23$ possible positions in the permutation.
The other 22 letters can be placed in $\displaystyle 22!$ orders. .[1]
. . Hence, FISH appears in: .$\displaystyle 23\cdot 22!$ permutations.
The permutation contains the string RAT.
RAT can appear in $\displaystyle 24$ positions in the permutation.
The other 23 letters can be placed in $\displaystyle 23!$ orders.
. . Hence, RAT appears in: .$\displaystyle 24\cdot23!$ permutations.
The permutation contains the string BIRD.
BIRD can appear in $\displaystyle 23$ possible position in the permutation.
The other 22 letters can be placed in $\displaystyle 22!$ orders.
. . Hence, BIRD appears in: .$\displaystyle 23\cdot22!$ permutations.
I thought the answer is: .$\displaystyle 26! - (23\cdot22! + 24\cdot23! + 23\cdot 22!)$
. . but it is wrong.
In [1] when the other 22 letters are placed,
. . they could include the strings RAT or BIRD (or both).
I tried to eliminate this duplication,
. . but got stuck in a tangled, sticky web.
Can anyone salvage my work?
Or simply find a better approach?
You are very close! Due to having a common letter, fish and bird can't appear together, neither can rat and bird, so all we have to consider is fish and rat.
Backing up just a little, note that to count the permutations that contain "fish", we can treat "fish" as if it were a single letter, then just jump straight to 23! instead of writing 23 * 22!.
The number of permutations that contain both rat and fish is 21!
So the answer is 26! - (23! + 24! + 23!) + 21!
It is an application of the inclusion-exclusion principle.