The multiplication principle

Our main objective in this chapter is to count: how many ways are there for an event to occur? Listing the possibilities out is one way we can do that, but this quickly gets out of hand for large numbers.

Our first general technique will then to break up our event into a sequence of steps, and apply the multiplication principle.

Technique: the multiplication principle

Suppose we can break an event $E$ up into two steps: step 1 followed by step 2.

If there are $m$ ways for step 1 to occur followed by $n$ ways for step 2, then the total number of ways for $E$ to occur is $m \times n .$

Example: forming a number with repetition

Question

How many ways are there to form a five-digit number satisfying the following conditions using only the numbers from 1,2,3,4,5,6,7. Repetitions are allowed.

No restrictions.
The number must be greater than 30,000.
The number must be odd.
The number must be greater than 30,000 and odd.

Solution

Step 1: there are 7 ways to fill in the first digit.
Steps 2-5: there are 7 ways to fill in the second digit.

Repeating for all 5 digits, required number of ways $= 7 \times 7 \times 7 \times 7 \times 7 = 7^{5} = 16,807 ∎$

Step 1: there are 5 ways to fill the first digit (3,4,5,6,7).
Steps 2-5: there are 7 ways to fill in the subsequent digits.

Required number of ways $= 5 \times 7 \times 7 \times 7 \times 7 = 5 \times 7^{4} = 12,005 ∎$

Step 1: there are 4 ways to fill the last digit (1,3,5,7).
Steps 2-5: there are 7 ways to fill in the subsequent digits.

Required number of ways $= 4 \times 7 \times 7 \times 7 \times 7 = 4 \times 7^{4} = 9,604 ∎$

Step 1: there are 5 ways to fill the last digit (3,4,5,6,7).
Step 2: there are 4 ways to fill the last digit (1,3,5,7).
Steps 3-5: there are 7 ways to fill in the subsequent digits.

Required number of ways $= 5 \times 4 \times 7 \times 7 \times 7 = 5 \times 4 \times 7^{3} = 6,860 ∎$