Current time:0:00Total duration:11:40

0 energy points

# Generalizing with binomial coefficients (bit advanced)

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

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.