Secret Santa is a way to share gifts among work mates, family, etc. It is organized in such a way that every person is commited to gift secretly to another, and the latter does not know who is the gifter. In Spanish this game is called amigo invisible (invisible friend).

Secret Santa should take care of two points:

  1. It must be secret (nobody can know her Santa)
  2. Whatever the assignment method, nobody must be her own Santa

How can we organize a Secret Santa?

The naïve approach for, say, 4 members group (Arthur, Beatrice, Charles and Diana {A, B, C, D}) is creating a random permutation of this set and putting it besides the original. For example we have computed randomly the permutation {B, D, A, C}:

   A  B  C  D
   B  D  A  C

It can be read as: Arthur gifts to Beatrice, Beatrice to Diana, Charles to Arthur and Diana to Charles.

The problem arises when this random permutation puts a person besides herself, that shouldn’t occur accordingly to the second condition expressed before; for example, the permutation {C, B, D, A} is not allowed because Beatrice would be her own Secret Santa.

So the question stands: How many permutations of the original set are valid under the Secret Santa conditions? In other words, how many permutations of the original set shifts all elements from their starting positions?

Analysis

So the matter is the $n$-element set permutation analysis. The number of permutations is $P(n) = n!$ and we will called $p(n)$ the number of valid Secret Santa permutations.

The easy cases

Let’s start with the easiest cases. By simple finger calculation we obtain:

  • Case $n = 1$. Then $P(1) = 1$ and, obviously $p(1) = 0$ since the only participant can’t gifts herself.
  • Case $n = 2$. Then $P(2) = 2$ and $p(2) = 1$. Say the set is {A, B} then the only valid permutation is {B, A}.
  • Case $n = 3$. Then $P(3) = 6$ and $p(3) = 2$; As we chan easily check for the initial set {A, B, C} there are only two valid permutations: {B, C, A} y {C, A, B}, that correspond to circular shifts by one element.

From now on we must proceed carefully. Let’s plunge into the non-trivial cases.

4 elements

Let’s begin with the next step in complexity (4 elements). Firstly we try to calculate the number of permutations where there are coincidences (at least one) and we define this concept as $\pi(n)$. So:

\[p(n) = P(n) - \pi(n)\]

In addition we define permutations with partial coincidences. So $\pi_1(4)$ is the number of permutations of 4 elements set where one, and only one, of its elements coincides with the starting permutation; $\pi_2(4)$, $\pi_3(4)$, $\pi_4(4)$ represents the number of permutations where coincide respectively 2, 3, and 4 elements. So for general $n$:

\[\pi(n) = \sum_{i=1}^{n} \pi_i(n)\]

1 coincidence (4 elements)

We calculate $\pi_1(4)$. Let’s suppose that there is a coincidence in the first element. The other 3 elements can’t coincide; so we know that the number of non-coincident permutations of three elements are $p(3) = 2$. Since we can fix 4 positions for legitimate single coincidence we have $4\times 2 = 8$ combinations where only coincides one element. So:

\[\pi_1(4) = 4 \times p(3) = 8\]

2 coincidences (4 elements)

When we fix 2 coincident elements there are other 2 that must not coincide. So, that is $p(2) = 1$. Looking again at the coincident pair we must calculate all the combinations of 4 elements taking by pairs, that is

\[\binom{4}{2} = \frac{4 \times 3}{2} = 6\]

Thus,

\[\pi_2(4) = \binom{4}{2} p(2) = 6\]

3 coincidences (4 elements)

There are no 3 coincidences and 1 void y a 4 element set:

\[\pi_3(4) = \binom{4}{3} p(1) = 0\]

4 coincidences (4 elements)

That is trivially 1:

\[\pi_4(4) = 1\]

In general it is easy to see that $\pi_n(n) = 1$.

Total number of coincidences

So,

\[\pi(4) = 8 + 6 + 0 + 1 = 15\]

And then, the number of valid permutations for a Secret Santa with 4 friends is 9:

\[p(4) = P(4) - \pi(4) = 24 - 15 = 9\]

Unfortunately the proposed method is not constructive and thus it does not provide the 9 legitimate permutations. These are:

{B, C, D, A}, {C, D, A, B}, {D, A, B, C}, 
{B, A, D, C}, {C, D, B, A}, {D, C, B, A}, 
{C, A, D, B}, {B, D, A, C}, {D, C, A, B}

General method

So it is easy to deduct the general formula for $\pi(n)$, being $n > 2$:

\[\pi(n) = 1 + \sum_{i=1}^{n-2} \binom{n}{i} p(n-i)\]

or in terms of $p(n)$

\[p(n) = n! - 1 - \sum_{i=1}^{n-2} \binom{n}{i} p(n-i)\]

The counterpart is that this formula is recursive; in order to get $p(n)$ is needed to have the previous $n-1$ values. For example, the calculation for $n=5$:

\[p(5) = 120 - 1 -\left(5\cdot 9 + 10\cdot 2 + 10\cdot 1 \right) = 44\]

A surprise!…

$p(n)$ is always lower than $P(n)$. Looking at the so far calculated values it seems that there is a proportional factor. May it varies, diverges oscillates or perhaps converges with $n$? Let’s see with the following table, with an extra $n=6$ case added:

$n$ $P(n)$ $p(n)$ $P(n)/p(n)$
2 2 1 2.000
3 6 2 3.000
4 24 9 2.667
5 120 44 2.727
6 720 265 2.720

So, it looks that there is a convergence… to what value? Isn’t that convergence number familiar, $2.72\ldots$? Indeed it is! It is the famous number $e$, base of natural logarithm, $e = 2.71828\ldots$ In fact we can propose the following formula (without formal proof) of $p(n)$ that does not need the previous $n-1$ values:

\[p(n) = \lfloor n!/e + 0.5 \rfloor\]

It predicts all the previously tabulated values. We can precict now the term $n=7$:

\[7!/e = 5040/2.71828\ldots \simeq 1854.11\]

Hence $p(7) = 1854$. I invite the reader to check this result with the exact formula.

So, if we generate a random permutataion the probability it allows a valid Secret Santa is $1/e$ or, say, 37%.

Isn’t it curious that searching about gift sharing by means of Secret Santa we arrived to number $e$!?


P.S. 2016-12-04 Reddit user louswins points out that this kind of permutations are called derangements