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 A1, A2, , Ak. Then

|A| = |A1| + |A2| + + |Ak|.

Proof: Let P(k) be the property "If a finite set A equals the union of k distinct mutually disjoint subsets A1, A2, , Ak. Then

|A| = |A1| + |A2| + + |Ak|."

The property is true for n = 1: Suppose a finite set A equals the union of one subset A1, then A = A1, so |A| = |A1|.

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 A1, A2, , Ai + 1. Then A = A1 A2 Ai + 1 and Ai Aj = for all integers i and j with i j. Let B be the set B = A1 A2 Ai. Then A = B Ai + 1 and B Ai + 1 = . Now A is the union of two mutually disjoint sets B and Ai + 1. Since B and Ai + 1 have no elements in common, the total number of elements in B Ai + 1 can be obtained by first counting the elements in B, next counting the elements in Ai + 1, and then adding the two numbers together. It follows that |B Ai + 1| = |B| + |Ai + 1| which equals
|A1| + |A2| + + |Ai| + |Ai + 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 = 262 because forming such a word can be thought of as a two step process, 26 choices each.

# of length 3 = 263 a three step process with 26 choices for each step.

Hence, by the addition rule there are 26 + 262 + 263 = 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 (A0) and those ending with 5 (A5). 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 A0 is then 9(10) = 90. Similarly the cardinality of A5 is 90. By the addition rule, the number of three-digit integers divisible by 5 is

|A0| + |A5| = 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).

  1. How many PINs contain repeated symbols?
  2. If all PINs are equally likely, what is the probability that a randomly chosen PIN contains a repeated symbol?

Solution

  1. There are S = 364 = 1,679,616 PINs with repetition allowed and A = P(36, 4) = 36! / 32! = 1,413,720 PINs when repetition is not allowed. Thus by the difference rule, there are
  2. S A = E,

    1,679,616 1,413,720 = 265,896

    PINs that contain at least one repeated symbol.

  3. P(E) = 265,896 / 1,679,616 @ .1583

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

  1. Let A = {1, 2, , 1000}. How many integers in A are multiples of 4 or multiples of 6?
  2. How many integers in A are neither multiples of 4 nor multiples of 6?

Solution

  1. Using sublists: A4 = 250 -1 +1 = 250. A6 = 166 - 1 + 1 = 166, A4 A6 = A12  =  83 - 1 + 1 = 83.
    By the inclusion/exclusion rule: |A4 A6| = |A4| + |A6| - |A4 A6|. So the number of integers from 1 through 1000 that are multiples of 4 or multiples of 6 is:
    250 + 166 - 83 = 333.
  2. This question is asking for |A4c A6c|, which by DeMorgan's law is equivalent to
    |(A4 A6)c|. Now |(A4 A6)c| = |A| - |A4 A6| = 1000 - 333 = 667.

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.

  1. How many students did not take any of the three courses?

  2. How many students took all three course?

  3. How many students took Precalculus and Calculus but not Java?

  4. How many students took Precalculus but neither Calculus nor Java?
Solution
  1. 50 - 47 = 3
  2. |P C J| = |P| + |C| +  |J| - |P C| - |P J| - | C J| + |P C J|
                  47 = 30 + 26 + 18 -      9      -    16    -       8     + |P C J|
    |P C J| = 6
  3. The number of students who took both Precalculus and Calculus but not Java = 9 - 6 = 3.
  4. The number of students who took Precalculus but neither Calculus nor Java = |P| - |P C| - |P J| + |P C J|
      = 30 - 9 - 16 + 6 = 11.