# The maths of Secret Santa

**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:

- It must be secret (nobody can know her
*Santa*) - 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:

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:

### 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:

### 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