# Combinatorial Proof of $Q_n = D_n + D_{n-1}$ [duplicate]

Let $Q_n$ be the number of permutation of $n$ integers $\{1, 2, \cdots, n \}$ such that, in the permutation, every $i$ is not succeeded by $i+1$ and let $D_n$ be the number of derangement of $n$ integers. Find a combinatorial proof of $$Q_n = D_n + D_{n-1}.$$

For the algebraic proof it is easy. Just play with those factorials. But what about a combinatorial proof?

I tried the case where $n=4$ and I want to show for any permutation of the form $Q_4$, it is either in $D_4$ or $D_3$. But it is not true by simply looking at the permutation $1,4,3,2$ as there are already $2$ fixed points and now I am stuck.

Another thing that comes to my mind is that, for $n$ integers to permutation, at most $\lceil \frac{n}{2} \rceil$ of the integers can be fixed points, which is approximately half of the number of integer. Does this suggest that we should divide into two cases, one for those fixed points and another for non-fixed points?

• If someone could use the simplification of RHS to $nD_{n+1}$ (due to Euler, $n \ge 2$) and then show that $\frac{Q_n}{n}$ is equivalent to $D_{n+1}$, we are done. Sep 21, 2015 at 16:27
• @Shailesh : suppose we can do so, how should we proceed? Sep 21, 2015 at 16:41
• @Shailesh: You have the $n$ on the wrong side: $D_{n+1}=n(D_n+D_{n-1})$. Sep 21, 2015 at 16:49
• @BrianM.Scott Oops. Sorry, You are absolutely right. I also checked the duplicate link and saw the answer, it is not very straightforward. Sep 21, 2015 at 16:51
• @Shailesh: No, it isn’t. I’m going to think about it a bit more to see whether I can come up with anything simpler. Sep 21, 2015 at 16:53

Sorry to post this as an answer, but I don't have enough reputation to do otherwise.

It seems like this question may have what OP is looking for.

• i am looking for a combinatorial proof :) Sep 21, 2015 at 16:43
• @LeeKM: The second answer there is a combinatorial proof. Sep 21, 2015 at 16:48