Secret Santa problem

Asked Nov 08 '20 at 14:37

Active Nov 08 '20 at 14:37

Viewed 81 times

I saw this problem on my exams and I just literally wrote down the formula for derangements and derived it but I am not sure if it is the case. This was the problem:

Problem: Let there be $n$ number of people and each one of them buys a gift and places them in a bag. Then each member chooses a gift out of the bag without seeing what they choose. What is the probability that none of the $n$ people chooses their own gift?

I was just wondering isnt this just a restatement of the derangement problem? Where the derangement formula is given by:

$$!n=n!\sum_{i=0}^n\frac{(-1)^i}{i!}$$

asked Nov 08 '20 at 14:37

Aurora Borealis

1,747

You are right, this is the same as a derangement. – lulu Nov 08 '20 at 14:39
So is the answer exactly that formula? – Aurora Borealis Nov 08 '20 at 16:57
Sure. The the packages people pick up are precisely a permutation of the original list (originally, everyone was paired with their own package). You want this to be a permutation with no fixed point, hence a derangement. The number of derangements is $!n$ as you say so the desired probability is $\frac {!n}{n!}$. If $n$ is large, this approaches $\frac 1e$. – lulu Nov 08 '20 at 17:30
Thank you, how about the $(-1)^i$ term of the summation in your expression? – Aurora Borealis Nov 09 '20 at 02:59
Which expression are you talking about? The sum formula for the number of derangements? What's the problem with it? – lulu Nov 09 '20 at 09:41
Like I do nut understand if the answer is $!n$ or $!n/n!$ – Aurora Borealis Nov 09 '20 at 12:23
Never mind I understand thank you ! – Aurora Borealis Nov 09 '20 at 12:30

Secret Santa problem

0 Answers0