Secret Santa math problem
Poll
 | 1 vote (14.28%) | ||
| | 1 vote (14.28%) | ||
| No votes (0%) | |||
| | 3 votes (42.85%) | ||
| | 3 votes (42.85%) | ||
| | 1 vote (14.28%) | ||
| | 2 votes (28.57%) | ||
| No votes (0%) | |||
| No votes (0%) | |||
| | 3 votes (42.85%) |
7 members have voted
January 27th, 2019 at 1:50:39 PM
permalink
Your office of 100 workers does a Secret Santa gift exchange. This where you write down everybody's name on individual pieces of paper, put them in a hat, and everybody draws a name at random to give a gift to.
The question is, how many closed loops will there be, on average? For example of a closed loop, Gordon gives to Don, who gives to Jon, who gives to Nathan, who gives to Gordon. Or drawing your own name.
For extra credit, what is an expression of the answer, or a very close estimate, for large numbers of workers, n, as a function of n.
I would like to request that anyone who has won a beer in the last year not submit an answer for 24 hours. You may still explain to others why their answers are wrong or generally help out.
The question is, how many closed loops will there be, on average? For example of a closed loop, Gordon gives to Don, who gives to Jon, who gives to Nathan, who gives to Gordon. Or drawing your own name.
For extra credit, what is an expression of the answer, or a very close estimate, for large numbers of workers, n, as a function of n.
I would like to request that anyone who has won a beer in the last year not submit an answer for 24 hours. You may still explain to others why their answers are wrong or generally help out.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
January 27th, 2019 at 1:58:38 PM
permalink
If you do it the right way, just 1. https://youtu.be/GhnCj7Fvqt0 .
“Man Babes” #AxelFabulous
January 27th, 2019 at 2:38:54 PM
permalink
Quote: mipletIf you do it the right way, just 1. https://youtu.be/GhnCj7Fvqt0 .
Darn. That was going to be my answer. Really well explained there, though. We used to do it that way. So I can't really take credit for figuring it out myself anyway.
If the House lost every hand, they wouldn't deal the game.
January 27th, 2019 at 8:17:22 PM
permalink
Come on guys, this is the perfect opportunity to seize that beer while the math geniuses are on 24-hour hold.
Hint: There is a very intuitive way to solve this problem that requires no advanced math, although a spreadsheet would be helpful.
Hint: There is a very intuitive way to solve this problem that requires no advanced math, although a spreadsheet would be helpful.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
January 28th, 2019 at 4:16:04 PM
permalink
Okay, the math wizards may jump in.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
January 28th, 2019 at 6:05:37 PM
permalink
I noticed that this process forms a permutation, but that didn't seem to lead to a direct proof... I think this way might be better:
In order to analyze this process, make the guests draw in a particular order following these two rules. The ordering should be without loss of generality (*hands wave*). On drawing i: Rule 1: If Person P was on the card drawn, but has not picked a card already, P draws next. Rule 2: If the card had P who was picked before, a uniformly random person who has not selected a card goes next. Note that the person picked in Rule 2 must be at the back of the last loop, as everyone else in the loop has already been picked, and the random person starts a new loop. So, cases where Rule 2 apply are the only times our number of loops increases (by one) (we would formally track this by a random variable). We can calculate the probability of Rule 2 occurring. Since there's only one person at the back of the loop, it's 1 out of the remaining people = 1/(n-i+1). So, we have a sum from 1/n to 1. This makes sense as the first person has 1/n chance of picking himself, and the last person is guaranteed to complete a loop (since everyone else has already been picked before).
So, the answer for 100 should be the 100th harmonic number, and the answer for n should be the nth harmonic number which is on the order of logarithmic.
All of the above could be further formalized, but I think it is a good first pass?
EDIT: changed "chain" to "number of loops"
In order to analyze this process, make the guests draw in a particular order following these two rules. The ordering should be without loss of generality (*hands wave*). On drawing i: Rule 1: If Person P was on the card drawn, but has not picked a card already, P draws next. Rule 2: If the card had P who was picked before, a uniformly random person who has not selected a card goes next. Note that the person picked in Rule 2 must be at the back of the last loop, as everyone else in the loop has already been picked, and the random person starts a new loop. So, cases where Rule 2 apply are the only times our number of loops increases (by one) (we would formally track this by a random variable). We can calculate the probability of Rule 2 occurring. Since there's only one person at the back of the loop, it's 1 out of the remaining people = 1/(n-i+1). So, we have a sum from 1/n to 1. This makes sense as the first person has 1/n chance of picking himself, and the last person is guaranteed to complete a loop (since everyone else has already been picked before).
So, the answer for 100 should be the 100th harmonic number, and the answer for n should be the nth harmonic number which is on the order of logarithmic.
All of the above could be further formalized, but I think it is a good first pass?
EDIT: changed "chain" to "number of loops"
January 28th, 2019 at 6:45:32 PM
permalink
What happens if someone picks their own name?
What if the 100'th person picks their own name?
Do-over in both cases, I assume?
Almost certainly wrong, but yolo. 5.16
What if the 100'th person picks their own name?
Do-over in both cases, I assume?
Almost certainly wrong, but yolo. 5.16
January 28th, 2019 at 6:51:01 PM
permalink
There are no do-overs. Everybody picks a random name. I'm not looking for a better way to do a Secret Santa, although that is a worthy discussion.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
January 28th, 2019 at 7:23:41 PM
permalink
Quote: WizardThere are no do-overs. Everybody picks a random name. I'm not looking for a better way to do a Secret Santa, although that is a worthy discussion.
So someone can pick their own name, is that correct (according to this math problem)?
Edit: Nevermind I’m retarded. I never learned to read. Thanks djtech
Last edited by: RS on Jan 28, 2019
January 28th, 2019 at 7:54:54 PM
permalink
Quote: RSSo someone can pick their own name, is that correct (according to this math problem)?
Yes, that's in the problem statement:
Quote: Wizard... Or drawing your own name...
January 28th, 2019 at 9:09:45 PM
permalink
I agree with djtech.
I started with a complicated series of nested equations where:
E(1) = 1 and
E(N) = (N + E(N) + E(N-1) + . . . + E(1))/N
After playing around with it for awhile I noticed it was the harmonic function.
So E(100) = 1 + 1/2 + 1/3 + . . . + 1/100
And E(N) for a large enough N is approximated by ln(N) plus Euler’s constant. (I googled last bit as I couldn’t recall it.)
E(1) = 1 and
E(N) = (N + E(N) + E(N-1) + . . . + E(1))/N
After playing around with it for awhile I noticed it was the harmonic function.
So E(100) = 1 + 1/2 + 1/3 + . . . + 1/100
And E(N) for a large enough N is approximated by ln(N) plus Euler’s constant. (I googled last bit as I couldn’t recall it.)
The race is not always to the swift, nor the battle to the strong; but that is the way to bet.
January 29th, 2019 at 6:07:23 AM
permalink
unJon has the right answer, but I'd prefer to see an explanation for why it is right. The explanation is very intuitive.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
January 29th, 2019 at 6:23:15 AM
permalink
Quote: WizardunJon has the right answer, but I'd prefer to see an explanation for why it is right. The explanation is very intuitive.
I’m not sure it’s intuitive, but here’s how I got there:
Order the pickers where #1 goes first, if he picks himself, you’ve just reduced it to an N-1 game plus 1 loop (of #1 picking himself). If #1 picks someone else, then that person goes next and has an N-1 chance of picking #1, which reduces it to an N-2 game plus 1 loop (of #1 to second picker). So it nests all the way down to smaller games.
This is the same as saying that a game of N players is the same as a game of N-1 players plus the 1/N chance of the first person picking himself.
Since a 1 player game always has one loop, a two player game has 1 + 1/2 loops and a 3 player game has that plus 1/3, etc.
Order the pickers where #1 goes first, if he picks himself, you’ve just reduced it to an N-1 game plus 1 loop (of #1 picking himself). If #1 picks someone else, then that person goes next and has an N-1 chance of picking #1, which reduces it to an N-2 game plus 1 loop (of #1 to second picker). So it nests all the way down to smaller games.
This is the same as saying that a game of N players is the same as a game of N-1 players plus the 1/N chance of the first person picking himself.
Since a 1 player game always has one loop, a two player game has 1 + 1/2 loops and a 3 player game has that plus 1/3, etc.
The race is not always to the swift, nor the battle to the strong; but that is the way to bet.
January 29th, 2019 at 9:27:18 AM
permalink
There are several Secret Santa problems, but I managed to find a published scholarly paper on this particular one. It is The Secret Santa Problem by Michael J. Reske in the Pi Mu Epsilon Journal v. 10 No. 1 (1994) I have this volume and would be glad to send it as an ordinary e-mail attachment. In my opinion unJon's solution is much simpler than Reske's and could be a significant contribution to the theory of the problem.
OnceDear is a Dear!
January 29th, 2019 at 12:28:38 PM
permalink
Quote: netzerThere are several Secret Santa problems, but I managed to find a published scholarly paper on this particular one. It is The Secret Santa Problem by Michael J. Reske in the Pi Mu Epsilon Journal v. 10 No. 1 (1994) I have this volume and would be glad to send it as an ordinary e-mail attachment. In my opinion unJon's solution is much simpler than Reske's and could be a significant contribution to the theory of the problem.
Thanks, netzer. Though now Crystalmath will think I’m one of your socks. :-)
The race is not always to the swift, nor the battle to the strong; but that is the way to bet.
January 29th, 2019 at 1:54:09 PM
permalink
Quote: unJonThanks, netzer. Though now Crystalmath will think I’m one of your socks. :-)
Don't worry about that! He's been very nice to me and went to considerable trouble to check my algebra in the Biased Coin Problem. If you want the paper just send me your e-mail address in a private message and it's on it's way. That goes for CrystalMath too!
I would like to know more about you. I took my degree at Cambridge and teach Physics at the Durban University of Technology. One of my greatest experiences was reading the original papers of Sir Isaac Newton, which recently have been translated into English. Albert Einstein read them too but belittled them. Nevertheless, Newtonian physics still is accurate if you don't approach the speed of light.
OnceDear is a Dear!
January 29th, 2019 at 3:46:21 PM
permalink
Here's my answer:
Let E(n) be the expected number of "loops" in a group of n people
1/n of the time, the first person will choose himself, forming a 1-person loop; this is 1/n x (1 + E(n-1))
(n-1)/n x 1/(n-1) = 1/n of the time, the first person will choose, say, P2, and P2 chooses the first person;, forming a 2-person loop; this is 1/n x (1 + E(n-2))
(n-1)/n x (n-2)/(n-1) x 1/(n-2) = 1/n of the time, the first person will choose P2, P2 chooses P3, and P3 chooses the first person;, forming a 3-person loop; this is 1/n x (1 + E(n-3))
And so on
The total is 1/n x ((1 + E(n-1)) + (1 + E(n-2)) + (1 + E(n-3)) + ... + (1 + E(2)) + (1 + E(1)) + (1 + E(0))), where E(0) is zero
E(n) = 1/n x ((1 + E(n-1)) + (1 + E(n-2)) + (1 + E(n-3)) + ... + (1 + E(2)) + (1 + E(1)) + (1 + E(0)))
= 1/n x (1 + E(n-1)) + (n-1)/n x 1/(n-1) x ((1 + E(n-2)) + (1 + E(n-3)) + ... + (1 + E(2)) + (1 + E(1)) + (1 + E(0)))
= 1/n + E(n-1) / n + (n-1)/n x E(n-1)
= 1/n + E(n-1)
Thus, the value is recursive; E(100) = 1/100 + E(99) = 1/100 + 1/99 + E(98) = 1/100 + 1/99 + 1/98 + E(97) = ...
= 1/100 + 1/99 + 1/98 + ... + 1/3 + 1/2 + E(1)
E(1) = 1, since there is always one loop in a set of one person
The answer is 1 + 1/2 + 1/3 + ... + 1/99 + 1/100, or about 5.18738.
Let E(n) be the expected number of "loops" in a group of n people
1/n of the time, the first person will choose himself, forming a 1-person loop; this is 1/n x (1 + E(n-1))
(n-1)/n x 1/(n-1) = 1/n of the time, the first person will choose, say, P2, and P2 chooses the first person;, forming a 2-person loop; this is 1/n x (1 + E(n-2))
(n-1)/n x (n-2)/(n-1) x 1/(n-2) = 1/n of the time, the first person will choose P2, P2 chooses P3, and P3 chooses the first person;, forming a 3-person loop; this is 1/n x (1 + E(n-3))
And so on
The total is 1/n x ((1 + E(n-1)) + (1 + E(n-2)) + (1 + E(n-3)) + ... + (1 + E(2)) + (1 + E(1)) + (1 + E(0))), where E(0) is zero
E(n) = 1/n x ((1 + E(n-1)) + (1 + E(n-2)) + (1 + E(n-3)) + ... + (1 + E(2)) + (1 + E(1)) + (1 + E(0)))
= 1/n x (1 + E(n-1)) + (n-1)/n x 1/(n-1) x ((1 + E(n-2)) + (1 + E(n-3)) + ... + (1 + E(2)) + (1 + E(1)) + (1 + E(0)))
= 1/n + E(n-1) / n + (n-1)/n x E(n-1)
= 1/n + E(n-1)
Thus, the value is recursive; E(100) = 1/100 + E(99) = 1/100 + 1/99 + E(98) = 1/100 + 1/99 + 1/98 + E(97) = ...
= 1/100 + 1/99 + 1/98 + ... + 1/3 + 1/2 + E(1)
E(1) = 1, since there is always one loop in a set of one person
The answer is 1 + 1/2 + 1/3 + ... + 1/99 + 1/100, or about 5.18738.
January 29th, 2019 at 5:16:36 PM
permalink
Quote: unJonI’m not sure it’s intuitive, but here’s how I got there...
Nice explanation and now I can see a proof by induction. Thinking a little and adapting your proof slightly here's an alternative way to look at it using your A and B idea.
Suppose there are n people and look at the first one A.
(i) If A has picked himself then the answer is 1 + f(n-1); as has been explained the chance of this is 1/n.
(ii) If A has picked someone else, then let that person be B and, as above, put them as the second person; the chance of this is (n-1)/n.
The loop that starts with A B ... ... eventually finishes when someone picks A. It also means noone else in this layout can pick B, but someone somewhere has picked A.
Now consider the situation of the remaining (n-1) people (i.e. excluding A) but whoever picked A above now picks B instead. This layout forms the same number of loops as the one above. The loop that includes B is the same except above it goes A B ... and here it goes B ... . All the other loops are identical.
Therefore the expected number of loops once it is known that A picks B, is the same as for (n-1) people, i.e. f(n-1).
Thus f(n) = the sum of the above = 1/n * ( 1+f(n-1) ) + (n-1)/n * f(n-1) = 1/n + f(n-1).
As f(1)=1, f(n)=1+1/2+1/3....+1/n.
Suppose there are n people and look at the first one A.
(i) If A has picked himself then the answer is 1 + f(n-1); as has been explained the chance of this is 1/n.
(ii) If A has picked someone else, then let that person be B and, as above, put them as the second person; the chance of this is (n-1)/n.
The loop that starts with A B ... ... eventually finishes when someone picks A. It also means noone else in this layout can pick B, but someone somewhere has picked A.
Now consider the situation of the remaining (n-1) people (i.e. excluding A) but whoever picked A above now picks B instead. This layout forms the same number of loops as the one above. The loop that includes B is the same except above it goes A B ... and here it goes B ... . All the other loops are identical.
Therefore the expected number of loops once it is known that A picks B, is the same as for (n-1) people, i.e. f(n-1).
Thus f(n) = the sum of the above = 1/n * ( 1+f(n-1) ) + (n-1)/n * f(n-1) = 1/n + f(n-1).
As f(1)=1, f(n)=1+1/2+1/3....+1/n.
January 29th, 2019 at 7:50:14 PM
permalink
Good work people! I think we can quit hiding comments in spoiler tags. This may be one of the other solutions in different words, but here is how I think of it.
Suppose there is just one employee who comes to the Secret Santa party. Obviously he will pick himself, so one closed loop.
Then a second employee arrives late and asks to join. They give her a list of the now two employees. There is a 1/2 chance she picks employee 1 and 1/2 herself. If she picks employee 1, then she can be squeezed into his loop, where she buys for employee 1 and he buys for her. So, now we're at 1 + 0.5*1 = 1.5
Then a third employee arrives late and asks to join. They give her a list of the now 3 employees. There is a 2/3 chance she picks employee 1 or 2 and 1/3 herself. If she picks employee 1 or 2, then she can be squeezed into their loop, where she buys for employee she picks and the one who formally was supposed to buy for that employee now buys for 3. So, now we're at 1.5 + (1/3) = 11/6.
Then a fourth employee arrives late and asks to join. They give her a list of the now 4 employees. There is a 3/4 chance she picks employee 1 to 3 and 1/4 herself. If she picks employee 1 to 3, then she can be squeezed into their loop, where she buys for employee she picks and the one who formally was supposed to buy for that employee now buys for 4. So, now we're at 11/6 + (1/4) = 25/12.
Keep doing this and the final answer is 1/1 + 1/2 + 1/3 + ... + 1/100 =~ 5.187377518.
Suppose there is just one employee who comes to the Secret Santa party. Obviously he will pick himself, so one closed loop.
Then a second employee arrives late and asks to join. They give her a list of the now two employees. There is a 1/2 chance she picks employee 1 and 1/2 herself. If she picks employee 1, then she can be squeezed into his loop, where she buys for employee 1 and he buys for her. So, now we're at 1 + 0.5*1 = 1.5
Then a third employee arrives late and asks to join. They give her a list of the now 3 employees. There is a 2/3 chance she picks employee 1 or 2 and 1/3 herself. If she picks employee 1 or 2, then she can be squeezed into their loop, where she buys for employee she picks and the one who formally was supposed to buy for that employee now buys for 3. So, now we're at 1.5 + (1/3) = 11/6.
Then a fourth employee arrives late and asks to join. They give her a list of the now 4 employees. There is a 3/4 chance she picks employee 1 to 3 and 1/4 herself. If she picks employee 1 to 3, then she can be squeezed into their loop, where she buys for employee she picks and the one who formally was supposed to buy for that employee now buys for 4. So, now we're at 11/6 + (1/4) = 25/12.
Keep doing this and the final answer is 1/1 + 1/2 + 1/3 + ... + 1/100 =~ 5.187377518.
Last edited by: Wizard on Jul 18, 2022
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
January 29th, 2019 at 8:16:56 PM
permalink
Wow I can’t believe I actually did this correctly (I didn’t add in 1/99 and 1/100 and maybe 1/98 [but originally I did!] because I don’t know how to read the rules). *Applauses for RS*
Yes I am quite humble.
January 30th, 2019 at 7:49:02 AM
permalink
Here is an extension of this problem.
Suppose you have 100 shoelaces. They are all in a box with only the ends protruding. You tie the ends to each other randomly. When you're done, how many closed loops will there be?
Suppose you have 100 shoelaces. They are all in a box with only the ends protruding. You tie the ends to each other randomly. When you're done, how many closed loops will there be?
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
January 30th, 2019 at 8:20:12 AM
permalink
Without thinking about it much I can see that when you've picked one end of lace A there are 199 other ends. The change here is the probability of picking yourself is 1/199 rather than 1/100. The logic of recursion is the same so it's 1+1/3+1/5...+1/199. As a check the chances of picking the same lace when there are 2 laces is 1/3, so the average number f(2) is 1 1/3. The value of f(100)=3.284342...
January 30th, 2019 at 11:02:58 AM
permalink
I agree with Charlie's answer.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
October 16th, 2023 at 10:00:02 AM
permalink
Sorry to wake up an old thread, but I recently played a Deal or No Deal game on a cruise ship. Every card had 20 cases with 20 different prizes. A computer then randomly mixed up the prizes for an actual game, where the player was chosen randomly. However, everyone with a card got to play along and was eligible for prizes according to how many of his prizes matched the random placement.
To convert this to the Secret Santa problem, if there are 20 people in the exchange, what is the probability any given number from 0 to 20 (except 19) draw their own prize?
I haven't thought about this for a while. Can anyone who recalls the method of the calculating the answer better than I provide the combinations? Otherwise, I'll go with estimates using the Poisson distribution, which I'm sure are very close. However, it's always so unsatisfying to go with estimates.
To convert this to the Secret Santa problem, if there are 20 people in the exchange, what is the probability any given number from 0 to 20 (except 19) draw their own prize?
I haven't thought about this for a while. Can anyone who recalls the method of the calculating the answer better than I provide the combinations? Otherwise, I'll go with estimates using the Poisson distribution, which I'm sure are very close. However, it's always so unsatisfying to go with estimates.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
November 1st, 2023 at 4:39:03 PM
permalink
To reply to my own post, I wrote a program to count the combinations for any number of matches and number number of Santas. 15 Santas took several hours to loop through, so that is as far as I got with that. However, I discovered a pretty easy recursive method to find any number of matches. Here it is.
It's obvious with 1 Santa there is a 100% chance at a match.
With 2 Santas, there is a 50/50 chance of 0 and 2 matches.
3 Santas
With 3, or any number, there is always 1 way that everybody matches.
There are always 0 ways to have s-1 matches with s Santas. This is because if the s-1 people match, the last person has only his name left, so he must match too. So, 0 ways to have 2 matches.
For one match, there are 3 Santas that can be that one match. Then there is 1 way the other two people can be assigned each other. So 3*1 = 3 ways to have one match.
For zero matches, there are 6! - 1 - 3 = 2 ways. I will get to a more logical formula later in this post.
4 Santas
As always, there is one way everybody (4) matches.
By the logic for 3 Santas, it's impossible to have 3 matches with 4 Santas, so 0 combinations.
For 2 matches, there are combin(4,2)=6 ways to choose the two matching Santas out of four. Then there is one way the other two do not match (from 2 Santas). So 6 ways 2 match.
For 1 match, there are 4 ways to choose the one Santa who does match. We saw from 3 Santas there are 2 ways the other 3 Santas do not match. So 4*2=8 ways there is one match.
Out of 4!=24 possible orders, the number of combinations for zero matches is 24-1-6-8=9 ways zero match.
5 Santas
As always, there is one way everybody (5) matches.
By the logic for 3 Santas, it's impossible to have 4 matches with 5 Santas, so 0 combinations for 4 matches.
For 3 matches, there are combin(5,3)=10 ways to choose the 3 matching Santas out of 5. Then there is one way the other two do not match (from 2 Santas). So 10 ways 2 match.
For 2 matches, there are combin(5,3)=10 ways to choose the 2 matching Santas out of 5. Then there are 2 ways the other two do not match (from 3 Santas). So 10*2=20 ways 2 match out of 5.
For 1 match, there are 5 ways to choose the one Santa who does match. We saw from 4 Santas there are 9 ways the other 5 Santas do not match. So 5*9=45 ways there is one match.
Out of 5!=120 possible orders, the number of combinations for zero matches is 120-1-10-20-45=44 ways zero match zero.
Just keep following this logic.
The following table shows the combinations up to 10 Santas.
Notice how the combinations for zero matches are always one more or less than for one match. It's one more for an even number of Santas and one less for odd. Very interesting!
You can use that formula for the case of zero matches, although I know it is so unsatisfying when you can't prove why it works, other than observing that it always does.
I may write later on my logic in C++ to count use a looping program to do this the hard way, if there is any interest.
Hours of work went this this post, which will probably explain why it gets no replies.
It's obvious with 1 Santa there is a 100% chance at a match.
With 2 Santas, there is a 50/50 chance of 0 and 2 matches.
3 Santas
With 3, or any number, there is always 1 way that everybody matches.
There are always 0 ways to have s-1 matches with s Santas. This is because if the s-1 people match, the last person has only his name left, so he must match too. So, 0 ways to have 2 matches.
For one match, there are 3 Santas that can be that one match. Then there is 1 way the other two people can be assigned each other. So 3*1 = 3 ways to have one match.
For zero matches, there are 6! - 1 - 3 = 2 ways. I will get to a more logical formula later in this post.
4 Santas
As always, there is one way everybody (4) matches.
By the logic for 3 Santas, it's impossible to have 3 matches with 4 Santas, so 0 combinations.
For 2 matches, there are combin(4,2)=6 ways to choose the two matching Santas out of four. Then there is one way the other two do not match (from 2 Santas). So 6 ways 2 match.
For 1 match, there are 4 ways to choose the one Santa who does match. We saw from 3 Santas there are 2 ways the other 3 Santas do not match. So 4*2=8 ways there is one match.
Out of 4!=24 possible orders, the number of combinations for zero matches is 24-1-6-8=9 ways zero match.
5 Santas
As always, there is one way everybody (5) matches.
By the logic for 3 Santas, it's impossible to have 4 matches with 5 Santas, so 0 combinations for 4 matches.
For 3 matches, there are combin(5,3)=10 ways to choose the 3 matching Santas out of 5. Then there is one way the other two do not match (from 2 Santas). So 10 ways 2 match.
For 2 matches, there are combin(5,3)=10 ways to choose the 2 matching Santas out of 5. Then there are 2 ways the other two do not match (from 3 Santas). So 10*2=20 ways 2 match out of 5.
For 1 match, there are 5 ways to choose the one Santa who does match. We saw from 4 Santas there are 9 ways the other 5 Santas do not match. So 5*9=45 ways there is one match.
Out of 5!=120 possible orders, the number of combinations for zero matches is 120-1-10-20-45=44 ways zero match zero.
Just keep following this logic.
The following table shows the combinations up to 10 Santas.
| Matches | 10 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 |
|---|---|---|---|---|---|---|---|---|---|---|
| 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 |
Notice how the combinations for zero matches are always one more or less than for one match. It's one more for an even number of Santas and one less for odd. Very interesting!
You can use that formula for the case of zero matches, although I know it is so unsatisfying when you can't prove why it works, other than observing that it always does.
I may write later on my logic in C++ to count use a looping program to do this the hard way, if there is any interest.
Hours of work went this this post, which will probably explain why it gets no replies.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
November 14th, 2023 at 11:59:23 AM
permalink
To reply to my own post again, here is a formula for the number of combinations of zero matches with n secret Santas:
n!*(1/2! - 1/3! + 1/4! - 1/5! + ... ) alternating + and - up to 1/n!.
Questions on notation:
1. Where is factorial in the order of operations? Do you think it's clear in this case to do the factorial before division?
2. How should I express this formula. I'm unsure of the notation when the signs alternate and it's unclear if the last operation is + or -. By the way, the last operation is positive if n is even and negative if odd.
n!*(1/2! - 1/3! + 1/4! - 1/5! + ... ) alternating + and - up to 1/n!.
Questions on notation:
1. Where is factorial in the order of operations? Do you think it's clear in this case to do the factorial before division?
2. How should I express this formula. I'm unsure of the notation when the signs alternate and it's unclear if the last operation is + or -. By the way, the last operation is positive if n is even and negative if odd.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
November 14th, 2023 at 12:14:29 PM
permalink
I think that factorial is a special notation of multiplication, and "PEMDAS" is pretty clear that it comes before division.
No extra parenthesis should be necessary.
No extra parenthesis should be necessary.
May the cards fall in your favor.
