The Secret Santa Puzzle
You may recall in the October 26, 2023 newsletter I wrote about a game show they played on the ship known as Deal or No Deal. In that game, every player could purchase cards for a chance to play on stage. However, every card had a chance to win consolation prizes. The way the consolation prizes worked was that each card had 20 suitcases with 20 different monetary prizes randomly placed behind the 20 boxes. The suitcases were opened by lifting up flaps. The player won according to how many of the prizes on his card matched a random shuffle of the same prizes shown on a screen. An unsolved problem from that newsletter was the probability of any given number of matches.
This problem is usually referred to as the Secret Santa puzzle. It gets the name from the Christmas party activity where a group of people, usually in the same office, each pick a name from a hat of all office workers to determine who to give a gift to. A problem with the game is that there is a chance of drawing your own name, which is no fun. On average, this will happen to one player in every office, regardless of the number of workers. One question I endeavor to answer in this newsletter is the exact probability nobody draws his own name.
At the time I wrote the Oct 26 newsletter, I didn’t know exactly how to work out the math, so used the Poisson function to make estimates. However, the problem has been gnawing at me ever since. I have always found estimates to be so intellectually unsatisfying.
First, I wrote a computer program to cycle through all possible orders of prizes and count the number of matches with each permutation. However, with 13 suitcases, that program took about a day to cycle through all 6,227,020,800 permutations. 20 suitcases would have 2,432,902,008,176,640,000 permutations, which would have taken about one million years to cycle through.
Second, I went to Excel and tried to work it out recursively. This was much easier than expected. I should have done it this way to begin with. The rest of this newsletter will explain the logic behind that approach.
I assume the reader is familiar with the Excel combin(x,y) function, which is the number of ways to choose y items out of x. The exact equation is x!/(y!*(x-y)!).
Let’s start with some obvious cases.
- 1. With one Santa, it is obvious he gets his own name.
- 2. With two Santas, there is a 50/50 chance both people get their own names or each other’s names.
- 3. With three Santas, there is 1 way everyone gets his own name. There are 0 ways two people get their own name, because if they did, the last person would draw his name too because it’s the only one left. There are 3 ways one person gets his own name, one for each of the 3 people and then 1 way the other two get each other’s names. 3*1 = 1. There are a total of 3!=6 possible ways to order 3 names. The number of ways 0 people get their own name is whatever is left: 6-1-3 = 2.
Here is where we are at so far:
| Matches | 3 Santas | 2 Santas | 1 Santas |
| 3 | 1 | ||
| 2 | 0 | 1 | |
| 1 | 3 | 0 | 1 |
| 0 | 2 | 1 | 0 |
| Total | 6 | 2 | 1 |
Next, let’s move onto 4 Santas.
4 matches: There is always 1 way everyone gets their own name.
3 matches: It’s always impossible for everybody to draw their name except one person. After everybody but one person matched, there would be only one person and one name left they would have to be the same.
2 matches: There are combin(4,2)=6 ways to choose 2 people out of 4 to match. With the other 2, there is 1 way they don’t match, by drawing each other’s name.
1 match: There are 4 ways to choose the Santa who matches himself. We can see from the 3 Santa case there are 2 ways the other 3 Santas do not match, which would have to happen. So, the number of combinations for 1 match is 4*2=8.
0 matches: Again, we subtract all other possibilities from the total permutations. 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.
5 matches: There is always 1 way everyone gets their own name.
4 matches: Impossible, for reasons stated in the 4 Santas case.
3 matches: There are combin(5,3)=10 ways to choose 3 people out of 5 to match themselves. There is 1 way the other two can get each other’s names. So, there are 10 ways for 3 matches.
2 matches: There are combin(5,2)=10 ways to choose 2 people out of 5 to match. With the other 3, there are 2 ways they don’t match, which we see from the 3 Santa case. So, there are 10*2=20 ways for 2 matches.
1 match: There are 5 ways to choose the Santa who matches himself. We can see from the 4 Santa case there are 9 ways the other 4 Santas do not match, which would have to happen. So, the number of combinations for 1 match is 5*9=45.
0 matches: Again, we subtract all other possibilities from the total permutations. 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 |
Following the same logic, we get the following table 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 |
Note that the number of permutations for 0 and 1 match are always within one of each other. The total for 0 matches is one more than 1 match for even number of Santas and one less for an odd number. If we accept that this is always the case, which it is, we can quickly determine the number of 0 matches for 11 or more Santas, as follows.
11 Santas: For one match, there are 11 Santas to be the one to match and 133,496 ways the other 10 do not match, from the 10 Santa case. The number of permutations for 1 match is thus 11*133,496 = 14,684,571. Since 11 is odd, the number of permutations for 0 matches is one less, or 14,684,571 – 1 = 14,684,570.
12 Santas: For one match, there are 12 Santas to be the one to match and 14,684,570 ways the other 11 do not match, from the 11 Santa case. The number of permutations for 1 match is thus 12*14,684,570 = 176,214,840. Since 12 is even, the number of permutations for 0 matches is one more, or 176,214,840 + 1 = 176,214,841
Continuing with the same logic, here are the number of permutations for 0 matches for 1 to 20 Santas, including the total permutations and probability.
| 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 |
Notice how the probability of 0 matches approaches 0.367879. Does that number look familiar? It should! It’s 1/e. I could write a short book at the Poisson estimate at this point, but this newsletter is already running too long. For more on that, I recommend Sharp Sports Betting by Stanford Wong, which explains how to use the Poisson function to analyze Super Bowl proposition bets.
Let’s get back to the Deal or No Deal game, which is equivalent to the 20 Santa case. We want to know the number of combinations for 0 to 20 matches.
The number of combinations for m matches out of 20 Santas is combin(20,m)*z(m), where z(m)=number of combinations of zero matches for m Santas. The following table uses that method to find the number of permutations for 0 to 20 matches with 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 |
If you compare those probabilities to my Poisson estimates in the October 26, 2023 newsletter you will see all agree to the six decimal points provided, which goes to show the usefulness of the Poisson function and the number e.
Next week, I plan to elaborate on this topic and show a general formula for the number of permutations for any number of Santas.