Prove that for $n>0$ number of permutations of set $\{1,...,n\}$ for every $i=1,2,..,n-1$ is equal to....

Question

Prove that for $n>0$ number of permutations of set $\{1,...,n\}$ such that $a_{i+1}-a_i \neq 1$ for every $i=1,2,..,n-1$ is equal to $$D_n + (n-1)D_{n-2} + (-1)^{n-1} $$

where $D_n$ is number of disorders.

Could you give me a hint ?

Answer 1

$\text{Hint:}$

Try letting $E_{i}$ be the set of permutations which have $a_{i+1}-a_{i}=1$ for $1\le i\le n-1$, and then use Inclusion-Exclusion to find $|E_{1}^{c}\cap\cdots\cap E_{n-1}^{c}|$.