Counting permutations with given condition I need to find number of permutations $p$ of set $\lbrace 1,2,3, \ldots, n \rbrace$ such for all $i$ $p_{i+1} \neq p_i + 1$.
I think that inclusion-exclusion principle would be useful. Let $A_k$ be set of all permutation that for every permutation $a$ in this set $a_{k+1} \neq a_k + 1$. So our answer would be $| A_1 \cap A_2 \cap \ldots \cap A_n |$. Could you help me with completing the proof?

I would recommend initially counting the set of all of those permuttations and
then using inclusion-exclusion on this set by systematically removing
the sets $B_k$ which we can define as the set of all permutations where
$p_k = p_k+1$. I.e. We can account for the set of all permutations as
$$|S| = n!,$$
and count each $A_k$ given that there are $n-1$ options of $p_k$ and $n-2$
free variables left as
$$|A_k| = n-1 \times (n-2)! = (n-1)!.$$
Performing inclusion-exclusion by using the $A_k$'s as removal sets should
follow cleanly.
