Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

2 Answers 2

up vote 1 down vote accepted

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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.