The Secret Santa Puzzle

You may recall in the October 26, 2023 newsletter I previously discussed a game show featured on the cruise ship titled Deal or No Deal. In this game, participants had the opportunity to buy cards, granting them a chance to compete on stage. Each card provided chances for consolation prizes. Each card contained 20 suitcases, with different monetary amounts randomly hidden behind each one. Players opened the suitcases by lifting flaps, and their winnings depended on how many of the prizes on their card matched a randomly displayed sequence on a screen. A question posed in that newsletter revolved around determining the probability of achieving a specific number of matches.

This concept is commonly known as the Secret Santa dilemma, named after a seasonal gift exchange activity often held in workplaces. During this event, individuals select a name from a collective pool, determining whom they will surprise with a gift. A notable challenge in this game arises from the possibility of individuals inadvertently selecting their own names, which diminishes the excitement. Statistically, one person in each group will likely face this situation, regardless of the group's size. One of the queries I aim to resolve in this newsletter concerns the probability that no one ends up with their own name.

When I composed the newsletter on October 26, I did not have a clear method for resolving the mathematical aspects, so I relied on the Poisson function for estimations. This issue, however, has continued to trouble me. I have always considered estimates to be less than satisfactory intellectually.

Initially, I developed a computer program capable of generating all possible sequences of prizes to tally the number of matches for each variation. Unfortunately, with 13 suitcases, this program took nearly an entire day to compute all 6,227,020,800 possible sequences. To consider 20 suitcases would yield an unfathomable 2,432,902,008,176,640,000 combinations, leading to a staggering one million years to process all permutations.

Next, I turned to Excel, attempting to solve the problem using a recursive approach. Surprisingly, this turned out to be far easier than I had anticipated. I should have opted for this method from the start. The remainder of this newsletter will detail the logic underpinning this strategy.

I will presume that readers are familiar with the Excel function combin(x,y), which calculates the number of ways to select y items from a set of x. The precise formula is expressed as x!/(y!*(x-y)!).

Let’s start with some obvious cases.

1. 1. In the scenario with one Santa, it’s clear that he will always choose his own name.
2. 2. For two Santas, there exists an equal probability that both individuals receive their own names or each other’s names.
3. 3. Observing three Santas, there is exactly 1 scenario where all receive their own names. There are no combinations where two participants draw their own names because that would necessitate the last person drawing their name as well, given it would be the only name remaining. However, there are three scenarios where one person successfully draws their name, while the other two select each other’s names. The calculation yields 3*1 = 1. Thus, with a total of 3! or 6 arrangements available, the number of scenarios with 0 individuals matching their name can be deduced by subtracting the successful outcomes: 6-1-3 = 2.

Here is where we are at so far:

Matches	3 Santas	2 Santas	1 Santa
3	1
2	0	1
1	3	0	1
0	2	1	0
Total	6	2	1

Next, let’s move onto 4 Santas.

When there are 4 matches: There is always 1 way for everyone to select their respective names.

For a situation with 3 matches: it's inherently impossible for every individual to select their name except for one. If everyone else’s match occurs, the leftover individual will inevitably end up with their name as well.

In the case of 2 matches: we have combin(4,2)=6 methods to pick 2 individuals from 4 to match. The remaining 2 will inevitably select each other’s names, which accounts for 1 outcome.

For 1 match, there are 4 different options for the Santa who draws correctly. Referring back to our 3 Santa example, we see that there are 2 combinations where the other 3 fail to match. Thus, the total number of configurations for 1 match amounts to 4*2=8.

Now considering 0 matches: once again, we can find this by removing all other possibilities from the total arrangements, leading to 4! – 1 – 6 – 8 = 24-15=9.

Now we are at:

Matches	4 Santas	3 Santas	2 Santas	1 Santa
4	1
3	0	1
2	6	0	1
1	8	3	0	1
0	9	2	1	0
Total	24	6	2	1

Next, let’s move onto 5 Santas.

When it comes to 5 matches: there is always 1 way for all to select their own names.

For 4 matches: this scenario is impossible, as clarified in the discussion regarding the 4 Santas case.

In the situation of 3 matches: combin(5,3)=10 indicates the number of ways to select 3 out of 5 to pair with their own names. Furthermore, with the other 2 participants having the option to swap names, there remains just 1 way for this scenario. Therefore, the final count for 3 matches equals 10.

Regarding 2 matches: there are combin(5,2)=10 ways to choose 2 Santas from 5, and looking at the 3 Santa analysis, we find 2 methodologies where the remaining individuals fail to match. Thus, we multiply for total configurations resulting in 10*2=20.

In the case of 1 match: there are 5 ways to select the Santa who draws his own name. Observing the example with 4 Santas, we establish that there are 9 configurations where none of the other Santas align. Hence, we calculate 5*9=45 for 1 match.

For 0 matches: once again, we proceed by subtracting all other configurations from the total permutations, arriving at 5! – 1 – 0 – 10 – 20 – 45 = 44.

Now we are at:

Matches	5 Santas	4 Santas	3 Santas	2 Santas	1 Santa
5	1
4	0	1
3	10	0	1
2	20	6	0	1
1	45	8	3	0	1
0	44	9	2	1	0
Total	120	24	6	2	1

By applying this reasoning consistently, we can compile the distribution of possibilities for up to 10 Santas.

Mat.	10 Santas	9 Santas	8 Santas	7 Santas	6 Santas	5 Santas	4 Santas	3 Santas	2 Santas	1 Santa
10	1
9	0	1
8	45	0	1
7	240	36	0	1
6	1890	168	28	0	1
5	11088	1134	112	21	0	1
4	55650	5544	630	70	15	0	1
3	222480	22260	2464	315	40	10	0	1
2	667485	66744	7420	924	135	20	6	0	1
1	1334960	133497	14832	1855	264	45	8	3	0	1
0	1334961	133496	14833	1854	265	44	9	2	1	0
Total	3628800	362880	40320	5040	720	120	24	6	2	1

It's important to note that the discrepancies in the number of possibilities for 0 and 1 match always exist within a unit of each other. Total arrangements yielding 0 matches is one greater than for 1 match when the number of Santas is even and one less when it's odd. By accepting this pattern as a certainty, we can swiftly calculate the number of arrangements for 0 matches with 11 or more Santas.

For 11 Santas: If one match occurs, we have 11 possible Santas who could match themselves, complemented by 133,496 methods for the other 10 Santas to balance out without matching, a result derived from the 10 Santa situation. Hence, the total arrangements featuring one match becomes 11*133,496 = 14,684,571. Given that 11 is an odd number, the permutations for 0 matches consequently decrease by one: 14,684,571 – 1 = 14,684,570.

For 12 Santas: We find that one Santa can match, offering 12 ways to select this Santa and 14,684,570 approaches for the other 11 to avoid matching, stemming from the previous case. Therefore, the permutations for one match computes to 12*14,684,570 = 176,214,840. Since 12 is even, the arrangements for 0 matches then increase by one: 176,214,840 + 1 = 176,214,841.

Continuing this consistent approach, below are the numbers representing the configurations for 0 matches, ranging from 1 to 20 Santas, along with total arrangements and probabilities.

Santas	0 Matches	Total Permutations	Probability
20	895,014,631,192,902,000	2,432,902,008,176,640,000	0.367879
19	44,750,731,559,645,100	121,645,100,408,832,000	0.367879
18	2,355,301,661,033,950	6,402,373,705,728,000	0.367879
17	130,850,092,279,664	355,687,428,096,000	0.367879
16	7,697,064,251,745	20,922,789,888,000	0.367879
15	481,066,515,734	1,307,674,368,000	0.367879
14	32,071,101,049	87,178,291,200	0.367879
13	2,290,792,932	6,227,020,800	0.367879
12	176,214,841	479,001,600	0.367879
11	14,684,570	39,916,800	0.367879
10	1,334,961	3,628,800	0.367879
9	133,496	362,880	0.367879
8	14,833	40,320	0.367882
7	1,854	5,040	0.367857
6	265	720	0.368056
5	44	120	0.366667
4	9	24	0.375000
3	2	6	0.333333
2	1	2	0.500000
1	0	1	0.000000

It's evident how the likelihood of achieving 0 matches gradually approaches the value of 0.367879. That number may seem familiar; it's actually the mathematical constant 1/e. While I could delve into extensive detail regarding the Poisson estimate at this point, the newsletter is becoming too lengthy. For a deeper exploration, I suggest consulting Sharp Sports Betting by Stanford Wong, which elaborates on leveraging the Poisson function to analyze proposition bets for the Super Bowl.

Now, returning to the game of Deal or No Deal, which mirrors the situation of the 20 Santas case, we seek to uncover the combinations corresponding to 0 to 20 matches.

The calculation for the combinations of m matches out of a pool of 20 Santas is represented as combin(20,m)*z(m), where z(m) denotes the number of configurations yielding zero matches among m Santas. The table presented below employs this method to establish the permutations available for 0 to 20 matches among 20 Santas.

Matches	Permutations	Probability
20	1	0.000000
19	-	0.000000
18	190	0.000000
17	2,280	0.000000
16	43,605	0.000000
15	682,176	0.000000
14	10,271,400	0.000000
13	143,722,080	0.000000
12	1,868,513,010	0.000000
11	22,421,988,160	0.000000
10	246,642,054,516	0.000000
9	2,466,420,377,200	0.000001
8	22,197,783,520,770	0.000009
7	177,582,268,088,640	0.000073
6	1,243,075,876,659,240	0.000511
5	7,458,455,259,939,930	0.003066
4	37,292,276,299,704,500	0.015328
3	149,169,105,198,817,000	0.061313
2	447,507,315,596,451,000	0.183940
1	895,014,631,192,902,000	0.367879
0	895,014,631,192,902,000	0.367879
Total	2,432,902,008,176,640,000	1.000000

When juxtaposing these probabilities with my Poisson estimations provided earlier, you will observe a complete agreement at six decimal places, demonstrating the effectiveness of both the Poisson function and the significance of the constant e. October 26, 2023 newsletter In the coming week, I aim to provide further insights on this topic, including a comprehensive formula for calculating the permutations applicable to any number of Santas.

Strategies grounded in mathematical accuracy and insights relevant to casino games—spanning blackjack, craps, roulette, and countless others—await you.

Written by: Michael Shackleford