5
$\begingroup$

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?

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.