Derangements - Numberphile
video description
Example. Let n = 4 and m = 0. We have! 4 = 9 so 9 permutations with no fixed points.
Let n = 4 and m = 1. We have C ( 4, 1 ) = 4 and! 3 = 2 so 8 permutations with one fixed point.
Let n = 4 and m = 2. We have C ( 4, 2 ) = 6 and! 2 = 1 so 6 permutations with two fixed points.
Let n = 4 and m = 3. We have C ( 4, 3 ) = 4 and! 1 = 0 so no permutations with three fixed points.
Let n = 4 and m = 4. We have C ( 4, 4 ) = 1 and! 0 = 1 so one permutation with four fixed points.
Total number 9 + 8 + 6 + 0 + 1 = 24 = 4!
Date: 2022-04-08
Related videos
Comments and reviews: 9
tildessmoo
I have a deck of cards on my desk, so I tried this out with all 13 hearts (with half-hearted shuffling. My first two tries, there were no fixed points. The next two had two each, which were two apart (4, 6; 7, 9. Isn't it fun when small samples of randomness appear to demonstrate patterns?
Anyway, while the exact ratio is interesting, it's not hard to intuit that the chances of at least one fixed point emerging is greater than 50%: There's more ways to have _one or more_ match than to have none. (Emphasis because -one or more- is quite distinct from -one and only one. -) Also, while I wouldn't have predicted e to be part of this, I'm not surprised, given this is related to probability.
reply
I have a deck of cards on my desk, so I tried this out with all 13 hearts (with half-hearted shuffling. My first two tries, there were no fixed points. The next two had two each, which were two apart (4, 6; 7, 9. Isn't it fun when small samples of randomness appear to demonstrate patterns?
Anyway, while the exact ratio is interesting, it's not hard to intuit that the chances of at least one fixed point emerging is greater than 50%: There's more ways to have _one or more_ match than to have none. (Emphasis because -one or more- is quite distinct from -one and only one. -) Also, while I wouldn't have predicted e to be part of this, I'm not surprised, given this is related to probability.
reply
Benny
Looks a bit like a solitaire card game i play once in a while, called Counting Solitaire (the only solitaire game i know wher you dont need a table or other surface to play on. Shuffle the deck, start counting from 1 (ace) to 13 (king) while looking through the deck one card at a time. If you get a match, you start counting from 1 for the next card (i. e. 5th card is a match, the next count is 1 and then continue. The goal is to count through the whole deck. If you get to 13 without getting a match and still have cards left to count, you lose.
I wonder what the probability of winning that solitaire is.
reply
Looks a bit like a solitaire card game i play once in a while, called Counting Solitaire (the only solitaire game i know wher you dont need a table or other surface to play on. Shuffle the deck, start counting from 1 (ace) to 13 (king) while looking through the deck one card at a time. If you get a match, you start counting from 1 for the next card (i. e. 5th card is a match, the next count is 1 and then continue. The goal is to count through the whole deck. If you get to 13 without getting a match and still have cards left to count, you lose.
I wonder what the probability of winning that solitaire is.
reply
Chris
I've been looking at what happens when you sum mutual digit derangements. For example 247, 742, 274 are derangements of each other. Any other permutation, such as 724 has at least one element, 7, in the same position. The sum always seems to be a multiple of 37. I don't think that's got anything to do with 1/e, but with what you get when you factorize repunits of varying size. 111 = 3-37, and 1111 = 11-101, so the sum of say 2473 and its derangements 3247, 7324, 4732 is 17776 = 11-101-16. For 5 digit derangement sets the sum is a multiple of 41 and 271.
reply
I've been looking at what happens when you sum mutual digit derangements. For example 247, 742, 274 are derangements of each other. Any other permutation, such as 724 has at least one element, 7, in the same position. The sum always seems to be a multiple of 37. I don't think that's got anything to do with 1/e, but with what you get when you factorize repunits of varying size. 111 = 3-37, and 1111 = 11-101, so the sum of say 2473 and its derangements 3247, 7324, 4732 is 17776 = 11-101-16. For 5 digit derangement sets the sum is a multiple of 41 and 271.
reply
looney1023
2 questions:
1. Why is the probability a -constant-? The approximation of e get better as n gets larger, and thus the probability will increase as n increases, approaching 1/e, but not truly a constant?
2. How does this formulation of the secretary problem relate to the secretary problem discussed in the -choosing the best toilet video-? That is, you should reject the first 100/e% of applicants then choose the next one that is better than all the previous and you'll have a 100/e% chance of having the best one overall?
reply
2 questions:
1. Why is the probability a -constant-? The approximation of e get better as n gets larger, and thus the probability will increase as n increases, approaching 1/e, but not truly a constant?
2. How does this formulation of the secretary problem relate to the secretary problem discussed in the -choosing the best toilet video-? That is, you should reject the first 100/e% of applicants then choose the next one that is better than all the previous and you'll have a 100/e% chance of having the best one overall?
reply
SD
I thought he would mention this. When you divide n! by e, you get a number between two integers. The closer one is the number of derangements. The other one is the number of permutations with exactly one fixed point. For example 4! /e is about 8. 83. 9 derangements and 8 permutations with one fixed point. 5! /e gives you 44. 145. 44 derangements and 45 permutations with one fixed point. For n even, the number of derangements is larger. For n odd, it is smaller.
reply
I thought he would mention this. When you divide n! by e, you get a number between two integers. The closer one is the number of derangements. The other one is the number of permutations with exactly one fixed point. For example 4! /e is about 8. 83. 9 derangements and 8 permutations with one fixed point. 5! /e gives you 44. 145. 44 derangements and 45 permutations with one fixed point. For n even, the number of derangements is larger. For n odd, it is smaller.
reply
Nicolai
finding out how likely it is for m out of n match up should be rather straightforward, as long as n-m>3. After all, if you have at least m-1 matching up, then the chance for m matching up should just be the same problem as 1 matching up out of the n-m+1 subset, so you can just concatenate to (1-1/e)-m. if you want to exclude any more after m to match up, you jsut multiply by 1/e again
reply
finding out how likely it is for m out of n match up should be rather straightforward, as long as n-m>3. After all, if you have at least m-1 matching up, then the chance for m matching up should just be the same problem as 1 matching up out of the n-m+1 subset, so you can just concatenate to (1-1/e)-m. if you want to exclude any more after m to match up, you jsut multiply by 1/e again
reply
Nikola
Wait wait wait. Something doesnt make sense to me. If you you have 100 people and 100 hats. And you are the first to go get his hat. The probability is 66/100? To me it sounds like its 1 in 100? Or is the probabilty calculated once all hats have been distributed? So if you are 99th person and nobody has gotten your hat. Even thou they were 100 you would have 1 in 2 chance to get it?
reply
Wait wait wait. Something doesnt make sense to me. If you you have 100 people and 100 hats. And you are the first to go get his hat. The probability is 66/100? To me it sounds like its 1 in 100? Or is the probabilty calculated once all hats have been distributed? So if you are 99th person and nobody has gotten your hat. Even thou they were 100 you would have 1 in 2 chance to get it?
reply
education
What if you have a deck of 52 cards, and the participant is to guess the first 20 cards to be dealt out. The dealer lays out 20 cards. A match is a card lining up with the participant's sequence. I am getting a probability of 32% for at least 1 match occurring. Are you able to describe the math behind that?
reply
What if you have a deck of 52 cards, and the participant is to guess the first 20 cards to be dealt out. The dealer lays out 20 cards. A match is a card lining up with the participant's sequence. I am getting a probability of 32% for at least 1 match occurring. Are you able to describe the math behind that?
reply
Mannershark
Cool, I know the 1-1/e from randomization algorithms. At first, it didn't seem related at all, but once we got into the bipartite graph I remembered it.
Also, randomization algorithms are hilarious: Say you have a chance of 1/2-n to succeed, then just repeat it 2-n times to get a 1-1/e success rate.
reply
Cool, I know the 1-1/e from randomization algorithms. At first, it didn't seem related at all, but once we got into the bipartite graph I remembered it.
Also, randomization algorithms are hilarious: Say you have a chance of 1/2-n to succeed, then just repeat it 2-n times to get a 1-1/e success rate.
reply
Add a review, comment
Other channel videos
