Sometimes, the order of our objects does not matter. For example, suppose a professor is trying to assign people to different study groups. Then, it does not matter who gets assigned to the study group first; what matters is who is in which study groups, as in the following example:
A professor is trying to split up his class of 9 students into 3 groups of 3. How many ways can he do this?
Or we might have:
An appeals court is convening a 3-judge panel to hear a certain case. There are 26 judges in the courthouse. How many 3-judge panels are possible?
Now suppose that of the 26 judges, 13 are conservative and 13 are liberal. How many possible 3-judge panels will have at least one conservative and one liberal on the panel?
To address these kinds of problems, we will use the following:
Rule for Combinations
If you have n objects and you want to pick k of them to form a group, then there are n!/((n-k)!k!) ways to do so.
Let's try to solve our earlier example with this rule.
By applying our rule, we know that there are ways of choosing 3 judges from the total group of 26 judges in order to form a panel. We can directly calculate this:
, since and .
So there are 2600 ways to pick such a panel.
But why does this rule make sense? Well, let’s start with our rule for permutations: if I want to form a line of three judges from this group of 26, then there are 26*25*24 ways of doing this. This is because we have three spots to fill:
____ ____ ____
And for the first spot, we can pick any of the 26 judges; for the second, we can pick any of the remaining 25 judges, and for the last spot, we can pick any of the remaining 24 judges.
But here is the problem: we don’t actually care about the order in which we pick the judges. Suppose we have Judge Abby, Judge Ben, and Judge Cynthia. Then, we want to treat this possibility:
Abby Ben Cynthia
the same as this possibility:
Ben Abby Cynthia
which is in turn the same as
Cynthia Abby Ben
Cynthia Ben Abby
Abby Cynthia Ben
Ben Cynthia Abby.
We want to count all of these possibilities just once, since for us, a panel with Abby, Ben and Cynthia on it is just the same as a panel with Cynthia, Abby, and Ben on it. They’re not actually different!
Now, whenever we pick three judges from the 26 total judges, there are 3! ways to order those judges. This is because, for the first slot, we can pick any one of the three judges, for the second slot, we can pick any one of the remaining two judges, and for the last slot, we are stuck with the final judge.
So our permutation 26*25*24 actually counts each of these panels 3! times, when we only want to count each panel once. Suppose a panel has judge A, B, and C on it. Then our permutation counts:
So since our permutation is counting these panels 3! times when it should be counting them just once, we divide by 3! to get our final answer.
And, in general, the formula for how many combinations of k items we can pick from n objects is just equal to the number of permutations of k items we can pick from n objects, divided by (k!). Dividing by k! is how we make sure we are not counting all the different orders a particular combination can be put in.
A professor is trying to split up his class of 8 students into two groups of 4 students each. How many ways can he do this?
Notice that if we pick one of the groups of 4, then the other group is already chosen (just as the people who are left out of our initial group). Thus, we just need to determine how many ways the professor can pick a group of 4. Following our rule, there are ways to do so.
Congress has decided to randomly pick a group of 4 congresspeople to lead a congressional committee. There are 535 congresspeople. How many groups are possible? What is the probability that any particular congressperson will be on the committee?
This is fairly straightforward: how many ways to pick 4 people from 535 people are there? That is just ways. Now, to determine the probability that any particular congressperson will be on the committee, suppose that person is on the committee. Then, we must pick 3 other people from 534 remaining people. There are (following our rule) 25236484 ways to do so. Thus, there is a likelihood of that any particular congressperson will be on the committee.
Congress has decided to randomly pick a committee of 4 congresspeople, but they decide to pick as follows: 2 seats are randomly chosen from the Representatives while the remaining 2 are randomly chosen from the Senate. How many committees are possible? What is the probability that any particular Representative will be on the committee? What is the probability that any particular Senator will be on the committee?
Now, we need to find the two parts of the committees separately and then multiply them together. So, for the representatives, there are ways to choose while for the senators, there are ways. Thus, there are total ways to choose the committees. Note how much smaller this amount is than before. And for any particular representative to be on the committee, that person must be one of the two chosen from the representatives. Fixing one of the representatives allows 434 options for the other person. Thus, there is a chance of any particular representative being chosen. And fixing one of the senators allows options for the other person and thus, chance of being chosen.