2.1 Additive and Multiplicative Principles

Investigate!

A restaurant offers 8 appetizers and 14 entrées. How many choices do you have if:
1. you will eat one dish, either an appetizer or an entrée?
2. you are extra hungry and want to eat both an appetizer and an entrée?
Think about the methods you used to solve question 1. Write down the rules for these methods.
Do your rules work? A standard deck of playing cards has 26 red cards and 12 face cards.
1. How many ways can you select a card which is either red or a face card?
2. How many ways can you select a card which is both red and a face card?
3. How many ways can you select two cards so that the first one is red and the second one is a face card?

Consider this rather simple counting problem: at Red Dogs and Donuts, there are 14 varieties of donuts, and 16 types of hot dogs. If you want either a donut or a dog, how many options do you have? This isn't too hard, just add 14 and 16. Will that always work? What is important here?

It is important that the events be disjoint: i.e., that there is no way for $A$ and $B$ to both happen at the same time. For example, a standard deck of 52 cards contains $26$ red cards and $12$ face cards. However, the number of ways to select a card which is either red or a face card is not $26 + 12 = 38$ . This is because there are 6 cards which are both red and face cards.

The additive principle also works with more than two events. Say, in addition to your 14 choices for donuts and 16 for dogs, you would also consider eating one of 15 waffles? How many choices do you have now? You would have $14 + 16 + 15 = 45$ options.

Note that in both of the previous examples, when using the additive principle on a bunch of events all the same size, it is quicker to multiply. This really is the same, and not just because $6 + 6 + 6 + 6 = 4 \cdot 6$ . We can first select the topping in 4 ways (that is, we first select which of the disjoint events we will take). For each of those first 4 choices, we now have 6 choices of yogurt. We have:

The multiplicative principle generalizes to more than two events as well.

Example 4

How many license plates can you make out of three letters followed by three numerical digits?

Here we have six events: the first letter, the second letter, the third letter, the first digit, the second digit, and the third digit. The first three events can each happen in 26 ways; the last three can each happen in 10 ways. So the total number of license plates will be $26 \cdot 26 \cdot 26 \cdot 10 \cdot 10 \cdot 10$ , using the multiplicative principle.

Does this make sense? Think about how we would pick a license plate. How many choices we would have? First, we need to pick the first letter. There are 26 choices. Now for each of those, there are 26 choices for the second letter: 26 second letters with first letter A, 26 second letters with first letter B, and so on. We add 26 to itself 26 times. Or quicker: there are $26 times 26$ choices for the first two letters.

Now for each choice of the first two letters, we have 26 choices for the third letter. That is, 26 third letters for the first two letters AA, 26 choices for the third letter after starting AB, and so on. There are $26 times 26$ of these $26$ third letter choices, for a total of $(26 \cdot 26) \cdot 26$ choices for the first three letters. And for each of these $26 \cdot 26 \cdot 26$ choices of letters, we have a bunch of choices for the remaining digits.

In fact, there are going to be exactly 1000 choices for the numbers. We can see this because there are 1000 three-digit numbers (000 through 999). This is 10 choices for the first digit, 10 for the second, and 10 for the third. The multiplicative principle says we multiply: $10 \cdot 10 \cdot 10 = 1000$ .

All together, there were $26 cubed$ choices for the three letters, and $10 cubed$ choices for the numbers, so we have a total of $26 cubed times 10 cubed$ choices of license plates.

Careful: “and” doesn't mean “times.” For example, how many playing cards are both red and a face card? Not $26 times 12$ . The answer is 6, and we needed to know something about cards to answer that question.

Another caution: how many ways can you select two cards, so that the first one is a red card and the second one is a face card? This looks more like the multiplicative principle (you are counting two separate events) but the answer is not $26 times 12$ here either. The problem is that while there are 26 ways for the first card to be selected, it is not the case that for each of those there are 12 ways to select the second card. If the first card was both red and a face card, then there would be only 11 choices for the second card.¹

Example 5 Counting functions

How many functions $f: open brace 1, 2, 3, 4, 5 close brace → open brace a, b, c, d close brace$ are there?

Remember that a function sends each element of the domain to exactly one element of the codomain. To determine a function, we just need to specify the image of each element in the domain. Where can we send 1? There are 4 choices. Where can we send 2? Again, 4 choices. What we have here is 5 “events” (picking the image of an element in the domain) each of which can happen in 4 ways (the choices for that image). Thus there are $4 \cdot 4 \cdot 4 \cdot 4 \cdot 4 = 4^{5}$ functions.

This is more than just an example of how we can use the multiplicative principle in a particular counting question. What we have here is a general interpretation of certain applications of the multiplicative principle using rigorously defined mathematical objects: functions. Whenever we have a counting question that asks for the number of outcomes of a repeated event, we can interpret that as asking for the number of functions from $open brace 1, 2, and so on, n close brace$ (where $n$ is the number of times the event is repeated) to $open brace 1, 2, and so on, k close brace$ (where $k$ is the number of ways that event can occur).

Counting With Sets

Do you believe the additive and multiplicative principles? How would you convince someone they are correct? This is surprisingly difficult. They seem so simple, so obvious. But why do they work?

To make things clearer, and more mathematically rigorous, we will use sets. Do not skip this section! It might seem like we are just trying to give a proof of these principles, but we are doing a lot more. If we understand the additive and multiplicative principles rigorously, we will be better at applying them, and knowing when and when not to apply them at all.

We will look at the additive and multiplicative principles in a slightly different way. Instead of thinking about event $A$ and event $B$ , we want to think of a set $A$ and a set $B$ . The sets will contain all the different ways the event can happen. (It will be helpful to be able to switch back and forth between these two models when checking that we have counted correctly.) Here's what we mean:

Example 6

Suppose you own 9 shirts and 5 pairs of pants.

How many outfits can you make?
If today is half-naked-day, and you will wear only a shirt or only a pair of pants, how many choices do you have?

By now you should agree that the answer to the first question is $9 \cdot 5 = 45$ and the answer to the second question is $9 + 5 = 14$ . These are the multiplicative and additive principles. There are two events: picking a shirt and picking a pair of pants. The first event can happen in 9 ways and the second event can happen in 5 ways. To get both a shirt and a pair of pants, you multiply. To get just one article of clothing, you add.

Now look at this using sets. There are two sets, call them $S$ and $P$ . The set $S$ contains all 9 shirts so $vertical bar S vertical bar equals 9$ while $vertical bar P vertical bar equals 5$ , since there are 5 elements in the set $P$ (namely your 5 pairs of pants). What are we asking in terms of these sets? Well in question 2, we really want $| S \cup P |$ , the number of elements in the union of shirts and pants. This is just $| S | + | P |$ (since there is no overlap; $vertical bar S intersection P vertical bar equals 0$ ). Question 1 is slightly more complicated. Your first guess might be to find $| S \cap P |$ , but this is not right (there is nothing in the intersection). We are not asking for how many clothing items are both a shirt and a pair of pants. Instead, we want one of each. We could think of this as asking how many pairs $(x, y)$ there are, where $x$ is a shirt and $y$ is a pair of pants. As we will soon verify, this number is $| S | \cdot | P |$ .

From this example we can see right away how to rephrase our additive principle in terms of sets:

This hardly needs a proof. To find $A \cup B$ , you take everything in $A$ and throw in everything in $B$ . Since there is no element in both sets already, you will have $| A |$ things and add $| B |$ new things to it. This is what adding does! Of course, we can easily extend this to any number of disjoint sets.

From the example above, we see that in order to investigate the multiplicative principle carefully, we need to consider ordered pairs. We should define this carefully:

The question is, what is $| A \times B |$ ? To figure this out, write out $A \times B$ . Let $A equals open brace a sub 1, a sub 2, a sub 3, and so on, a sub m close brace$ and $B equals open brace b sub 1, b sub 2, b sub 3, and so on, b sub n close brace$ (so $| A | = m$ and $| B | = n$ ). The set $A \times B$ contains all pairs with the first half of the pair being some $a sub i ∈ A$ and the second being one of the $b sub j ∈ B$ . In other words:

$\begin{aligned} A \times B = { & (a_{1}, b_{1}), (a_{1}, b_{2}), (a_{1}, b_{3}), \dots (a_{1}, b_{n}), \\ (a_{2}, b_{1}), (a_{2}, b_{2}), (a_{2}, b_{3}), \dots, (a_{2}, b_{n}), \\ (a_{3}, b_{1}), (a_{3}, b_{2}), (a_{3}, b_{3}), \dots, (a_{3}, b_{n}), \\ ⋮ \\ (a_{m}, b_{1}), (a_{m}, b_{2}), (a_{m}, b_{3}), \dots, (a_{m}, b_{n})} \end{aligned}$

Notice what we have done here: we made $m$ rows of $n$ pairs, for a total of $m \cdot n$ pairs.

Each row above is really ${a_{i}} \times B$ for some $a sub i ∈ A$ . That is, we fixed the $A$ -element. Broken up this way, we have

$A \times B = ({a_{1}} \times B) \cup ({a_{2}} \times B) \cup ({a_{3}} \times B) \cup \dots \cup ({a_{m}} \times B)$

So $A \times B$ is really the union of $m$ disjoint sets. Each of those sets has $n$ elements in them. The total (using the additive principle) is $n + n + n + \dots + n = m \cdot n$ .

To summarize:

Again, we can easily extend this to any number of sets.

Principle of Inclusion/Exclusion

Investigate!

A recent buzz marketing campaign for Village Inn surveyed patrons on their pie preferences. People were asked whether they enjoyed (A) Apple, (B) Blueberry or (C) Cherry pie (respondents answered yes or no to each type of pie, and could say yes to more than one type). The following table shows the results of the survey.

Pies enjoyed:	A	B	C	AB	AC	BC	ABC
Number of people:	20	13	26	9	15	7	5

How many of those asked enjoy at least one of the kinds of pie? Also, explain why the answer is not 95.

While we are thinking about sets, consider what happens to the additive principle when the sets are NOT disjoint. Suppose we want to find $| A \cup B |$ and know that $vertical bar A vertical bar equals 10$ and $vertical bar B vertical bar equals 8$ . This is not enough information though. We do not know how many of the 8 elements in $B$ are also elements of $A$ . However, if we also know that $vertical bar A intersection B vertical bar equals 6$ , then we can say exactly how many elements are in $A$ , and, of those, how many are in $B$ and how many are not (6 of the 10 elements are in $B$ , so 4 are in $A$ but not in $B$ ). We could fill in a Venn diagram as follows:

Intersecting circles labeled A and B. Inside the region enclosed by both circles is the number 6. The number 4 is in the region inside A but outside B. The number 2 is in the region inside B but outside A.

This says there are 6 elements in $A \cap B$ , 4 elements in $A ∖ B$ and 2 elements in $B ∖ A$ . Now these three sets are disjoint, so we can use the additive principle to find the number of elements in $A \cup B$ . It is $6 + 4 + 2 = 12$ .

This will always work, but drawing a Venn diagram is more than we need to do. In fact, it would be nice to relate this problem to the case where $A$ and $B$ are disjoint. Is there one rule we can make that works in either case?

Here is another way to get the answer to the problem above. Start by just adding $| A | + | B |$ . This is $10 + 8 = 18$ , which would be the answer if $vertical bar A intersection B vertical bar equals 0$ . We see that we are off by exactly 6, which just so happens to be $| A \cap B |$ . So perhaps we guess,

$| A \cup B | = | A | + | B | - | A \cap B |$

This works for this one example. Will it always work? Think about what we are doing here. We want to know how many things are either in $A$ or $B$ (or both). We can throw in everything in $A$ , and everything in $B$ . This would give $| A | + | B |$ many elements. But of course when you actually take the union, you do not repeat elements that are in both. So far we have counted every element in $A \cap B$ exactly twice: once when we put in the elements from $A$ and once when we included the elements from $B$ . We correct by subtracting out the number of elements we have counted twice. So we added them in twice, subtracted once, leaving them counted only one time.

In other words, we have:

We can do something similar with three sets.

Example 8

An examination in three subjects, Algebra, Biology, and Chemistry, was taken by 41 students. The following table shows how many students failed in each single subject and in their various combinations:

Subject:	A	B	C	AB	AC	BC	ABC
Failed:	12	5	8	2	6	3	1

How many students failed at least one subject?

The answer is not 37, even though the sum of the numbers above is 37. For example, while 12 students failed Algebra, 2 of those students also failed Biology, 6 also failed Chemistry, and 1 of those failed all three subjects. In fact, that 1 student who failed all three subjects is counted a total of 7 times in the total 37. To clarify things, let us think of the students who failed Algebra as the elements of the set $A$ , and similarly for sets $B$ and $C$ . The one student who failed all three subjects is the lone element of the set $A \cap B \cap C$ . Thus, in Venn diagrams:

Now let's fill in the other intersections. We know $A \cap B$ contains 2 elements, but 1 element has already been counted. So we should put a 1 in the region where $A$ and $B$ intersect (but $C$ does not). Similarly, we calculate the cardinality of $open parenthesis A intersection C close parenthesis ∖ B$ , and $open parenthesis B intersection C close parenthesis ∖ A$ :

Next, we determine the numbers which should go in the remaining regions, including outside of all three circles. This last number is the number of students who did not fail any subject:

We found 5 goes in the “ $A$ only” region because the entire circle for $A$ needed to have a total of 12, and 7 were already accounted for. Similarly, we calculate the “ $B$ only” region to contain only 1 student and the “ $C$ only” region to contain no students.

Thus the number of students who failed at least one class is 15 (the sum of the numbers in each of the eight disjoint regions). The number of students who passed all three classes is 26: the total number of students, 41, less the 15 who failed at least one class.

Note that we can also answer other questions. For example, how many students failed just Chemistry? None. How many passed Algebra but failed both Biology and Chemistry? This corresponds to the region inside both $B$ and $C$ but outside of $A$ , containing 2 students.

Could we have solved the problem above in an algebraic way? While the additive principle generalizes to any number of sets, when we add a third set here, we must be careful. With two sets, we needed to know the cardinalities of $A$ , $B$ , and $A \cap B$ in order to find the cardinality of $A \cup B$ . With three sets we need more information. There are more ways the sets can combine. Not surprisingly then, the formula for cardinality of the union of three non-disjoint sets is more complicated:

To determine how many elements are in at least one of $A$ , $B$ , or $C$ we add up all the elements in each of those sets. However, when we do that, any element in both $A$ and $B$ is counted twice. Also, each element in both $A$ and $C$ is counted twice, as are elements in $B$ and $C$ , so we take each of those out of our sum once. But now what about the elements which are in $A \cap B \cap C$ (in all three sets)? We added them in three times, but also removed them three times. They have not yet been counted. Thus we add those elements back in at the end.

Returning to our example above, we have $vertical bar A vertical bar equals 12$ , $vertical bar B vertical bar equals 5$ , $vertical bar C vertical bar equals 8$ . We also have $vertical bar A intersection B vertical bar equals 2$ , $vertical bar A intersection C vertical bar equals 6$ , $vertical bar B intersection C vertical bar equals 3$ , and $vertical bar A intersection B intersection C vertical bar equals 1$ . Therefore:

$| A \cup B \cup C | = 12 + 5 + 8 - 2 - 6 - 3 + 1 = 15$

This is what we got when we solved the problem using Venn diagrams.

This process of adding in, then taking out, then adding back in, and so on is called the Principle of Inclusion/Exclusion, or simply PIE. We will return to this counting technique later to solve for more complicated problems (involving more than 3 sets).

Your Blu-ray collection consists of 9 comedies and 7 horror movies. Give an example of a question for which the answer is:

For example, 16 is the number of choices you have if you want to watch one movie, either a comedy or horror flick.
For example, 63 is the number of choices you have if you will watch two movies, first a comedy and then a horror.

Let $A$ , $B$ , and $C$ be sets.

Find $vertical bar open parenthesis A union C close parenthesis ∖ B vertical bar$ provided $vertical bar A vertical bar equals 50$ , $vertical bar B vertical bar equals 45$ , $vertical bar C vertical bar equals 40$ , $vertical bar A intersection B vertical bar equals 20$ , $vertical bar A intersection C vertical bar equals 15$ , $vertical bar B intersection C vertical bar equals 23$ , and $vertical bar A intersection B intersection C vertical bar equals 12$ .
Describe a set in terms of $A$ , $B$ , and $C$ with cardinality 26.

For part (a) you could use the formula for PIE, but for part (b) you might be better off drawing a Venn diagram.

For how many three digit numbers (100 to 999) is the sum of the digits even? (For example, $343$ has an even sum of digits: $3 + 4 + 3 = 10$ which is even.) Find the answer and explain why it is correct in at least two different ways.

You could consider cases. For example, any number of the form ODD-ODD-EVEN will have an even sum. Alternatively, how many three digit numbers have the sum of their digits even if the first two digits are 54? What if the first two digits are 19?

The number 735000 factors as $2^{3} \cdot 3 \cdot 5^{4} \cdot 7^{2}$ . How many divisors does it have? Explain your answer using the multiplicative principle.

For a simpler example, there are 4 divisors of $6 = 2 \cdot 3$ . They are $1 = 2^{0} \cdot 3^{0}$ , $2 = 2^{1} \cdot 3^{0}$ , $3 = 2^{0} \cdot 3^{1}$ and $6 = 2^{1} \cdot 3^{1}$ .

Discrete Mathematics: An Open Introduction, 3rd edition, by Oscar Levin (discrete.openmathbooks.org), licensed under CC BY-SA 4.0; this adaptation is distributed under the same license. License: CC-BY-SA-4.0.