Combinatorics - Video Tutorials & Practice Problems
On a tight schedule?
Get a 10 bullets summary of the topic
1
concept
Fundamental Counting Principle
Video duration:
4m
Play a video:
If you have one clean shirt and one clean pair of pants, then you have a super easy decision when getting ready in the morning. But what if you just did laundry and you actually have three clean shirts and four clean pairs of pants. How many different possible outfits could you come up with then? Well, this is actually the exact sort of thing that you'll be asked to do, find the number of total possible outcomes when faced with multiple options for multiple different things. Now, this might sound like it could be overwhelming, time consuming, having to come up with all of these outcomes. But here I'm going to show you that it's actually super simple and we're not just going to have to individually count each of these options. We can come up with it much easier. So let's go ahead and just jump right in here. Now with our three shirts and four pairs of pants, if I take that first color shirt and pair it with all four different colors of my pants, and then I do the same thing for my second shirt and for my third shirt, if I count all of these up. I see that I have 12 total possible outfits that I could make on that day. But I can actually come to this conclusion much easier using the fundamental counting principle. The fundamental counting principle tells us that if there are m possible choices for one thing and N possible choices for another thing, I can simply multiply these together M times N in order to get the number of total possible choices is for both of those things together. So for my three shirts and four pairs of pants here, I can simply take three and multiply it by four in order to get my total of 12 possible outfits without having to actually come up with them and count them out. So now that we've seen the fundamental counting principle, let's go ahead and work through some more examples together. So looking at this first example here, I see that a menu list for appetizers and six entrees and I want to know how many different meals with both an appetizer and an entree do we have to choose from? So looking at that first thing, my first choice to make is of those four appetizers. So I have four possible choices there. Then for my second thing, I have six entrees to choose from. So I have six possible choices there. Now, if I multiply those two together four times six, I get my number of total possible choices of a meal with an appetizer and an entree. And we're done here. Now, let's look at our second example here. We're asked to find how many possible outcomes are there? If we flip a coin and then roll a six sided die. Well, something that you might notice here is that we're not really making a choice. If I flip a coin, there are two things that could happen. I could get heads or tails, but I'm not really choosing here. And that's OK because the fun, the middle counting principle also applies to outcomes of events. So if there are m possible outcomes of one event and N possible outcomes of another event, I can still multiply M times N in order to get the number of total possible outcomes of both events. So let's go ahead and do that here. When flipping a coin, we know that we can get heads or tails. There are only two possible outcomes here. So I'm gonna take that too and then supply it by the number of total possible outcomes of that second event. When I roll a six sided die, I could get any number one through six. So I know that I have a six total possible outcomes here. So multiplying those two together two times six, I get my total of 12 possible outcomes of both of these events together. Let's take a look at one final example here. Here we're asked how many different outfits can be made from four shirts, five pairs of pants and three pairs of shoes. So the first choice I have to make is what shirt I'm going to wear out of these four. So I know that I have four possible choices there. Then for my second thing, I have five pairs of pants. So I want to multiply four times five. But since I have a third thing here, what exactly do I need to do? Well, the fundamental counting principle doesn't just apply to two events. It can also apply to any number of events. So if I have more than two things that I'm choosing from, I'm just going to continue to multiply by the number of options of each thing and that will give us our total. So here, since I have three pairs of shoes, I'm going to continue to multiply and I'm gonna multiply by that three and I get four times five times three, which gives me 60 my number of total possible options of those three things together. Now that we've seen the fundamental counting principle and know how to use it. Let's get some more practice. Thanks for watching and I'll see you in the next one.
2
Problem
Problem
How many possible outcomes are there if you roll 5 dice?
A
720
B
7,776
C
5
D
6
3
Problem
Problem
How many options are there for license plates with any three letters (A-Z) followed by any 3 numbers (0-9)?
A
260
B
2,340
C
11,232,000
D
17,576,000
4
Problem
Problem
Phone numbers are 10 digits long. How many possible phone numbers are there if the 1st and 4th numbers can't be 0?
A
10
B
90
C
8,100,000,000
D
10,000,000,000
5
concept
Introduction to Permutations
Video duration:
7m
Play a video:
Hey, everyone, we just learned how to find the number of different ways we could wear different outfits on any given day. But what if instead of a single day, we wanted to look at the week ahead and determine the different ways we could wear five different shirts over five different days. While the number of ways that we could choose to do this is actually something called permutations, which are just a way to arrange a number of things in a specific order with each thing occurring only once. Now, that word permutations might make this sound like it's going to be complicated and a bit tricky, but you don't have to worry about that because here I going to walk you through exactly what permutations are and how we can calculate them using the fundamental counting principle and factorials two things that we already know how to do. So let's go ahead and get started. So when looking at our five different shirts that we want to figure out how to wear over five different days, we're going to use the fundamental counting principle. And first look at the number of options that we have on that first day. So on Monday, I have all five different shirts to choose from. So I have five total options. But then on Monday, if I pick to wear this pink shirt, then on two, I'm left with only four options. So if on Tuesday, I choose to wear this teal shirt over here on Wednesday, I now only have three options left, then two on Thursday and one on Friday. Now this five times, four times, three times, two times one, you might recognize as being a five factorial and you'd be right. The number of different ways we could wear five different shirts over five days is equal to five factorial. But what if instead of five shirts, I actually had eight different shirts to choose from. How would I choose that? Well, on that first day, I now have eight total options because now I have eight shirts to choose from. Then on that second day, I only have seven and then six and then five and then four. But this is not equal to eight factorial. So if we can't always find permutations by just taking the factorial, how exactly are we going to calculate it? Well, permutations actually has a specific formula, this formula right here. That is based on the number of total options that were given and how many things we're picking out of that total. So if I take this formula and apply it to my problem with eight shirts over five days, I'm going to take the total number of options I'm faced with in this case eight and the factorial of that and divide it by that total minus the number of things that I'm choosing. In this case, since I'm only choosing shirts for five days, my number here is five, then the factorial of that. Now this simplifies to eight factorial over three factorial, which is actually exactly what this here is. So a couple of things that I want to point out about our equation here is that N is always, is going to be the largest number. So N factorial on the top that N is always going to be your total, it's going to be the largest number that you're given in a problem. Then on the bottom, we're going to take that total and subtract our smaller number. Now, in terms of notation, you may see this written as P with N and R as subscripts here or P with N and R in parenthesis. Now, this can be read as the number of permutations of N things taken R at a time. Now, that might sound a little bit overwhelming just because there's so many words going on. But let's go ahead and work through some examples to get to make this a bit more clear. So in our first problem here, we have a teacher that is choosing a line leader and a door holder from her class of 25 students. So we want to know how many ways there are for the teacher to choose these positions. So using our permutations formula here, the first thing we want to do is identify our values for N and R. Now remember N is always going to be your largest number here. So in this case, we have a total of 25 students. So this 25 represents our value of N. Now for R, we're looking at how many things we're choosing out of that total. So we're choosing a line leader and a door holder. So that tells us that our value for R is equal to two because we're choosing two positions out of our total of 25 different students. So in that permutations notation, I would write that as 25 P two. And from here, we're just going to plug these values into our formula. So remember our largest number RN is always going to come on the top there so that I have 25 factorial on the top. Then on the bottom, I take that 25 and I subtract that smaller number in this case two. And I take the factorial of that. Now simplifying this, this gives me 25 factorial over 23 factorial. Now you may be worried that we're now going to have to write all of these factorials out, but you don't have to worry about that because there's actually a much easier way to solve this by simply rewriting the numerator in order to cancel out the denominator. So here, since our numerator is 25 factorial and our denominator is 23 factorial, we want to rewrite 25 factorial in order to cancel that 23 factorial. So I can rewrite that 25 factorial as 25 times 24 times 23 factorial using what we know about factorials here. Then since this gets divided by 23 factorial that will end up canceling out and give me my final answer of 25 times 24 which is simply equal to 600. So there are 600 different ways that the teacher could choose a line leader and a door holder from their class of 25 different students. Now looking at our second example here, we see that on our homework, there are 10 fill in the blank questions and a word bank of 14 words. If we can only use each word once, how many possible ways could we answer these 10 questions? So again, the first thing that we want to do here is identify our values of N and R. So remember N is always going to be your the largest number in this case 14, this represents my total. Then R is my smaller number that I'm choosing from my total. In this case, I'm choosing 10 words out of my total of 14. So 10 represents my value for R. Now writing this in our permutations notations. This is written as 14 P and then 10. Now we're just left to plug everything into our formula here. So in this formula, we're gonna take that 14 factorial on the top our largest number and then on the bottom, we have 14 minus 10 factorial. Now, this simplifies to 14 factorial divided by four factorial. And again, here we want to go ahead and rewrite the numerator to cancel the denominator. Now, something that you might notice here is that we actually could just type this into our calculator if we know how to use the factorial button. And there actually is a specific function on your calculator to do permutations. But if you're not quite sure how to use that, we can always work this out by hand. So let's continue here and rewrite our numerator to cancel our denominator. Now, this one is going to get a, get a bit long, but that's OK. So let's go ahead and start now on that numerator can simplify this to 14 times 13 times 12 all the way down to four factorial. So now in the denominator that four factorial will cancel with that four factorial on the top, leaving me with all of this 14 counting down to five, multiplying all of that along the way. Now, if I type this in my calculator, now multiplying all of that, I'm going to get a value of 3 billion, 632,428,800. So these are all of the different ways that we could fill in these 10 questions. So it's safe to say that guessing is not going to be your best bet. So now that we know what permutations are and how to calculate them. Let's get some more practice. Let me know if you have any questions.
6
Problem
Problem
A student formed a club at their school. They have 13 members, and need to elect a president, vice president, and treasurer. How many ways are there to fill these officer positions?
A
2197
B
1716
C
13
D
6
7
Problem
Problem
Emily is organizing her closet. She has 15 shirts left to hang but has space in one section for 6 shirts. How many ways could she hang shirts in that section?
A
3,603,600
B
90
C
9
D
362,880
8
Problem
Problem
Evaluate the given expression. 9P4
A
24
B
3,024
C
15,120
D
362,880
9
concept
Permutations of Non-Distinct Objects
Video duration:
6m
Play a video:
Hey, everyone, we now know how to find permutations when dealing with multiple different or distinct objects. Like picking five different shirts to wear over five days or choosing six marbles out of a bag of six different colored marbles. But what if instead in that bag, there were four blue marbles and two red marbles. If I chose this blue marble on the first try, wouldn't it be the same thing as if I were to choose this blue marble? Well, yes, it would be the same thing, which means that we're going to have a different number of outcomes here. So when faced with multiple objects that are the same or non distinct, we're going to have to go about it a little bit differently. Now, just saying that permutations of non distinct objects sounds really complicated, but you don't have to worry because here we're just going to take our equation for permutations that we already know and just alter it slightly in order to account for these objects that are the same. And here I'm going to walk you through exactly what that change is and how we're going to use this equation. So let's go ahead and get started. So when finding all of the outcomes of drawing six different marbles out of a bag of six different colored marbles, simply using our permutations equation, we're going to take our total and the factorial of that and divide it by our total minus the number of things that we're choosing. And the factorial of that. Now, since the number of things we're choosing happens to be the same thing I get six factorial over six minus six factorial using this formula here. And when looking at our permutations of non distinct objects with our bag of four blue marbles and two red marbles, we're going to start out the same way. So still taking our total number of objects and the factorial of that on the top. Now here, since I still have a total of six, I get six factorials still in that numerator. Now, in the denominator is where we're going to account for objects that are the same. So we need to consider all of the different types of objects that we have. Now, in this case, we have blue marbles and we have red marbles, two different types of objects. So we want to look at the number of different types of objects that we have and take the factorial of that on the bottom. So since I have two different types of objects, I'm going to make sure and count those and take the factorial of the number of each of them on the bottom. So here, since I have four blue marbles, I'm going to take four factorial and then I have two red marbles. So I'm going to multiply that four factorial by two factorial. And this is my final equation here. And I would just solve that as we already know how now that we've seen that equation, let's go ahead and work through some examples to make this a bit more clear. So looking at our first example here, we are asked how many different eight digit codes can be made from five zeros and three ones. Now, the first thing we want to do here as we did with permutations for distinct objects is still identify what our value of N and what our different values of R are. So here, remember N is your highest number, it's your total. So in this case, I have a total of eight digits. So this represents my value for N. Then since I have two, two distinct objects, I have zeros and I have ones that means I have this value for R one which is five and then I have this value for R two, which is three. Now it doesn't really matter which one is R one and R two. So long as you're accounting for them both, so let's go ahead and write our permutations formula following this here. So we're going to again take our total on the top R value for N So eight factorial and then we're going to divide by five factorial times three factorial. Now, here we've been rewriting our numerator in order to cancel our denominator. Now, since we have a multiple factorials on the bottom, we are simply going to rewrite our numerator to cancel the highest factorial in order to simplify this in the most effective way. So from here, we're gonna want to cancel this five factorial. So let's rewrite eight factorial our numerator in order to cancel that. So I can rewrite eight factorial as eight times seven times six times five factorial. And then in my denominator, I have five factorial and three factorial. Now those five factorials are going to cancel, leaving me on the top with eight times seven times six and in my denominator with three factorial, which expanded out is simply three times two times one. Now, we could choose to cancel some more things here because you might see a couple of things that cancel. But I'm going to go ahead and just fully multiply this out in order to simplify from there. So on the numerator, I end up getting 336 and then in the denominator, I get six. Now dividing this out, I end up with a final answer of 56 different eight digit codes that contain five zeros and three ones. Let's take a look at our second example here. We're asked how many different ways there are to arrange the letters of the word banana. Now, this might seem like a kind of strange question, but we can still attack it the same way. Now, the first thing again, we want to do is identify our different values here. So we want to find N and we want to find any values of RR one R two. And if I have more than that as well. So here, since we're looking at this word banana, we want to know how to arrange all of these different letters. So that means my value of N is going to be the total number of letters in this word. Now, the word banana has six different letters. So that tells me that my value of N is equal to six. Now, we need to identify all of the different types of objects that we have here. In this case, any letters that are the same in this word. Now starting out with B, that's going to be my first type. There's only one B in the word banana. So that means my value for R one is simply going to be one. Then I get to my A and there are actually three A's in the word banana. So that tells me that my R two is going to B three. Now, finally, I have N here and there are two NS in the word banana. So R three is going to be two. Now from here, since we have our N and all of our values are, we can go ahead and use our formula. So I'm going to take that N factorial on the top as I always do. So six factorial and then I'm going to divide that by all of my different types of objects that the, and the factorials of those. So I have one factorial times three factorial times two factorial. And remember we're going to rewrite the numerator in order to cancel the highest factorial in the denominator here. Now, my highest factorial here is this three factorial. So we're gonna go ahead and rewrite that numerator to cancel that out. Now doing that, I get six times five times four times three factorial. And then in my denominator, I still have that one factorial times three factorial times two factorial. Now those three factorials will of course cancel leaving me with my numerator as six times five times four. And then in my denominator, I know that one factorial is just one. So it's not going to do anything there. And then two factorial is two times one. Now fully multiplying that out, that gives me 100 and 20 in my numerator divided by two in my denominator to give me a final answer of 60 different ways to arrange the letters in the word banana. Now that we've seen how to work with permutations of non distinct objects. Let's get some more practice. Thanks for watching and I'll see you in the next one.
10
Problem
Problem
You want to arrange the books on your bookshelf by color. How many different ways could you arrange 12 books if 4 of them have a blue cover, 3 are yellow, and 5 are white?
A
120
B
11,880
C
27,720
D
479,001,600
11
Problem
Problem
How many ways are there to arrange the letters in the word CALCULUS?
A
40,320
B
5,040
C
720
D
6
12
concept
Permutations vs. Combinations
Video duration:
3m
Play a video:
Hey, everyone, up to this point, we've been working with the permutations of different objects. So when considering the permutations of two letters from A B and C, I would consider A B but I would also consider B A, these are two different permutations because they're in two different orders. But now we're going to look at a new way to organize objects called a combination. Now distinguishing between permutations and combinations can be tricky, especially because these words are sometimes used interchangeably in everyday language. But here, I'm going to walk you through exactly what the mathematical difference is between these two things and how to distinguish between them by considering just one thing whether or not the order of these objects matters. So let's go ahead and jump right in here. Now, in working with permutations, we saw that they were a different way to arrange objects in a particular order. So we know that when working with permutations, the order definitely does matter. So when writing all the permutations of two letters from A B and C, I would want to consider BC, but also CB and AC. But also C because these are in completely different orders, they represent different permutations. But when working with combinations, combinations are simply a way to group objects. So if I consider groups of two letters from A B and C, I might consider a BBC and AC, but nothing else because when working with A B, this is the same group of letters as if I were to have B A. So when working with combinations, the order does not matter at all. Now, this might seem a little abstract. So let's go ahead and look at some different examples and determine whether we're working with a permutation or a combination. So looking at this first example here, I'm told that an ice cream shop has 32 different flavors and we need to pick two flavors to blend into a milkshake. And we want to know how many possible ways we can select these flavors. Now, here we're just concerned with identifying whether this is a permutation or a combination. So we want to ask ourselves one question. Does the order of my object matter? Well, if I'm blending up a milkshake, I might want to consider the outcome. So if I pick chocolate and vanilla and I blend that up, wouldn't that be the same milkshake as if I picked vanilla and then chocolate? Well, it would, so my outcome would be no different even if I changed the order. So since the order does not affect the outcome here, I'm simply working with a combination the order does not matter. Let's look at our next example. Here we're asked, how many ways could a photographer line up the members of a family of five? If I were taking this photo, I might consider a couple of different things. So I might consider the height of the people in it or the outfits that they're wearing. So if I put one person on the end in one of those photos, but then I move them to the other side in another photo, this would be a completely different photo. So if I change the order that affects the outcome, so because the order affects the outcome, that tells me that order does matter. And here we're working with a permutation. Let's look at one final example. Here, here we're asked how many different teams, the four people can be formed from a group of nine people. Well, let's say that I pick four people out of these group of nine. Well, if I pick this person first instead, is that going to change what my team is? Well, it's not going to change it at all besides maybe starting a fight between teammates. So because the order does not have an impact on the outcome here, the order does not matter and we're working with a combination. So now that we know how to distinguish between permutations and combinations, let's keep going. Thanks for watching and I'll see you in the next one.
13
concept
Combinations
Video duration:
5m
Play a video:
Hey, everyone, when finding the number of permutations of two letters out of these three letters, knowing that the order matters. Whenever I list these out, I end up with six permutations. But when considering the combinations of two letters out of these three letters, knowing that the order does not matter, I only get three combinations. Now, just seeing that these give me different numbers, you might realize that we're going to have to calculate these two things differently. But don't worry, we're not just going to have to learn, have to learn a brand new equation for combinations because we're just going to take our permutations formula and alter it slightly in order to account for the fact that order doesn't matter in order to get our new combinations formula. So with that in mind, let's go ahead and get started. Now in working with our combinations, if we just plug in our values for N and R, we end up getting three factorial over one factorial, which is just equal to six. Now, for our combinations formula, it looks almost identical to our permutations formula, but now we're just dividing by our factorial. So you'll see that I have my permutations form right here. And I'm just going to add this extra factor of R factorial on the bottom here. So whenever I compute my combinations formula plugging in my values for N and R I end up getting three factorial over one factorial times two factorial, which gives me my answer of three. Now with this formula, remember that N is always going to be your largest number because this represents your total. And R is the number of things you're choosing out of that total. Now, one way that you could remember this formula seeing that we have an N and then an N and then an R and an R. Whenever you think of combinations, you can think N and RR in order to remember the order that these variables come in. Now, something else that might seem familiar here is this combinations notation looks similar to our permutations. Well, with the C with the N and the RS subscripts or C with N and R in parentheses. Both of these can be read as the number of combinations of R things taken N at a time. Now that we know what our combinations formula is, let's get a bit more practice using it by working through some examples together. So looking at this first example, we're told that an ice cream shop has 32 flavors and we need to pick two flavors to blend into a milkshake. We want to know how many possible ways we could do this. Now remember this is a combinations problem because the order doesn't matter. A chocolate and vanilla milkshake is the same thing as a vanilla and chocolate milkshake. Now, the first thing we want to do here is identify our values for N and R. Remember that N is always going to be the largest number our total. So here, my value for N is 32. Then this two right here represents my value for R. So plugging this into my combinations notation, I get 32 C two. And then I'm just plugging these numbers into the formula. So I start with 32 factorial on the top your largest number. And then I have 32 minus two factorial. And don't forget that extra factor of R factorial on the bottom there. Now simplifying this a bit more. I have 32 factorial on the top divided by 30 factorial times two factorial. Now here, since we have multiple factorials in that denominator there, remember we can rewrite our numerator in order to cancel the highest factorial in the denominator. So here we want to cancel this 30 factorial. So let's rewrite that numerator to cancel it. So 32 factorial can be rewritten as 32 times 31 times 30 factorial. And then in my denominator, I have 30 factorial times two factorial. Now those 30 factorials will cancel leaving me on the top 32 times 31 and then on the bottom, expanding that two factorial, that's just two times one. Now, actually multiplying that out gives me 992 on the top, divided by two on the bottom, giving me a final answer of 496 different possible ways we can select our flavors here. Let's move on to our next example. Here, here we're asked how many different teams of four people can be formed from a group of nine people. So let's first identify our value use of N and R. Now remember N is your highest number. So this nine right here and then R is our other number. So four, now writing this as a combination, we have nine C four and we can plug in those values to our formula. So starting with N on the top, of course, we have nine factorial divided by nine minus four factorial times four factorial. Now simplifying this a bit further, we end up with nine factorial over five factorial times four factorial. Now again, we want to cancel the highest factorial in the denominator here by rewriting that numerator. So here I'm going to rewrite my numerator as nine times eight times seven times six times five factorial. And then on the bottom, I have that five factorial and four factorial. But those five factorials are going to cancel. So on the top I am left with nine times eight times seven times six and on the bottom, I have that four factor which expanded out is four times three times, two times one. Now, multiplying that out, I get a rather high number in my numerator here, 3024. And then on the bottom I get 24. Now actually dividing, that gives me a final answer of 126 different teams of four people that can be formed from that nine. Now that we know how to calculate combinations. Let's get some more practice. Thanks for watching and let me know if you have questions.
14
Problem
Problem
From a class of 28 students, in how many ways could a teacher select 4 students to lead the class discussion?