How many different arrangements are possible such that there are no consecutive A's, B's or C's?

Question

Suppose we have 7 different items:

(A1)(A2) (B1)(B2) (C1)(C2)(C3)

How many different arrangements are possible such that there are no consecutive A's, B's or C's?

e.g. (A1)(B1)(C3)(A2)(C2)(B2)(C1) is allowed but (A1)(A2)(B1)(C1)(B2)(C2)(C3) is not allowed.

My attempt so far:

I inserted gaps between the C's

_ C1 _ C2 _ C3 _

Then, I added the A's between the C's so they would always stay separate

_ C1 A1 C2 A2 C3 _

I added more gaps

_ C1 _ A1 _ C2 _ A2 _ C3 _

And filled them with potential B's. Thus ending up with

3! (for arranging the C's) $\times$ 2! (for arranging the A's) $\times$ 6P2 (for arranging the B's in the gaps)

The answer I get from this is 360 but I was told the correct answer is 4896. Any help would be most appreciated.

Answer 1

Starting by placing the C's is indeed a good strategy. But there are 10 positions to do so, not only 1 as you restrained yourself to.

• In the case you consider, the four remaining letters stand alone, i.e. the four remaining gaps come in singletons:

.C.C.C.

Then there are $4!=24$ ways of placing the A's and B's.

• In 6 cases, the resulting gaps for A's and B's are: two singletons and one pair:

..C.C.C

.C..C.C

C.C.C..

C.C..C.

C..C.C.

.C.C..C

Each time, you have $4*2*2=16$ ways of placing the A's and B's.

• Then in two cases, you got one singleton and one triplet:

C...C.C

C.C...C

This time you got $8$ ways of disposing A's and B's (4 ways to pick the singleton, and then you can only swap the two extremities of the triplet).

• Finally there is one case with two pairs:

C..C..C

Which gives you $16$ arrangements of A's and B's (4 ways to pick the letter in first position, 2 ways for the second position, 2 ways for the third).

---

You correctly calculated that there are $6$ ways of placing the C's in a given disposition.

Summing up you got

$6*(1*16+2*8+6*16+1*24)=6*152=912$ solutions.

Which is not the result you expected.

Answer 2

Unfortunately I cannot write this as a comment, but the problem is: You cannot assume that the A's separate the C's. You don't cover (A1) (C1) (B1) (C2) (B2) (C3) (A2), for instance.

Answer 3

The arrangement $A_1C_1B_1C_2A_2C_3B_2$ satisfies the restrictions. However, your method does not count this arrangement since the $A$'s do not separate the $C$'s.

One way around this would be to consider arrangements of the forms:

$\square A \square A \square B \square B \square$

$\square A \square B \square A \square B \square$

$\square A \square B \square B \square A \square$

$\square B \square A \square A \square B \square$

$\square B \square A \square B \square A \square$

$\square B \square B \square A \square A \square$

where an $A$ represents a place $A_1$ or $A_2$ can be placed, a $B$ represents a place where $B_1$ or $B_2$ could be placed, and a square indicates a place where $C_1$, $C_2$, or $C_3$ could be placed.

$\square A \square A \square B \square B \square$: There are $2!$ ways of arranging the $A$'s and $2!$ ways of arranging the $B$'s in the indicated positions. We must place a $C$ in the square between the adjacent $A$'s and another $C$ in the square between the adjacent $B$'s. We can do this in $3 \cdot 2$ ways. We must then place a $C$ in one of the remaining three positions indicated by a square. Thus, there are $2!2! \cdot 3 \cdot 2 \cdot 3 = 72$ such arrangements.

$\square B \square B \square A \square A \square$: By symmetry, there are $72$ arrangements of this type.

$\square A \square B \square A \square B \square$: There are $2!$ ways of arranging the $A$'s and $2!$ ways of arranging the $B$'s in the indicated positions. The $C$'s can be arranged in the five spaces indicated by a square in $5 \cdot 4 \cdot 3$ ways. Hence, there are $$2!2! \cdot 5 \cdot 4 \cdot 3 = 240$$ such arrangements.

$\square B \square A \square B \square A \square$: By symmetry, there are $240$ arrangements of this type.

$\square A \square B \square B \square A \square$: There are $2!$ ways of arranging the $A$'s and $2!$ ways of arranging the $B$'s in the indicated positions. One of the three $C$'s must be placed in the square between the two $B$'s. The remaining two $C$'s can be placed in the remaining four spaces indicated by a square in $4 \cdot 3$ ways. Hence, there are $$2!2! \cdot 3 \cdot 4 \cdot 3 = 144$$ such arrangements.

$\square B \square A \square A \square B \square$: By symmetry, there are $144$ such arrangements.

Total: The number of arrangements of $A_1, A_2, B_1, B_2, C_1, C_2, C_3$ in which no $A$'s, no $B$'s, and no $C$'s are adjacent is $$2(2!2! \cdot 3 \cdot 2 \cdot 2 + 2!2! \cdot 5 \cdot 4 \cdot 3 + 2!2! \cdot 3 \cdot 4 \cdot 3) = 2(72 + 240 + 144) = 2 \cdot 456 = 912$$ in agreement with Evargalo's result.

The same result can be obtained using the Inclusion-Exclusion Principle by subtracting the number of arrangements with one or more pairs that violate the restrictions from the $7!$ arrangements of distinct letters.

Answer 4

Just to showcase the power of the tools of discrete mathematics as framework for combinatorial problems (namely, generating functions and the matrix-transfer-method):

The solution to your problem is given by

$$[x^2y^2z^3]\left(2!\cdot 2!\cdot 3!\cdot \sum\left(\begin{pmatrix} 0& y& z& 0\\ x& 0& z& 0\\ x& y& 0& 0\\ x& y& z& 0 \end{pmatrix}^7\right)_4\right) $$

I.e. we take the matrix $\begin{pmatrix} 0& y& z& 0\\ x& 0& z& 0\\ x& y& 0& 0\\ x& y& z& 0 \end{pmatrix}$, take its 7-th power and extract its 4-th row. We obtain:

$[x·(x^3·(y + z)^3 + 4·x^2·y·z·(2·y^2 + 5·y·z + 2·z^2) + 9·x·y^2·z^2·(y + z) + 2·y^3·z^3),\\ y·(x^3·(y + z)·(y^2 + 7·y·z + 2·z^2) + x^2·y·z·(3·y^2 + 20·y·z + 9·z^2) + x·y^2·z^2·(3·y + 8·z) + y^3·z^3),\\ z·(x^3·(y + z)·(2·y^2 + 7·y·z + z^2) + x^2·y·z·(9·y^2 + 20·y·z + 3·z^2) + x·y^2·z^2·(8·y + 3·z) + y^3·z^3), 0]$

Then we sum over all entries of the extracted row and multiply them by $2!2!3!$. The result is a polynomial in $x,y,z$, and using $[x^2y^2z^3]$ we extract the coefficient of $x^2y^2z^3$ of the polynomial.

We obtain the result $912$.

Answer 5

Solution on base of inclusion/exclusion.

---

Let $a$ denote the set of arrangements were the $A$'s are consecutive.

Let $b$ denote the set of arrangements were the $B$'s are consecutive.

Let $c_{1}$ denote the set of arrangements were $C_{2}$ and $C_{3}$ are consecutive.

Let $c_{2}$ denote the set of arrangements were $C_{1}$ and $C_{3}$ are consecutive.

Let $c_{3}$ denote the set of arrangements were $C_{1}$ and $C_{2}$ are consecutive.

To be found is $\left|a^{\complement}\cap b^{\complement}\cap c_{1}^{\complement}\cap c_{2}^{\complement}\cap c_{3}^{\complement}\right|=7!-\left|a\cup b\cup c_{1}\cup c_{2}\cup c_{3}\right|$.

Applying inclusion/exclusion, symmetry and $c_{1}\cap c_{2}\cap c_{3}=\varnothing$ we find at first hand that this equals:

$7!-5\left|a\right|+7\left|a\cap b\right|+3\left|c_{1}\cap c_{2}\right|-3\left|a\cap b\cap c_{1}\right|-6\left|a\cap c_{1}\cap c_{2}\right|+3\left|a\cap b\cap c_{1}\cap c_{2}\right|$

Working this out we find:

$$\left|a^{\complement}\cap b^{\complement}\cap c_{1}^{\complement}\cap c_{2}^{\complement}\cap c_{3}^{\complement}\right|=7!-5\cdot2!6!+7\cdot2!2!5!+3\cdot2!5!-3\cdot2!2!2!4!-6\cdot2!2!4!+3\cdot2!2!2!3!$$$$=912$$

Answer 6

(My own interpretation/presentation of the solution, quite similar to EvarGalo's, except that it first assumes that $A, B,C$'s are indistinguishable, with distinguishability introduced only at the last step.)

First, assume that the $A, B, C$'s are indistinguishable.

Find the number of ways to arrange AABBCCC without having two consecutive identical letters. Separate the $C$'s by spaces indicated by $P,Q,R,S$, as shown below. Each space may be filled by one or more letters, or not at all, with the exception of $Q,R$ which must contain at least one letter (hence indicated by a box). $$\large{[P]}, C,\boxed{[Q]}, C, \boxed{[R]},C, [S] $$

Consider the number of ways of filling spaces $P,Q,R,S$ with two $A$'s and two $B$'s such that there is no occurrence of $AA$ or $BB$. We will use the convention where, e.g. $PQQR$ means $1$ letter in $P$, $2$ letters in $Q$, $1$ letter in $R$.

• Case 1: "1+1+1+1" ($PQRS$)
  Choose $2$ spaces out of $4$ to fill with $A$'s. The other two will be filled with $B$'s.
  Number of ways: $$\binom 42=6$$

• Case 2: "2+1+1" ($\underline{PP}QR, P\underline{QQ}R, \underline{QQ}RS, PQ\underline{RR}, Q\underline{RR}S, QR\underline{SS}$: - $6$ possibilities)
  The double-letter space should contain either $AB$ or $BA$ ($2$ ways to chose first letter).
  The other two single spaces are left with $A,B$ or $B,A$ ($2$ ways to chose first letter).
  Number of ways: $$6\cdot 2\cdot 2 = 24$$

• Case 3: "2+2" ($\underline{QQ}\underline{RR}$)
  Each double-letter space should contain either $AB$ or $BA$ ($2$ ways to chose first letter).
  Number of ways: $$2\cdot 2 = 4$$

• Case 4: "3+1" ($Q\underline{RRR}, \underline{QQQ}R$: 2 possibilities)
  Choose $A$ or $B$ for the single-letter space. ($2$ ways).
  For the 3-letter spaces, the middle letter must be the same as the letter in the single-letter space (to separate the other two).
  Number of ways: $$2\cdot 2 = 4$$

Hence, total number of ways to arrange $AABBCCC$ without two consecutive identical letters is: $$6+24+4+4=38$$

If $AA, BB, CCC$ are distinguishable:
then the number of possible arrangements is $$2!\cdot 2!\cdot 3!\cdot 38 = 24\cdot 38 = 912 \;\blacksquare$$

---

(Alternative approach, using Inclusion-Exclusion Principle)

Assume that same letters are indistinguishable.

Let

• $\overline{a}$ = number of arrangements where some/all $A$ are adjacent, (i.e. not separate).

• $\dot{a}$ = number of arrangements where all $A$'s are separate (i.e. none are adjacent).

and similarly for $\overline{b}, \overline{c}, \dot{b}, \dot{c}$.

Let

• $\cal E$ = total number of arrangements to arrange $7$ letters, $AABBCCC$, where the repeats of the same letters are indistinguishable.
• $\cal J$= number of arrangements where at least some letters are adjacent to a similar letter.

We want to find $\dot{a}\dot {b}\dot {c}$.

Note that:

$$\begin{align} \overline {a}&=\boxed{AA}BBCCC=\frac {6!}{2!3!}&&=60\\ \overline{b}&=\overline{a} &&=60\qquad \text{(by symmetry)}\\ \overline{c}&=AABB\boxed{CC}C-AABB\boxed{CCC} =\frac {6!}{2!2!}-\frac {5!}{2!2!}&&=150\\ \overline{a}\overline{b}&=\boxed{AA}\boxed{BB}CCC=\frac {5!}{3!}&&=20\\ \overline{b}\overline{c}&=AA\boxed{BB}\boxed{CC}C-AA\boxed{BB}\boxed{CCC} =\frac {5!}{2!2!}-\frac {4!}{2!2!}&&=48\\ \overline{c}\ \overline{a}&= \overline{b}\overline{a}&&=48\qquad \text{(by symmetry)}\\ \overline{a}\overline{b}\overline{c}&=\boxed{AA}\boxed{BB}\boxed{CC}C-\boxed{AA}\boxed{BB}\boxed{CCC}=4!-3!&&=18\\\\ \text{Note that}\\ \cal E&=\frac {7!}{2!2!3!}&&=210\\ \text{By Inclusion-Exclusion}&\text{ Principle},\\ \cal J&=\overline{a}+\overline{b}+\overline{c}-\overline{a}\overline{b}-\overline{b}\overline{c}-\overline{c}\ \overline{a}+\overline{a}\overline{b}\overline{c}\\ &=60+60+150-20-48-48+18&&=172\\\\ \text {Number of ways }&\text{to arrange }AABBCCC \text{ without adjacent identical letters is }\\ \; \; \dot{a}\dot{b}\dot{c}&=\cal {E}-\cal {J} = 210-172 &&=38\\ \end{align}$$

If $A,B,C$'s are distinguishable,

then number of ways to arrange $AABBCCC$ without adjacent identical letters is $$2!2!3!\times \dot{a}\dot{b}\dot{c}=2!2!3!\cdot 38 = 912\qquad\blacksquare$$