# How many string of numbers $1,…,n$ of length $2n$ where two of the same numbers are not consecutive. [duplicate]

I need to find the number of strings of length $2n$ that consist of numbers $1,...,n$ each appearing exactly twice and not next to each other.

Let $f(n)$ denote the function that gives me back that information:

$f(1)=0$, because $11$ is not correct.

$f(2)=2$ there are two possibilities- $2121$ i $1212$.

Now let's consider $f(n)$. Let's take out two of the $n's$. The string without $n$'s can be created $f(n-1)$ different ways, and since we have to put two $n$'s somewhere between the numbers in that string, we can do that ${{2n-1}\choose{2}}=(n-1)(2n-1)$ ways, so the answer is $f(n)=(n-1)(2n-1)*f(n)$. And now I have to solve this recurrence by annihilating it for example.

Correct?

## marked as duplicate by Henry, Arek Krawczyk, Tomas, azimut, Branimir ĆaćićNov 20 '13 at 0:24

This question was marked as an exact duplicate of an existing question.

• It does not look correct to me. The string $2211$ is not allowed, but $232131$ is valid for $n=3$. – M.B. Nov 19 '13 at 22:30
• Essentially the same question as the five linked from math.stackexchange.com/questions/465318/… as inclusion-exclusion leads to an answer of $$\displaystyle\sum_{i=0}^n (-2)^i {n \choose i}\frac{(2n-i)!}{(2n)!}$$ – Henry Nov 19 '13 at 22:34
• Your recurrence has a solution of $f(n)=(2n-1)!/2^{n-2}$ but for M.B.'s reason is wrong – Henry Nov 19 '13 at 22:43
• $f(n)$ is dividable by $n!$ since you can bijectively map $1...n$ in itself. e.g. having a desired sequence of length $2n$, applying bijective mapping on it will return a sequence with the same desired property. – Fibo Kowalsky Nov 19 '13 at 22:49
• @Fibo, a nice observation. – Doc Nov 19 '13 at 23:36