@mathprofbrony
Yes! The results from this are very surprising as most people would assume the likelihood of failure is very low. What’s even more surprising is that the size of the group doesn’t change the probability (gotta love consistency). The fact that e suddenly shows up is the icing on the cake.
Now to recap:
The function that gives the number of distinct derangements of n elements is called the “Subfactorial” and is written (!n):
If we plug in n=7, the subfactorial equation will tell us how many permutations exist where every element has shifted to a different place. In this case, it tells us how many permutations exist where no pony (or dragon) picked their own name.
If we divide this number by the total permutations possible (n!), we will get the probability that no one picks their own name. Since we want the compliment, we subtract this value from 1. This tells us the probability that someone picks their own name.
This is known as a derangement problem, or more colloquially the hat check problem.
The probability that at least one pony gets their own name (counting Spike as a pony) is the opposite of (that is, 100% minus) the probability that no pony gets their own name. We ask, in how many ways can this happen? This is the number of derangements of seven elements.
To let Opal out of the bag, there are 1854 derangements of 7 elements, out of 7! (seven factorial) or 5040 possible permutations, and so in 5040-1854 = 3186 outcomes, at least one pony gets their own name. The probability of this happening is thus 3186/5040, or approximately 63.214%. There is almost a 2 in 3 chance that some pony gets their own name!
Now, if you’re still reading you might be curious as to whether there is a better way of coming up with such a number than sitting down and looking at every single one of 5040 permutations.
There is! The method is called inclusion-exclusion.
Start with all 5040 permutations of 7 elements.
Subtract those that have at least one element in the wrong place: you can pick any one of the 7 elements to “fix,” and then there are 6! permutations of the other elements. There are 76! many such permutations. So far our sum is 7! - 76!.
But wait! you might say, mathprofbrony you doofus, seven times six-factorial is just seven-factorial again! You’ve subtracted everything!
Hold your ponies, I reply, because a lot of those got counted twice or more – any permutation where two of them were in the same place. So we have to add them back in.
To count those, we pick two of seven places to fix: we can do that in 7-choose-2 ways, or 21 ways – and then let the other five names fall where they may. There are 215! such permutations. Now our sum is
7! - 76! + 215!.
With me so far?
You’re gonna say we overcounted some again, aren’t you.
You bet your horseshoes! Any of them where three or more were in the wrong place. We have to subtract those from the ones we added back in. There are 7-choose-3 * 4!, or 354!, of those. Get the pattern? Our final sum is
Which, sure enough, is 1854. And this pattern is a lot shorter for finding derangement numbers for bigger sets.
What if the number gets really big? I don’t want to add up a lot of .
If you’re willing to approximate, then the n-th derangement number is roughly just n!/e, e being 2.71828…. Which means that if 1000000 ponies put their names into a giant hat and drew them back out, the probability that at least one pony got their own name back would still be very close to 1-1/e, or about…
63.212%.
So as it turns out, once you’re up to seven or more ponies, the chance of somepony getting their own name back doesn’t change much regardless of whether you’re drawing for 7 or 7 million.
@root
1/7 for the first person.
1/6 for the next person IF their name is still in the hat.
1/5 for the next person IF their name is still in the hat.
1/4 for the next person IF their name is still in the hat.
1/3 for the next person IF their name is still in the hat.
1/2 for the next person IF their name is still in the hat.
100% for the last person IF their name is still in the hat.
But these are offset by the probability of their name being chosen up to that point, making it 1/7 for all of them from the start. For example, there is a 6/7 chance that the last person already had their name taken. So there is a… you guessed it, 1/7 chance that their name is still left in the hat, even though they have a 100% chance of taking the last name (whoever’s it is.)
your current filter.“Gahhhh! – I see…”
Yes! The results from this are very surprising as most people would assume the likelihood of failure is very low. What’s even more surprising is that the size of the group doesn’t change the probability (gotta love consistency). The fact that e suddenly shows up is the icing on the cake.
Now to recap:
The function that gives the number of distinct derangements of n elements is called the “Subfactorial” and is written (!n):
If we plug in n=7, the subfactorial equation will tell us how many permutations exist where every element has shifted to a different place. In this case, it tells us how many permutations exist where no pony (or dragon) picked their own name.
If we divide this number by the total permutations possible (n!), we will get the probability that no one picks their own name. Since we want the compliment, we subtract this value from 1. This tells us the probability that someone picks their own name.
This is known as a derangement problem, or more colloquially the hat check problem.
The probability that at least one pony gets their own name (counting Spike as a pony) is the opposite of (that is, 100% minus) the probability that no pony gets their own name. We ask, in how many ways can this happen? This is the number of derangements of seven elements.
To let Opal out of the bag, there are 1854 derangements of 7 elements, out of 7! (seven factorial) or 5040 possible permutations, and so in 5040-1854 = 3186 outcomes, at least one pony gets their own name. The probability of this happening is thus 3186/5040, or approximately 63.214%. There is almost a 2 in 3 chance that some pony gets their own name!
Now, if you’re still reading you might be curious as to whether there is a better way of coming up with such a number than sitting down and looking at every single one of 5040 permutations.
There is! The method is called inclusion-exclusion.
Start with all 5040 permutations of 7 elements.
Subtract those that have at least one element in the wrong place: you can pick any one of the 7 elements to “fix,” and then there are 6! permutations of the other elements. There are 76! many such permutations. So far our sum is 7! - 76!.
But wait! you might say, mathprofbrony you doofus, seven times six-factorial is just seven-factorial again! You’ve subtracted everything!
Hold your ponies, I reply, because a lot of those got counted twice or more – any permutation where two of them were in the same place. So we have to add them back in.
To count those, we pick two of seven places to fix: we can do that in 7-choose-2 ways, or 21 ways – and then let the other five names fall where they may. There are 215! such permutations. Now our sum is
7! - 76! + 215!.
With me so far?
You’re gonna say we overcounted some again, aren’t you.
You bet your horseshoes! Any of them where three or more were in the wrong place. We have to subtract those from the ones we added back in. There are 7-choose-3 * 4!, or 354!, of those. Get the pattern? Our final sum is
17! - 76! + 215! - 354! + 353! - 212! + 71! - 10!.
Which, sure enough, is 1854. And this pattern is a lot shorter for finding derangement numbers for bigger sets.
What if the number gets really big? I don’t want to add up a lot of .
If you’re willing to approximate, then the n-th derangement number is roughly just n!/e, e being 2.71828…. Which means that if 1000000 ponies put their names into a giant hat and drew them back out, the probability that at least one pony got their own name back would still be very close to 1-1/e, or about…
63.212%.
So as it turns out, once you’re up to seven or more ponies, the chance of somepony getting their own name back doesn’t change much regardless of whether you’re drawing for 7 or 7 million.
MPB out.
Edited
Correct, no one has got the right answer yet. This question is deceptive in that it looks simple at first glance.
I’ll point you guys in the right direction HERE
… Still 6/7.
1 - (6/7 * 5/6 * 4/5 * 3/4 * 2/3 * 1/2)
~86%
1/7 for the first person.
1/6 for the next person IF their name is still in the hat.
1/5 for the next person IF their name is still in the hat.
1/4 for the next person IF their name is still in the hat.
1/3 for the next person IF their name is still in the hat.
1/2 for the next person IF their name is still in the hat.
100% for the last person IF their name is still in the hat.
But these are offset by the probability of their name being chosen up to that point, making it 1/7 for all of them from the start. For example, there is a 6/7 chance that the last person already had their name taken. So there is a… you guessed it, 1/7 chance that their name is still left in the hat, even though they have a 100% chance of taking the last name (whoever’s it is.)
So the answer is still 1/7.
Edited
That’s the odds of the first pony drawing their own name, now what about the others?
1 in 7.
Edited
It would be:
1/7! < factorial (since you add probabilities. 1/7 for the first person, then 1/6 for the second etc.)
1/28
(not 1/29, since the last person has a 100% chance of drawing the last name)
Edited
>>1426211p (merged)
(6x6) + (5x5) + (4x4) + (3x3) + (2x2) + (1x1) = 91
odds: 1/91
How does my math hold up ROOT?
Edited