I found that the series of number of derangements follows a certain sequence that can be expressed as such : $nD_{n-1} +(-1)^n$.

Now, I found others saying it can be expressed as follows $(n-1)(D_{n-1}+D_{n-2})$.

I have seen some people explaining the second formula intuitively. What I am curious about is , whether there is a way to explain the FIRST formula intuitively. I want an explanation for the first formula. Meaning, I am trying to find the logic for it in such a way that the expression as it's written would be understood.

I started somewhat by saying that there is some logic behind the number of derangements of $D_{n-1}$ to be multiplied by $n$ because the new object has $n$ places to be placed in while $n-1$ objects are placed as was ordered in $D_{n-1}$. But I can't seem to find the logic behind the $-1^n$. I started to think that maybe for odd numbers I have to reduce one due to the middle? But I am not sure.

I want a logical/intuitive proof that would prove MY (first) formula and I want it to be followed somehow in the way I started. I don't want completely different proofs.

But can someone please make some sense of my proof or show why it's wrong? Or show other intuitive thing to my formula?



You must log in to answer this question.

Browse other questions tagged .