Addition Rule.
If \(A\) is the union of \(k\) distinct, mutually disjoint sets, \(A_1, A_2, \ldots, A_k\text{,}\) then the number of elements in \(A\) is given by
\begin{equation*}
N(A)=N(A_1)+N(A_2)+\cdots +N(A_k).
\end{equation*}
Section 9.3 Addition Rule
In this section we look at how to count unions of disjoint sets, then look at counting sets with nontrivial intersections.
Example 9.3.1. Addition Rule: Counting Numbers Divisible by 5.
How many 3 digit numbers are divisible by 5?
We were able to count 3 digit numbers in the last section by constructing the number as a sequence of digits. We will use this example to think about how to count these as disjoint sets.
Let \(A_1\) be the set of 3 digit numbers ending in 5.
Let \(A_2\) be the set of 3 digit numbers ending in 0.
\(N(A_2)=9\cdot 10 \cdot 1\text{.}\)
Since no number ends in both 5 and 0, \(A_1\cap A_2=\emptyset\text{.}\) Thus, by the addition rule,
\begin{equation*}
N(A)=90+90=180.
\end{equation*}
Activity 9.3.1.
How many 3 digit numbers are divisible by 10?
Activity 9.3.2.
How many 3 digit numbers are divisible by 2?
It is going to take practice to be able to see when to use the multiplication rule and when to use the addition rule. If you are counting elements of different sets, use addition. If you are counting elements that are constructed in a process (can you determine step 1, step 2, etc?), then use the multiplication rule. Many problems require both rules, as we saw in Example 9.3.1.
Now we want to look at what happens if our sets are not disjoint.
If we want to count the number of elements in \(A\cup B\text{,}\) we can count those in \(A\) and those in \(B\text{.}\) But every element in the intersection has now been counted twice. so we need to subtract \(N(A\cap B)\text{.}\) This is the idea behind the Inclusion-Exclusion Rule.
Theorem 9.3.2. Inclusion-Exclusion Rule.
Let \(A, B, C\) be finite sets.
\begin{equation*}
N(A\cup B)=N(A)+N(B)-N(A\cap B).
\end{equation*}
\begin{align*}
N(A\cup B\cup C)=&N(A)+N(B)+N(C)\\
& -N(A\cap B)-N(A\cap C)-N(B\cap C)\\
& +N(A\cap B\cap C).
\end{align*}
For the case with three sets, we can see that each element in the intersection of at least two sets got counted twice, but when we subtract off all three intersections, we end up subtracting each element in more than one intersection twice, so we need to add back the elements in the intersection of all three sets. For this class, we won’t need to use Inclusion-Exclusion on more than three sets, but the rule does generalize to \(n\) sets by adding the sets, subtracting intersections of two sets, adding the intersections of three sets, subtracting the intersections of four sets, etc.
Example 9.3.3. Inclusion-Exclusion: Counting Multiples.
How many integers from 1 to 1000 are multiples of 3 or multiples of 5?
Then \(A\cap B\) is the set of multiples of 3 and 5, so multiples of 15.
We need a good way to count the multiples of 3. We know they have the form \(n=3k\text{.}\) Since \(1\leq n\leq 1000\text{,}\) we have that \(1\leq 3k \leq 1000\text{.}\) Hence, \(1/3\leq k\leq 1000/3\approx 333.3\text{.}\) Since \(k\in \mathbb{Z}\text{,}\) \(1\leq k\leq 333\text{.}\) Thus,
\begin{equation*}
A=\{3k : 1\leq k\leq 333\}.
\end{equation*}
Similarly, since \(1000/5=200\text{,}\)
\begin{equation*}
B=\{5k : 1\leq k \leq 200\}.
\end{equation*}
Since \(1000/15\approx 66.6\text{,}\)
\begin{equation*}
A\cap B=\{15k : 1\leq k \leq 66\}.
\end{equation*}
By Inclusion-Exclusion,
\begin{equation*}
N(A\cup B)=N(A)+N(B)-N(A\cap B)=333+200-66=467.
\end{equation*}
Activity 9.3.3.
We want to count the number of integers from 1-50 that are divisible by 3 or 7.
(a)
How many integers from 1-50 are divisible by 3?
(b)
How many integers from 1-50 are divisible by 7?
(c)
What is the number of integers from 1-50 divisible by 3 or 7? You can pretty easily check you answer by writing them all down. Can you use inclusion-exclusion to calculate this?
Activity 9.3.4.
We want to count the number of integers from 1-1000 that are divisible by 4, 7 or 9.
(a)
How many integers from 1-1000 are divisible by 4?
(b)
How many integers from 1-1000 are divisible by 7?
(c)
How many integers from 1-1000 are divisible by 9?
(d)
Now calculate the number of integers 1-1000 divisible by 4, 7, or 9 using inclusion-exclusion. What other sets do you need to calculate?
Activity 9.3.5.
How many ways can the word THEORY be arranged if the TH must be next to each other as TH or HT?
Example 9.3.4. Inclusion-Exclusion: Drug Study.
Suppose a study was done with three drugs, A, B and C. A total of 50 subjects used all three drugs. They reported which drugs made them feel better, with the following results:
-
21 felt better with A
-
21 felt better with B
-
31 felt better with C
-
9 felt better with A and B
-
14 felt better with A and C
-
15 felt better with B and C
-
41 felt better with at least one drug
Some of the subjects who had relief from, say, A, might also have had relief from another drug. So some of the 21 who reported feeling better with A, may also be included in the count of the 9 who felt better with A and B.
How many had relief from none of the drugs?
Answer 1.
\(50-41=9\)
How many had relief from all three of the drugs?
We need to calculate \(N(A\cap B\cap C)\text{,}\) which we can find by rewriting the Inclusion-Exclusion Rule:
\begin{align*}
N(A\cap B\cap C)=&N(A\cup B\cup C)-N(A)-N(B)-N(C)\\
& +N(A\cap B)+N(A\cap C)+N(B\cap C).
\end{align*}
Answer 2.
\(41-21-21-31+9+14+15=6\)
Reading Questions Check Your Understanding
1.
How many 3 digit numbers begin with 1 or begin with a 2?
2.
How many 3 digit numbers end with 1 or end with 2?
3.
How many 3 digit numbers begin with 1 or end with a 2?
4.
How many 3 digit numbers begin with 1 or 2 or end with 2, 3, or 4?
5.
How many integers from 1 to 2500 are multiples of 3 or multiples of 5?
6.
How many integers from 1 to 2500 are multiples of 2 or multiples of 7?
Exercises Exercises
1.
How many bit strings consist of from one through four digits? (Note, strings of different lengths are considered distinct. For example 10 and 0010 are distinct strings.)
2.
How many bit strings consist of from five through eight digits?
3.
The hexadecimal numbers are constructed using 16 digits: 0-9, A, B, C, D, E, F.
-
How many strings of hexadecimal digits consist of from one through three digits?
-
How many strings of hexadecimal digits consist of from two through five digits?
4.
Consider the integers 1-999.
-
How many integers from 1 through 999 do not have any repeated digits?
-
How many integers from 1 through 999 have at least one repeated digit?
-
What is the probability that an integer chosen at random from 1 through 999 has at least one repeated digit?
5.
Consider all five digit integers, 10,000-99,999.
-
How many five-digit integers are divisible by 5?
-
What is the probability that a five digit integer chosen at random is divisible by 5?
6.
At a certain company, passwords must be 3-5 symbols long and composed of the 26 letters, the ten digits, and the 14 symbols !, @, #, $, %, ^, &, *, (, ), \(-\text{,}\) \(+\text{,}\) {, }.
-
How many passwords are possible if repetition of symbols is allowed?
-
How many passwords contain no repeated symbols?
-
How many passwords have at least one repeated symbol?
-
What is the probability that a password chosen randomly has at least one repeated symbol?
7.
Consider the letters in the word \(QUICK\text{.}\)
-
How many ways can the letters of the word \(QUICK\) be arranged in a row?
-
How many ways can the letters of the word \(QUICK\) be arranged in a row if the \(QU\) must remain together in that order?
-
How many ways can the letters of the word \(QUICK\) be arranged in a row if the \(QU\) must remain together in either order (\(QU\) or \(UQ\))?
8.
Assume any seven digits can be used to form a telephone number.
-
How many seven-digit telephone numbers would not have any repeated digits?
-
How many seven-digit telephone numbers would have at least one repeated digit?
-
What is the probability that a randomly chosen seven-digit telephone number would have at least one repeated digit?
9.
A college conducted a survey to explore the academic interests and achievements of its students. It asked students to place checks beside the numbers of all statements that were true of them. Statement #1 was “I was on the honor roll last term.” Statement #2 was “I belong to an academic club.” Statement #3 was “I am majoring in at least two subjects.” Out of a sample of 100 students, 28 checked #1, 26 checked #2, and 14 checked #3, 18 checked both #1 and #2, 4 checked both #1 and #3, 3 checked both #2 and #3, and 2 checked all three. Note that some of the students who checked #1 (or #2 or #3) may have also checked other numbers.
-
How many of the students checked at least one of the statements?
-
How many students checked none of the statements?
-
How many students checked #1 and #2, but not #3?
-
How many students checked #2 and #3, but not #1?
-
How many students checked #2, but not the other two?
You have attempted of activities on this page.
