Key (part 2): Throwback to my lonely days

Hello again. This will be the second part of the key to the challenge.

We've proved before:

Where d_k = D(k) is the amount of derangements of {1, ..., n}.

It naturally comes the strong induction relationship, by isolating the last term of the sum:

--------------------------------------------

The question is... Do we have a simpler form of D(n)?

Hmmm...

Let's try to get other forms of D(n).

The idea to build a derangement of {1, ...n} is to pick a certain amount of fixed points, and do a derangement of the rest of the points. In particular, to build a derangement σ of Sn...

Pick i∈ {2, ..., n} (n-1 possible choices)

Case 1: Either σ(i) = 1

Then you will surely have σ(1) =/= 1.

Do a derangement of the rest (without 1): there are D(n-2) possible choices.

Case 2: Either σ(i) =/= 1

Do a derangement with the rest (with 1): D(n-1) possible choices.

So, since there are n-1 possible choices for i...

D(n) = (n-1)(D(n-1) + D(n-2))

--------------------------------------------------

Okay.

What do we do with this relationship as well?

Well... Let's see. The forms are quite look-alike if you attempt to put D(n) and D(n-1) together,  because:

D(n) - nD(n-1) = -D(n-1) + (n-1)D(n-2)

So, with U(n) = D(n) - nD(n-1):

U(n) = -U(n-1)

So: U(n) = U(2)*(-1)^(n-2) = U(2)*(-1)^n

With U(2) = D(2) - 2D(1) = 1 because D(2) = 1 and D(1) = 0

D(n) = nD(n-1) + (-1)^n

--------------------------------------------------

So now, we can finally start talking about probabilities.

By taking Sn with the uniform distribution over every permumtation, the probability of a derangement on Sn is given by:

Because n! = Card Sn.

The second relationship, divided by n!, gives:

Keep in mind this is true for all n, so it will be true if you plug k < n instead of n.

Now by doing a bit of telescoping...

Now, note that the term in k = 0 is 1/0! = 1 and the term in k = 1 is -1/1! = -1, so they cancel out if you add them together.

-------------------------------------------------------------

And at last!!!

To recap, pn is the probability of picking a derangement in Sn. In other words, it's the probability that no student gets their own gift.

The probability of someone getting their own gift is 1 - pn.

1 - pn ~ 0.63

So... actually, isn't that pretty big??

Feelsbad, never do those Secret Santa events if you don't plan to compute the redistribution of gifts... That's a pretty sad christmas for everyone.

And that's all for my sad memories! Thank you for spending time and effort in trying to figure answers!

Props to Phi Guy for figuring the right answer...

===================================================

Post Scriptum

On a side note, pn converges to exp(-1) as n approaches infinity and very fast on top of that (the quality of convergence is stronger than just geometric here), so with n = 41, a fair approach of p(41) is 1/e.