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?
 A: 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.
A: 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.
A: 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)!$
