Addition and Subtraction Principles

The Addition Principle (AP) and Subtraction Principle (SP) are fundamental principles in counting. In essence, the AP allows you to break a counting problem into different cases that are easier to manage, and then count each case separately. The SP is similar, but it allows us to remove (or “uncount”) cases that we have already counted but do not want in our final total.

The AP and SP are commonly used in more advanced problems, but they themselves are fairly intuitive. We use them often when we solve counting problems, sometimes without being aware that we are using them. We will start each section by asking a series of questions meant to highlight the aspects of each principle before we give you statements of the principles. Then, we will discuss how they can be used in counting problems.

Addition Principle

Let’s begin by solving the following problems.

How did you feel about those problems? Now let’s look at statements of the Addition Principle.

Addition Principle Basic (AP)

Suppose a set of events \(S\) can be partitioned (or separated) into subsets of events \(A\) or \(B\) such that every event in \(S\) belongs to one and exactly one of \(A\) or \(B\). Then the number of events in \(S\) is equal to the sum of the number of events in \(A\) and the number of events in \(B\). Said another way, if we consider \(|A|\) to be the number of elements in the set \(A\) (also called the cardinality of \(A\)), Then we have that \(|S| = |A| + |B|\).

Addition Principle Full (AP)

Suppose a set of events, \(S\) can be partitioned (or separated) into a number of subsets \(S_1, S_2, \ldots , S_k\), where every event in \(S\) belongs to one and exactly one of these subsets. Then the total number of events in \(S\) is the sum of the number of events in each subset \(S_1, S_2, \ldots , S_k\). Alternatively, \(|S| = |S_1| + |S_2| + \cdots + |S_k|\).

The way the AP statements are written may seem more detailed and intimidating than how you might have been thinking about it. This is done with the primary reason of intimidating you. Mathematicians bond over scaring their students, and they often swap intimidation tactics at holiday parties.

All joking aside, the reason for wordy mathematical statements like the AP is so that we can be precise. We will walk through the language of the AP to help you develop a robust understanding of it. Informally, we might say that the addition principle states, “if you can break down a set of events into different cases, then you can add together the sizes of all the cases to find out the total number of events.”

The word “partition” in the statements of the AP is actually doing a lot of work here. While it is a familiar term, it actually has a specific definition when we are talking about sets. In particular, a partition breaks a set into subset, but those subsets have two important properties: First, the subsets are disjoint, which means that any element of the set can only belong to exactly one (and not more than one) subset of the partition. Second, taken together, all of the subsets exactly form the set, which means that any element of the set must be in exactly one (and not less than one) subset of the partition. Thus, when a partition is formed, we know that every element of the set is in exactly one part (or subset) of partition. This is what allows us to sum as we do in our statements of the AP.

Let’s return to the previous car examples. In the first questions, we said that you owned three red cars, four blue cars, and no cars of other color. Because cars cannot both be red and blue, then there are no cars that fall into both of those categories. Further, we specified that every car fits into one of those categories. Hence, the two categories together make up all of your cars, and each car falls into exactly one category. This exactly satisfies the requirements of the partition, as describe above. From this, then, we can gather that the total number cars you own is the sum of each of the size of the categories.

Lets’s review with a simple example. I want to pick out a shirt to wear. I own 8 different cat shirts and 6 different Rocket Raccoon shirts. I might ask how many ways I can pick a single shirt to wear. Because I can partition each choice of which shirt to wear into either choosing a cat shirt or a Rocket shirt, then the total number of ways to choose a shirt is the sum of ways to pick a Cat shirt and ways to pick a Rocket shirt. Hence, there are \(8+6=14\) ways I can pick a shirt to wear.

There are a couple of characteristics of this example to point out. The first is that every choice of shirt can be categorized as choosing a Cat or a Rocket shirt. This makes sure that we are are not missing outcomes. The second is that there are no t-shirts that are both Cat and Rocket shirts (although that would be amazing). This makes sure that we are not counting a shirt more than once. Thus, we are counting all of our shirts, and we are only counting a shirt once.

The AP is typically used for problems where the set of outcomes or events can be categorized into sets that are easier to count. Consider the following problem.

We can consider what it might look like to write a program to list outcomes so as to leverage the addition principle. Consider a problem like the following.

Problem: Username

You are deciding on a username for social media. To keep things simple, you decide that it will have two letters and two numbers, where either the numbers come first (such as 79HI) or the letters come first (such as HI79). How many ways are there to create such a username?

Here, we can break the usernames into two cases, based on whether or not the numbers come first. If the numbers come first, then there are \(10^2\times 26^2\) ways to create a username. If the letters come first, then there are \(26^2 \times 10^2\) ways to create a username. Hence, there are \(10^2\times26^2 + 26^2\times 10^2\) total ways to create a username.

The code below is meant to reflect this process and this case breakdown. In particular, the two successive sets of nested for loops correspond to the two cases. In the first set of loops, we compute the usernames that consist of numbers followed by letters. In the second set of loops, we compute the usernames that consist of letters followed by numbers.

Look at the code below. Before you run it, answer the following multiple choice question.

Problem: Book Genres

You are traveling on vacation and you decide to bring two books with you. Your three favorite series are Harry Potter (there are 7 HP books), Game of Thrones (there are 5 GoT books), and Lord of the Rings (there are 3 LOTR books). How many possibilities are there for which two books you take with you on vacation, if the books must be from different series?

Subtraction Principle

Technically, we can think of the Subtraction Principle (SP) as an application of the Addition Principle (AP). Just like you can do algebra on the expression \(y = x+3\) to find that \(y-3 = x\), we can subtract off outcomes or events that we don’t want to count. Try it for yourself.

Did you count number of xs one by one? Probably not. Although that would work, an easier method is to recognize that there are 8 rows and 8 columns, so there are 64 total entries. Plus, you know that there are only four entries that are not xs. How many does this leave that are xs?

Let’s state the Subtraction Principle so we have it on record.

Subtraction Principle Basic (SP)

Suppose a set of events \(S\) can be partitioned into two subsets of events \(A\) and \(B\) so that every event in \(S\) belongs to either \(A\) or \(B\), but not both. Then the number of events in \(B\) is equal to the number of events in \(S\) minus the number of events in \(A\). Alternatively, \(|S| - |A| = |B|\).

Let’s unpack this statement using the x and OO example. We can partition the number of entries in the table (the set \(S\)) into those that are xs (the set \(B\)) and those that are OOs (the set \(A\)). If we want to count the number of xs (\(|B|\)), we can do so by subtracting the number of OOs from the total number of entries (\(|S|-|A|\)).

Subtraction Principle Full (SP)

Suppose a set of events \(S\) can be partitioned into subsets \(S_1, S_2, \ldots , S_k\), where every event in \(S\) belongs to exactly one of the subsets. Then the number of events in \(S_k\) is the number of events in \(S\) minus the number of events in all other subsets. Alternatively, \(|S|-|S_1| -|S_2| - \cdots - |S_{k-1}| = |S_k|\).

This sounds much more difficult than how the SP is applied in practice. The basic premise is that we can overcount, and then ‘uncount’ the outcomes we don’t want in our final tally. Try the following problem.

This is how the subtraction principle is usually applied. You count a larger number of events because it is easy (or familiar), and then you subtract, or “uncount”, the unwanted events.

Problem: Hotel

Steve and Royce arrive at a hotel that has 10 available rooms. They decide to book rooms so that they don’t share a room. Examine the following code.

Look at the list of outcomes when you run the code above. Some combinations of numbers are missing. Which numbers are missing, and why does that make sense? What would a missing number correspond to in terms of Steve and Royce booking a room?

Let’s use the SP to count the number of ways that Steve and Royce can book rooms if they do not share a room. First, we note that there are \(10^2\) ways for them to book rooms. Steve has 10 different rooms he can be in, and for any room Steve is in Royce also has 10 different rooms he can be in. Thus, there are \(10\times 10\) ways that they can be placed in hotel rooms. However, these choices also include the options where they share a hotel room, which we do not want to count. There are \(10\) ways they can share a hotel room (1 way per available room). Hence, there are \(10^2-10\) ways that they can be booked into the hotel, if they don’t want to share a room.

Q-15: In the space below, explain why expression \(10^2-10\) makes sense in terms of the the code and the output of the code.

The SP can also be used in a more sophisticated way. Suppose we have two group of objects, group A and group B, but there are some objects that are in both groups. If we wanted to count the number of objects that are in either group A or group B, we can start by adding the number of objects in A to the number of objects in B. However, this will count anything that is both in A and in B twice because we count them once when we count group A and a second time when we count group B. However, we can compensate for this by subtracting the number of things that are in both A and B.

Problem: Cars, Revisited

Problem: Division

How many of the numbers from 1 to 20 are divisible by 2 or 3?

Solution:

We notice that the numbers divisible by 2 are \({2,4,6,8,10,12,14,16,18,20}\) and the numbers divisible by 3 are \({3,6,9,12,15,18}\). Thus, there are \(10\) numbers divisible by 2 and \(6\) numbers divisble by 3. However, we can’t just add \(10 + 6\) to find our final answer because some numbers are divisible by both 2 and 3. Hence, we need to subtract all numbers that are divisible by both 2 and 3. Whenever a number is divisible by 2 and 3, it is a multiple of 6. Hence, the numbers divisible by 2 and 3 are \({6,12,18}\). Thus, three numbers are divisible by 6 so there are \(10+6-3 = 13\) numbers divisible by either 2 or 3.

Coordinating the AP and the SP:

Problem: Wayside Hotel

The Wayside Hotel is an infinitely tall hotel where the number of rooms on each floor is equal to the floor number (e.g. the 5th floor has 5 rooms and the 18th floor has 18 rooms).

A Preview of Inclusion/Exclusion

In these problems, we can use addition and subtraction together. We will talk about this strategy later in a section on the Principle of Inclusion/Exclusion, which uses this coordination of addition and subtraction more formally.

You have attempted of activities on this page