Permutations and combinations
Combinations Introduction to combinations
⇐ 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 how many different ways
- could 5 people sit in 3 chairs.
- So for example, if this is chair one, this is chair
- two, this is chair three.
- We said, well, in chair one we could put 5 people.
- No one's sitting down.
- Then there's only going to be 4 people left, so we could put 4
- different people in chair 2.
- And then there would be 3 people left that we could
- put in chair three.
- So the total permutations, the different ways that people
- could sit in the different yours if we cared about the
- order-- if we cared about which chair they were sitting down
- in-- it would be 5 times 4 times 3.
- And another way of thinking about that-- 5 times 4 times
- 3-- that's the same thing.
- That equals 5 times 4 times 3 times 2 times 1 over what?
- Over 2 times 1.
- And that's the same thing as 5 factorial over 2 factorial.
- Now where does this 2 come from?
- How is 2 related to the 5 and 3?
- What's the difference between the two?
- So this is the same thing, this is equal to 5 factorial
- over 5 minus 3 factorial.
- And that in general is how we figure out, how many
- permutations can 5 things place themselves or be
- placed into 3 positions?
- And the general formula is-- and we learned
- this in the last video.
- And I will switch colors.
- If we want to put n things into k positions, and k has to
- be less than or equal to n.
- Well actually, it doesn't have to.
- But for our purposes right now we'll assume it is because our
- formula might break down if it weren't.
- And that equals n factorial over n minus k factorial.
- I always find this harder to memorize than just
- thinking about the spot.
- Then just saying, oh well, you know, 5 people, 5 of
- the things could be here.
- And then once one thing is here, there's 4 possibilities
- left and then there's 3 possibilities left.
- The way I think of it I take the first k terms
- of the n factorial.
- Or in this case, I take the first three terms
- of the 5 factorial.
- 5 times 4 times 3.
- That's how I think of permutations.
- This is great if we cared-- let's say these are
- people A, B, C, D, E.
- So these are the 5 people that are going to sit in the chairs.
- This is great if we wanted to count the permutation ABC as
- different from the permutation ACB, as different from the
- permutation-- I don't know-- BAC as different from
- the permutation BCA.
- Because remember, when we did this we actually cared about
- where they're sitting.
- And in the previous video we double counted everything
- because it matters if person A is in seat one and
- person B is in seat two.
- And then if they switch we recounted, right?
- This is where they switch.
- But what if we didn't care about that?
- What if we didn't care who's in what seat?
- We just wanted to know how many different ways can
- the 5 people sit down?
- So we want to count all the situations where person A, B,
- and C are sitting down as essentially one situation.
- We don't care who's sitting in which chair.
- We just care that those are the 3 people sitting down.
- That's the set, the subset of the people sitting down.
- And so the question then becomes not how many different
- permutations or how many different ways can the people
- sit down, the question becomes, how many subsets of 3 can
- we take out of a set of 5?
- And I know I'm kind of jumping up around a little bit, but
- that's essentially what a combination is.
- A combination is a permutation where you don't care
- about the order.
- So how do we figure it out?
- Well, when we figured out the permutations using this formula
- we counted-- for example, we counted ABC, ACB, BAC,
- BCA, and let's see.
- There should be two more permutations.
- CAB and CBA.
- We counted all 6 of these as different permutations.
- But in our combinations we're going to want to-- this is all
- essentially the same combination because we don't
- care about the order.
- So for any 3 different people that are in these seats,
- there's actually going to be 6 permutations that we're
- counting when we do the permutations.
- So if we want the combinations we'll just divide by the number
- of ways we can rearrange 3 people into 3 seats.
- That's essentially what we did here.
- So how many different ways can you arrange 3
- people into 3 seats?
- Well, this is kind of another permutation problem.
- The first seat you could put 3 different people, the second
- seat you put 2 different people, and the last seat--
- well, there's only 1 person left.
- So it equals 3 factorial, which is equal to 6.
- This is equal to 3 factorial, which is equal to 6.
- Hope I'm not confusing.
- What I'm just trying to say is when you did a permutation we
- counted all of the different orders of how people could
- arrange themselves.
- And what I'm saying now is well, how many different ways
- can people arrange themselves?
- Well, it's going to be the number of places factorial
- because if we have 3 people in 3 spots or let's say,
- 4 people in 4 spots.
- The fourth spot can have 4 people, the second spot can
- have 3, and so forth, the third spot could have 2, and the
- last spot will only have 1.
- So it's the number of spots factorial is how many
- permutations we're counting.
- When we have just the same people, they're just playing
- musical chairs in the exact same seats.
- So on order to figure out the combination, so if we wanted to
- say how many people-- let's say if we had 5 people.
- How many different groups of 3 can be seated?
- And we don't want to double.
- We don't want to more than double count.
- I don't know what the word is for counting
- something six times.
- Well, it's just going to be the same thing as the permutation
- divided by all of the extra counting we did.
- We'll just divide by the number of ways that 3 people can
- arrange themselves in 3 seats.
- And that's 3 factorial.
- And I hope I'm making sense.
- Maybe I'll do a couple more examples in other videos.
- And definitely request it if you think this
- is extra confusing.
- So in general, if we say, what are the different ways that
- n things can be chosen?
- Or the number of combinations that n things can be chosen
- into sets of r, where r is less than or equal to n.
- It's equal to the number of permutations you could create
- of putting n things into r spots, divided by r factorial.
- We're going to divide by the number of ways the r spots
- themselves could be rearranged because we don't want to
- count those as extra.
- And so if we go back to this formula up here, well, this
- was a k, but now we're saying it's an r.
- This is the same thing as-- so the permutations was
- n factorial over n minus r factorial.
- And now we're dividing everything by r factorial.
- So that equals-- let me just write this.
- This is often written as n choose r.
- Another way it's written is n choose r.
- This is called the binomial coefficient and we'll do a
- whole series of modules on that as well because this actually
- shows up in polynomial expansion when you take
- polynomials to powers.
- But this is equal to n factorial over r factorial
- divided by n minus r factorial.
- You could memorize this.
- You know, it's useful if you want to do things
- quickly on tests.
- But it's very important to think about where it came from.
- The n factorial over the n minus r factorial-- this
- is just the permutation.
- And what is that?
- Well, that was just the first r-- I guess you could call
- it the first r factors.
- The r largest factors of n factorial.
- That's all that is.
- And then when we do the combinations we divided by r
- factorial because we want to divide it by all the different
- arrangements that the people could seat themselves
- in r seats.
- Or, the balls could be placed in r cups.
- So in this situation if we want to know how many different
- groups of 3 can be selected from 5 people or from 5
- letters, it's going to be 5 factorial over 3 factorial
- times 5 minus 3 factorial.
- And that's 5 times 3 times 2 times 1, over-- 3
- factorial is just 6.
- We'll put that aside for a second.
- Divided by-- this is 3 factorial.
- 2 times 1.
- So notice, this is a permutation part right here.
- This term just gets rid of the two lowest factors.
- You get 5 times 3.
- Oh, sorry there's a 4.
- 5 times 4 times 3, which is the number of permutations.
- And then we divide by 6 because we get 6 permutations for
- really every combination.
- Maybe that confused you.
- But anyway, so we get 5 times 4 times 3 divided by 6.
- And that's what?
- 5 times 12 divided by 6, which is equal to 5 times 2.
- There's 10 possible ways that we can take sets of 3
- from a group of 5 things.
- See you in the next video.
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.
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.
abuse
- disrespectful or offensive
- an advertisement
not helpful
- low quality
- not about the video topic
- soliciting votes or seeking badges
- a homework question
- a duplicate answer
- repeatedly making the same post
wrong category
- a tip or feedback in Questions
- a question in Tips & Feedback
- an answer that should be its own question
about the site
Share a tip
Suggest a fix
Have something that's not a tip or feedback about this content?
This discussion area is not meant for answering homework questions.