Permutations and combinations
Permutations Introduction to permutations
⇐ 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.
- Let's say I have 3 chairs.
- They'll just be blanks: 1, 2, and 3.
- 3 chairs, and I have 7 people.
- I'll call them people A, B, C, D, E-- how many is that?
- That's 5-- F, G.
- So we have 7 people and what I want to know is how many
- different ways can these 7 people sit in these 3 chairs?
- Well, before anyone sits down if we just pick a chair, these
- are just arbitrary labels for the chairs, but let's start at
- the left with chair number one.
- If no one is sitting down, how many different people could
- sit down in chair one?
- Well, 7 people are standing up, no one is sitting in any of the
- chairs, so 7 different people could sit in chair one.
- So there are 7 possibilities for chair one.
- So 1 of those 7 possibilities is going to sit
- down in chair one.
- So how many people are left to sit in chair two?
- Well, 1 less than 7, right?
- 6 people are going to be left to sit in chair two.
- And then of course, if 2 people are already sitting down, how
- many people are left to sit in chair three?
- Well, there's going to be 5 possibilities.
- So a way to think about it, for each of these possibilities,
- there are 6 possibilities in this chair and 5 possibilities
- in that chair for each of those 6.
- So you would multiply all of the possibilities.
- Hopefully that makes some sense.
- We'll try it out with some examples.
- So the total number of possibilities in this
- case is 7 times 6 times 5, and what is that?
- 6 times 5 is 30.
- 30 times 7 equals 210.
- There's 210 possibilities.
- That's a lot of possibilities.
- Let's do a slightly smaller example.
- I mean we don't have to do people in chairs.
- Let's say we have cups.
- And I'll do the cups in a different color.
- So this is 1 cup, cup one.
- And then I have cup two.
- And then I have 3 balls.
- I have a magenta ball, I have a brown ball, and
- I have a yellow ball.
- And I want to know, how many different ways can I put these
- 3 balls into these 2 cups?
- Well, assuming that I haven't put any of the balls into any
- of the cups as yet, how many balls-- well, let's just
- start with cup two.
- I just want to show you that you don't have to start at the
- cup that happens to be labeled number one sitting on the left.
- If we haven't put any balls into any of the cups, how
- many can we put in cup two?
- Well, there's 3 possibilities, right?
- And for each of those 3 then, how many can
- we put into cup one?
- Well, we would've put 1 into here, so there will be 2
- left to put into cup two.
- So it'd be 3 times 2 possibilities, which
- is equal to 6.
- And let's see if we can draw them out.
- Let me number these cups because it's going to be
- too difficult to keep switching colors.
- So let's say this is A, B, and C.
- I'm going to show you that there are 6 ways of putting
- these 3 balls into these 2 cups.
- So it could be A in cup one, B in cup two.
- It could be B in cup one, A in cup two.
- Right, you could just switch them.
- So we actually care which ball goes into what cup.
- Not just is a ball in a cup.
- It could be A with C.
- A in cup one, C in cup two.
- It could be C in cup one, A in cup two.
- And then finally, you could just have B and C.
- B in cup one, C in cup two.
- Or C in cup one, B in cup two.
- And notice, if we just cared which of the balls were picked,
- but we didn't care whether they were in cup one or cup two, we
- could get rid of this bottom line and there would be 1/2
- as many ways to place them.
- But when we care where the balls are-- we care whether
- they're in cup one or cup two, or in this case we care if
- they're in seat one, two, or three.
- The ways in which we're ordering, we call
- these permutations.
- And up here, the way we would write this permutation, we
- would say, well, how many ways can we fit 7 people into 3
- chairs if we care about what chair they're sitting in?
- So we could write that as 7 people-- and the p isn't
- for people, it's for permutations-- into 3 chairs.
- And another notation for it, you write a big P and you
- say, how many ways can I put 7 things into 3 spaces?
- Or it could be written as, how many ways could you put
- 7 things into 3 spaces?
- And in this case, we got the answer is 210.
- And actually, it will always be 210.
- And I'll show you why in a second.
- How would we write this?
- Well, this would be-- I'll do it in green.
- We had 3 things and we put it into 2 spaces.
- So 3 things into 2 spaces.
- That's the same thing as 3 things into 2 spaces, which
- is equal to 3 things into 2 spaces.
- I'm just showing you the different notations, and we
- figured out that that was 6.
- Let's see if we can figure out a general formula if
- we wanted to evaluate nPk.
- How many ways can we fit n things into k spaces?
- So if we think about it, let's just use some analogy.
- We'll have k spots, so it'll be 1 spot, 2 spots, 3 spots,
- all the way to k spots.
- In the first spot there's n possibilities, just like we
- did in the last two examples.
- There's n possibilities there.
- Then, since 1 person or 1 thing will be placed in spot one,
- there's going to be n minus 1 possibilities for spot two.
- And similarly, n minus 2 possibilities for spot three.
- And then, we could follow that pattern all the way, and how
- many possibilities are there going to be for spot k?
- Well in everything it's n minus 1 thing less than the
- spot number in our case.
- I mean I guess we could have started with spot 0, but this
- is better because we actually numbered all the way to k.
- So it will be n minus k minus 1.
- And that might seem complicated, but
- it makes sense.
- When we did 7 things into 3 spots we went 7 times 6 times--
- we literally put in the top three of you could almost
- say from the factorial.
- 7 factorial will be 7 times 6 times 5.
- I think this will help.
- If this was just 3 was so 7 times 6 times 5 times 4
- times 3 times 2 times 1.
- That's 7 factorial.
- But we only took the first 3 of the factorial.
- And similarly, 6-- well, 6 is also 3 factorial.
- But another way you could view it is we only took the first 2
- of 3 factorial So what we're saying here is we just take
- the first k of n factorial.
- So is there any easy way to write that?
- To write the first k of n factorial.
- Why sure.
- We could write it as n factorial and the formula's
- almost harder than what it's saying.
- We could write it as n factorial-- it;s a lower
- case n-- n factorial over n minus k factorial.
- Let's see if that works.
- Well, what's going to happen?
- So in this case, n factorial was 7.
- So it was 7 times 6 times 5 times 4 times
- 3 times 2 times 1.
- And then what was n minus k factorial?
- Well, in our example, k was the number of spots,
- and there were 3 spots.
- So 7 minus 3 is 4, so 4 factorial.
- 4 times 3 times 2 times 1.
- And of course, this will cancel.
- Let me do that in a different color.
- This will cancel with this, and so you're just left with
- the first 3 of 7 factorial.
- The 3 largest components of 7 factorial.
- I always rederive this because all I think of is what
- we did originally.
- I was like, oh, OK.
- If we're doing permutations, I just start the factorial
- until I run out of spots.
- I do 7 times 6 times 5.
- And let's see if it works out here too.
- So what is 3 factorial because we have 3 different things?
- 3 factorial over-- and then 3 minus 2 factorial.
- Well, that's just 1 factorial.
- So it becomes 3 times 2 times 1 over 1.
- And of course, the 1's cancel out and we got the 3 times 2.
- Hopefully that make sense.
- A lot of people, they learn the permutation notation and they
- say, oh, that's n factorial over n minus k factorial, where
- n is the number of things I need to place and n minus
- the whole thing factorial.
- And k is the number of spots I have.
- And they just memorize it.
- But all this is saying is you start doing the n factorial,
- but you only do the first 3 components of the factorial.
- And it makes sense just from how we started off the video.
- If you 7 things, well, 7 things could go here, 6 things could
- go here, 5 things could go here.
- No more spots?
- Just multiply them.
- And that's all this formula is saying.
- Hopefully I didn't confuse you, and I will see you in the
- next video on combinations.
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.