In how many ways can we permute the digits $2,3,4,5,2,3,4,5$ if identical digits must not be adjacent?

Question

In how many ways can we permute the digits $2,3,4,5,2,3,4,5$ if identical digit must not be adjacent?

I tried this by first taking total permutation as $\dfrac{8!}{2^4}$
Now $n_1$ as $22$ or $33$ or $44$ or $55$ occurs differently
$N_1 = \left(^7C_1\times \dfrac{7!}{8}\right)$
And $n_2 = \left(^4C_1 \times 4!\right)$
Using the inclusion-exclusion principle I got:
$\dfrac{8!}{16}-\left(^7C_1\times\dfrac{7!}{8}\right)+\left(^4C_1\times4!\right)$
But answer was wrong
Please help me solve the question
This question is from combinatorics and helpful for RMO

Answer 1

You need a few more inclusion-exclusion steps to complete this approach.

Without constraints, you do indeed have $\dfrac {8!}{2^4} = 2520 $ arrangements.

Then there are $\dfrac {7!}{2^3} = 630$ cases where a $22$ is found in the arrangement, and similarly for the other digits.

Then there are $\dfrac {6!}{2^2} = 180$ cases where both a $22$ and a $33$ are found, and similarly for other pairs, etc.

So by inclusion-exclusion, we have to subtract the paired cases then add back the double-paired cases, then subtract off triple-paired again and finally add in the cases where all digits appear in pairs.

$$\frac {8!}{2^4} - \binom 41\frac {7!}{2^3} + \binom 42\frac {6!}{2^2} - \binom 43\frac {5!}{2} + \binom 44\frac {4!}{1} \\[3ex] =2520 -4\cdot 630 +6\cdot 180-4\cdot60 + 24 = 864$$

[Sharp eyes might notice that $\frac {8!}{2^4} = \binom 41\frac {7!}{2^3}$, shortening the calculation process.]

Answer 2

Here is a variation based upon generating functions of Smirnov words. These are words with no equal consecutive characters. (See example III.24 Smirnov words from Analytic Combinatorics by Philippe Flajolet and Robert Sedgewick for more information.)

We encode the digits \begin{align*} 2,3,4,5 \qquad\text{as}\qquad a,b,c,d \end{align*} and look for Smirnov words of length $8$ built from $a,b,c,d$ with each letter occurring exactly twice.

A generating function for the number of Smirnov words over a four letter alphabet $V=\{a,b,c,d\}$ is given by \begin{align*} \left(1-\frac{4z}{1+z}\right)^{-1} \end{align*}

We use the coefficient of operator $[z^n]$ to denote the coefficient of $z^n$ in a series $A(z)$. The number of all Smirnov words of length $8$ over a four letter alphabet is therefore \begin{align*} [z^8]\left(1-\frac{4z}{1+z}\right)^{-1} \end{align*}

Since we want to count the number of words of length $8$ with each character in $V$ occurring twice, we keep track of each character. We obtain with some help of Wolfram Alpha \begin{align*} [a^2b^2c^2d^2]\left(1-\frac{a}{1+a}-\frac{b}{1+b}-\frac{c}{1+c}-\frac{d}{1+d}\right)^{-1}=\color{blue}{864} \end{align*}

Answer 3

Here is another approach:

Assume for the moment that the first appearance of the four digits is in increasing order. The places of their first appearance can be distributed in six ways, see the following figure. The places for the prospective second appearances have been marked by empty boxes, next to which is written the number of choices we have when filling them in. The last column shows the product of these numbers in each row. $$\matrix{ 2&3&4&5&\square_3&\square_3&\square_2&\square_1&&18\cr 2&3&4&\square_2&5&\square_2&\square_2&\square_1&&8\cr 2&3&4&\square_2&\square_2&5&\square_1&\square_1&&4\cr 2&3&\square_1&4&5&\square_2&\square_2&\square_1&&4\cr 2&3&\square_1&4&\square_1&5&\square_1&\square_1&&1\cr 2&3&\square_1&\square_1&4&5&\square_1&\square_1&&1\cr}$$ Summing the last column gives $36$. This has to be multiplied by $4!$ in order to compensate for the chosen order $2345$. It follows that there are $864$ admissible arrangements of the eight digits.