Section 9.3 Basic counting principles
Now that you are hopefully convinced of both the utility and difficulty of the task ahead, let us begin to learn to count. There are three sections remaining in this chapter. First, we will learn the basic techniques of enumeration, addition, and multiplication. These are what I consider the three most basic of the fundamental counting principles. The two more complicated principles, correspondence and using generating functions, will be discussed in the next chapter. Before that, in this chapter, we will learn to count ordered samples (these are easier) followed by unordered samples.
The first basic principle of counting is the systematic enumeration of the set of objects being counted. This is a fancy way of saying that we are going to list everything out. However, instead of listing objects haphazardly (opening ourselves up to mistakes), we will list objects carefully, following some pattern. There is no “correct” pattern. However, you choose some sort of rule of thumb, and follow that until the entire set has been listed. Remember how we wrote down the rows of a truth tables by exhausting the first letter's true rows before moving on to its false rows in the chapter on logic: this is the same idea.
Example 9.3.1.
Suppose that we are to choose a team of three from Alicia, Bob, Carlos, Derrick, and Eve (\(A,B,C,D,E\) for short). In two sections this problem will become very easy, so let's add the additional wrinkle that Bob and Derrick, who have recently feuded, refuse to participate on the team together. Now, one way to solve this problem is to enumerate the possible outcomes.
There is no comment that the team has three different roles, so by default this is an unordered sample with no replacement. First, let's consider the teams with Alicia in them. Then, let Bob be the “second” participant. It remains to choose the “third” participant from the two remaining people, Carlos and Eve (because Derrick will not be on a team with Bob). Therefore we have found the samples \(ABC\) and \(ABE\text{.}\)
(Technically these are sets, so they should be written \(\{A,B,C\}\text{,}\) but since we are writing many down it is convenient to lose the braces and commas.)
Let's leave Alicia on the team, but now take Bob off and add Carlos to the team. Since the order of the team is irrelevant, we have already counted the team containing Alicia, Carlos, and Bob. The only new options are Derrick and Eve: \(ACD\) and \(ACE\text{.}\)
Next, count the teams with Alicia and Derrick. The only option is \(ADE\text{.}\) We could try to count the teams with Alicia and Eve, but again because of the lack of order, we have already counted those. Therefore, we have counted all the teams involving Alicia:
It now remains to count the teams that do not involve Alicia. We will slot Bob into the “first” position now, but remember, since there really isn't an order Alicia won't appear in any of these teams. It stands to reason that for each person in the “first” slot we will see fewer teams than before.
The only new team with Bob is \(BCE\) because \(BCD\) and \(BDE\) are impossible.
This leaves \(CDE\) as the only team without Bob or Alicia.
Therefore, the total set of teams is
There are seven total possible teams. This problem may have appeared quite hard at first, but hopefully now you see that by carefully listing out all of our options it is not so bad.
The next principle of counting is the addition principle. The great thing about this principle is that you already know it. Recall that if \(X\) and \(Y\) are finite sets, then
In other words, if you are trying to count the number of ways to arrive at one event or another, then you can do so by adding the number of ways to arrive at each individual event. However, since there may be some overlap, you should subtract the number of ways to arrive at both events simultaneously so that nothing is double-counted. The key phrase here is “(either) or” signaling that you should add the cardinalities and subtract the intersection's cardinality.
Sometimes this is referred to as the inclusion-exclusion principle.
Example 9.3.2.
How many teams of three from Alicia, Bob, Carlos, Derrick, and Eve, where Bob and Derrick refuse to cooperate, contain Alicia or Derrick?
We know that five teams contain Alicia: \(ABC, ABE, ACD, ACE, ADE\text{.}\)
Three teams contain Derrick: \(ACD, ADE, CDE\text{.}\)
The answer is not eight, since two teams contain both Alicia and Derrick and are being double-counted. Therefore the answer is \(5+3-2=6\text{.}\) We confirm by enumerating:
Example 9.3.3.
Two six-sided dice are rolled, one red and one blue. The sum of the two dice are tallied. In how many outcomes is the sum greater than 7 or the red die result a 4?
The easiest way to start is to enumerate all possible outcomes. The columns correspond to the results of the red die (across) and the rows correspond to the results of the blue die (down).
1 | 2 | 3 | 4 | 5 | 6 | |
1 | 2 | 3 | 4 | 5 | 6 | 7 |
2 | 3 | 4 | 5 | 6 | 7 | 8 |
3 | 4 | 5 | 6 | 7 | 8 | 9 |
4 | 5 | 6 | 7 | 8 | 9 | 10 |
5 | 6 | 7 | 8 | 9 | 10 | 11 |
6 | 7 | 8 | 9 | 10 | 11 | 12 |
We may count to see that 15 outcomes have a sum greater than 7. There are 6 outcomes where the red die is a 4. There are 3 outcomes (the 8, 9, and 10 in the fourth column) where the red die is 4 and the sum is higher than 7. Since \(15+6-3=18\text{,}\) there are 18 outcomes where either the sum is greater than 7 or the red die showed a 4.
Finally, we arrive at the multiplication principle. You know this one as well. Remember that if \(X\) and \(Y\) are sets then
If two events are to both occur, then we must have something leading to the first even and something leading to the second. Basically, this is an ordered pair \((x,y)\) where the outcome \(x\) leads to the event \(X\) occurring and \(y\) leads to \(Y\text{.}\) The important caveat here is that \(X\) and \(Y\) must be “independent” in the sense that every outcome in one set must not affect the number of outcomes in the second set. (For example, Bob and Derrick's unwillingness to work with each other would cause an issue with the multiplication principle.) The important thing is that when you see the word “and,” you will likely multiply two cardinalities together.
Example 9.3.5.
Two students from Alicia, Bob, Carlos, Derrick, and Eve are to do a task together. This time, Bob and Derrick have made up. How many combinations of two students are possible?
We could enumerate, but we could also multiply. First we choose one of the five students. Then there are four students left to choose regardless of who we picked first. So, \(5\times 4 = 20\text{.}\)
If the order of the students chosen matters (ie. there is a leader), then 20 is the answer. If not, we have counted each pair twice. So, divide by 2 to get the answer (10).
Example 9.3.6.
At a popular coffee chain it is possible to get one of four roasts. Then you may choose whether or not to have cream, and whether or not to have sugar. Finally, you can choose among ten different flavors of syrup. How many different drinks are possible if you have exactly one flavor in your coffee?
This is an “and”-type event comprised of the four events “you pick a roast,” “you decide whether to have cream,” “you decide whether to have sugar,” and “you choose a flavor.” One choice of an outcome in one event doesn't affect the number of possibilities for the other three, hence there are
possible drinks. (“Cream or not” is two choices, same for sugar.)
If the outcome of one event affects the number of outcomes for the other, then you must use a combination of enumeration, addition, and multiplication to find the answer.