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

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 _

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

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.

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

• Interesting solution. Can you please explain further, in particular, the choice and use of the matrix? – hypergeometric Aug 20 '19 at 17:33
• @hypergeometric At the beginning I wanted to. But it's really a lot if you start from zero (about one course in discrete mathematics/combinatorics). But regarding the matrix: The underlying idea is that every $n\times n$ matrix represents a graph with $n$ nodes (see adjacency matrix of a graph). For a slightly modified definition of path weight (where the weight of a path is the product of its edges), we then have the result that for a matrix $A$ interpreted as a graph, the cell $(i,j)$ in $A^n$ is the sum of all paths of length $n$ from node $i$ to node $j$. – Sudix Aug 20 '19 at 17:48
• Thanks. Will explore further. This looks like a neat approach which can be applied to the general case, without having to consider cases and sub-cases in the process of counting. – hypergeometric Aug 20 '19 at 17:51

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.

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

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.

• Wouldn't this be akin to swapping the A's with the B's? That would mean multiplying 360 by 2 to get 720 but that still doesn't yield the right answer though. – Chung Ren Khoo Aug 13 '19 at 15:12
• Not necessarily, both of A's and B's could be in that gap. – Ekin Aug 13 '19 at 15:14

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