8.2: Addition and Multiplication Principles

Recall that the cardinality of a finite set \(A\), denoted \(|A|\), is the number of elements it contains.

Example \(\PageIndex{1}\label{eg:addmult-01}\)

If \(A=\{-1,0,2\}\), then \(|A|=3\). Also, \[\begin{array}{rcl} |\{2\}| &=& 1, \\ |\{2,5,-1,-3\}| &=& 4, \\ |\{x\in\mathbb{R}\mid x^2=1\}| &=& 2. \end{array} \nonumber\] Notice that \(|\emptyset|=0\), because an empty set does not contain any element.

It becomes more interesting when we consider the cardinality of a union or an intersection of two or more sets.

Example \(\PageIndex{2}\label{eg:addmult-02}\)

Determine \(|A \cup B|\) and \(|A \cap B|\) if \(A=\{2,5\}\) and \(B=\{7,9,10\}\).

Solution

Since \(A\cup B = \{2,5,7,9,10\}\), and \(A\cap B = \emptyset\), it is clear that \(|A\cup B|=5\), and \(|A\cap B|=0\).

Example \(\PageIndex{3}\label{eg:addmult-03}\)

Determine \(|A \cup B|\) and \(|A \cap B|\) if \(A=\{2,5\}\) and \(B=\{5,9,10\}\).

Solution

Since \(A\cup B = \{2,5,9,10\}\), and \(A\cap B = \{5\}\), it is clear that \(|A\cup B|=4\), and \(|A\cap B|=1\).

hands-on exercise \(\PageIndex{1}\label{he:addmult-01}\)

Let \(A=\{n\in\mathbb{Z} \mid -5\leq n\leq3\}\), and \(B=\{n\in\mathbb{Z} \mid -3\leq n\leq5\}\). Evaluate \(|A\cap B|\) and \(|A\cup B|\).

The difference between the last two examples is whether the two sets \(A\) and \(B\) have a nonempty intersection. Two sets \(A\) and \(B\) are disjoint if \(A \cap B = \emptyset\). A collection of sets \(A_1, A_2, \ldots, A_n\) is said to be pairwise disjoint if \(A_i \cap A_j = \emptyset\) whenever \(i\neq j\). When \(A_1, A_2, \ldots, A_n\) are pairwise disjoint, their union is called a disjoint union.

Example \(\PageIndex{4}\label{eg:addmult-04}\)

Let \(A=\{1,0,-1\}\), \(B=\{-2,0,2\}\), \(C=\{-2,2\}\) and \(D=\{3,4,5\}\). Then \(A\), \(C\), and \(D\) are pairwise disjoint, so are \(B\) and \(D\), but \(A\), \(B\), and \(C\) are not.

Theorem \(\PageIndex{1}\): Addition Principle

If the finite sets \(A_1, A_2, \dots, A_n\) are pairwise disjoint, then \[|A_1 \cup A_2 \cup \cdots \cup A_n| = |A_1| + |A_2| + \cdots + |A_n|. \nonumber\]

Use the addition principle if we can break down the problems into cases, and count how many items or choices we have in each case. The total number is the sum of these individual counts. The idea is, instead of counting a large set, we divide it up into several smaller subsets, and count the size of each of them. The cardinality of the original set is the sum of the cardinalities of the smaller subsets. This divide-and-conquer approach works perfectly only when the sets are pairwise disjoint.

Example \(\PageIndex{5}\label{eg:addmult-05}\)

To find the number of students present at a lecture, the teacher counts how many students there are in each row, then adds up the numbers to obtain the total count.

When the sets are not disjoint, the addition principle does not give us the right answer because the elements belonging to the intersection are counted more than once. We have to compensate the over-counting by subtracting the number of times these elements are over-counted. The simplest case covers two sets.

Theorem \(\PageIndex{2}\label{pie}\): Principle of Inclusion-Exclusion (PIE)

For any finite sets \(A\) and \(B\), we have \[|A\cup B| = |A|+|B|-|A\cap B|. \nonumber\]

Proof

Observe that \(A\cup B\) is the disjoint union of three sets \[A \cup B = (A-B) \cup (A \cap B) \cup (B-A). \nonumber\] It is clear that \(|A-B| = |A|-|A\cap B|\), and \(|B-A|=|B|-|A\cap B|\). Therefore, \[\begin{array}{rcl} |A \cup B| &=& |A-B| + |A\cap B| + |B-A| \\ &=& (|A|-|A \cap B|) + |A\cap B| + (|B|-|A \cap B|) \\ &=& |A| + |B| - |A \cap B|, \end{array} \nonumber\] which is what we have to prove.

The principle of inclusion-exclusion also works if \(A\) and \(B\) are disjoint, because in such an event, \(|A\cap B|=0\), reducing PIE to the addition principle.

Example \(\PageIndex{6}\label{eg:pie}\)

Assume the current enrollment at a college is 4689, with 60 students taking MATH 210, 42 taking CSIT 260, and 24 taking both. Together, how many different students are taking these two courses? In other words, determine the number of students who are taking either MATH 210 or CSIT 260.

Solution

Let \(A\) be the set of students taking MATH 210, and \(B\) the set of students taking CSIT 260, Then, \(|A|=60\), \(|B|=42\), and \(|A\cap B|=24\). We want to find \(|A\cup B|\). According to PIE, \[|A\cup B| = |A| + |B| - |A\cap B| = 60+42-24 = 78. \nonumber\] Therefore, 78 students are taking either MATH 210 or CSIT 260.

Example \(\PageIndex{7}\label{eg:addmult-07}\)

Among 4689 students, 2112 of them have earned at least 60 credit hours and 2678 of them have earned at most 60 credit hours. How many students are there who have accumulated exactly 60 hours?

Solution

Let \(A\) be the set of students who have earned at least 60 credit hours, and \(B\) be the set of students who have earned at most 60 credit hours. We want to find \(|A\cap B|\). According to PIE, \[4689 = |A\cup B| = |A|+|B|-|A\cap B| = 2112+2678-|A\cap B|. \nonumber\] Hence, \[|A\cap B| = (2112+2678)-4689 = 101. \nonumber\] There are 101 students who have accumulated exactly 60 credit hours.

hands-on exercise \(\PageIndex{2}\label{he:addmult-02}\)

The attendance at two consecutive college football games was 72397 and 69211 respectively. If 45713 people attended both games, how many different people have watched the games?

hands-on exercise \(\PageIndex{3}\label{he:addmult-03}\)

The attendance at two consecutive college football games was 72397 and 69211 respectively. If 93478 different individuals attended these two games, how many have gone to both?

Sometimes, it is easy to work with the complement of a set.

Lemma \(\PageIndex{3}\)

For any finite set \(S\), we have \[|\overline{S}| = |{\cal U}| - |S|, \nonumber\] where \({\cal U}\) is the universal set containing \(S\).

Example \(\PageIndex{8}\label{eg:addmult-08}\)

In Example 8.2.6, since there are 78 students taking either MATH 210 or CSIT 260, the number of students taking neither is \(4689-78=4611\).

The principle of inclusion-exclusion can be extended to any number of sets. The situation is more complicated, because some elements may be double-counted, some triple-counted, etc. To give you a taste of the general result, here is the principle of inclusion-exclusion for three sets.

Theorem \(\PageIndex{1}\)

For any three finite sets \(A\), \(B\) and \(C\), \[|A \cup B \cup B| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|. \nonumber\]

Proof

The union \(A \cup B \cup C\) is the disjoint union of seven subsets: \[\displaylines{ A-(B\cup C), \quad B-(C\cup A), \quad C-(A\cup B), \quad (A\cap B)-(A\cap B\cap C), \cr (B\cap C)-(A\cap B\cap C), \quad (C\cap A)-(A\cap B\cap C), \quad \mbox{and}\quad A\cap B\cap C. \cr} \nonumber\] We can apply an argument similar to the one used in the union of two sets to complete the proof. We leave the details as an exercise.

hands-on exercise \(\PageIndex{4}\label{he:addmult-04}\)

A group of students claims that each of them had seen at least one part of the Back to the Future trilogy. A quick show of hands reveals that

• 47 had watched Part I;
• 43 had watched Part II;
• 32 had watched Part III;
• 33 had watched both Parts I and II;
• 27 had watched both Parts I and III;
• 25 had watched both Parts II and III;
• 22 had watched all three parts.

How many students are there in the group?

Another useful counting technique is the multiplication principle.

Theorem \(\PageIndex{5}\) (Multiplication Principle)

For any finite sets \(A\) and \(B\), we have \[|A\times B| = |A|\cdot|B|. \nonumber\]

Clearly, this can be extended to an \(n\)-fold Cartesian product.

Theorem \(\PageIndex{6}\)

For any finite sets \(A_1, A_2, \ldots, A_n\), we have \[|A_1 \times A_2 \times \cdots \times A_n| = |A_1| \cdot |A_2| \cdot \cdots \cdot |A_n|. \nonumber\]

In many applications, it may be helpful to use an equivalent form.

Theorem \(\PageIndex{7}\) (Multiplication Principle: Alternate Form)

If a task consists of \(k\) steps, and if there are \(n_i\) ways to finish step \(i\), then the entire job can be completed in \(n_1 n_2 \ldots n_k\) different ways.

Now that we have two counting techniques, the addition principle and the multiplication principle, which one should we use? The major difference between them is whether

• the jobs can be divided into cases, groups, or categories; or
• each job can be broken up into steps.

In practice, it helps to draw a picture of the configurations that we are counting.

Example \(\PageIndex{9}\label{eg:addmult-09}\)

How many different license plates are there if a standard license plate consists of three letters followed by three digits?

Solution

We need to decide how many choices we have in each position. Draw a picture to show the configuration. Draw six lines to represent the six positions. Above each line, describe briefly the possible candidates for that position, and under each line, write the the number of choices.

\[ \begin{array}{ccccccc} \text{choices:} & \text{any letter} & \text{any letter} & \text{any letter} & \text{any digit} & \text{any digit} & \text{any digit} \\ & - & - & - & - & - & - \\ \text{# of choices:} & 26 & 26 & 26 & 10 & 10 & 10 \end{array} \nonumber\]

This left-to-right configuration suggests that the multiplication principle should be used. The answer is \(26\cdot 26\cdot 26\cdot 10\cdot 10\cdot 10 = 260^3\).

As you become more experienced, you can argue directly, as follows. There are 26 choices for each of the three letters, and 10 choices for each digit. So there are \(26\cdot 26\cdot 26\cdot 10\cdot 10\cdot 10 = 260^3\) different license plates.

Example \(\PageIndex{10}\label{eg:addmult-10}\)

Find the number of positive integers not exceeding 999 that end with 7.

Solution 1

The integers can have one, two, or three digits, so we have to analyze three cases.

• Case 1. There is only one integer with one digit, namely, the integer 7.
• Case 2. If there are two digits, the first could be any digit between 1 and 9, and the last digit must be 7. \[ \begin{array}{ccc} \text{choices:} & 1-9 & 7 \\ & - & - \\ \text{# of choices:} & 9 & 1 \end{array} \nonumber\] This gives us nine choices.
• Case 3. If there are three digits, the first digit could be any digit between 1 and 9, the second any digit between 0 and 9, and the last digit must be 7. \[ \begin{array}{cccc} \text{choices:} & 1-9 & \text{any digit} & 7 \\ & - & - & - \\ \text{# of choices:} & 9 & 10 & 1 \end{array} \nonumber\] Hence, there are 90 integers in this case.

Combining the three cases, we have a total of \(1+9+90=100\) integers that meet the requirements.

Solution 2

The integers could be written as three-digit integers if we allow 0 as the leading digits. For instance, 7 can be written as \(007\), and \(34\) as \(034\). Under this agreement, we have to fill three positions where the last one is always occupied by the digit 7. The first two digits are \(0, 1, 2, \ldots, 8\), or 9, so there are 10 choices for each position.

\[ \begin{array}{cccc} \text{choices:} & \text{any digit} & \text{any digit} & 7 \\ & - & - & - \\ \text{# of choices:} & 10 & 10 & 1 \end{array} \nonumber\]

Together, there are \(10\cdot10=100\) such integers.

hands-on exercise \(\PageIndex{5}\label{he:addmult-05}\)

How many natural numbers less than 1000000 are there that end with the digit 3?

hands-on exercise \(\PageIndex{6}\label{he:addmult-06}\)

How many natural numbers less than 10000 are there that end with the digit 0?

Example \(\PageIndex{11}\label{eg:addmult-11}\)

Determine the number of four-digit positive integers without repeated digits.

Solution

We want to determine how many choices there are for each place value. The first digit has nine choices because it cannot be 0. Once the first digit is chosen, there are nine choices left for the second digit; and then eight choices for the next digit, and seven choices for the last digit. Together, we have \(9\cdot 9\cdot 8\cdot 7 =4536\) four-digit positive integers that do not contain any repeated digits. Question: Can we start counting from the last digit?

hands-on exercise \(\PageIndex{7}\label{he:addmult-07}\)

How many six-digit natural numbers are there that do not have any repeated digit?

Example \(\PageIndex{12}\label{eg:addmult-12}\)

Determine \(|\wp(S)|\), where \(S\) is an \(n\)-element set.

Solution

We want to determine the number of ways to form a subset. Let the \(n\) elements be \(s_1, s_2, \ldots, s_n\). To form a subset, we go through each element \(s_i\) and decide whether it should be included in the subset, thus there are two choices for each element.

\[ \begin{array}{ccccc} \text{element:} & s_1 & s_2 & & s_n \\ \text{choices} & \text{Y/N} & \text{Y/N} & \cdots & \text{Y/N} \\ & - & - & & - \\ \text{# of choices:} & 2 & 2 & & 2 \end{array} \nonumber\]

We have \(\underbrace{2\cdot2\cdot\,\cdots\, \cdot2}_{n \text{ factors}} = 2^n\) ways to form the subsets. Thus, \(|\wp(S)|=2^n\).

Example \(\PageIndex{13}\label{eg:addmult-13}\)

How many two-digit positive integers do not have consecutive 5s?

Solution 1

There are three disjoint cases:

1. both digits are not 5,
2. only the first digit is 5, and
3. only the last digit is 5.

There are \(8\cdot9+9+8=89\) integers that meet the requirement.

Solution 2

An easier solution is to consider the complement of the problem. There is only one integer with consecutive 5s, namely, the integer 55. There are 90 two-digit integers, hence \(90-1=89\) of them do not have consecutive 5s.

hands-on exercise \(\PageIndex{8}\label{he:addmult-08}\)

How many three-digit natural numbers are there that do not have consecutive 4s?

Example \(\PageIndex{14}\label{eg:addmult-14}\)

In how many ways can we draw a sequence of three cards from a standard deck of 52 cards?

Solution

This is a trick question! The answer depends on whether we can return a drawn card to the deck. With replacement, the answer is \(52^3\); without replacement, it is \(52 \cdot 51 \cdot 50\).

Example \(\PageIndex{15}\label{eg:addmult-15}\)

A standard New York State license plate consists of three letters followed by four digits. Determine the number of standard New York State license plates with K as the first letter or 8 as the first digit.

Solution

The keyword “or” suggests that we are looking at a union, hence, we have to apply PIE. We need to analyze three possibilities:

• There are \(26^2\cdot10^4\) license plates with K as the first letter.
• There are \(26^3\cdot10^3\) license plates with 8 as the first digit.
• There are \(26^2\cdot10^3\) license plates with K as the first letter and 8 as the first digit.

The answer is \(26^2\cdot10^4+26^3\cdot10^3-26^2\cdot10^3\).

hands-on exercise \(\PageIndex{9}\label{he:addmult-09}\)

To access personal account information, a customer could log in to the bank’s web site with a PIN consisting of two letters followed by

1. exactly four digits,
2. at most six digits,
3. at least two but at most 6 digits.

How many different PINs are there in each case?

Summary and Review

• Use the addition principle if the problem can be divided into cases. Make sure the cases do not overlap.
• If the cases overlap, the number of objects belonging to the overlapping cases must be subtracted from the total to obtain the correct count.
• In particular, the principle of inclusion-exclusion states that \(|A\cup B|=|A|+|B|-|A\cap B|\).
• Use the multiplication principle if the problem can be solved in several steps.
• How can we get started? Imagine you want to list all the possibilities, what is a systematic way of doing so? Follow the steps, and count how many objects you would end up with.
• It may be helpful to use a schematic diagram. Draw one line for each step. Above the lines, write the choices. Below the lines, write the number of choices. Apply the multiplication principle to finish the problem.
• If there are other cases involved, repeat, and add the results from all the possible cases.

exercise \(\PageIndex{1}\label{ex:addmult-01}\)

A professor surveyed the 98 students in her class to count how many of them had watched at least one of the three films in The Lord of the Rings trilogy. This is what she found:

• 74 had watched Part I;
• 57 had watched Part II;
• 66 had watched Part III;
• 52 had watched both Parts I and II;
• 51 had watched both Parts I and III;
• 45 had watched both Parts II and III;
• 43 had watched all three parts.

How many students did not watch any one of these three movies?

exercise \(\PageIndex{2}\label{ex:addmult-02}\)

Forty-six students in a film class told the professor that they had watched at least one of the three films in The Godfather trilogy. Further inquiry led to the following data:

• 41 had watched Part I;
• 37 had watched Part II;
• 33 had watched Part III;
• 33 had watched both Parts I and II;
• 30 had watched both Parts I and III;
• 29 had watched both Parts II and III.

1. How many students had watched all three films?
2. How many students had watched only Part I?
3. How many students had watched only Part II?
4. How many students had watched only Part III?

exercise \(\PageIndex{3}\label{ex:addmult-03}\)

Joe has 10 dress shirts and seven bow ties. In how many ways can he match the shirts with bow ties?

exercise \(\PageIndex{4}\label{ex:addmult-04}\)

A social security number is a sequence of nine digits. Determine the number of social security numbers that satisfy the following conditions:

1. There are no restrictions.
2. The digit 8 is never used.
3. The sequence does not begin or end with 8.
4. No digit is used more than once.

exercise \(\PageIndex{5}\label{ex:addmult-05}\)

A professor has seven books on discrete mathematics, five on number theory, and four on abstract algebra. In how many ways can a student borrow two books not both on the same subject?

Hint

Which two subjects would the student choose?

exercise \(\PageIndex{6}\label{ex:addmult-06}\)

How many different collections of cans can be formed from five identical Cola-Cola cans, four identical Seven-Up cans, and seven identical Mountain Dew cans?

Hint

How many cans of Cola-Cola, Seven-Up, and Mountain Dew would you pick?

exercise \(\PageIndex{7}\label{ex:addmult-07}\)

How many five-letter words (technically, we should call them strings, because we do not care if they make sense) can be formed using the letters A, B, C, and D, with repetitions allowed. How many of them do not contain the substring BAD?

Hint

For the second question, consider using a complement.

exercise \(\PageIndex{8}\label{ex:addmult-08}\)

How many different five-digit integers can be formed using the digits 1, 3, 3, 3, 5?

Hint

The three digits 3 are identical, so we cannot tell the difference between them. Consequently, what really matters is where we put the digits 1 and 5. Once we place the digits 1 and 5, the remaining three positions must be occupied by the digits 3.

exercise \(\PageIndex{9}\label{ex:addmult-09}\)

Four cards are chosen at random from a standard deck of 52 playing cards, with replacement allowed. This means after choosing a card, the card is return to the deck, and the deck is reshuffled before another card is selected at random. Determine the number of such four-card sequences if

1. There are no restrictions.
2. None of the cards can be spades.
3. All four cards are from the same suit.
4. The first card is an ace and the second card is not a king.
5. At least one of the four cards is an ace.

exercise \(\PageIndex{10}\label{ex:addmult-10}\)

Three different mathematics final examinations and two different computer science final examinations are to be scheduled during a five-day period. Determine the number of ways to schedule these final examinations from 11 AM to 1 PM if

1. There are no restrictions.
2. No two examinations can be scheduled on the same day.
3. No two examinations from the same department can be scheduled on the same day.
4. Each mathematics examination must be the only examination for the day on which it is scheduled.

exercise \(\PageIndex{11}\label{ex:addmult-11}\)

Determine the number of four-digit positive integers that satisfy the following conditions:

1. There are no restrictions.
2. No integer contains the digit 8.
3. Every integer contains the digit 8 at least once.
4. Every integer is a palindrome (A positive integer is a palindrome if it remains the same when read backward, for example, 3773 and 47874).

exercise \(\PageIndex{12}\label{ex:addmult-12}\)

A box contains 12 distinct colored balls (for instance, we could label them as 1, 2, …, 12 to distinguish them). Three of them are red, four are yellow, and five are green. Three balls are selected at random from the box, with replacement. Determine the number of sequences that satisfy the following conditions:

1. There are no restrictions.
2. The first ball is red, the second is yellow, and the third is green.
3. The first ball is red, and the second and third balls are green.
4. Exactly two balls are yellow.
5. All three balls are green.
6. All three balls are the same color.
7. At least one of the three balls is red.

exercise \(\PageIndex{13}\label{ex:addmult-13}\)

Let \(A=\{a,b,c,d,e,f\}\) and \(B=\{1,2,3,4,5,6,7,8\}\). Determine the number of functions \(f: A \to B\) that satisfy the following conditions:

1. There are no restrictions.
2. \(f\) is one-to-one.
3. \(f\) is onto.
4. \(f(x)\) is odd for at least one \(x\) in \(A\).
5. \(f(a)=3\) or \(f(b)\) is odd.
6. \(f^{-1}(4)=\{a\}\).

exercise \(\PageIndex{14}\label{ex:addmult-14}\)

How many onto functions are there from an \(n\)-element set \(A\) to \(\{a,b\}\)?