How many different arrangements are there of all the nine letters A, A, A, B, B, B, C, C, C in a row if no two of the same letters are adjacent?
First I tried to find how many ways to arrange so at least two similar letters are adjacent (the complementary) then subtract from total ways without restriction. I tried to do this via extended addition rule (i.e. with the three circle venn diagram) and now I'm confused how to calculate each case.
My attempt so far:
let a be set of 'two A's adjacent to each other'
let b be set of 'two B's adjacent to each other'
let c be set of 'two C's adjacent to each other'
I need to find |complement of a U b U c| (Let Z be universal set, no restriction)
= |Z| – |a| – |b| – |c| + |ab| + |bc| + |ca| – |abc|
I know |a| = |b| = |c| and |ab| = |bc| = |ca|
therefore |complement of a U b U c| = |Z| – 3|a| + 3|ab| -|abc|.
|Z| = 9!/3!3!3!, but I'm not sure how to compute |a| or |ab| or |abc|
Best Answer
There are $\binom{6}{3} = 20$ sequences of three $A$'s and three $B$'s. Consider the ten sequences of three $A$'s and three $B$'s that begin with an $A$.
$\color{red}{AAABBB}$
$\color{green}{AABABB}$
$\color{green}{AABBAB}$
$\color{blue}{AABBBA}$
$\color{green}{ABAABB}$
$\color{cyan}{ABABAB}$
$\color{magenta}{ABABBA}$
$\color{green}{ABBAAB}$
$\color{magenta}{ABBABA}$
$\color{blue}{ABBBAA}$
No matter how we place $C$'s in the sequence $\color{red}{AAABBB}$, at least two consecutive letters will be the same.
There is only one way to place the $C$'s in the sequences $\color{blue}{AABBBA}$ and $\color{blue}{ABBBAA}$ since we are forced to place a $C$ between each pair of consecutive $B$'s and the pair of consecutive $A$'s.
The number of ways we can fill three of the seven spaces (the beginning, the end, and the five spaces between consecutive letters) in the sequence $\color{cyan}{ABABAB}$ is $\binom{7}{3}$.
We must place a $C$ between the pair of consecutive $B$'s in the sequences $\color{magenta}{ABABBA}$ and $\color{magenta}{ABBABA}$, which leaves us $\binom{6}{2}$ ways to insert the two remaining $C$'s in the six remaining spaces.
We must place one $C$ between the pair of consecutive $A$'s and another $C$ between the pair of consecutive $B$'s in the sequences $\color{green}{AABABB}$, $\color{green}{AABBAB}$, $\color{green}{ABAABB}$, $\color{green}{ABBAAB}$, leaving five spaces in which to place the remaining $C$.
Hence, the number of sequences of three $A$'s, three $B$'s, and three $C$'s that begin with $A$ that do not contain consecutive letters that are the same is $$1 \cdot 0 + 2 \cdot 1 + 2 \cdot \binom{6}{2} + 4 \cdot \binom{5}{1} + 1 \cdot \binom{7}{3} = 0 + 2 + 30 + 20 + 35 = 87$$ By symmetry, there are also $87$ such sequences that begin with a $B$. Hence, the number of sequences of three $A$'s, three $B$'s, and three $C$'s that do not contain consecutive letters that are the same is $2 \cdot 87 = 174$.