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 permutations of the alphabet.
How many of these do contain FISH, RAT, or BIRD?
The permutation contains the string FISH.
FISH can appear in possible positions in the permutation.
The other 22 letters can be placed in orders. .[1]
. . Hence, FISH appears in: . permutations.
The permutation contains the string RAT.
RAT can appear in positions in the permutation.
The other 23 letters can be placed in orders.
. . Hence, RAT appears in: . permutations.
The permutation contains the string BIRD.
BIRD can appear in possible position in the permutation.
The other 22 letters can be placed in orders.
. . Hence, BIRD appears in: . permutations.
I thought the answer is: .
. . 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.