2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.