Counting the number of permutations where $i$ does not follow $i-1$ Whilst reviewing, I've found a problem where the book has an answer, but no suitable explanation, and I can't begin to connect the two.
The problem is simply as follows:
Count the number of permutations of size $q$, where in one-line notation, each element $i$ does not follow element $i-1$.
The book states that the answer is $D_q+D_{q-1}$ (where $D_j$ represents the number of derangements of length $j$).
I've tried picking a first element, then counting the number of ways we can pick the next, and seeing a pattern, but this doesn't bring me to an answer (unless I've been making a mistake).
I've also tried starting with the collection of derangements of size $q$ and $q-1$ but this seems like I'd be picking the answer after already knowing it.

If you let $A_i$ be the set of permutations where $i-1$ is followed by $i$, for $2\le i\le q$, then you can find the number of permutations described using
Inclusion-Exclusion:
$|A_2^c\cap\cdots\cap A_q^c|=|S|-\sum|A_i|+\sum|A_i\cap A_j|-\sum|A_i\cap A_j\cap A_k|+\cdots$
$\hspace{.8 in}=q!-\binom{q-1}{1}(q-1)!+\binom{q-1}{2}(q-2)!-\binom{q-1}{3}(q-3)!+\cdots$
After simplifying this expression, you can use the formula for $D_n$ to show that this gives $D_q+D_{q-1}$.
