0
$\begingroup$

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?

$\endgroup$
5
  • 4
    $\begingroup$ It does not look correct to me. The string $2211$ is not allowed, but $232131$ is valid for $n=3$. $\endgroup$ – M.B. Nov 19 '13 at 22:30
  • 1
    $\begingroup$ 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)!}$$ $\endgroup$ – Henry Nov 19 '13 at 22:34
  • 1
    $\begingroup$ Your recurrence has a solution of $f(n)=(2n-1)!/2^{n-2}$ but for M.B.'s reason is wrong $\endgroup$ – Henry Nov 19 '13 at 22:43
  • 3
    $\begingroup$ $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. $\endgroup$ – Fibo Kowalsky Nov 19 '13 at 22:49
  • 1
    $\begingroup$ @Fibo, a nice observation. $\endgroup$ – Doc Nov 19 '13 at 23:36