Main content

## Statistics and probability

### Course: Statistics and probability > Unit 8

Lesson 4: Combinatorics and probability- Probability using combinations
- Probability & combinations (2 of 2)
- Example: Different ways to pick officers
- Example: Combinatorics and probability
- Getting exactly two heads (combinatorics)
- Exactly three heads in five flips
- Generalizing with binomial coefficients (bit advanced)
- Example: Lottery probability
- Probability with permutations and combinations
- Conditional probability and combinations
- Mega millions jackpot probability
- Birthday probability problem

© 2023 Khan AcademyTerms of usePrivacy PolicyCookie Notice

# 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?

- I can never make sense of where the (n-(k-1)) bit comes from...(78 votes)
- 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)

- 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)- I think the easiest way is just to add up all probabilities of exact arragments.

for example, we have p% of probability of getting heads.

therefore probability of getting exactly n heads in m flips:

(p%)^n * (1-p%)^(m-n) * ( mCn )

mCn is binomial coefficients.

(1-p%) is probablity of getting tails.(15 votes)

- 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) - Why does he say the "last" video when the last video was about the mega millions jackpot????(5 votes)
- He is referring to "Exactly Three Heads in Five Flips" which was the point at which he recorded this video. This one turned out to be more advanced because it is about generalization, so he kept the other one with the more basic examples, I guess.(8 votes)

- At8:45he 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)
- 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)

- Why does Sal write × (times) symbols as . (decimal points)?(2 votes)
- 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)

- 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)- 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)

- 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)- 0! = 1, not 0. Here's why it makes sense:

...

4! = 5!/5 = 24

3! = 4!/4 = 6

2! = 3!/3 = 2

1! = 2!/2 = 1

0! = 1!/1 = 1

Using the same logic also reveals why factorials with negative integers are undefined.(7 votes)

- When he says, "we have a fair coin...", does that mean there are coins out there that are unfair?(3 votes)
- Yes. Coins can be specially weighted so that one outcome is more likely than the other.(1 vote)

- Is n always larger than k?

I don't think it would make sense to get 4 heads out of three flips!(2 votes)- For non-negative integers n and k, n choose k is 1 if n=k, and n choose k is 0 if n<k.

Have a blessed, wonderful day!(2 votes)

## 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.