This article has been reviewed according to Science X's editorial process and policies. Editors have highlighted the following attributes while ensuring the content's credibility:
fact-checked
trusted source
written by researcher(s)
proofread
20 people, 2.4 quintillion possibilities: The baffling statistics of Secret Santa
Christmas, we're told, is the most wonderful time of the year. For many of us, however, it is preceded by one of the least wonderful times: the awkward social spectacle of the office Secret Santa or Kris Kringle, where employees agree to purchase a gift for a randomly allocated colleague.
As you watch your co-workers unwrap their often wildly inappropriate gifts, each chosen by a office mate they barely know, cast your mind to the sheer statistical improbability of what you're seeing. The odds of such a combination of these cheaply re-gifted photograph frames, inexplicably scented candles or unwanted Lynx Africa gift sets being passed around your office is, in its own way, truly a Christmas miracle.
The 12! ways of Christmas?
To work out how many possible pairings of buyers and recipients there are, you need to calculate the number of permutations of the people involved.
Consider a workplace with four employees. If there is no rule to prevent people selecting their own names, there are four people who could be selected to buy the first person's gift.
Once this is decided, there are three remaining choices for the second person, then two choices for the third person. Finally, there is one choice for the last person's workplace Santa.
This means there are 4 × 3 × 2 × 1 = 24 possible permutations. Mathematicians write this as 4!, which is pronounced "four factorial".
However, factorials soon get out of hand. Spare a thought for poor Santa himself. With nine reindeer, there are 9! = 362,880 ways these could be arranged, although perhaps on one foggy Christmas Eve, this number is reduced by the requirement to have a red nose leading his sleigh.
Once the office workforce swells to 20, there are more than 2.4 quintillion permutations. To put this mind-boggling 20! figure into context, that's more than three times current estimates of the number of grains of sand on Earth.
Yule buy for someone else
Of course, nobody wants to draw themselves in a Secret Santa.
What a Secret Santa really wants is not a permutation of all employees, but instead what mathematicians call a derangement. This is simply a permutation where no element remains in its original position, which means no employee has to buy their own gift.
The calculation is far from simple, but the number of ways n employees can be assigned another unique co-worker is called the n th de Montmort number.
Amazingly, this is equal to n!/e , rounded to the nearest whole number. The e here is one of the most famous numbers in mathematics, Euler's number, approximately equal to 2.71828, and the bane of anyone whose schooldays involved logarithm tables.
In the 24 permutations of four employees illustrated, there are 9 derangements, which is equal to 24/e rounded to the nearest whole number. For large numbers, approximately 63.2% of possible permutations are not derangements and so would be excluded.
For a 20-employee situation, this cuts the over 2.4 quintillion permutations to a mere 895 quadrillion or so. (This is still more than 100 million times the current global population.)
Uniquely self-Santa-ed?
Another surprising feature of a Secret Santa arises from the number of people who will, on average, be assigned their own name in a random draw. It doesn't matter if you have one person (although that is a terribly un-secret and desperately sad Secret Santa) or a billion people, the expected number of people to be allocated to buy their own gift is the same—just one person.
A full proof is a little more complicated than this, but think what happens if you double the number of employees. With twice as many gifts to buy, everybody's chance of selecting themselves is halved. Twice as many people, each with half the chance of matching, then gives an unchanged average.
For example, of the 24 permutations of four people illustrated, one involves four self-matches, none involve three self-matches, six involve two self matches and eight involve a single self-match. In total, this gives 24 possible self-matches in the 24 permutations, so an average of one each.
Ho Ho Hope for the best
If you do find yourself trapped in the dystopian office whodunit of guessing which of your co-workers gifted a hunky shirtless firefighter calendar to an elderly colleague from human resources, at least hope that the one-in-a-billion or one-in-trillion permutation that was drawn in your office lands you something useful.
Mariah Carey may have assured us of more specific requests, but all I want for Christmas is avoid getting dragged into a workplace Secret Santa in the first place.
Bah humbug indeed.
Provided by The Conversation
This article is republished from The Conversation under a Creative Commons license. Read the original article.