- The Addition Rule for Disjoint Sets.

- If a finite set S equals the union of n distinct and mutually disjoint subsets,
then the number of elements in A equals the sum of the numbers of elements in the subsets.

In other words if finite set S equals the union of n distinct, mutually disjoint subsets A_{1}, A_{2}, ..., A_{n}, then

n

N(S) = ∑ N(A_{k})

k=1

- Examples:

- A password for your computer.
Suppose you decide to create a password made up of capital letters
of the alphabet, and ≤ 3 characters in length. How many ways
can you choose such a password?

Solution:

Let S = {passwords from capital letters | length ≤ 3}

Let A_{1}= {password from capital letters | length = 1}

Let A_{2}= {password from capital letters | length = 2}

Let A_{3}= {password from capital letters | length = 3}

Since S = A_{1}A_{2}A_{3}, and the subsets are distinct, and the subsets are mutually disjoint, we can apply the Addition Rule.

What is N(A_{1})?

What is N(A_{2})?

What is N(A_{3})?

What is N(S)? Do the math. Did you get 18,278?

- A password for an online shopping account. The rules say that
your password must be at least 5 characters long, no more than 8
characters long, and made up of capital letters and digits.

Solution:

Let S = {passwords from the 36 letters & digits | 5 ≤ length ≤ 8}

Now form four distinct, mutually disjoint subsets, calculate the number of elements in each subset, and add up the numbers. Do the math. Did you get 2,901,711,320,064? Or, wouldn't your calculator show that many digits?

- A password for your computer.
Suppose you decide to create a password made up of capital letters
of the alphabet, and ≤ 3 characters in length. How many ways
can you choose such a password?

- If a finite set S equals the union of n distinct and mutually disjoint subsets,
then the number of elements in A equals the sum of the numbers of elements in the subsets.
- The Difference Rule for a Set and a Subset.

- If A is a finite set and B is a subset, then N(A - B) = N(A) - N(B).

This must be true, because B and A - B are disjoint sets whose union is A. Thus, N(A) = N(B) + N(A - B).

- In the special case where A is a universal set (the set of all possible outcomes),
the difference rule gives us

P(B^{c}) = P(U) - P(B), which simplifies to P(B^{c}) = 1 - P(B).

Perhaps that seems obvious, since another way to write it is P(B) + P(B^{c}) = 1

(every outcome is either in an event or its complement)

- Examples:

- A password for an online shopping account.
The rules say that your password must be at least 3 characters long,
no more than 4 characters long, made up of capital letters,
and have at least one letter that appears more than once.

Solution:

Let U = {password from capital letters | 3 ≤ length ≤ 4} (passwords with or without repetition)

Let X = {x U | no letters are repeated} (passwords without repetition)

Then our solution set is S = U - X, or X^{c}(passwords with repetition)

Break U into U_{3}U_{4}.

Use the Multiplication Rule to calculate N(U_{3}) and N(U_{4}).

Use the Addition Rule to calculate N(U) = N(U_{3}) + N(U_{4}).

Break X into X_{3}X_{4}.

Use the Multiplication Rule to calculate N(X_{3}) and N(X_{4}).

Use the Addition Rule to calculate N(X) = N(X_{3}) + N(X_{4}).

Use the Difference Rule to calculate N(S) = N(U) - N(X).

- A password for an online shopping account.
The rules say that your password must be at least 3 characters long,
no more than 4 characters long, made up of capital letters,
and have at least one letter that appears more than once.

- If A is a finite set and B is a subset, then N(A - B) = N(A) - N(B).
- Inclusion/Exclusion Rule for Overlapping Sets.

- If A and B are any finite (possibly overlapping) sets, then

N(A B) = N(A) + N(B) - N(A B)

Similarly, if A, B, and C are any finite sets, then

N(A B C) = N(A) + N(B) + N(C) - N(A B) - N(A C) - N(B C) + N(A B C)

It should seem reasonable that using mathematical induction we could prove that similar formulas hold for unions of n sets, where n is any integer > 1.

- Examples:

- How many integers from 1 through 1,000 are
multiples of 3 or multiples of 5?

1, 2, 3=3*1, 4, 5, 6=3*2, 7, ..., 999=333*3 so there are 333 multiples of 3

1, 2, 3, 4, 5=5*1, 6, 7, 8, 9, 10=5*2, 11, ..., 1000=5*200 so there are 200 multiples of 5.

1, 2, 3, ..., 15=15*1, ..., 30=15*2, ..., 990=15*66, 991, 992, ..., 1000 so there are 66 multiples of 15

By the Inclusion/Exclusion Rule for Overlapping Sets:

N({mults of 3} {mults of 5}) = N({mults of 3}) + N({mults of 5}) - N({mults of 3} {mults of 5})

= 333 + 200 - 66 = 467

- How many integers from 1 through 1,000 are
neither multiples of 3, nor muliples of 5?

We know how many integers there are in all, and we know how many of them are multiples of 3 or 5, so use the Difference Rule.

- Suppose we have a class of students,
all students in the class own either an Xbox or a PlayStation,
15 students own an Xbox, 12 students own a PlayStation,
and 5 students own both an Xbox and a PlayStation.

How many students are in the class?

We know how many are in each of the two subsets, and the intersection, so use the Inclusion/Exclusion Rule to figure out how many are in the class.

- How many integers from 1 through 1,000 are
multiples of 3 or multiples of 5?

- If A and B are any finite (possibly overlapping) sets, then