Section 9.2 Multiplication Rule
In this section we look at how to count a process that has several steps. We start with an example.
Toss a coin three times. How many ways can you get exactly two heads in the three tosses?
First toss: H or T
Second toss: H or T
Third toss: H or T
If we think about what happens after the first toss, we have H or T. For each of those outcomes, we get H or T on the second toss, so we now have 4 outcomes: HH, HT, TH, TT
With the third toss, each of our four outcomes could end with H or T, giving us 8 outcomes: HHH, HTH, THH, TTH, HHT, HTT, THT, TTT.
Out of these 8 possible outcomes, there are 3 outcomes with exactly 2 heads: HTH, THH, HHT.
We can also see the possibilies using a possibility tree, where the first (top) level represents the first toss, the second level, the second toss, and the third level, the third toss. The blue βpathsβ show the outcomes with exactly two Heads.
In Example 9.2.1, we saw that each toss doubled the number of outcomes from the previous toss. For example, if we tossed the coin 4 times, we would have outcomes. We are using the multiplication rule to determine the number of outcomes.
Multiplication Rule.
Activity 9.2.1.
Suppose a restaurant offers 3 appetizers, 3 entrees, and 2 desserts.
(a)
Draw a possibility tree for how many different meals (one appetizer, one entree, and one dessert) you can create.
(b)
How many total meals can you create?
Example 9.2.3. Multiplication Rule: License Plates.
Find the number of license plates that can be made if each one consists of two letters from A through E, followed by four digits from 1 through 9.
There are 5 choices for the letters: A, B, C, D, E.
There are 9 choices for the digits: 1, 2, 3, 4, 5, 6, 7, 8, 9.
First choose a letter, then another letter, then choose each of the numbers. We can use the multiplication rule since we can choose each character as a process.
Thus, we have license plates.
Now, suppose you cannot repeat a number in any one license plate. How many license plates can we make?
When choosing the numbers, first we have 9 choices, then 8, since we can't choose the same number as the first digit, etc.
The total number of license plates if we can't repeat a number is
Activity 9.2.2.
Suppose a license plate consists of 3 letters followed by 2 digits.
(a)
How many license plates can you make?
(b)
How many license plates can you make if you cannot repeat a letter or number?
A string of length over is a list of characters where the characters come from set A binary string or bit string is a string with The null string is the string of length 0, denoted
Example 9.2.4. Multiplication Rule: Strings.
Find the number of bit strings of length 5.
Answer 1.Find the number of βwordsβ of length 4. These are just strings where is the alphabet.
Answer 2.Find the number of strings of length 7, where
Answer 3.Definition 9.2.5.
Example 9.2.6. Permutations of a Set.
Let Then a permutation of is a list of elements in List all the permutations of
Since we have 3 choices for our first element, then 2 choices for the second, and 1 for the last, there are permutations.
The permutations are abc, acb, bca, bac, cab, cba.
How many permutations are there of the set
Answer.Activity 9.2.3.
List all the permutations of
Hint.
There are 6.
Activity 9.2.4.
How many permutations are there of a set with 5 elements?
Activity 9.2.5.
How many permutations are there of a set with elements?
Activity 9.2.5 gives us a formula for finding the number of permutations of a set with elements.
Theorem 9.2.7.
Definition 9.2.8.
An -permutation of a set is an ordered selection of elements taken from the elements of in a row. We use the notation for the number of -permutations from a set of elements.
Example 9.2.9. -Permutations of a Set.
Let Then a 3-permutation of is a list of 3 (non-repeating) elements from For example, ace, dbe, bda are all 3-permutations.
Find the number of 3-permutations of
We have 5 choices for the first letter, 4 choices for the second, and 3 choices for the last. Thus,
How many 4-permutations are there of the standard English alphabet?
Answer.Activity 9.2.6.
How many 2-permutations are there of
Activity 9.2.7.
How many 3-permutations are there of
Hint.
Think of finding a way to count them using the multiplication rule rather than writing them all down.
Activity 9.2.8.
Theorem 9.2.10.
Activity 9.2.9.
Find
Example 9.2.11. Finding Four-Digit Integers.
How many odd integers are there from 1000 to 9999?
The number is a string of 4 digits. The first digit cannot be 0, so there are 9 choices: 1 through 9. The second and third digits can be anything from 0 to 9, so there are 10 choices for each. The last digit must be odd, so the only choices are 1, 3, 5, 7, 9.
Thus, there are odd numbers.
How many integers are there from 1000 to 9999 that have distict digits?
The first digit cannot be 0, so there are 9 choices: 1 through 9. The second digit can be anything from 0 to 9, except for whatever the first digit is, so there are 9 choices. Similarly, there are 8 choices for the third digit, and 7 for the last digit.
Thus, there are numbers with distinct digits.
Reading Questions Check Your Understanding
1.
Toss a coin 4 times. How many ways are there to get exactly 1 Head?
2.
Toss a coin 4 times. How many ways are there to get exactly 2 Heads?
3.
Toss a coin 4 times. How many ways are there to get 0 Heads?
4.
How many 3 digit numbers begin with 1 or 2 and end with 2, 3, or 4?
5.
How many 3 digit numbers are divisible by 5?
6.
Calculate the number of permutations of a set with 6 elements.
7.
Calculate
8.
Calculate
Exercises Exercises
1.
A bag contains two green balls (labeled and ) and one purple ball. A second bag contains one green ball and two purple balls (labeled and ). Suppose the following experiment is performed: One of the two bags is chosen at random. Next a ball is randomly chosen from the bag. Then a second ball is chosen from the same bag without replacing the first ball.
- Construct the possibility tree showing all possible outcomes of the experiment.
- What is the total number of outcomes in this experiment?
- What is the probability that two green balls are chosen?
- What is the probability that two balls of different colors are chosen?
2.
A person buying a computer system is offered a choice of three models of the basic unit, two models of the keyboard, and two models of printer. How many distinct systems can be purchased?
3.
Recall that a bit string is a finite sequence of 0βs and 1βs.
- How many bit strings have length 8?
- How many bit strings have length 8 and begin with 3 0βs?
- How many bit strings have length 8 and begin and end with a 1?
4.
A coin is tossed four times. Each time the result for heads or for tails is recorded. Assume heads and tails are equally likely on each toss.
- How many distinct outcomes are possible?
- What is the probability that exactly two heads occur?
- What is the probability that exactly one head occurs?
5.
Suppose a license plate consists of four letters followed by three digits.
- How many different license plates are possible?
- How many license plates could begin with an
and end with 0? - How many license plates could begin with
- How many license plates are possible if you cannot repeat a letter or number (all the letters and numbers are distinct)?
- How many license plates could begin with
and have no repeated letters or numbers?
6.
Consider all two digit integers 10-99.
- How many integers are there from 10 through 99?
- How many odd integers are there from 10 through 99?
- How many integers from 10 through 99 have distinct digits?
- How many odd integers from 10 through 99 have distinct digits?
- What is the probability that a randomly chosen two-digit number has distinct digits? has distinct digits and is odd?
7.
We want to count the number of possible functions from a finite set to a finite set. You may need to recall the definition of a function, Definition 7.1.1.
- How many functions are there from a set with three elements to a set with four elements?
- How many functions are there from a set with five elements to a set with two elements?
- How many functions are there from a set with
elements to a set with elements, where and are positive integers?
8.
We consider various arrangements of the letters in the word
- How many ways can the letters of the word
be arranged in a row? - How many ways can the letters of the word
be arranged in a row if and must remain together (in order) as a unit? - How many ways can the letters of the word
be arranged in a row if the letters must remain together (in order) as a unit?