Hello again. This will be the second part of the key to the challenge.
![Key (part 2): Throwback to my lonely days-[C]Hello again. This will be the second part of the key to the challenge.
[IMG=HAJ](https://image.staticox.com/?url=https%3A%2F%2Fpa1.aminoapps.vertvonline.info%2F7613%2Fc1d2cbe2b7b3191bae29d222e390fef5d5c3d2d5r1-300-333_hq.gif)
We've proved before:
![Key (part 2): Throwback to my lonely days-[C]Hello again. This will be the second part of the key to the challenge.
[IMG=HAJ](https://image.staticox.com/?url=http%3A%2F%2Fpm1.aminoapps.vertvonline.info%2F7613%2F4296c59aaf15656e40fb2f486a2fc2fce5792a84r1-278-115v2_hq.jpg)
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:
![Key (part 2): Throwback to my lonely days-[C]Hello again. This will be the second part of the key to the challenge.
[IMG=HAJ](https://image.staticox.com/?url=http%3A%2F%2Fpm1.aminoapps.vertvonline.info%2F7613%2F11a9eab9eaf9ee3f76d959c148c8ed8565b3946br1-257-99v2_hq.jpg)
--------------------------------------------
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
![Key (part 2): Throwback to my lonely days-[C]Hello again. This will be the second part of the key to the challenge.
[IMG=HAJ](https://image.staticox.com/?url=http%3A%2F%2Fpm1.aminoapps.vertvonline.info%2F7613%2F1ab9b8b4a5dee89ccc4674f6b95685dd12ebddb9r1-253-60v2_hq.jpg)
--------------------------------------------------
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:
![Key (part 2): Throwback to my lonely days-[C]Hello again. This will be the second part of the key to the challenge.
[IMG=HAJ](https://image.staticox.com/?url=http%3A%2F%2Fpm1.aminoapps.vertvonline.info%2F7613%2Fa24298891178252974b684d36abb921db2ba0885r1-115-73v2_hq.jpg)
Because n! = Card Sn.
The second relationship, divided by n!, gives:
![Key (part 2): Throwback to my lonely days-[C]Hello again. This will be the second part of the key to the challenge.
[IMG=HAJ](https://image.staticox.com/?url=http%3A%2F%2Fpm1.aminoapps.vertvonline.info%2F7613%2Fa7292fd2854f96a22428a105bcf2159fab0cc5cer1-288-91v2_hq.jpg)
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...
![Key (part 2): Throwback to my lonely days-[C]Hello again. This will be the second part of the key to the challenge.
[IMG=HAJ](https://image.staticox.com/?url=http%3A%2F%2Fpm1.aminoapps.vertvonline.info%2F7613%2F40e89e1922cadc4b388c7bd641da594aadf71b5ar1-390-193v2_hq.jpg)
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!!!
![Key (part 2): Throwback to my lonely days-[C]Hello again. This will be the second part of the key to the challenge.
[IMG=HAJ](https://image.staticox.com/?url=http%3A%2F%2Fpm1.aminoapps.vertvonline.info%2F7613%2Fbf3c8cc7c19ba052f54e82de4911792c1147733ar1-285-161v2_hq.jpg)
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.
![Key (part 2): Throwback to my lonely days-[C]Hello again. This will be the second part of the key to the challenge.
[IMG=HAJ](https://image.staticox.com/?url=https%3A%2F%2Fpa1.aminoapps.vertvonline.info%2F7613%2F013f302673f27e85907b54dbc2799830ddb61c33r1-444-250_hq.gif)
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.
![Key (part 2): Throwback to my lonely days-[C]Hello again. This will be the second part of the key to the challenge.
[IMG=HAJ](https://image.staticox.com/?url=http%3A%2F%2Fpm1.aminoapps.vertvonline.info%2F7613%2F4c07449fb240390677d82cfb5a54eb2b503b0e06r1-344-154v2_hq.jpg)
Comments (5)
Hello Grey.
The binomial law is invalid here because the n-1 students and I aren't taking our presents independantly. The amount of presents decreases when a student takes one, so it's not the same experiment repeated 41 times.
Your result coincidentally gets close to the wanted result numerically because the amount of students n is large enough. It wouldn't work for small values such as 3 or 4 students.
Let me show you why our probabilities are asymptotically the same.
Our probabilities converge to the same value as n approaches infinity...
Ohh ok that makes sense. I’ll have another think if I have any time after my ridiculous exam revision. Also ty for calling this an awkward moment
Last row for cumulative probability to save everyone’s time
Sorry for being late to the party. I’m not a math genius so I didn’t really get the rigorously pure proof you gave, but a fairly simplistic idea I had was that since there were 41 gifts and 41 peeps, the probability of anyone getting their own gift is 1/41, so I thought this would follow a binomial distribution with X~B(41,1/41). I used a binomial calculator and boom P(X>0)~0.63 too (it rounds to 0.64 but hey it’s close enough right). Is there anything wrong with using a binomial model and is it just a coincidence