The Addition Principle

The Addition Principle for Counting Procedures

If a procedure can be broken up into $m$ events or cases whose sets of outcomes are mutually exclusive, with $j_{1}$ possible outcomes for the first event, $j_{2}$ possible outcomes for the second event, $\dots$ , and $j_{m}$ for the $m^{t h}$ event, then the total number of outcomes of the procedure is $j_{1} + j_{2} + \dots + j_{m}$

Example

On a bookshelf there are 5 different calculus books, 6 different linear algebra books and 7 different combinatorics books

In how many ways can a pair of books of different types be chosen
In how many ways can single book of each type be chosen

Part 1:
Mutually Exclusive Events:

Calculus + Linear Algebra
- $5 \times 6$ choices
Calculus + Combinatorics
- $5 \times 7$ choices
Linear Algebra + Combinatorics
- $6 \times 7$ choices
  $∴$ Total number of outcomes $: = (5 \times 6) + (5 \times 7) + (6 \times 7) = 107$
  Part 2:
  Independent Events:
Calculus book
- 5 choices
Linear Algebra book
- 6 choices
Combinatorics book
- 7 choices
  $∴$ Total number of outcomes $: = 5 \times 6 \times 7 = 210$

Example

How many integers are the from 1 through 9999 that have distinct digits?

Answer:
Mutually Exclusive Events:

One digit
- 9
Two digits
- $9 \times (10 - 1) = 9 \times 9$
- First digit can’t be 0, second cant be the same as the first
Three digits
- $9 \times 9 \times 8$
Four digits
- $9 \times 9 \times 8 \times 7$
  $∴$ Total number of integer $: = (9) + (9 \times 9) + (9 \times 9 \times 8) + (9 \times 9 \times 8 \times 7) =$