Section 2.2 The sum rule
The sum rule is a rule that can be applied to determine the number of possible outcomes when there are two different things that you might choose to do (and various ways in which you can do each of them), and you cannot do both of them. Often, it is applied when there is a natural way of breaking the outcomes down into cases.
Example 2.2.1.
Recall the example of buying a bagel or a doughnut at a doughnut shop that sells five kinds of doughnuts and three kinds of bagels. You are only choosing one or the other, so one way to determine how many choices you have in total, would be to write down all of the possible kinds of doughnut in one list, and all of the possible kinds of bagel in another list:
| Doughnuts | Bagels |
| chocolate glazed | blueberry |
| chocolate iced | cinnamon raisin |
| honey cruller | plain |
| custard filled | |
| original glazed |
The total number of possible choices is the number of entries that appear in the two lists combined, which is five plus three.
In other words, to determine the number of choices you have, we add the number of choices of doughnut (that is, the number of entries in the first list) and the number of choices of bagel (that is, the number of entries in the second list). This is an example of the sum rule.
We're now ready to state the sum rule in its full generality.
Theorem 2.2.2 (Sum Rule).
Suppose that when you are determining the total number of outcomes, you can identify two distinct cases with the property that every possible outcome lies in exactly one of the cases. If there are \(n_1\) possible outcomes in the first case, and \(n_2\) possible outcomes in the second case, then the total number of possible outcomes will be \(n_1+n_2\text{.}\)
It's hard to do much with the sum rule by itself, but we'll cover a couple of additional examples and then in the next section, we'll get into some more challenging examples where we combine the two rules.
Sometimes the problem naturally splits into more than two cases, with every possible outcome lying in exactly one of the cases. If this happens, we can apply the sum rule more than once to determine the answer. First we identify two cases (one of which may be “everything else”), and then subdivide one or both of the cases. Let's look at an example of this.
Example 2.2.3.
Iswar is planning to flip his coin up to three times. What are the possible combinations of heads and tails he might end up with, if we aren't keeping track of the order of the outcomes? (By not keeping track of the order of the outcomes, I mean that we'll consider flipping two heads followed by one tails as being the same as flipping two heads and one tails in any other order.)
To answer this question, we'll break the problem into cases. First we'll divide the problem into two possibilities: Iswar flips the coin no times; or he flips it at least once. If Iswar does not flip the coin, there is only one possible outcome (no heads and no tails). If Iswar flips the coin at least once, then he flips it between one and three times. We'll have to break this down further to find how many outcomes are involved.
We break the case where Iswar flips the coin between one and three times down into two cases: he might flip it exactly once, or he might flip it more than once. If he flips it exactly once, the outcome of that might be heads or tails, so there are two possible outcomes. If he flips it more than once, again we'll need to further subdivide this case.
The case where Iswar flips the coin either two or three times naturally breaks down into two cases: he might flip it twice, or he might flip it three times. If he flips it twice, the number of heads he gets might be zero, one, or two, so there are three possible outcomes (the remaining results, if any, must all be tails). If he flips it three times, the number of heads he gets might be zero, one, two, or three, so there are four possible outcomes (again, any remaining results must be tails).
Now we put all of these outcomes together with the sum rule. We conclude that in total, there are \(1+(2+(3+4))=10\) different combinations of heads and tails that Iswar might end up with.
Notice that it was artificial to repeatedly break this example up into two cases at a time. Thus, Example 2.2.3 serves as a good demonstration for a generalisation of the sum rule as we stated it above. It would have been more natural to have broken the problem of Iswar's coin flips up into four cases from the beginning, depending on whether he flips the coin zero, one, two, or three times. The total number of combinations of heads and tails that Iswar might end up with, is the sum of the combinations he can end up with in each of these cases; that is, \(1+2+3+4=10\text{.}\)
Theorem 2.2.4 (Sum Rule for many cases).
Suppose that when you are determining the total number of outcomes, you can identify \(k\) distinct cases with the property that every possible outcome lies in exactly one of the cases. If for each \(i\) between \(1\) and \(k\) there are \(n_i\) possible outcomes in the \(i\)th case, then the total number of possible outcomes will be \(\sum_{i=1}^k n_i\) (that is, the sum as \(i\) goes from \(1\) to \(k\) of the \(n_i\)).
There is one other important way to use the sum rule. This application is a bit more subtle. Suppose you know the total number of outcomes, and you want to know the number of outcomes that don't include a particular event. The sum rule tells us that the total number of outcomes is comprised of the outcomes that do include that event, together with the ones that don't. So if it's easy to figure out how many outcomes include the event that interests you, then you can subtract that from the total number of outcomes to determine how many outcomes exclude that event. Here's an example.
Example 2.2.5.
There are \(216\) different possible outcomes from rolling a white die, a red die, and a yellow die. (You can work this out using the product rule.) How many of these outcomes involve rolling a one on two or fewer of the dice?
Tackling this problem directly, you might be inclined to split it into three cases: outcomes that involve rolling no ones, those that involve rolling exactly one one, and those that involve rolling exactly two ones. If you try this, the analysis will be long and fairly involved, and will include both the product rule and the sum rule. If you are careful, you will be able to find the correct answer this way.
We'll use a different approach, by first counting the outcomes that we don't want: those that involve getting a one on all three of the dice. There is only one way for this to happen: all three of the dice have to roll ones! So the number of outcomes that involve rolling ones on two or fewer of the dice, will be \(216-1=215\text{.}\)
Exercises 2.2.6.
Use only the sum rule to answer the following questions:
I have four markers on my desk: one blue and three black. Every day on my way to class, I grab three of the markers without looking. There are four different markers that could be left behind, so there are four combinations of markers that I could take with me. What is the probability that I take the blue marker?
Ocean is thinking of either a letter, or a digit. How many different things could they be thinking of?
How many of the \(16\) four-bit binary numbers have at most one \(1\) in them?