8
$\begingroup$

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|

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Rishi Sep 4 '15 at 15:35
  • 2
    $\begingroup$ @Rishi I advice you to copy your comment (your efforts uptil now) and paste it in the question. This will prevent downvotes of your question. $\endgroup$ – drhab Sep 4 '15 at 15:39
  • 1
    $\begingroup$ See also math.stackexchange.com/questions/1060583 $\endgroup$ – user84413 Sep 5 '15 at 20:23
3
$\begingroup$

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

$\endgroup$
5
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Perhaps to avoid confusion it's worth adding that in $iAAjAk$ and $iAjAAk$, the restriction $j\ne0$ is implied (otherwise there would be $\binom82$ solutions each). The case $j=0$ is handled separately to avoid counting it twice. Alternatively, it could be included and then subtracted to correct for the overcount: $\binom63\left[\binom82+\binom82-\binom71\right]$. $\endgroup$ – joriki Sep 4 '15 at 17:45
  • $\begingroup$ @N.F.Taussig This answer for $|a|$ looks right to me. $\endgroup$ – user84413 Sep 4 '15 at 18:33
  • $\begingroup$ @user84413 I withdraw the comment. I had not realized what $|a|$ represented. $\endgroup$ – N. F. Taussig Sep 4 '15 at 18:41
  • $\begingroup$ @N.F.Taussig Thanks for your reply (and for your answer). $\endgroup$ – user84413 Sep 4 '15 at 18:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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