The Derangement of the Secret Santa

Santacon 2009 - Astoria, Queens NYC

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.

  1. Person #2 picks out person #1.
  2. 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* . . . . .

0.36786

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.

3 comments

  1. A few years back, at our company meal where we swapped presents we were seated at a round table. It turned out that everyone had bought for the person on their right, except for 2 who had bought for each other. Probability of that? ;-D

  2. To work that out you need to know the total number of people around the table.

    The denominator in your case will be !n, because I assume that the Secret Santa was managed so that nobody picked themselves.

    The numerator is the product of the number of possible instances of pairs and the number of ways that the rest of the group can be ordered so they are sat to left of their Secret Santa. The former I haven’t worked out, but will have a think about (and scout around a few maths sites). The latter is n-3, I think as you have n-2 remaining and 1 fewer than that solutions to the problem.

    If you let me know how many people were there then I’ll give it a go.

Leave a Reply

Your email address will not be published. Required fields are marked *