0
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Interesting solution. Can you please explain further, in particular, the choice and use of the matrix? $\endgroup$ – hypergeometric Aug 20 at 17:33
  • $\begingroup$ @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$. $\endgroup$ – Sudix Aug 20 at 17:48
  • $\begingroup$ 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. $\endgroup$ – hypergeometric Aug 20 at 17:51
3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Chung Ren Khoo Aug 13 at 15:12
  • $\begingroup$ Not necessarily, both of A's and B's could be in that gap. $\endgroup$ – Ekin Aug 13 at 15:14
1
$\begingroup$

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

$\endgroup$

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.