Number of anagrams of 'AABBCCDD' that have no repeated letters.

Question

I am seeking to find the number of anagrams of 'AABBCCDD' (that is strings with 2 A's, 2 B's, 2 C's and 2 D's). That have no repeated letters. So far my thoughts have been to find the total number of anagrams and subtract it from the number of anagrams that do have repeated letters. Now my calculation for the total number of anagrams for this eight letter string is:

$8! / 16$

I got this from taking the generic $8!$ number of anagrams for an eight letter string and dividing out by $(2! * 2! * 2! *2!)$ to account for the 4 letters that have repetition. I am stuck at this point because I am unsure how to count the number of anagrams that do have repeated letters.

Answer 1

Hint: Try Inclusion/Exclusion.

To continue with your approach, let us count the "bad" strings.

First count how many strings have AA. Think of this as a single letter. The number of strings with AA is $\frac{7!}{2^3}$.

If we multiply by $4$, we get our first estimate of the number of bads, which is $4\cdot \frac{7!}{2^3}$. Note that it is wildly off. But it's a start.

However, $4\cdot \frac{7!}{2^3}$ double counts the bad strings that have, for example, an AA and a BB. Count these. There are $\frac{6!}{2^2}$ of them. There are $\binom{4}{2}$ ways of choosing two doubled letters, so our new estimate of the number of bads is $4\cdot \frac{7!}{2^3}-\binom{4}{2}\frac{6!}{2^2}$.

But we have subtracted too much, for we have subtracted one too many times the words that have three doubled letters. Continue, its almost over.