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
    @ 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