If you're seeing this message, it means we're having trouble loading external resources on our website.

If you're behind a web filter, please make sure that the domains *.kastatic.org and *.kasandbox.org are unblocked.

Main content

Generalizing with binomial coefficients (bit advanced)

Conceptual understanding of where the formula for binomial coefficients come from. Created by Sal Khan.

Want to join the conversation?

  • leaf green style avatar for user fishingconspiracy
    I can never make sense of where the (n-(k-1)) bit comes from...
    (77 votes)
    Default Khan Academy avatar avatar for user
    • blobby green style avatar for user michael
      You can think of it as a way to limit the number of terms in

      n . (n - 1) . (n - 2) . (n - 3)...

      We want K terms here - one for each heads that will appear in our coin flips. If you look at the digits in those terms, they're nicely numbered: 1, 2, 3...

      Since we want K terms, we nearly want a set of terms that goes 1, 2, 3, all the way up to K. BUT! Our first term is just n on its own. This means the last term we want isn't (n - K), but the one before it in the sequence: (n - (K - 1)).
      (108 votes)
  • blobby green style avatar for user isaac.sennerholt
    How do i apply this method if it's not fair coins? if there is a larger percentage to get heads than tails?
    Best of regards,
    (23 votes)
    Default Khan Academy avatar avatar for user
  • orange juice squid orange style avatar for user Thomas Løfgren
    Is there a formula for calculating (or rules for addin up) probability of pulling AT LEAST some amount (k) of similar items from a bag of (n) mixed items, when you get to take out x amount of items from the bag?

    E.g. a bag has 8 colored beads, 4 of them are blue beads. What's the probability of getting AT LEAST 3 blue beads (i.e. 3 or 4 blue beads) when you can take out 4 beads.

    I've tried figuring this out but could use some help.
    (7 votes)
    Default Khan Academy avatar avatar for user
  • blobby green style avatar for user Joe Farr
    Why does he say the "last" video when the last video was about the mega millions jackpot????
    (5 votes)
    Default Khan Academy avatar avatar for user
  • leafers ultimate style avatar for user David Pasc
    At he says that you can use this formula for finding the number of ways to stick 5 things in 2 chairs without differentiating between those two things. What does he mean when he says differentiate?
    (4 votes)
    Default Khan Academy avatar avatar for user
    • leaf blue style avatar for user Dr C
      He means essentially that we don't care if Object #1 and Object #2 are different, we won't be thinking of them as different.

      So say you have 5 people that you need to put into two chairs. One chair is on the left, the other is on the right. Jack and Jill are two different people, but we don't care if Jack is on the left and Jill on the right, or if Jill is on the left and Jack on the right. All we care is that we have Jack and Jill, instead of Jack and Sally, or Bob and Charles, etc.
      (5 votes)
  • leaf green style avatar for user AIR
    Why does Sal write × (times) symbols as . (decimal points)?
    (2 votes)
    Default Khan Academy avatar avatar for user
    • leaf blue style avatar for user Dr C
      The dot operator is a very commonly used symbol for multiplication. In my experience, the dot ( · ) notation is much more common than the times sign ( × ). The × sign can sometimes get confused for the letter X, which we would really like to avoid doing. When dealing with multiple variables, it's also fairly common to not have a multiplication sign at all - multiple letters next to each other just implies multiplying the together. The · or × can be inserted when substituting numbers in for variables, or you can just use parentheses.

      Similarly for division, using the solidus ( / ) is much more common than the obelus ( ÷ ) for "inline" fractions (that is: a faction written like a line of text, instead of being vertically aligned). For example:
      (a-b) / c instead of (a-b) ÷ c
      (7 votes)
  • blobby green style avatar for user Josh
    I don't understand about marking the heads A, B etc. You either flip one coin 5 times in a row or flip 5 coin simultaneously, what is he talking about with the A, B, C etc.
    It's like you're saying you choose coin A, then choose where to insert that coin in the 5 possibilities/spaces (like space 1, 2 etc.).
    (3 votes)
    Default Khan Academy avatar avatar for user
    • blobby green style avatar for user Maxim Veksler
      It doesn't matter if you flip 1 coin 5 times of 5 coins simultaneously, what does makes a difference is the "bucket" you assign to each coin.

      Think of it this way: You have 5 "slots" to fill with coin flip results. How you fill then is left to you, if you flip just 1 coin you say: I'm flipping the coin and the results goes into "slot 1". Now I'm doing it again and the result goes into slot 2, and co... If OTOH you would have 5 coins you would say: coin 1 flip results goes into slot 1, coin 2 into slot 2. Now flip them all and lets see the results.
      (3 votes)
  • leaf green style avatar for user Eva Gebezis
    I'm a bit confused here, what happens when k = n, like in 5 heads in 5 flips? It seems the denominator goes to zero :S What am I getting wrong?

    Edit: Aha I think I got it, if k = n only k! should be left in the denominator, no need for the (n-k)! term, right?
    (4 votes)
    Default Khan Academy avatar avatar for user
  • male robot hal style avatar for user Aidan Iannello
    When he says, "we have a fair coin...", does that mean there are coins out there that are unfair?
    (3 votes)
    Default Khan Academy avatar avatar for user
  • mr pants teal style avatar for user Ahmed
    Is n always larger than k?
    I don't think it would make sense to get 4 heads out of three flips!
    (2 votes)
    Default Khan Academy avatar avatar for user

Video transcript

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.