3
$\begingroup$

Just a little combinatorial theory problem I am having trouble wrapping my head around. It has to do with rearrangement of a string of letters:

Determine the number of rearrangements of the string AAABBBCCC that do not contain three consecutive letters of the same type

2 Answers 2

1

It's probably easier to determine the number that do. If all three As are in a row, there are $7$ positions for the As and $\binom63=20$ positions for the Bs and Cs, for a total of $140$. The same for all three Bs and all three Cs, makes 420. Now we've double-counted the ones where all As and all Bs are in a row – that leaves $\binom53=10$ positions for the Cs, times $2$ for whether the As or the Bs come first, and the same again for all As and all Cs and for all Bs and all Cs, so substract $60$. But now we've triple-counted and triple-uncounted the $6$ possibilities where they're all in a row, so add those back in to get $420-60+6=366$. Subtract that from the total number $\binom{9}{3,3,3}=1680$ to get $1680-366=1314$.

In the meantime EuYu has posted an answer that expresses the same thing more systematically, and you immediately accepted it, but I'll post this anyway since it contains some explanations of EuYu's numbers.

1

You can use the principle of inclusion and exclusion. $p - p_A - p_B - p_C + p_{A,B} + p_{A,C} + p_{B,C} - p_{A,B,C}$ where there $p$s denote the number of permutations in which the letters of the subscript are together, i.e. $p_{A,B}$ denote the number of permutations in which the $A$s and the $B$s are grouped in three.

It is a bit tedious, but we end up with $1680 - 3\times 140 + 3\times 20 - 6 = 1314$ possible rearrangements.