Weight Loss Made a Bit Easier: Realistic and Practical Advice for Healthy Eating and Exercise
Available on Amazon.com in paperback/Kindle formats for $6.25/$2.99. Please click here for details.
Home | My Math and Education Books | Math Lessons | Ask a Math Question
Site Info | Contact Info | Tutoring Info | LarryZafran.com | Tweet
Lesson 140: Intro to Combinations
In this lesson we'll look at permutation-type problems in which order doesn't matter.
Before starting this lesson, be sure that you fully understand the previous lesson about permutations. This lesson builds on that material. Here is very typical question involving combinations: There are five students in an after-school program. I only have room to take 3 of them on a field trip. How many different groups of 3 students can I form?
Notice how this is different than a permutation problem. In this case, the order of the students doesn't matter. I'm just forming a group of 3 out of the 5 students. There is no special order within the group that I choose. Here is what we do:
First, let's figure out 5P3. We will pretend for the moment that order matters. We saw in the last lesson that we compute 5! / 2!, to get 5 x 4 x 3 = 60. That means that there are 60 ways that we can choose the 3 students, placing them into a particular order.
In our problem, though, we don't care about any order. Let's pretend that we picked three students: A, B, and C. Our permutation formula calculated all of the possible ways of ordering those three students. How many ways can they be ordered? There are 3 ways to pick the first student, 2 ways for the second, and 1 for the third, for a total of 3!, or 6 arrangements. What we must do is take the answer that we got for 5P3, and divide by 3!, since each grouping of 3 students was actually counted 3! or 6 times in our permutation formula. We end up with an answer of 10, which is 6 times as small as answer that we got when order mattered.
That concept is a bit tricky, so take some time to think about it. When computing combinations, we need to compensate for the fact that when using the permutation formula, order was taken into account, when we don't actually care about order.
Here is our formula for combinations: nCr
= nPr
/ r!. Of course C stands for combination. To
find the number of possible combinations of r objects taken from a
pool of n objects, first compute nPr, and then
divide by r! to compensate for the fact that the permutation formula
calculated every possible ordering within each combination.
Let's try another example. There are 12 students, of which you need to select 4 to form a group. The order of those students don't matter. First we'll pretend that order does matter, and we'll compute 12P4. We do 12! / (12-4)!, which is 12! / 8!, which is 12 x 11 x 10 x 9 = 11,880. We're not done. Each group of 4 was counted 4! or 24 times, since within each group of 4, there are 4! different ways of ordering the group. We must divide our answer by 4!, to find the number of combinations, where order doesn't matter. We'll do 11,880 / 24 to get 495.
Some combination problems ask you to find the number of ways you can choose items from two separate groups. For example, let's say that there are 9 books, and 7 CDs. How many different ways can we choose 3 books and 5 CDs. All we do is compute 9C3 and 7C5, and then multiply the results, since we have an "and" condition.
Some problems will present a variety of special conditions. As with permutation problems, just read the problem very carefully. A common component of a question involves computing "at most," or "at least." For example, how many different ways can you choose at least 5 objects from a pool of 7. Here we're going to do 3 separate computations, and add the results since we have an "or" condition.
We need to determine the number of combinations of 5, plus the combinations of 6, plus the combinations of 7. Any of those conditions will satisfy the problem. A combination of either 5, 6, or 7 will work, so we really have 7C5 or 7C6 or 7C7. We can compute the first one using our formula, and we get 21. There is a shortcut for the second combination. We can choose 6 from the 7 by eliminating 1 of the 7. We can do that in 7 different ways, since there are 7 objects. There is also a shortcut for the third combination. There is only 1 possible way that we can choose 7 items from 7...just choose them all! Our answer is 21 + 7 + 1 = 29.
These problems can be tricky. Just be sure to read the problem carefully. If necessary, use scrap paper to write out some of the possible combinations so you can get an idea of what the problem is really asking.
Don't panic if you forget the formula for combinations. It is not hard to recreate when needed. Just worry about n's and r's. Just ask yourself questions like, "How many ways can I choose the first student", etc., and, "Do I have to divide by a number to compensate for the fact that each permutation included a certain number of orderings, but order didn't matter." If you do this, you should be able to recreate the formula fairly easily. Just keep practicing with it so that you can really get a feel for how and why it works.
Remember that you can ask a math question if you have additional questions about a topic, or you can contact me if you have any comments or suggestions for this site.