How many different arrangements are there problem

Question

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|

Answer 1

Let $A_i$ be the set of arrangements with at least 2 consecutive letters of type $i$, where $1\le i\le3$.

Then $\displaystyle|\overline{A_1}\cap\overline{A_2}\cap\overline{A_3}|=|S|-\sum_{i}|A_i|+\sum_{i<j}|A_i\cap A_j|-|A_1\cap A_2\cap A_3|,\;\;$ where $\displaystyle|S|=\frac{9!}{3!3!3!}=\color{blue}{1680}$.

1) To find $|A_i|$, we will count the number of arrangements of AA, A, B, B, B, C, C, C and then

$\;\;\;$adjust for overcounting, which gives $\displaystyle \frac{8!}{3!3!}-\frac{7!}{3!3!}=\color{blue}{980}$.

2) To find $|A_i\cap A_j|$, we will count the number of arrangements of AA, A, BB, B, C, C, C and then

$\;\;\;$adjust for overcounting, which gives $\displaystyle\frac{7!}{3!}-2\cdot\frac{6!}{3!}+\frac{5!}{3!}=\color{blue}{620}$.

3) To find $|A_1\cap A_2\cap A_3|$, we will count the number of arrangements of AA, A, BB, B, CC, C and then

$\;\;\;$adjust for overcounting, which gives $\displaystyle6!-3\cdot5!+3\cdot4!-3!=\color{blue}{426}$.

Therefore $\displaystyle|\overline{A_1}\cap\overline{A_2}\cap\overline{A_3}|=1680-3\cdot980+3\cdot620-426=\color{red}{174}$.

Answer 2

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

Answer 3

A way to find $|a|$.

Let $i,k$ be nonnegative integers and let $j$ be a positive integer (also see the comment of Joriki).

Only looking at $B$'s and $C$'s there are $\binom{6}{3}$ arrangements for them.

Concerning $iAAAk$: for $i+k=6$ there are $\binom{7}{1}$ solutions.

Concerning $iAAjAk$: for $i+j+k=6$ there are $\binom{7}{2}$ solutions.

Concerning $iAjAAk$: for $i+j+k=6$ there are $\binom{7}{2}$ solutions.

This lead to $\left|a\right|=\binom{6}{3}\left[\binom{7}{1}+\binom{7}{2}+\binom{7}{2}\right]$.

Above integer $i$ stands for the number of non $A$'s that precede the first $A$ and $j$ and $k$ are sortlike. The context should be enough.