Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.