Rosen,
Discrete Mathematics and Its Applications, 6th edition
Extra
Examples
Section
5.1—The Basics of Counting
p.340, icon at Example 14
#5. Find the number of strings of length 10 of letters of the alphabet, with no repeated letters, that have vowels in the first two positions.
Solution:
Keep in mind a row of ten blanks:
.
We will first count the number of ways to place vowels in the first two blanks. We can choose any of the five vowels for the first blank and any of the remaining four vowels to put in the second blank. Because we must do both, there are 5 · 4 = 20 ways to place the two vowels. Next we will place eight of the remaining 24 letters in the remaining eight blanks. This can be done in 24 · 23 ··· 18 · 17 ways.
Therefore, by the product rule, the number of ways to place vowels in the first two blanks and eight letters
in the remaining eight blanks is
(5 · 4) · (24 · 23 ··· 18 · 17)
p.340, icon at Example 14
#6. Ten men and ten women are to be put in a row. Find the number of possible rows.
Solution:
Keep in mind a row of twenty blanks. There is no restriction on how the men and women can be placed
in a row, so the answer is 20 · 19 · 18 ··· 3 · 2 · 1 = 20!.
p.340, icon at Example 14
#7. Ten men and ten women are to be put in a row. Find the number of possible rows if no two of the same sex stand adjacent.
Solution:
Keep in mind a row of twenty blanks. If no two of the same sex stand in adjacent positions, then there are two possible patterns, using M for male and F for female:
MFMFMFMFMFMFMFMFMFMF and FMFMFMFMFMFMFMFMFMFM.
We will count the number of ways of achieving the first pattern and double this number to find the final answer. The first man can be chosen in 10 ways, the first woman can be chosen in 10 ways, this second man can be chosen in 9 ways, etc.
Thus, by the extended product rule, each pattern can be obtained in 10 or (10 · 9 ··· 2 · 1)2 ways.
The second pattern can be obtained in the same number of ways, so we double the answer to get 2(10 · 9 ··· 2 · 1)2 = 2 · 10!2 .
p.340, icon at Example 14
#8. Ten men and ten women are to be put in a row. Find the number of possible rows if Beryl, Carol, and Darryl want to stand next to each other in some order (such as Carol, Beryl, and Darryl, or Darryl, Beryl, and Carol).
Solution:
Keep in mind a row of twenty blanks.
We first consider the arrangements where Beryl, Carol, and Darryl stand next to each other in that order. We begin by putting the 17 other people in a row, which can be done in 17! ways.
No matter how the 17 are placed in a row, Beryl, Carol, and Darryl can either be inserted (in that order) between two of the 17, or else placed at one of the two ends. This is pictured in the following diagram, where the 17 x’s represent
the 17 people placed in a row.
There are 18 places in which Beryl, Carol, and Darryl can be placed together
— 16 places between the x’s and two places on the two ends — marked by blanks.
x x x x x x x x x x x x x x x x x
Therefore, the number of ways to place the 18 people, with Beryl, Carol, and Darryl next to each other (in
that order) is But Beryl, Carol, and Darryl can be permuted in 3! ways. Therefore, the final answer is 17! · 18 · 3!.
p.342, icon at Example 17
#1. Find the number of integers from 1 to 400 inclusive that are:
(a) divisible by 6.
(b) not divisible by 6.
Solution:
(a) Every sixth integer from 1 to 400 is divisible by 6, yielding 400 = 66. (Note: When we divide 400 by 6 we obtain 66 2/3. The fraction 2/3 indicates that we are two thirds of the way toward the next integer
divisible by 6, which is 402. We round down because 402 is beyond the range of numbers from 1 to 400.)
(b) From part (a) we know that 66 integers from 1 to 400 are divisible by 6. Hence the number that are not divisible by 6 is 400 − 66 = 334.
p.342, icon at Example 17
#2. Find the number of integers from 1 to 400 inclusive that are:
(a) divisible by 6 and 8.
(b) divisible by 6 or 8.
Solution:
(a) Divisibility by a and b is the same as divisibility by the least common multiple of a and b. Therefore, divisibility by 6 and 8 is the same as divisibility by 24. The answer is 400 = 16.
(b) We cannot take the number of integers divisible by 6 and add to it the number of integers divisible by 8, because this would count integers such as 24 or 48 twice (because they are divisible by both 6 and 8). We
need to use the inclusion-exclusion principle to avoid the “double counting”.
Let A1 = {x | 1 ≤ x ≤ 400, x is divisible by 6} and A2 = {x | 1 ≤ x ≤ 400, x is divisible by 8}. We want
|A1 ∪ A2 |. By the inclusion-exclusion principle we have
|A1 ∪ A2 |= |A1 | + |A2 |− |A1 ∩ A2 |
= 400 + 400 − 400
= 66 + 50 − 16
= 100.
Note: When the word “or” appears in a counting problem, it is a wise strategy to consider using the inclusion-exclusion principle.
p.342, icon at Example 17
#3. Find the number of strings of length 10 of letters of the alphabet, with repeated letters allowed, (a) that begin with C and end with V.
(b) that begin with C or end with V.
Solution:
(a) Keep in mind a row of ten blanks:
.
If the string has the form
C
V ,
there are 26 ways to fill in each of the eight intermediate blanks. Hence there are 268 strings of this form. (b) We need to count the number of strings that have the form
C or
V
The number of strings of each form is 269. However, we cannot simply add the two numbers to get our answer. If we do this, we are counting the number of strings of the form C
V twice because each such string fits both patterns.
We need to use the inclusion-exclusion principle to avoid the double-counting. Let A1 be the set of all strings of length ten that begin with C and let A2 be the set of all strings of length ten that end with V. We want
|A1 ∪ A2 |. But by the inclusion-exclusion principle,
|A1 ∪ A2 | = |A1 | + |A2 |− |A1 ∩ A2 |
= 269 + 269 − 268.
(The term 268 was obtained as the size of A1 ∩ A2 , which is the set of all strings of length ten that begin with C and end with V.)
No comments:
Post a Comment