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 believe an induction proof might work nicely.
The base case $ n=1 $ is easy enough, so consider the step from $ n=k $  to  $ n=k+1 $:
Of the $ k+1 $ gaps you could place the number $ k+1 $, only one will be illegal (immediately after $k$).  So we get $|A_{k+1}|=k|A_k|$, $|A_1|=1$
It doesn't take long to generate $|A_n|=(n-1)!$
