Generalizing with binomial coefficients (bit advanced)

In the last video, we figured out the probability of getting exactly three heads when we have five flips of a fair coin. What I want to do in this video is think about it in a slightly more general way. We're still going to assume we have a fair coin, although we'll shortly see we don't have to make that assumption. But what I want to do is figure out the probability of getting k heads in n flips of the fair coin. So the first thing to think about is just how many possibilities there are where there's going to be n flips. So literally, the first flip, second flip, third flip, all the way to the n-th flip. And this is a fair coin. Each of these, there's two equally likely possibilities. So the total number of possibilities is going to be 2 times 2 times 2, n times. So this is going to be equal to 2 to the n-th possibilities. Now, let's think about how many of those equally likely-- and these are all equally likely possibilities. This is a fair coin. Let's think about how many of those equally likely possibilities involve k heads. Well, just like we did for the case where we're thinking about three heads, we say, well, look, the first of those k heads-- how many different buckets could it fall into? Well, the first of the k heads could fall into n different buckets, right? It could be the first flip, second flip, all the way to the n-th flip. Then the second of those k heads-- and we don't know exactly how many k is-- will have n minus 1 possibilities. And then the third of those k heads will have n minus 2 possibilities, since two of the spots are already taken up. And we would do this until we have essentially accounted for all of the k heads. So this will go down all the way to-- so the number of things we're multiplying is going to be k, one for each of the k heads. So this is 1, 2, 3, and then you're going to go all the way to n minus k minus 1. And you could try this out in the case of 5. When n was 5 and k was 3, this resulted in 5 times 4 times-- and actually, we just have to go times 3. And actually, that was this term, right over here. So I'm doing a case that is a little bit longer, where k is a slightly larger number. Because this right over here is 5 minus 2. That is this one over here. Just so not to confuse you, let me write it like this. So you'll have n spots for that first head, n minus 1 spots for that second head. And then you keep going. And you're going to have a total of these k things you're multiplying. And that last one is going to have n minus k minus 1 possibilities. And now, hopefully, it'll map a little bit better to the one where we had five flips and three heads. Because here, there was five possibilities for the first head, four possibilities for the second head. And then n is 5. 5 minus 2-- you get three possibilities for the last head. So this actually works. This is the number of spots, or the number of ways that we can put three heads into five different possible buckets. Now just like the last video, we don't want to over-count things because we don't care about the order. We don't want to differentiate one ordering of heads. And I'm just going to use these letters to differentiate the different heads. We don't want to differentiate this from this, heads A, heads B. Or any of the other orderings of this. So what we need to do is we need to divide this number so that we don't count all of those different orderings. We need to divide this by the different ways that you can order k things. So if you have k things, so one thing, two things, all the way to k things, how many ways can you order it? Well, the first thing can be in k different positions. Or maybe I'll do it like this. Maybe I'll do it Thing 1. I'll call it T for Thing-- Thing 1, Thing 2, Thing 3, all the way to Thing k. How many different ways can you order it? Well, Thing 1 can be in k different positions. Then Thing 2 will be in k minus 1 positions. And then all the way down to the last one is only going to have one position. So this is going to be k times k minus 1 times k minus 2, all the way down to 1. And in the example where we had three heads in five flips, this was 3 times 2 all the way down to 1. 3 times 2 times 1. And so is there a simpler way that we can write this? Well, this expression right over here, this is the same thing as k factorial. And if you haven't ever heard of what a factorial is, it's exactly this thing right over here. k factorial literally means k times k minus 1 times k minus 2, all the way down to 1. So for example, 2 factorial is equal to 2 times 1. 3 factorial is equal to 3 times 2 times 1. 4 factorial is equal to 4 times 3 times 2 times 1. And it's actually a fun thing to play with. The factorials get large very, very, very, very, fast. So anyway, this denominator right over here can be rewritten as k factorial. This right over here can be rewritten as k factorial. And is there any way to rewrite this numerator in terms of factorials? So if we were to write n factorial-- so let me see how we can write this. If we were to write n factorial-- get some real estate over here-- so n factorial would be equal to n times n minus 1 times n minus 2, all the way down to 1. That's kind of what we want. We just want the first k terms of it. So what if we divide this by n minus k factorial. So let's think about what that is going to do. If we have n minus k factorial, that is the same thing as-- we have to do a little bit of algebraic manipulation right over here-- that is the same thing as n minus k times n minus k minus 1 times n minus k minus 2, all the way down to 1. When you divide these, the 1's going to cancel out. And what you may or may not realize-- and you could work out the math-- is everything is going to cancel out here until you're just left with, up here, everything from n times n minus 1 to n minus k minus 1. Because this, if you expand this out, or if you distribute this negative number, this is the same thing as n minus k plus 1. So n minus k plus 1 is the integer that's one larger than this right over here. So if you were to divide it out, this would cancel with something up here. This would cancel with something up here. This would cancel with something up here. And what you're going to be left with is exactly this thing over here. And if you don't believe me, we can actually try it out. So let's think about what 5 factorial over 5 minus 3 factorial is going to be. So this is going to be 5 times 4 times 3 times 2 times 1-- so all of that stuff up there, all the way down to 1. Over-- 5 minus 3 is 2-- over 2 factorial, 2 times 1. 2 cancels with 2. 1 cancels with 1. You don't even have to worry about that. And you're just left with 5 times 4 times 3. Exactly what we had up here, 5 times 4 times 3. And so in general, if you wanted to figure out the number of ways to stick two things in five chairs, and you don't care about differentiating between those two things, you're going to have this expression right over here, which is the same thing as this right over here. So you're going to have n factorial over n minus k factorial. And then you're going to divide it by this expression right over here, which we already said is the same thing as k factorial. So you're also going to divide it by k factorial. And then you have a generalized way of figuring out the number of ways you can stick k things in n different buckets, k heads in n different flips. And so another way of writing-- and this is actually a generalized formula for binomial coefficients. So another way to write this is the number of ways, given that you have n buckets, you can put k things in them without having to differentiate it. Or another way to think about it is if you have n buckets, or n flips, and you want to choose k of them to be heads. Or you want to choose k of them in some way, but you don't want to differentiate. So all of these are generalized ways for binomial coefficients. So going back to the original problem, what is the probability of getting k heads in n flips of the fair coin? Well, there's 2 to the n equally likely possibilities. So let's write this down. So the probability-- you have 2 to the n equally likely possibilities. And how many of those possibilities result in exactly k heads? Well, we just figured that out during this video. That's the number of possibilities. So n factorial over k factorial times n minus k factorial. Now, it probably is a OK idea to memorize this. But I'll just tell you frankly, the only reason why I still know how to do this 20 years after first seeing it, or whenever I first saw it, is that I actually just like to reason through it every time. I like to just reason through, OK, I've got five flips. Three of them need to be heads. The first of those heads can be in five different buckets, and the next in four different buckets, the next one in three different buckets. And then, of course, I don't want to differentiate between all of the different ways that I can rearrange three different things. So I have to make sure that I divide it by 3 factorial, by 3 times 2 times 1. I want to make sure that I divide it by all of the different ways that I can arrange three different things.