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.

Suppose a finite set A equals the union of k distinct mutually disjoint subsets A₁, A₂, …, A_k. Then

|A| = |A₁| + |A₂| + …+ |A_k|.

Proof: Let P(k) be the property "If a finite set A equals the union of k distinct mutually disjoint subsets A₁, A₂, …, A_k. Then

|A| = |A₁| + |A₂| + …+ |A_k|."

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

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₁, A₂, …, A_i + 1. Then A = A₁ È A₂ È … È A_i + 1 and A_i Ç A_j = Æ for all integers i and j with i ¹ j. Let B be the set B = A₁ È A₂ È … È 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₁| + |A₂| + …+ |A_i| + |A_i + 1| by inductive hypothesis. Hence P(i + 1) is true. QED

Example 6.3.1 Counting Code Words with Three or Fewer Letters

A computer access code word consists of from one to three letters chosen from the 26 in the alphabet with repetitions allowed. How many different code words are possible?

Solution The set of code words 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² because forming such a word can be thought of as a two step process, 26 choices each.

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

Hence, by the addition rule there are 26 + 26² + 26³ = 18,278 distinct computer access codes of 3 or less letters.

Example 6.3.2 Counting the Number of Three Digit Integers Divisible by 5 (see Example 6.1.3)

We partition the solution set into two distinct sets: those ending with 0 (A₀) and those ending with 5 (A₅). 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₀ is then 9(10) = 90. Similarly the cardinality of A₅ is 90. By the addition rule, the number of three-digit integers divisible by 5 is

|A₀| + |A₅| = 90 +90 = 180.

Theorem 6.3.2 The Difference Rule

If A is a finite set and B is a subset of A, then

|A – B| = |A| - |B|.

Example 6.3.3 Counting PINs with Repeated Letters (see Example 6.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 = 36⁴ = 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

S – A = E,

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

PINs that contain at least one repeated symbol.

2. 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 6.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.

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?

1. Using sublists: A₄ = 250 -1 +1 = 250. A₆ = 166 - 1 + 1 = 166, A₄ Ç A₆ = A₂₄ = 41.
   By the inclusion/exclusion rule: |A₄ È A₆| = |A₄| + |A₆| - |A₄ Ç A₆|. So the number of integers from 1 through 1000 that are multiples of 4 or multiples of 6 is:
   250 + 166 - 41 = 375.
2. This question is asking for |A₄^c Ç A₆^c|, which by DeMorgan's law is equivalent to
   |(A₄ È A₆)^c|. Now |(A₄ È A₆)^c| = |A| - |A₄ È A₆| = 1000 - 375 = 625.

Read Example 6.3.6.