Section PC.7 – Combinations
In the previous section we considered the situation where we chose r items out of n possibilities without replacement and where the order of selection was important. We now consider a similar situation in which the order of selection is not important.
| Example 1 | ||||||
| A charity benefit is attended by 25 people at which three $50 gift certificates are given away as door prizes. Assuming no person receives more than one prize, how many different ways can the gift certificates be awarded? | ||||||
Using the Basic Counting Rule, there are 25 choices for the first person, 24 remaining choices for the second person and 23 for the third, so there are 25 · 24 · 23 = 13,800 ways to choose three people. Suppose for a moment that Abe is chosen first, Bea second and Cindy third; this is one of the 13,800 possible outcomes. Another way to award the prizes would be to choose Abe first, Cindy second and Bea third; this is another of the 13,800 possible outcomes. But either way Abe, Bea and Cindy each get $50, so it doesn’t really matter the order in which we select them. In how many different orders can Abe, Bea and Cindy be selected? It turns out there are 6:
How can we be sure that we have counted them all? We are really just choosing 3 people out of 3, so there are 3 · 2 · 1 = 6 ways to do this; we didn’t really need to list them all, we can just use permutations! So, out of the 13,800 ways to select 3 people out of 25, six of them involve Abe, Bea and Cindy. The same argument works for any other group of three people (say Abe, Bea and David or Frank, Gloria and Hildy) so each three-person group is counted six times. Thus the 13,800 figure is six times too big. The number of distinct three-person groups will be 13,800/6 = 2300. |
We can generalize the situation in this example above to any problem of choosing a collection of items without replacement where the order of selection is not important. If we are choosing r items out of n possibilities (instead of 3 out of 25 as in the previous examples), the number of possible choices will be given by [latex]\frac{_n~P~_r}{_r~P~_r}[/latex] , and we could use this formula for computation. However this situation arises so frequently that we attach a special notation and a special definition to this situation where we are choosing r items out of n possibilities without replacement where the order of selection is not important.
| Combinations |
|
nCr = [latex]\frac{_n~P~_r}{_r~P~_r}[/latex] We say that there are nCr combinations of size r that may be selected from among n choices without replacement where order doesn’t matter. We can also write the combinations formula in terms of factorials: nCr = [latex]\frac{n!}{(n-r)!r}[/latex] |
| Example 2 |
| A group of four students is to be chosen from a 35-member class to represent the class on the student council. How many ways can this be done? |
| Since we are choosing 4 people out of 35 without replacement where the order of selection is not important there are 35C4 = = 52,360 combinations.
Your graphing calculator will also find combinations. For this example, type 35, select MATH, PRB, nCr. Your main screen should show “35 nCr” with a blinking cursor. Type 4. Your main screen should now show “35 nCr 4”. Hit “enter” to get the answer 52,360. |
| You Try PC.7.A |
| The United States Senate Appropriations Committee consists of 29 members; the Defense Subcommittee of the Appropriations Committee consists of 19 members. Disregarding party affiliation or any special seats on the Subcommittee, how many different 19-member subcommittees may be chosen from among the 29 Senators on the Appropriations Committee? |
In the preceding You Try problem we assumed that the 19 members of the Defense Subcommittee were chosen without regard to party affiliation. In reality this would never happen: if Republicans are in the majority they would never let a majority of Democrats sit on (and thus control) any subcommittee. (The same of course would be true if the Democrats were in control.) So let’s consider the problem again, in a slightly more complicated form:
| Example 3 |
| The United States Senate Appropriations Committee consists of 29 members, 15 Republicans and 14 Democrats. The Defense Subcommittee consists of 19 members, 10 Republicans and 9 Democrats. How many different ways can the members of the Defense Subcommittee be chosen from among the 29 Senators on the Appropriations Committee? |
|
In this case we need to choose 10 of the 15 Republicans and 9 of the 14 Democrats. There are 15C10 = 3003 ways to choose the 10 Republicans and 14C 9 = 2002 ways to choose the 9 Democrats. But now what? How do we finish the problem? Suppose we listed all of the possible 10-member Republican groups on 3003 slips of red paper and all of the possible 9-member Democratic groups on 2002 slips of blue paper. How many ways can we choose one red slip and one blue slip? This is a job for the Basic Counting Rule! We are simply making one choice from the first category and one choice from the second category, just like in the restaurant menu problems from earlier. There must be 3003 · 2002 = 6,012,006 possible ways of selecting the members of the Defense Subcommittee. |
Section PC.7 Answers to You Try Problems
PC.7.A
20,030,010
