Derangements – Numberphile

Derangements – Numberphile


I’ve got 10 cards here. I’m gonna shuffle them up. They’re just one to ten, or ace to ten. You can see there, look. Ace of hearts, ten of hearts, nine, look. Seven, four. So I’m just gonna shuffle them up, I’m gonna lay them out, I’ll count- Brady: “Hey Jamie, It looks like you’ve got the world’s smallest hands.” These are normal sized cards. I’m just a tiny person. I’m gonna lay these out. I’ll count along when I lay them out. And I win… if the position matches its value, which means if ace comes out first, I win. If, if the four comes out fourth, I win, okay? Now, what’s the chance of me winning this game? So, am I likely to get a match? That’s the question. Am I likely to get a match? Do you think it’s likely? Do you think it’s unlikely? Do you think it’s greater than 50%? Do you think it’s less than 50%? 1 2 3 4 5 6 7 8 9 ah, 10! So I got no match. Now, is that what you expected? Did you expect me to get no match? Well, actually I think I was quite unlucky there to get no match, because the probability of having no match is 37%. So, the probability of getting one match, winning the game, would have been 63%, so it’s actually more likely to win. Over 50%, not a huge amount over 50%, so it can go wrong, okay? So you can lose this game. Brady: “If you’re a specially unlucky guy.” Yeah, if you’re like me. If you’re unlucky like me, you might lose this game. But I used 10 cards here, and the probability of winning with 10 cards is 63%. Do you think, then, if I had 100 cards, am I more likely to get a match, or less likely to get a match? Well, I can tell you it’s still 63%. It doesn’t matter. It doesn’t matter how many cards you have, it’s a constant. It’s gonna be 63% no matter how many cards you have. Brady: “What if it’s two cards?” Okay, you caught me out there. I was gonna get to that. I was gonna get to that. It’s 63% if you use four or more cards. So pretty much any game, okay? So you don’t, a game that uses three and two and one… uh, is not 63%, but hey, four or more and you will always get 63% chance of winning. That’s a, that’s a constant. So the way you solve this problem, it’s about matches, getting a match. Or not getting a match. And these things where you are not looking for a match is called as a derangement. A derangement, which is such fun to say! So we’re gonna get deranged, so let’s do that. So if you’re mixing up cards or any objects like that, that’s called a permutation, or you might call it an arrangement. Maybe that’s a word you would use. If I had, say, five things, let’s do five dots, Eh, five dots here. And then I could arrange them in any way. I’m gonna do that with arrows, to show that, you know, one becomes two, two becomes three, let’s say three becomes five, Let’s say four goes across to four, and five becomes one, like that. So you can have any kind of scramble like that. So how many ways can you scramble those objects? Well, that’s n factorial, in general, so there are n factorial ways you can scramble up n objects, number, um, number of permutations, n factorial. Now a derangement is a permutation that has no fixed points. Now, this is not a derangement. Look. Four went to four. It’s fixed. It didn’t change. That’s not a derangement. So a derangement is something like that, but there are no fixed points. So if I did the same sort of idea, and draw one in, a derangement would mean something like this, maybe like that, and maybe something down there, there you go. That would be a valid derangement. And the symbol for derangements, so how many derangements are there? So it’s a subset of permutations. So there’s fewer. And the number of derangements has this symbol. It’s exclamation mark n. It’s like a backwards factorial. Now, how many of these are there? Well, there’s a formula for that. The number of derangements is approximately the number of permutations divided by e. [gasp] Surprise e! Oh, where did that come from? Surprise e! There he is! And that, in fact, is a very accurate formula. In fact, you, say approximately, just take the nearest integer, round up or round down, and you’re done. That’s how many derangements there are. Boom, straight away. So if I’m interested in the probability of losing this game, I’m looking in, I’m looking at the probability of no fixed points. So it’s, I’m looking for the number of derangements, so it’s probability of no fixed points. Brady: “And you found one there, didn’t you? That was a no fixed points.” This was a, this was a derangement. I accidentally had a derangement. I didn’t plan it, I just went and saw what happened. Brady: “So we thought you lost, but you’re a genius!” Well, I didn’t plan it, but, but it works out for this video. so if you want to find the probability of no fixed points, it’s how many derangements we have. So this is equal to number of derangements divided by the total number of ways I could have scrambled up those n objects, which is the total number of permutations. So if this is the probability of no fixed points, you’re taking all the derangements and dividing by all the possible permutations, and we have a formula for that, and so this is going to be approximately 1 over e, which is going to be 0.37, which is why it’s 37% to get a derangement, or 63% to get a match, which is the opposite question. So one of the classic versions of this same problem is called the secretary problem. So imagine having a secretary, and that person’s got letters to various people, and they’ve got envelopes to those same people, so you need to put the letters in the right envelopes. So that secretary, they’re looking at their watch, they’re trying to get out the door, right? So they’re just quickly shoving in letters into envelopes. What’s the probability that at least one letter goes to the right person? Ends up in the right envelope. And that’s going to be 63%. Another version of the same problem is the hat problem, hat checking problem, this sounds a bit old-fashioned to me, sounds a bit Edwardian. Which is, you go to the theater, and people check their hats at the cloakroom. That sounds very old-fashioned. But they put them in boxes, and then they just give them out back to people without thinking. So again, what’s the probability that someone gets their hat back? 63% again. So there are various versions of the same question. Brady: “Would we be using the same style of mathematics if we started wanting to know what’s the probability of “two people getting their hat back, or 10 people, or would we start using other mathematical weapons to figure that out?” Yeah, so to answer the question of exactly two people, something like that, it’s harder. What I’ve actually done here is worked out the probability that no one gets the correct match. And that’s quite an easy thing to solve. Once you start asking questions about, these people did, so many people did, and so many people didn’t, it gets more complicated to work out. So this formula I’ve just given you seems to come out of nowhere. I want to show you where that formula comes from. But this is going to be for the dedicated viewer, I think. It’s not a simple proof, but I think it’s doable, but we’re going to try, all right, let’s, let’s see where that formula came from. So imagine having all the possible permutations, right? It’s the set of all possible permutations. I’m actually gonna draw a Venn diagram. So these are all the possible permutations that you can have, which means there are–

Leave a Reply

Your email address will not be published. Required fields are marked *