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?

We can complete Penitent's induction argument as follows:
Denote the number of valid permutations of $k+1$ elements by $a_k$. There are two ways to generate a valid permutation of $k+1$ elements from a permutation of $k$ elements: Either by inserting $k+1$ into a valid permutation of $k$ elements at any of the $k+1$ gaps except the one behind $k$; this yields $ka_k$; or by inserting $k+1$ into a single consecutive pair that made the permutation invalid, thus making it valid. Each permutation of $k$ elements with a single consecutive pair corresponds to exactly one valid permutation of $k-1$ elements obtained by merging the pair and suitably renumbering the remaining elements. This yields a contribution $(k-1)a_{k-1}$, since each of the $k-1$ elements in each of the $a_{k-1}$ valid permutations of $k-1$ elements can be expanded into a pair. Thus we have the recurrence relation
$$
a_{k+1}=ka_k+(k-1)a_{k-1}
$$
with the initial values $a_1=a_2=1$. We can rearrange the recurrence relation
$$!(k+2)=(k+1)(!(k+1)+!k)$$
for the number $!k$ of derangements of $k$ elements to
$$
\frac{!(k+2)}{k+1}=k\frac{!(k+1)}k+(k-1)\frac{!k}{k-1}\;.
$$
This is our present recurrence relation with $a_k=\frac{!(k+1)}k$, and the initial values coincide, so this is a "closed form" for $a_k$, though since the number of derangements is usually counted using inclusion-exclusion, it's not really more "closed" than what you'd get directly using inclusion-exclusion in the way Rob outlined.
I posted this new question asking for a combinatorial proof of the count $a_k=\frac{!(k+1)}k$.
By the way, this is OEIS sequence A000255, shifted by one.
