No pairs in a list.

Question

This is a difficult problem that I've been thinking for some time with little success and was wondering if anyone will have a look at it for me? First of all I want to clarify something before we start, in an unsorted list a pair exists if two adjacent elements in the list have the same value. It seems obvious but it's good to know for later.

Let $A$ be an unsorted list of size $2n$ which contains the numbers $1,...,n$ exactly twice. How many of these lists will have no pairs?

To give an example for $n=2$, $[1,2,1,2]$ is a list with no pairs. Another example but for $n=3$ is $[1,3,2,3,1,2]$.

Answer 1

A114938 -- Number of permutations of the multiset {1,1,2,2,....,n,n} with no two consecutive terms equal.

2, 30, 864, 39480, 2631600, 241133760, ...

Answer 2

Let $S$ be the set of arrangements of $A=\{1,1,2,2,\cdots,n,n\}$,

and let $A_i$ be the set of arrangements with the two elements $i,i$ adjacent, for $1\le i\le n$.

Then $\displaystyle\big|\overline{A_1}\cap\cdots\cap\overline{A_n}\big|=|S|-\sum_{i}|A_i|+\sum_{i<j}|A_i\cap A_j|-\sum_{i<j<k}|A_i\cap A_j\cap A_k|+\cdots$

$\displaystyle=\frac{(2n)!}{2^n}-\binom{n}{1}\frac{(2n-1)!}{2^{n-1}}+\binom{n}{2}\frac{(2n-2)!}{2^{n-2}}-\binom{n}{3}\frac{(2n-3)!}{2^{n-3}}+\cdots+(-1)^n\binom{n}{n}\frac{(2n-n)!}{2^{n-n}}$