The number of sequences of length $10$ that can be formed with $5$ unique digits containing two of each where no two adjacent elements are alike

Question

We have $5$ unique digits. For the sake of simplicity let's say that these are $0$, $1$, $2$, $3$ and $4$.
We want to find the number of such sequences built using these numbers that:

• Two adjacent elements cannot be identical
• Each digit must be used exactly 2 times
  

For example, this sequence meets our criteria: $0102314243$

I have been thinking about the way of solving this and I have reached the conclusion that this algorithm is quite reasonable

1. Calculate the number of all possible $10$-length sequences built with $5$ numbers: $5^{10}$
2. Subtract sequences in which one digit appears only once: $5 \cdot 10 \cdot 4^9$
3. Subtract sequences in which one digit appears three times: $5 \cdot {10 \choose 3} \cdot 4^7$
4. Subtract sequences in which one digit appears four times: $5 \cdot {10 \choose 4} \cdot 4^6$ You see where it is going.
5. ... in which one digit appears 10 times: $10$
   Now, we have excluded some sequences more than once, and so we need to compensate for this.
   
6. Add sequences in which one digit appears only once and one appears three times
7. ... in which one appears nine times and one appears only once

Now, we will get the number of $10$ digits sequences in which all digits five digits were used exactly twice. Now, we need to exclude those in which two adjacent elements are identical. There are $9$ choices of two adjacent positions. We repeat the procedure

1. Exclude sequences in which the first and the second elements are identical
2. ... in which the ninth and the tenth elements are identical
3. Add sequences in which the first and the second elements are identical AND the third and the fourth elements are identical
4. ... in which the 1st, 2nd and 3rd, 4th, and 5th, 6th, and 7th, 8th and 9th, 10th elements are identical

This way, we should get our desired answer.

Do you think that this method can work? Are there simpler ways of tackling this problem?

Answer 1

The following approach avoids the inclusion/exclusion process suggested in a comment. We begin by counting the number of admissible partitions of the set $[1..10]$ of sites into five unlabeled pairs.

Separate $[1..10]$ into the blocks $[1..5]$ and $[6..10]$. A pair is split if its members are not in the same block. There are $1$, $3$, or $5$ split pairs.

If there is $1$ split pair each of the two blocks contains two full pairs. The two pairs in block $[1..5]$ can be one of $$(53)\bigl(4(1\vee2)\bigr),\quad (52)\bigl(1(3\vee4)\bigr),\quad (51)(24),\quad (42)(31)\ ,$$ makes $6$ in all. These can be freely combined with the $6$ such choices for the block $[6..10]$, except that $(42)(31)$ cannot be combined with $(79)(8\>10)$. It follows that there are $35$ partitions with $1$ split pair.

If there are $3$ split pairs each of the two blocks contains one full pair. The pair in block $[1..5]$ can be one of $$\bigl(5(3\vee2\vee1)\bigr), \quad\bigl(4(2\vee1)\bigr),\quad(3,1)\ .$$ These $6$ choices can be freely combined with the $6$ such choices for the block $[6..10]$, and then the three split pairs can be paired in $3!=6$ ways, with the following exception: If $5$ and $6$ do not occur in the choices of the nonsplit pairs there are only $4$ admissible pairings of the split pairs. It follows that there are $6\cdot6\cdot 6-3\cdot3\cdot2=198$ partitions with $3$ split pairs.

If there are $5$ split pairs we can pair the sites in block $[6..10]$ in $4\cdot4!=96$ ways with the sites in block $[1..5]$.

It follows that there are $35+198+96=329$ admissible pairings of the ten sites. Multiply this with $5!$ to obtain the final number $39\,480$ of admissible sequences of length $10$.

Note that the number of such pairings of $[2n]$ is dealt with in MSE question The number of sequences of length $2n$ that can be formed with digits from set $A={1,2, ... ,n}$ and..., where one may also find the above $a_5=329$.

Answer 2

here is how it looks by inclusion-exclusion :

let T(2n) be the total number of sequences of n digits.

$T(2n) = \binom {2n}{2}\binom {2n-2}{2} ...\binom {4}{2} \binom {2}{2}$

Let $T_1, T_2, T_3, T4, T_5$ be the number of sequences that have at least a bad couple, at least two bad couples, etc.

$T_1 = \binom {5}{1}.\ 1!\ .\binom {8+1}{1} \times T(8) $

$T_2 = \binom {5}{2}.\ 2!\ .\binom {6+2}{2} \times T(6) $

$T_3 = \binom {5}{3}.\ 3!\ .\binom {4+3}{3} \times T(4) $

$T_4 = \binom {5}{4}.\ 4!\ .\binom {2+4}{4} \times T(2) $

$T_5 = \binom {5}{5}.\ 5!\ . \binom {0+5}{5} \times T(0) $

I will describe $T_2$ , the case we have at least two bad couples:

$\binom {5}{2} \ $ - stands for the choice of the two couples considered

$2! \ $ - the order of the two bad pairs matter

$\binom {6+2}{2} \ $ - the two couples are separators for the rest of 6 digits (bin bar)

$T(6)\ $ - is just the number of filling the 6 remaining slots

The required number is, by inclusion-exclusion :

$T(10) - T_1 + T_2 - T_3 + T_4 - T_5 = 39480$

Answer 3

via generating functions :

Let $A$ be strings that end in $a$, $B$ that and in $b$ ... until $E$ are strings that end in $e$.

The Ordinary Generating Function system is then

$ \begin{cases} A = a + a.(B+C+D+E), \\ B = b + b.(A+C+D+E),\\ C = c + c.(A+B+D+E),\\ D = d + d.(A+B+C+E),\\ E = e + e.(A+B+C+D),\\ S = A+B+C+D+E \end{cases} $

Maple solve delivers as generating function :

$$ \frac { a+ b + c+ d + e + 2( ab + ac + ...) + 3(abc + abd + ... ) + 4(abcd + abce ... ) + 5abcde}{ 1 -(ab + ac ...) - 2(abc + abd + ... ) - 3(abcd + abce ... ) - 4abcde } $$

The required number is the coefficient of $a^2b^2c^2d^2e^2$ in the taylor development of the above and it is $39480$