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.
- 3
- Incorrect
- 7
- Correct
- 4
- Incorrect
Q-1: You own three red cars, four blue cars, and no cars of other colors. How many cars do you own?
- Yes
- Correct. Some of the cars may be in multiple categories.
- No
- Incorrect. What if a car can fit into multiple categories?
Q-2: Five of your cars are Toyotas, and three of your cars are red, and seven of your cars are vans. Can you own fewer than 15 cars?
- No
- Incorrect. What if you have a blue car without ABS?
- Yes
- Correct.
Q-3: Three of your cars are red, and two of your cars have anti-lock braking systems (ABS). Can you own more than five cars?
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.
- Electric, Diesel
- Incorrect, there are cars that are neither electric nor diesel.
- Red, Toyota, neither Red nor Toyota
- Incorrect, red Toyotas would fit into multiple categories.
- Toyota, Hyundai, neither Toyota nor Hyundai
- Correct!
Q-4: Thinking about buying a car, you try to determine which type of car you want. Which of the below ways to categorize cars would account for all cars, so that each car fits into exactly one 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 one letter and one number, where either the number comes first (such as 9I) or the letter comes first (such as I9). 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 \times 26\) ways to create a username. If the letters come first, then there are \(26 \times 10^2\) ways to create a username. Hence, there are \(10\times26 + 26\times 10\) total ways to create a username.
The code below is meant to reflect this process and this case breakdown. In particular, only the first case is shown, where the first column corresponds to the letter and the second the number. What would the second case look like?
Look at the code below. Before you run it, answer the following multiple choice question.
- 260
- Correct.
- 520
- Incorrect.
Q-5: How many letter-number pairs do you expect to see when you run it?
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?
- 7*5 + 7*3 + 5*3
- Correct
- (7*5)^2 + (7*3)^2 + (5*3)^2
- Incorrect. Your solution accounts for multiple orderings of the two books.
- 7*5*3
- Incorrect. Your solution counts the way to order three books.
Q-6: Which of the following expressions counts the number of ways to bring two books from different genres with you?
(Aside, this is where the parsons problem was, and can we do a similar but horizontal style here?)
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.
- 60
- Incorrect, this is the number of non-face pairs.
- 18
- Correct.
- There is not enough information given in the problem
- Incorrect, if a pair is not non-face, must they be a face pair?
Q-7: There are 78 possible pairs in a standard deck of cards (e.g. two 5s). Of these, 60 are non-face pairs. How many face pairs are there?
- Yes
- Correct
- No
- Incorrect, what if two of your Toyotas are red?
Q-8: Suppose you have seven cars. Three of your cars are Toyotas, and two of your cars are red. Is it possible that you own three blue Hyundais?
- 62
- Incorrect
- 61
- Incorrect
- 60
- Correct
- 59
- Incorrect
Q-9: How many xs are there in the following table?
x |
x |
x |
x |
x |
x |
x |
x |
x |
OO |
x |
x |
x |
x |
x |
x |
x |
x |
x |
x |
x |
OO |
x |
x |
OO |
x |
x |
x |
x |
x |
x |
x |
x |
x |
x |
x |
x |
x |
x |
x |
x |
x |
x |
x |
x |
x |
OO |
x |
x |
x |
x |
x |
x |
x |
x |
x |
x |
x |
x |
x |
x |
x |
x |
x |
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.
Q-10: Does the above code list and count all of the ways Steve and Royce can book rooms if they do not share a room?
- Yes
- Correct.
- No
- Incorrect.
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?
- Doubles, such as 11, 22, 33, etc. are missing. A double would mean that Royce is staying in two rooms.
- Correct.
- Doubles, such as 11, 22, 33, etc. are missing. A double would mean that both Royce and Steve are in the same room.
- Incorrect.
- Numbers like 01, 02, 03, etc. are missing. Such numbers would mean that no one is staying at the hotel.
- Incorrect.
Q-11: Which numbers are missing from the list of all possible combinations, and what do they correspond to?
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-12: 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¶
Q-13: Suppose you own seven Hondas and five red cars. If two of your Hondas are red, how many cars do you own that are either Hondas or are red?
- 12.
- Incorrect.
- 35.
- Incorrect.
- 10.
- Correct.
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).
Q-14: How many rooms are on or are below the 5th floor?
Q-15: There are \(\frac{n(n+1)}{2}\) rooms on or below the nth floor (this is a fact, you do not need to verify it). How many rooms are between the 7th and 12th floors, including the rooms on the 7th and 12th floors?
Q-16: How many rooms are there on or below floor 20 whose floor numbers are divisible by either 2 or 3? Feel free to use the cell below to write a computer program that answers the question.
Q-18: The number of rooms on the even-numbered floors between floors 1 and \(2m\), inclusive, is \(m(m+1)\). The number of rooms that are on the odd-numbered floors between floors 1 and 20, including those on floor 1, is . Feel free to use the space below to write code to answer the question.
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.