Find the number of rearrangements of AABBBCCDDD where there are no two consecutive As or Bs

Question

I tried using inclusion exclusion where set $A$ is all the rearrangements where two $A$s are consecutive and set $B$ where two $B$s are consecutive. However, I got $8400$ which is incorrect. I think it has to do with there being $3$ $B$s so I am somehow counting them wrong.

This was my process:

Total rearrangements of $AABBBCCDDD:$ ${10\choose 2,3,2,3} = 25200$

$\left|A\right| = {9\choose 1,3,2,3} = 5040$

$\left|B\right| = {9\choose 2,1,1,2,3} = 15120$

$\left|AB\right| = {8\choose 1,1,1,2,3} = 3360$

$A\cup B = 25200 -(5040+15120)+3360 = 8400$

Any help or guidance would be extremely appreciated.

Answer 1

We wish to find the number of arrangements of AABBBCCDDD in which no two As are adjacent and no two Bs are adjacent.

As you found, the number of distinguishable permutations of AABBBCCDDD is $$\binom{10}{2, 3, 2, 3}$$ From these, we must subtract those arrangements with at least one pair of adjacent As or adjacent Bs.

A pair of adjacent identical letters: If a pair of As are adjacent, then we have nine objects to arrange: AA, B, B, B, C, C, D, D, D. As you found, they can be arranged in $$\binom{9}{1, 3, 2, 3}$$ ways.

If a pair of Bs are adjacent, then we have nine objects to arrange: A, A, BB, B, C, C, D, D, D. As you found, they can be arranged in $$\binom{9}{2, 1, 1, 2, 3}$$ ways.

Two pairs in which the letters in each pair are adjacent identical letters: There are two possibilities, either there is a pair of adjacent As and a pair of adjacent Bs or there are two pairs of adjacent Bs. As angryavian pointed out in the comments, you overlooked the second case.

If there is a pair of adjacent As and a pair of adjacent Bs, we have eight objects to arrange: AA, BB, B, C, C, D, D, D. As you found, they can be arranged in $$\binom{8}{1, 1, 1, 2, 3}$$ ways.

If there are two pairs of adjacent Bs, the three Bs must be consecutive. Again, we have eight objects to arrange: A, A, BBB, C, C, D, D, D. The number of ways they can be arranged is $$\binom{8}{2, 1, 2, 3}$$

Three pairs in which the letters in each pair are adjacent identical letters: For this to occur, the two As must be adjacent and the three Bs must be consecutive. Hence, we have seven objects to arrange: AA, BBB, C, C, D, D, D. The objects can be arranged in $$\binom{7}{1, 1, 2, 3}$$ ways.

Hence, by the Inclusion-Exclusion Principle, the number of arrangements of AABBBCCDDD in which no two As are adjacent and no two Bs are adjacent is $$\binom{10}{2, 3, 2, 3} - \binom{9}{1, 3, 2, 3} - \binom{9}{2, 1, 1, 2, 3} + \binom{8}{1, 1, 1, 2, 3} + \binom{8}{2, 1, 2, 3} - \binom{7}{1, 1, 2, 3}$$

Answer 2

Leaving out the $B's$ for the moment, there are $\dfrac{7!}{3!2!2!} = 210$ permutations of $AACCDDD$

Of these $\dfrac{6!}{3!2!} = 60$ will have the $A's$ together, thus $150$ will have the $A's$ apart.

For the together cases, let us borrow a $B$ to separate them, e.g. $\boxed{ABA}CCDDD$

The remaining $2\; B's$ can be inserted in the gaps between units (including ends) in $\binom72$ ways

For cases with $A's$ already separate, e.g. $ACACDDD$, the $3\; B's$ can be inserted similarly in $\binom83$ ways.

Thus permissible permutations $= 60\binom72 + 150\binom83 = 9660$

Answer 3

Normally, I would automatically attack this problem with Inclusion-Exclusion. However, since the answer of N.F.Taussig beat me to it, I will go ahead and use the (alternative) direct approach for the problem.

To me, the real challenge in the direct approach is identifying all of the satisfying ways that the $3$ B's and $2$ A's can be distributed. This is because for each satisfying way of distributing the $3$ B's and $2$ A's, there will then be $~\displaystyle \binom{5}{2} = 10~$ ways of distributing the $2$ C's and $3$ D's in the remaining $5$ positions.

It turns out that the enumeration of the A's and B's can be greatly simplified via Stars and Bars analysis.

First, consider the number of non-negative integer solutions to

$$x_1 + x_2 + x_3 + x_4 + x_5 + x_6 = 5 ~: ~\binom{10}{5} = 252 ~\text{solutions}. \tag1 $$

Here, the variables $x_1, \cdots, x_6$ represent the gaps before and after the [$3$ B's and $2$ A's]. However, the computation of $252$, shown in (1) above is wrong. For example, consider the following two placements:

• B,A,B,A,B
• B,B,A,B,A

In the 1st placement above, it is allowable to have any of the $6$ variables $x_1, \cdots, x_6$ equal to $0$. However, in the 2nd placement above (for example), because there are $2$ consecutive B's, it is not okay to have $x_2 = 0.$

Shown below, are the $10$ different ways that the $2$ A's and $3$ B's might be ordered. With each such way, the corresponding added constraints on the variables are shown.

---

A,A,B,B,B $~~: ~~x_2, x_4, x_5~$ each $~\geq 1.$
A,B,A,B,B $~~: ~~x_5~$ $~\geq 1.$
A,B,B,A,B $~~: ~~x_3~$ $~\geq 1.$
A,B,B,B,A $~~: ~~x_3, x_4~$ each $~\geq 1.$

B,A,A,B,B $~~: ~~x_3, x_5~$ each $~\geq 1.$
B,A,B,A,B $~~: ~\text{no added constraint}.$
B,A,B,B,A $~~: ~~x_4~$ $~\geq 1.$

B,B,A,A,B $~~: ~~x_2, x_4$ each $~\geq 1.$
B,B,A,B,A $~~: ~~x_2~$ $~\geq 1.$

B,B,B,A,A $~~: ~~x_2, x_3, x_5~$ each $~\geq 1.$

---

It is standard in Stars and Bars analysis, that if (for example) you have an equation like
$x_1 + \cdots + x_k = n ~: ~x_1, \cdots, x_k \in \Bbb{Z_{\geq 0}}$
and you add the constraint that $r$ of the variables must be $\geq 1 ~: r \leq k$,
then this analogizes to $y_1 + \cdots + y_k = (n-r)$,

which will have $~\displaystyle \binom{[n-r] + [k-1]}{k-1}~$ solutions.

Of the $10$ different A,B placements shown above:

• $2$ have $3$ added $\geq 1$ constraints.
• $3$ have $2$ added $\geq 1$ constraints.
• $4$ have $1$ added $\geq 1$ constraint.
• $1$ has no added $\geq 1$ constraints.

Therefore, the final computation is

$$10 \times \left\{~\left[2 \times \binom{7}{5}\right] + \left[3 \times \binom{8}{5}\right] + \left[4 \times \binom{9}{5}\right] + \left[1 \times \binom{10}{5}\right] ~\right\}$$

$$ = 9660.$$

Answer 4

Arrange the $C$'s and $D$'s in $\binom52=10$ ways, for example:

$$\square C\square C\square D\square D\square D\square$$

Case 1: Place the $A$'s in different squares: $\binom62=15$. This creates $8$ squares to place the $3 B$'s,

$$\square A\square C\square A\square C\square D\square D\square D\square$$

$\binom83=56$, giving $8400$ in total.

Case 2: Place the $A$'s in the same square, with one of the $B$'s between them:

$$\square ABA\square C\square C\square D\square D\square D\square$$

$\binom61=6$. This creates $7$ squares to place the $2 B$'s, $\binom72=21$, giving $1260$ in total.

Overall total $9660$.

Answer 5

This answer is rather a supplement which could be used as crosscheck for manual calculations. We consider a $4$-ary alphabet built from letters $\mathcal{V}=\{A,B,C,D\}$. Words which do not have any consecutive equal letters are called Smirnov words. A generating function for Smirnov words is given as \begin{align*} \left(1-\frac{Az}{1+Az}-\frac{Bz}{1+Bz}-\frac{Cz}{1+Cz}-\frac{Dz}{1+Dz}\right)^{-1}\tag{1} \end{align*} The coefficient $[z^n]$ of $z^n$ in the series (1) gives the number of $4$-ary words of length $n$ which do not have any consecutive letters.

In the current example we are looking for words which do not have consecutive letters $A$ and $B$. Since we do not have any restriction on $C$ or $D$ we replace $C$ and $D$ with one or more occurrences giving \begin{align*} Cz\quad&\to\quad Cz+\left(Cz\right)^2+\left(Cz\right)^3+\cdots=\frac{Cz}{1+Cz}\\ Dz\quad&\to\quad Dz+\left(Dz\right)^2+\left(Dz\right)^3+\cdots=\frac{Dz}{1+Dz}\tag{2}\\ \end{align*} With some help of Wolfram Alpha we calculate the answer from (1) and (2) as \begin{align*} [z^{10}&A^2B^3C^2D^3]\left(1-\frac{Az}{1+Az}-\frac{Bz}{1+Bz} -\frac{\frac{Cz}{1+Cz}}{1+\frac{Cz}{1+Cz}}-\frac{\frac{Dz}{1+Dz}}{1+\frac{Dz}{1+Dz}}\right)^{-1}\\ &=\color{blue}{[z^{10}A^2B^3C^2D^3]\left(1-\frac{Az}{1+Az}-\frac{Bz}{1+Bz} -Cz-Dz\right)^{-1}}\\ &\,\,\color{blue}{=9\,660} \end{align*}

Note: Smirnow words can be found for instance in example III.24 in Analytic Combinatorics by P. Flajolet and R. Sedgewick.