# Find the number of specific permutations

Find the number of all permutations of the set $\left\{ 1,2,...,2n \right\}$ such that does not have compact subsequence: $\langle i, \ i+1\rangle$ or $\langle i+1, \ i\rangle$ for all $1\le i\le 2n-1$.

I'm not sure if I translated above text properly, so please correct me if needed. For example, for $n=3$ permutation: $1,6,4,2,5,3$ is ok, but $4,6,2,1,3,5$ is not.

I've tried inclusion-exclusion principle, but it didn't help. Probably because I was always weak at this principle. How can I solve this problem?

-
To arrive at a good permutation of $\{1,2,...,n\}$, you can start with a good permutation of $\{1,2,...,n-1\}$ and insert $n$ in any of the $n-2$ positions not adjacent to $n-1$, or you can start with a permutation of $\{1,2,...,n-1\}$ with a single adjacent pair and insert $n$ between its members, breaking them up. – mjqxxxx Aug 30 '12 at 19:37
possible duplicate of OEIS A000255 recursion. Not quite, as that one didn't do both reversals. – Ross Millikan Aug 30 '12 at 20:42
OEIS A002464 gives formulae, generating functions, references etc. – Henry Aug 30 '12 at 20:45
@mjqxxxx, I understand your point, but I have problems with the second part. Single adjacent pair can be $k,k+1$ (which is easy) or $k+1,k$, which I don't know how to examine. So far I got: $a_n=(n-2)a_{n-1}+(n-2)(a_{n-2}+?)$, where $?$ should be the number of all permutations that contain substring $k+1,n,k$ but I don't know how to count them. – ray Aug 31 '12 at 10:12