Photo, Santacon 2009 – Astoria, Queens NYC by kstraw2 on Flickr
A friend texted me today and asked what the chances are of a group of seven people picking names in their office Secret Santa without anybody choosing themselves. A clean draw, so to speak.
Now, there are a number of ways that you can try and work this out, but I think the easiest to follow is by thinking of the problem in terms of the number of permutations of the possible outcomes.
In my friend’s office, the first person to draw a name out has 7 possible names to choose from, then the second person has six names, the third person has five names and so on.
This means that the total number of possible permutations is 7 x 6 x 5 x 4 x 3 x 2 x 1, which is also written as 7! and is known as the factorial of 7.
7! = 5040
Then, we need to find the number of permutations where 1 is not in the first position, 2 is not in the second position, and so on.
And, quite frankly, this is a bugger to work out.
One of the reasons for this is the way the probabilities shake out. If person #1 picks out person #2’s name then there are two situations that exist where a solution is still possible.
- Person #2 picks out person #1.
- Person #2 picks out a name from Person #3 – Person #7
In the first case Persons #1 and #2 are buying each other presents and create a closed circle. We are therefore left with the probability of the remaining 5 people not picking each other to be exactly the same as if they had started as just the 5 of them in the first instance.
In the second case, and I’ve burned a few brain cells trying to follow why this is, then we are left with the probability being the same as if the Secret Santa had started with 6 people in it. I think.
Appropriately enough, this is known as a derangement and it leads to the following equation, where !n is the number of derangements for a set of size n.
!n = (n-1)[(!(n-1) + !(n-2) ]
Great, as if this seemingly simple question hadn’t turned out to be difficult enough we are now left with a recurrence equation – this is one when the answer is expressed in terms of preceding answers of a ?sequence.
So, if we substitute for n=7 then we get
!7 = 6(!6 +!5)
Skipping somerather nifty and clever stuff, we get
!7 = 1854
Which means that we are close to finding out the answer to the question. Out of 5040 possible permutations of Secret Santas there are 1854 that do not include anybody picking their own name. So the probability of a clean draw is 1854/5040 which is *drum roll* . . . . .
In fact, once you have 7 people in your Secret Santa the probability of a clean draw will always be equal to this. Which means that just over one in every three draws will be a clean one.
I think this is why we used an online Secret Santa app this year. It stops us from having to think too hard about it.