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?