Counting Elements of Disjoint Sets: The Addition Rule
The basic rule underlying the calculation of the number of elements in a union, difference or intersection is the addition rule. This rule states that the number of elements in a union of mutually disjoint finite sets equals the sum of the number of each of the component sets.
Theorem 9.3.1 The Addition Rule
Suppose a finite set A equals the union of k distinct mutually disjoint subsets A_{1}, A_{2}, …, A_{k}. Then
|A| = |A_{1}| + |A_{2}| + …+ |A_{k}|.
Proof: Let P(k) be the property "If a finite set A equals the union of k distinct mutually disjoint subsets A_{1}, A_{2}, …, A_{k}. Then
|A| = |A_{1}| + |A_{2}| + …+ |A_{k}|."
The property is true for n = 1: Suppose a finite set A equals the union of one subset A_{1}, then A = A_{1}, so |A| = |A_{1}|.
If the property is true for n = i then it is true for n
= i + 1: Let i be an integer with i ³ 1 and suppose the property is true for n
= i. [This is the inductive hypothesis.] Let A be a
finite set that equals the union of i + 1 distinct mutually
disjoint subsets A_{1}, A_{2}, …, A_{i
}_{+ 1}. Then A = A_{1} È A_{2} È
… È A_{i }_{+ 1}
and A_{i} Ç A_{j}
= Æ for all integers i and j
with i ¹ j. Let B
be the set B = A_{1} È A_{2}
È … È A_{i}.
Then A = B È A_{i}_{
+ 1} and B Ç A_{i }_{+
1} = Æ . Now A is the union of
two mutually disjoint sets B and A_{i} _{+ }_{1}.
Since B and A_{i} _{+ }_{1}
have no elements in common, the total number of elements in B È A_{i}_{ + 1} can be
obtained by first counting the elements in B, next counting the
elements in A_{i}_{ + 1}, and then adding the
two numbers together. It follows that |B È
A_{i}_{ + 1}| = |B| + |A_{i}_{
+ 1}| which equals
|A_{1}| + |A_{2}| + …+ |A_{i}|
+ |A_{i}_{ + 1}| by inductive hypothesis. Hence P(i
+ 1) is true. QED
Example 9.3.1 Counting Passwords with Three or Fewer Letters
A computer access password consists of from one to three letters chosen from the 26 in the alphabet with repetitions allowed. How many different passwords are possible?
Solution The set of passwords can be partitioned into subsets consisting of those of length 1, those of length 2, and those of length 3:
# of length 1 = 26
# of length 2 = 26^{2} because forming such a word can be thought of as a two step process, 26 choices each.
# of length 3 = 26^{3} a three step process with 26 choices for each step.
Hence, by the addition rule there are 26 + 26^{2} + 26^{3} = 18,278 distinct computer access codes of 3 or less letters.
Example 9.3.2 Counting the Number of Three Digit Integers Divisible by 5 (see Example 9.1.4)
We partition the solution set into two distinct sets: those ending with 0 (A_{0}) and those ending with 5 (A_{5}). The three digit integers ending with 0 number the same as the possible choices for the left-most and middle digits (because the right-most digit must be a 0). There are nine choices for the left-most digit (1-9) and ten choices for the middle digit (0-9). The cardinality of A_{0} is then 9(10) = 90. Similarly the cardinality of A_{5} is 90. By the addition rule, the number of three-digit integers divisible by 5 is
|A_{0}| + |A_{5}| = 90 +90 = 180.
Theorem 9.3.2 The Difference Rule
If A is a finite set and B is a subset of A, then
|A – B| = |A| - |B|.
Example 9.3.3 Counting PINs with Repeated Letters (see Example 9.2.4)
A typical PIN has 4 symbols each of which consists of an alphabet letter (26) or a digit (0-9).
Solution
S – A = E,
1,679,616 – 1,413,720 = 265,896
PINs that contain at least one repeated symbol.
An alternative solution for b) is
P(S – A) = | S – A| / |S| = ( | S| – |A| ) / |S| = | S| / |S| – |A| / |S|
1 – P(A) @ 1 – .8417 @ .1583.
Theorem 9.3.3 The Inclusion/Exclusion Rule for Two or Three Sets
If A, B, and C are any finite sets, then
|A È B| = |A| + |B| – |A Ç B|
and
|A È B È C| = |A| + |B| +|C| – |A Ç B| – |A Ç C| – |B Ç C| + |A Ç B Ç C|.
Analogous formulae hold for unions of any finite number of sets.
Example Counting Elements of a General Union
Solution
Example 9.3.7 Counting the Number of Elements in an Intersection
A professor in a discrete mathematics class passes out a form asking
students to check all the mathematics and computer science courses they
have recently take. The finding is that out of a total of 50 students
in the class,
30 took Precalculaus; 16 took both Precalculus and
Java; 18 took Calculus;
8 took both Calculus and Java;
26 took Java;
9 took both Precalculus and Calculus; 47 took at least one of the three courses.