Generalizing with binomial coefficients (bit advanced)

in the last video we figured out the probability of getting exactly three heads oh 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 will 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 K heads in n flips and n flips flips of the fair coin of the fair 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 there going to be n flips so literally the first flip second flip third flip all the way to the nth flip and this is a fair coin each of these there's a each of these there's two equally likely possibilities so the total number of possibilities going to be 2 times 2 times 2 n times so this is going to be equal to 2 to the nth possibilities to do T and possibilities now let's think about how many of those equally likely these are all equally likely possibilities this is a fair coin let's think about how many of those equally likely possibilities involve involve K heads involve K heads well just like we did for the case where we had where we're thinking about 3 heads we don't think about 3 heads we say well look where the first of those K heads the first of those K heads how many different how many different buckets could it fall into well the first of the K heads could fall into 5 into n different buckets right it could be the first flip second flip all the way to the nth flip then the second of those K heads that we don't know exactly how many K is we'll have n minus 1 possibilities 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 this we will we will multiply the number of things we're multiplying is going to be k1 for each of the K heads so this is one two three and then you're going to go to all the way to n minus K minus one and you could try this out in the case of five when n was five and K was three this resulted in five times four times and actually we just have to go times three 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 so let me actually let me just not to confuse you let me write it like this let me write it like this so you'll have n spots for that first head and minus 1 spots for that second head and then you keep going and you're going to have a total of these K K things you're multiplying and that last one is going to be is going to have n minus n minus K minus 1 possibilities and now hopefully it'll map a little bit better to the one where we had 5 flips and 3 heads because here there there was 5 possibilities for the first head 4 possibilities for the second head and then n is 5 5 minus 2 you had 3 possibilities for the last head so this actually works this is the number of spots where or the number of ways that we could put that we can stick those heads in those or that we can stick we can put 3 heads into 5 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 we don't want to differentiate 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 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 the different ways that you can order K things so if you have K things you know 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 K different positions or maybe I'll do it like this maybe I'll do it thing one I'll call it t 4 thing thing one thing two thing three all the way to thing K how many different ways can you order it well thing one can be in K different positions then king two 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 all the way down to 1 and in the example where we had three heads in five flips was three times two 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 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 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 so and it's actually a fun thing to play with factorials get large very very very very fast so anyway this denominator right over here can be re-written as K factorial this right over here can be re-written as K factorial and is there any way to rewrite this numerator in terms of factorials so if we wrote 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 all the way down to 1 all the way down to 1 that's kind of what we want we just want the first K terms of it just want the first K terms of it so what if we divide this by so let's divide this by n minus K factorial so n minus K factorial so let's think about what that is going to do that 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 n minus K times n minus K minus 1 n minus K minus 1 minus 1 times n minus K times n minus K minus 2 all the way down to 1 and what I want to when you when you divide these the ones going to cancel out and what you may or may not realize and you can you can work out the math is everything is going to cancel out here until you're just left with up here you're just left everything from n times n minus 1 to n minus K minus 1 because this a queue if you if you if you expand this out or if you 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 if you don't believe me we can actually try it out so let's think about what 5 factorial what 5 factorial over 5 minus 3 factorial is going to be over 5 minus 3 factorial 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 have to worry about that and you're just left with 5 times 4 times 3 exactly what we had up here 5 times 5 times 4 times 3 and so in general if you wanted to figure out the number of ways to stick to things in five chairs and you don't care about differentiating between those two things you're going to have this expression you're going to have 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 the number of ways you can stick to things or the number of ways actually I should say the number ways you can stick K things in n different buckets K heads and n different flips and so and then 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 the number of ways given that you have given that you have n buckets 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 n buckets or n flips and you want to choose K of them and you want to choose K of them to be heads or you want to choose K of them in some way but you want to 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 what is the probability of getting K heads and n flips of the fair coin well there's two to the N equally likely possibilities so let's write this down so the probability you have two to the n equally likely possibilities and how many of those possibilities result in exactly K heads will we just figure that out in 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 okay idea to memorize this but I'll just tell you frankly you know what the only reason why I still know how to do this 20 years after first seeing it or whatever I first saw it is that I actually just like to reason through it every I like to just reason through okay I've got five flips three of them need to be heads the first of those heads can be in five different buckets than the next in four different buckets the next one three different buckets and then of course I don't want to differentiate between all of the different ways 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 that I divide it by three factorial by three times two times one I want to make sure that I divide it by all of the different ways that I can arrange three different things