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.
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.$$
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.
