As we approach the holiday season, some of you may soon participate in—or perhaps even organize—a “Secret Santa” exchange. Specifically, some number of people enter the exchange, and each is assigned one person (their Santee) to give a gift to (or multiple gifts… or other craziness…), in such a way that each person also receives from one person (their Santa). As organizers of such an exchange, how should we choose a permutation of the participants, i.e., an assignment of each person to his/her Santee? Here’s one method: put all names in a hat, and let each player extract a name at random. What could go wrong?

For starters, someone might pick their own name! Shopping for yourself might make the task easier, but this seems to contradict the (Christmas) spirit of the exchange. If we pick randomly as above, and if there are \(n\) people in the exchange, what is the probability that no one picks him/herself? For large \(n\), this answer tends toward \(1/e = .3679\ldots\), where \(e = 2.718\ldots\) is Euler’s number. So, with more than a 63 percent chance, someone is left out. (See below for a proof of this fact.)

What else might go wrong? Perhaps we also want to avoid two people being assigned each other, so that this pair doesn’t feel excluded. What is the chance of a randomly chosen permutation having no excluded person or pair? This can be computed to tend toward \(1/e^{3/2} = .2231\ldots\), so there is some left out person or pair with almost 80% probability. And if we wish to make sure there are no excluded groups of size at most 6, say, then the chance of failure limits to $$1-e^{-1-\frac{1}{2}-\frac{1}{3}-\frac{1}{4}-\frac{1}{5}-\frac{1}{6}} = .9137$$ for large \(n\).

So, while Santa hats may be fluffy and festive, Secret Santa hats are a bad idea. What should we do to organize our exchange? Here’s one option: just make a big cycle. Specifically, write all names in some random order and chain them up, e.g., \(2\to 6\to 7\to 3\to 1\to 4\to 5\to 2\) (if the “names” are just 1, 2, …, 7).

Where do these numbers come from?

How can we compute the probabilities mentioned above? One common method to prove the \(1/e\) probability uses the principle of Inclusion-Exclusion, but here is a sketch of an argument that doesn’t rely on this technique. Let \(A_n\) be the number of permutations of \(n\) people with no person assigned to him/herself. Such a permutation is called a Derangement, and a direct counting argument can be used to show that \(A_n = (n-1)(A_{n-1} + A_{n-2})\) (see the Wikipedia page for derangements, for example). As there are \(n!\) total permutations of the players, the desired probability is \(P_n = A_n/n!\), so the above formula can be manipulated to \(P_n-P_{n-1} = -\frac{1}{n}(P_{n-1}-P_{n-2})\). This produces \(P_n-P_{n-1} = \frac{(-1)^n}{n!}\) by induction, so we obtain $$P_n = 1-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+\cdots+\frac{(-1)^n}{n!}.$$ As \(n\) gets big this value tends toward the infinite sum \(\sum_{i=0}^\infty \frac{(-1)^i}{i!} = 1/e\).

The other probabilities mentioned take more work. A well-suited tool is that of (Exponential) Generating Functions, which in this case help organize a more complicated Inclusion-Exclusion argument. Using these, it can be shown that the probability that a random permutation of \(n\) players has no groups of size 6 or less is equal to the coefficient of \(x^n\) in the power series expansion of $$\frac{1}{1-x}\cdot e^{-\left(x+\frac{x^2}{2} + \cdots + \frac{x^6}{6}\right)}.$$