Generalizing with Binomial Coefficients (bit advanced) Conceptual understanding of where the formula for binomial coefficients come from
Generalizing with Binomial Coefficients (bit advanced)
⇐ Use this menu to view and help create subtitles for this video in many different languages. You'll probably want to hide YouTube's captions if using these subtitles.
- 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 will start assuming a fair coin although
- we will surely see we don't have to make that assumption.
- But what I want to do is to figure out the probability
- of getting K heads in N flips of the fair coin.
- So the first thing to think about is that
- how many possibilities there are.
- Well there is going to be n flips.
- So literally, there is first flip, second flip,third flip,
- all the way to the n flip.
- And this is a fair coin, each of this
- there is 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 nth 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 k heads.
- Well, just like we did for the case
- where we think 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 nth flip.
- Then the second of those k heads,
- we don't know exactly how many k is.
- We will have n minus 1 possibilities.
- And then the third of those k heads will have
- n minus 2 possibilities,
- since two of these buckets are already taken up.
- And we will do this untill
- we have essentially counted for all of the k heads.
- So this would go down all the way to,
- we will muptiply the number of things,
- We will multiply is going to be k,
- one for each of the k heads.
- So this is one, two, three,
- and then you are going to all the way to n minus k minus 1.
- 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,
- actually we just have to go, times three,
- actually that was this term right over here.
- So I am doing the case that it is a little bit longer,
- a case that is slightly larger number
- because this right over here is five minus two
- that is this one over here.
- Let me just not to confuse you.
- Let me write it like this.
- So you'll have n spots for that first head.
- N minus one spots for that second heads.
- And then you keep going and you are going to have
- a total of these k things you will multiply
- and that last one is going to be
- And now hopefully might be a little better to the one
- where we had five flips and three heads
- because here there was five posssibilities for the fisrt head
- four possibilities for the second head,
- You have three possibilities for the last head.
- So this actually works.This is a number of spots
- where or the numbers of ways that we could put,
- that we cna stick that head in those,
- or that we can put three heads into
- five different possible buckets.
- Now just like the last video,
- we don't want to overcount things
- because we don't care the order.
- We don't want to diffrentiate one ordering of heads
- that I am just going to use these letters
- differentiate the different heads.
- We don't want to differentiate this from this,
- Heads A, Heads B, or any of the other ordering of this.
- So we need to do is we need to divide this.
- We need divide these numbers so that
- we don't count all of these different orderings.
- We need divide these 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, so 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.
- Let me, I'll do it like this.Maybe I will do it thing 1,
- T for thing,thing 1,thing 2,thing 3,all the way to thing k.
- How mant different ways can you order it?
- Well thing 1 can be in k different positions.
- Then thing 2 would be in k minus 1 positions.
- And then all the way down to the last one
- is only going to have 1 position.
- So this is going to be k times k minus 1, times k minus 2,
- all the way down to 1.
- And an example that we had three heads in five flips,
- so three times two all the way down to 1,3 times 2 times 1.
- And so there are 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 have heard waht factorial is,
- exactly this thing right over here.
- K! literally means k times k minus 1 times k minus 2,
- all the way down to 1.
- So for example, 2! is equal to 2 times 1.
- So actually you will found something a play
- factorial get large, very very very very fast.
- So anyway, the denominator right over here
- can be rewrite in this K factorial.
- And there is any way to rewrite this numerator
- in terms of factorials.
- So if we wrote right n!, let me see how we can write this.
- If we are going to write an n!,
- let me do some reallistic over here.
- So n! would be equally 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 key turns of it.
- So what if we divide this by,
- so let's divide this by (n-k)!
- So let's think about what that is going to do.
- That if we have (n-k)! that is the same thing as,
- let me to do a little bit out of brick
- [inaudible] right over here,
- that is the same thing as n minus k,
- all the way down to 1.When you divide this,
- the 1 is going to cancel out,
- you may have not realised that
- you can work out this method anything is going to
- cancel out here until you are just left out with a pair,
- everything from n times n minus 1 to n minus k minus 1.
- Because this if you expend this out,
- 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 one larger
- than this right over here.
- So if you divide out this would cancel with something up here.
- This would cancel somnething up here.
- This would cancel something up here.
- And we are going to be the 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 5! over (5-3)!
- so this is going to be 5 times 4 times 3 times 2 times 1.
- So all of that stuff over there, all the way down to 1,
- over 5 minus 3 is 2, over 2!, 2 times 1. 2 cancels with 2,
- 1 cancels with 1.You don't have to worry about that,
- and you are just left with 5 times 4 times 3,
- exactly what we have it up here, 5 times 4 times 3.
- And so, in general, if you wanted to figure out
- the number of ways to stick 2 things in 5 chairs,
- you don't care about differentiating between those 2 things.
- You are going to have this expression right over here,
- which is the same thing as this right over here.
- So you are going to have n!/(n-k)!
- and then you are going to be divided
- by this expression right over here,
- which we have already said the same thing as k!.
- So you are also going to be divided by k!
- And then you have a generalized way of
- figuring out the number of ways you can stick 2 things,
- or the number of ways actually I should say
- 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,
- this is actually generalized formular binomial coefficient.
- 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 dom't want to differentiate.
- So all of these are generailized ways
- for binomial coefficient.
- So going back to the original problem:
- what is the probability of getting k heads
- in n flips of the fair coin?
- Well there are 2 to the nth equally likely possibilities.
- So let's wrtite this down.
- So the probablity of 2 to the nth of the equally
- likely possibilities
- and how many of those possibilities resulte
- in exactly k heads?
- Well we just figure that out in during this video.
- That's the number of possibilities.
- Now probability of a OK idea to memorize this.
- But I'll just tell you frankly, you know,
- the only reason why I still know how to do this
- 20 years after foreseen of whatever I first saw
- is that I actually just like just to reason it through
- every time, I like just to reason through.
- OK, I have got five flips, three of them need to be heads.
- The first of those heads can be in five different buckets
- that nexct in the four different buckets
- and next was in three different buckets
- and then of course I don't want to differentiate
- between all of the different ways
- that I can rearrange 3 different things.
- So I have to make sure that I divided by 3!
- by 3 times 2 times 1.
- I want to make sure that I divided by
- all of different ways
- that I can arrange three different things.
Be specific, and indicate a time in the video:
At 5:31, how is the moon large enough to block the sun? Isn't the sun way larger?
Have something that's not a question about this content?
This discussion area is not meant for answering homework questions.
Share a tip
When naming a variable, it is okay to use most letters, but some are reserved, like 'e', which represents the value 2.7831...
Have something that's not a tip or feedback about this content?
This discussion area is not meant for answering homework questions.
Discuss the site
For general discussions about Khan Academy, visit our Reddit discussion page.
Flag inappropriate posts
Here are posts to avoid making. If you do encounter them, flag them for attention from our Guardians.
- disrespectful or offensive
- an advertisement
- low quality
- not about the video topic
- soliciting votes or seeking badges
- a homework question
- a duplicate answer
- repeatedly making the same post
- a tip or feedback in Questions
- a question in Tips & Feedback
- an answer that should be its own question
about the site