5
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ I made some edits to help the layout and appearance - see this linked article for more help on formatting - but I am not clear how you derived your formulas. Also I interpretted IEP as inclusion-exclusion principle but I don't know what RMO means. Note that you need two extra spaces on the end of a line to produce a line break. $\endgroup$
    – Joffan
    Aug 20 '17 at 2:26
8
$\begingroup$

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

$\endgroup$
5
$\begingroup$

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*}

$\endgroup$
1
  • 3
    $\begingroup$ (+1) This approach is so elegant and considerably malleable! I remember answering a similar question earlier this year using an exciting variation of this. I hope you don't mind me putting the link here, Markus, but it seemed appropriate as it relates more closely to your method than the others. $\endgroup$
    – N. Shales
    Aug 21 '17 at 2:07
4
$\begingroup$

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.

$\endgroup$
1
  • 2
    $\begingroup$ One of the charms of mathematics is that there is always another way.... $\endgroup$
    – Joffan
    Aug 20 '17 at 13:52

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.