Word Permutations

Question

How many words can we build using exactly 5 A's, 5 B's and 5 C's if the first 5 letters cannot be A's, the second 5 letters cannot be B's and the third 5 letters cannot be C's?

Can anyone help me? I have been trying many ways of doing this, all to no avail.

Answer 1

This is a good exercise in the Inclusion-Exclusion principle. I'll give you a hint.

Let's try to count in a generic way the number of strings with 1A, 1B, 1C if the first letter is not A, and the second is not B and the third is not C.

You need

xxx - Axx - xBx + ABx - xxC + AxC + xBC - ABC

Note that strings with 2 unknowns like Axx have 2! choices, with one x -- only 1!, so we get

$$3! - 2! - 2! + 1! - 2! + 1! + 1! -1 = 6-2-2+1-2+1+1-1=2,$$

which is obviously correct (in our simple case, they are BCA and CAB).

Can you extend this to your case? Try with 2 letters first, it will be simpler to extend to 3 and then to 5 then.

Answer 2

First place the $A$'s. Since they cannot go in the first five spaces, there are $_{10}C_5$ arrangements.

Then, place the $B$'s. First, we must fill all of the empty spaces left in the last five before filling the others, because the $C$'s cannot go in the last five.

There are $n = 0 ... 5$ empty spaces in the last five to fill. After those are filled, the remaining $B$'s go in the first five spaces, which are all empty now (the $A$'s didn't go there).

We need to count the number of combinations for each case $n = 0 ... 5.$

For $n=0$, all five $B$'s go into the first five.

For $n=1$, one $B$ goes in the empty spot in the last five, and we choose where the other four go in the first five: $_5C_4$.

For $n=2$, two $B$'s go in the empty spots in the last five, and we choose where the remaining three go in the first five spaces: $_5C_3$.

For the other cases, there are $_5C_{5-n}$ choices.

The $C$'s go where's left.

So, the total number of combinations is $$_{10}C_5(_5C_0 + _5C_1 + _5C_2 + _5C_3 + _5C_4 + _5C_5) = 8064.$$