# 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.

## 1 Answer

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}$.

• Thanks! Sorry for the delay in accepting. – druckermanly Nov 10 '14 at 2:22
• Thanks for accepting this answer, and let me know if you have questions about it. – user84413 Nov 10 '14 at 15:11