3
$\begingroup$

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?

  • 0
    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.2012-08-30
  • 0
    possible duplicate of [OEIS A000255 recursion.](http://math.stackexchange.com/questions/178586/oeis-a000255-recursion) Not quite, as that one didn't do both reversals.2012-08-30
  • 1
    [OEIS A002464](http://oeis.org/A002464) gives formulae, generating functions, references etc.2012-08-30
  • 0
    @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.2012-08-31
  • 0
    @ mjqxxxx There are also be "bad" permutations for n-1 which after inserting n becomes a good one for n. Hence your prescription does not cover all good permutations (gp). E.g. for n=4 you have gp(4)=2. Expanding them according to your procedure gives gp(5) = 2*3 = 6. But in fact there are 14 good permutations.2018-05-16

0 Answers 0