Ch10
This document was uploaded by user and they confirmed that they have the permission to share it. If you are author or own the copyright of this book, please report to us by using this DMCA report form. Report DMCA
Overview
Download & View Ch10 as PDF for free.
More details
- Words: 7,846
- Pages: 10
.
Chapter 10 • Introduction to Counting Solutions for Selected Problems
d. Counting the number of integers ending in 9 we
have from each of 10 rows, 10 such integers: 9, 19, 29, … , 99 → 10 109, 119, 129, … , 199 → 10 209 → 10 .. .. . . 909, 919, … , 999 → 10 therefore n(H ) 100 and n(H) n(U) n(H ) 1000 100 n(H) 900.
Exercise 10.1 11. a. The result of the draw will form three-digit
numbers of the form 100a 10b c, a, b, c {1, 2, 3, … , 9} and a ≠ b ≠ c. b. Since the ball labelled 4 is selected first, the second
ball can be any of the remaining eight, and for each of these, the third ball can be any of the remaining seven, giving 8 7 56 subsets. Therefore n(A) 56. A similar argument applies when the second and third balls drawn are 4s, hence n(B) 3 56 168.
14. Letters A, B, and C are placed in envelopes a, b, and c.
Let the ordered triple (x, y, z) mean letter A is in envelope x, B in y, and C in z. The universal set will be U {(a, b, c), (a, c, b), (b, a, c), (b, c, a), (c, a, b), (c, b, a)}. No letters to the correct person will be the subset {(b, c, a,), (c, a, b)}.
12. a. The three-digit number will be of the form
100a 10b c, a, b, c {1, 2, 3, … , 9}. b. With the first ball labelled 4, the second ball can be
any of the balls labelled 1 through 9, and for each of these, the third ball can be any of the balls labelled one through nine, hence n(A) 9 9 81. The number of elements in U is n(U1) 9 · 9 · 9 729. (We get this from the argument that the first ball can be any of the nine. Since it is now replaced, the second can be any of nine as will the third after replacement of the second.) Now the number of elements in U, where no 4 is drawn, will be 8 · 8 · 8 512. (Each of the first, second, and third draws can be any of the balls numbered 1, 2, 3, 5, 6, 7, 8, 9). The number of three-digit numbers when 4 is selected will be n(B) 93 83 217. n(U1) > n(U) since U is a subset of U1. 13. U {1, 2, 3, … , 1000}. a. The integers divisible by 7 in factored form are
7(1), 7(2), 7(3), … , 7(142). 7 142 994, which is the lowest multiple of 7 less than 1000. n(E) 142. b. The perfect squares are 12, 22, 32, … , 312.
312 961 and n(F) 31. c. The integers divisible by 3 are
y
15.
(1, 1)
1 V V
x 1
Exercise 10.2 5. If A and B are disjoint, then n(A B) n(A) n(B).
If A and B have common elements, n(A B) ≠ 0, then n(A B) < n(A) n(B). Therefore n(A B) n(A) n(B).
8. With A and B disjoint, there are no elements common
to both A and B. The number of elements in the union of these two sets is the sum of the number of elements in both sets.
3(1), 3(2), 3(3), … , 3(333) therefore n(G) n(u) n(G ) 1000 333 n(G) 667.
Chapter 10: Introduction to Counting 149
11. Let the committee with two girls be P, one boy and
one girl Q, and two boys R. P {AB, AC, BC} Q {AD, AE, AF, BD, BE, BF, CD, CE, CF} R {DE, DF, EF} u P Q R. 13.
V: contain at least one 5. W: contain at least one 6. The complement of V W, V W is the set of twodigit integers that do not contain the digits 5 or 6. n(u) 9 10 90. n(V W ) 7 8 56 (the first digit is any one of 1, 2, 3, 4, 7, 8, 9, and for each of these the second digit can be any one of 0, 1, 2, 3, 4, 7, 8, 9). Therefore n(V W) n(U) n(V V W ) 90 56 n(V V W) 34.
j 4
5
6
7
8
3
4
5
6
7
2
3
4
5
6
1
2
3
4
5
1
2
3
4
i
7. Let A be the number of integers divisible by 3.
The labelling of a point represents i j c. c. All of the subsets in b are disjoint. d. The union of the subsets in b includes all of the
elements in P.
37 take Business 101, of which 42 19 23 are girls, hence 14 are boys. 14 boys take Business 101. A
B
B
A
10. Since the Ei, i 0, 1, 2, 3, are disjoint sets and
B
U E0 E1 E2 E3 then n(U) n(E0) n(E1) n(E2) n(E3).
AB
AB
A
A {3(1), 3(2), 3(3), … , 3(10)} therefore n(A) 10 therefore n(A ) n(U) n(A) 30 10 n(A ) 20. 8. Of 90 students, 42 are girls, therefore 48 are boys. Also
15. Consider n(A B) ≠ 0.
A
6. U: two-digit integers.
A
B
A
B
B
16. U (A B) (A B) (A B) (A B).
12. There are 365 days in a non-leap year. 365
7(52) 1, which gives 52 2 104 days that fall on a weekend. The extra day can fall on any day of the week. If it falls on a Saturday or Sunday there will be 104 1 105 days falling on a weekend, which is the maximum number possible.
13. a. The numbers divisible by 5, set A, are
Exercise 10.3 5. The ten numbers that start with 7 are 70, 71, 72, … ,
77, 78, 79, and those that end in 7 are 17, 27, 37, … , 77, 87, 97. The 77 is in both sets was counted twice.
A {5(1), 5(2), 5(3), … , 5(200)} therefore n(A) 200. b. The numbers divisible by 7, set B, are
B {7(1), 7(2), 7(3), … , 7(142)} therefore n(B) 142. c. Numbers divisible by both 7 and 5 are divisible by
35, set C, C {35(1), 35(2), 35(3), … , 35(28)} n(C) 28 n(A B).
150 Chapter 10: Introduction to Counting
d. n(A B) n(A) n(B) n(A B)
Exercise 10.4
200 142 28 314. The number of numbers divisible by neither 5 nor 7, n(A B ) 1000 314, is 686.
4. The number of letters available for postal codes is
n(X) 26 7 19. The number of digits is n(x) 10. There are 19 choices for the first X and for each of these there are 10 choices for the first x, 19 for the second X, 10 for the second x, 19 for the third X and 10 for the third x. Then the number of postal codes is 10 · 19 · 10 · 19 · 10 · 19 193 103 6 859 000.
e. Of the 200 numbers divisible by 5, 28 are also divisible
by 7. Therefore there are 200 28 172 numbers divisible by 5 but not divisible by 7. 14. The number of integers divisible by 7, the set A, is
5. 3 10 10 10 10 10 10. The first digit can be any one
n(A) 142 (from 13(c)). The integers divisible by 13, set B, B {13(1), 13(2), 13(3), … , 13(76)} therefore n(B) 76. Now A B {91(1), 91(2), 91(3), … , 91(10)} and n(A B) 10 n(A B) n(A) n(B) n(A B) 142 76 10 208. The number of integers divisible by 7 or 13 is 208.
of 3, 5, or 6, 3 choices. For each of these, the second digit can be any of the 10 digits. Similarly, the remaining digits can be any of 10. Hence from the product rule there will be 3 106 seven-digit telephone numbers starting with a 3, 5, or 6. 6. 2 4 3 2 1 1
The first person on the left can be either of the two tabled people, 2 choices, and the position of the extreme left then is filled with the other of the two tallest people. The second can be filled with any of the four remaining people, the third with 3, fourth with 2 and fifth in 1. Hence there are 2 · 4 · 3 · 2 · 1 · 1 48 possible arrangements.
17. Let A be the set of integers divisible by 2, n(A) 500.
B is the set of integers divisible by 3, therefore n(B) 333. C is the set of integers divisible by 5, therefore n(C) 200. Now A B {6(1), 6(2), 6(3), … , 6(166)} and n(A B) 166. A C {10(1), 20, 30, … , 10(100)} and n(A C) 100. B C {15(1), 15(2), 15(3), … , 15(66)} and n(B C) 66. A B C {30(1), 30(2), 30(3), … , 30(33)} and n(A B C) 33. Now n(A B C) = n(A) n(B) n(C) n(A B) n(A C) n(B C) n(A B C) = 500 333 200 166 100 66 33 = 734. 734 integers are divisible by 2, 3, or 5.
18. Define n(E1) so that
e
There are 6 choices in which the first box can be filled, for each of these the second box can be filled in 5 ways, the fourth in 4 ways, fifth in 3 ways, sixth in 2 ways, and the seventh in 1 way. Therefore the number of anagrams is 6 · 5 · 4 · 3 · 2 · 1 720. 8. a. b. Since there are only three letters, C, A, and T,
once the first letter is chosen, there are only two choices for the second letter and then one for the third letter. From the product rule, the number of different “words” is 3 · 2 · 1 6.
mushrooms, sausage, and onions is the same had we chosen sausage, mushrooms, and onions. Repetition is included in the 504 pizzas. Each selection of 3 items gives rise to 6 arrangements, hence there would be 504 6 84 different pizzas possible.
n(EiEj) be the sum of all possible intersecting pairs Ei Ej, 1 i, j n, i < j. n(EiEjEk) be the sum of all possible intersecting triples Ei Ej Ek, i 1, k n, i < j < k, and so on. Then n(Ei Ej Ek … En)
10. a. A possible answer sheet is T T F F F T F T T T.
= n(Ei) n(EiEj) n(EiEjEk) n(EiEjEkEl) … (1)
n
n(EiEjEk … En).
i
9. The product rule implies order. Choosing a pizza with
n(Ei) n(E1) n(E2) n(E3) … n(En)
–1
7.
b. Since each question can be either True or False,
there will be 210 1024 different answer sheets.
Chapter 10: Introduction to Counting 151
11. Since there are five possibilities for each question,
there are a possible 57 78 125 possible answer sheets. Since there are 30 000 students, every answer sheet could be different. 12. Consider a, e, i, o, and u as the only vowels for this
exercise. a. U {aab, pqr}
A {eez, ibc} B {pqr, pss} C {xyz, mno}
b. From the product law we have:
n(U) 26 · 26 · 26 17 576 n(A) 5 · 26 · 26 3380 n(B) 5 · 5 · 5 125 n(C) 26 · 25 · 24 15 600 c. n(A B) 0, since the acronym must start with
a vowel and the only letters that can be used are p, q, r, s, and t, none of which are vowels. d. A B represents the acronyms that start with
a vowel or are made up using only the letters p, q, r, s, and t. e. n(A B) n(A) n(B) n(A B)
3380 125 0 3505.
f. The number of acronyms in which all letters are
different is 26 · 25 · 24 15 600. The number of acronyms that use one letter at least twice is n(u) 15 600 1976. 13. Letters a, b, c, d, e, f are rearranged in n(u)
6 · 5 · 4 · 3 · 2 · 1 720 ways. The number of words that being with a is determined by the product rule as 1 · 5 · 4 · 3 · 2 · 1 120. Therefore the number of words that do not begin with a is 720 120 600. Or the first letter any of b, c, d, e, f and the product rule gives 5 · 5 · 4 · 3 · 2 · 1 600.
14. The first letter is any of the given 6, the second any
of 5, the third any of 4, and the fourth any of the remaining 3. From the product rule the number of four-letter words is 6 · 5 · 4 · 3 360. If the word begins with a, then the second letter is any of the remaining 5, the third any of 4, and the fourth any of 3, giving 1 · 5 · 4 · 3 60 words starting with a. 15 a. 9 · 10 · 10 · 10. The first digit can be any of 1, 2, 3,
4, 5, 6, 7, 8, or 9, 9 choices. The second, third, and fourth places can be any of the 10 digits, hence there are 9 · 10 · 10 · 10 9000 such integers.
b. The units digit is either 7 or 8, 2 choices. Hence
from the product rule we have 9 · 10 · 10 · 2 1800 integers ending in 7 or 8. c. If there are no repeated digits, then the second digit
has 9 possibilities, the third 8, and the fourth 7, giving 9 · 9 · 8 · 7 4536 integers. d. The number with repeated digits will be
9000 4536 4464. 16. There will be 26 26 10 62 symbols available. a. _ _ _ _ _ _ _ _ Each position can be any of the 62
symbols (with repetition) hence there will be 628 possible passwords. b. 10 _ _ _ _ _ _ 10 The first and last position have 10
choices. The remaining positions can be any of the 62 symbols, hence there are 626 102 passwords. c. With no repeated digits, there will be 6261 · 60 ·
59 · 58 · 57 · 56 · 55 different passwords. d. The number of passwords with no 9 is 618.
Therefore with at least one 9 there will be 628 618 passwords. 17. a. Represent each divisor as an ordered pair,
i.e., (a, b) 2a 3b. With 0 a 2 and 0 b 1 (0, 0) 1, (1, 0) 2, (2, 0) 4 (0, 1) 3, (1, 1) 6, (2, 1) 12. b. There are six sequences that can be formed as
shown in (a) as ordered pairs. c. 12 has 6 divisors. d. 144 24 · 32
Integer divisors of 144 can be written in the form 2a · 3b where 0 a 4, 0 b 2. There are 5 possible values of a, the first member of the sequence; and for each of these there are 3 possible values for b, the second member of the sequence; hence there will be 5 3 15 integer divisors of 144. e. For odd divisors, there can be no even factors,
hence the sequence has 0 as its first term, the second term is either 0, 1, or 2; hence there are 3 odd divisors. 18. a. 64 800 25 · 34 · 52.
Here we form three-term sequences where there are 6 choices for the first term (0, 1, 2, 3, 4, and 5); and for each of these, 5 choices for the second term and 3 for the third. Hence there are 6 · 5 · 3 90 integer divisors of 64 800. b. For even divisors, the first term of our sequence
152 Chapter 10: Introduction to Counting
must be one of 1, 2, 3, 4, or 5; 5 choices, hence there are 5 · 5 · 3 75 even divisors of 64 800.
19. a. n 2a3b5c
a 1, b 1, c 1. The first term of the three-term sequence has (a 1) choices; for each of these, the second term has (b 1), and the third term has (c 1). Hence there are (a 1)(b 1)(c 1) integer divisors of n.
365 · 364 · 363 · … · (365 n) 365
1 2
b. Now 1 > . n
365 · 364 · 363 · … · (365 n) 1 Therefore < 365n 2 for n 22, the fraction is 0.5243.
b. For an even divisor, a two must be included.
Therefore the first term of the sequence has a choices and there will be a(b 1)(c 1) even divisors of n. The fraction of even divisors is
Exercise 10.5 2. Sequence of length 6 using the 10 digits and 26
letters. If the letter is in the final position, there will be 26 · 10 · 9 · 8 · 7 · 6 passwords. The number of passwords will be the same if the letter is in the second, third, fourth, fifth, or sixth position. Therefore the number of passwords is 26 · 10 · 9 · 8 · 7 · 6 6 4 717 440.
a(b 1)(c 1) a . (a 1)(b 1)(c 1) a1 20. a. The first term of the sequence can be filled in m
ways; and for each of these, the second in (m 1) ways, and for each of these the third in (m 2) ways. From the product rule there will be m(m 1)(m 2) sequences of length three.
3. The number of binary sequences of length n is 2n. The
number of binary sequences with length of at most 5 will be the sum of the sequences having length 1, 2, 3, 4, and 5, i.e., 21 22 23 24 25 = 2 4 8 16 32 = 62.
b. Since the symbols can be repeated, the number of
sequences will be m · m · m m . 3
21. In a sequence of length r and the product rule there
will be r factors in the product, the last one being [m (r 1)] (m r 1). Hence the number of sequences will be m(m 1)(m 2) … (m r 1). With repetition allowed there will be mr sequences of length r. 22. a. Since the five people can have birthdays on the
same day, the number of sequences will be 3655. b. If the birthdays are distinct, the number of
sequences will be 365 · 364 · 363 · 362 · 361. Percent having distinct birthdays will be 365 · 364 · 363 · 362 · 361 0.972864 3655 97.29%. c. With two or more birthdays on the same day, we
have 100% 97.29% 2.71%. 23. a. The number of sequences that are possible is 365n.
With different birth dates, the number of sequences will be 365 · 364 · 363 · … · (365 n 1). With two or more birthdays on the same day, the fraction is 365 · 364 · 363 · … · (366 n) 1 . 365n
4.
0 22222 The number of binary sequences of length 6 that begins with a zero is 25. Similarly, the number of sequences of length 7 and 8 beginning with zero will be 26 and 27. Therefore the sum is 25 26 27 = 25 (1 2 4) = 25 7 = 224.
5. a. The number of one-letter words is 4; two-letter
words, 4 3 12; three-letter words, 4 · 3 · 2 24; and four-letter words, 4 · 3 · 2 · 1 24. The total number of words is 64. b. Number of words ending in a:
one-letter words 1; two-letter words, 3 · 1 3; three-letter words, 3 · 2 · 1 6; and four-letter words, 3 · 2 · 1 · 1 6. The number of words ending in a is 16. 1 Or of the words end in each of 4 1 a, b, c, or d. Therefore of 64 16 4 words end in a.
Chapter 10: Introduction to Counting 153
c. Number of words that do not contain an a:
one-letter words 3; two-letter words, 3 · 2 6; three-letter words, 3 · 2 · 1 6; and four-letter words 0. The number that do not contain an a is 15. Therefore the number of words that do contain an a is 64 15 49. 6. a. If repetition of letters is allowed,
one-letter word 4; two-letter word, 42 16; three-letter word 43 64; and four-letter word, 44 256. The number of words that can be created will be 340. b. Number of words that end in a:
one-letter: a 1; two-letter: _ a, 4 1 4; three-letter: _ _ a, 4 4 1 16; and four-letter: _ _ _ a, 43 1 64. The number of words ending in a is 85. c. Number of words that do not contain a:
one-letter: _ 3; two-letter: _ _ 3 3 9; three-letter: _ _ _ 33 27; and four-letter: _ _ _ _ 34 81. The number of words with no a is 120. Therefore the number of words containing an a will be 340 120 220. 7. The rectangular arrays that are possible are 1 by 10, 2
by 5, 5 by 2, and 10 by 1. In each array the numbers 1 to 10 can be arranged in 10 · 9 · 8 · 7 · 6 · 5 · 4 · 3 · 2 · 1 3 628 800 ways. There will be 3 628 800 4 14 515 200 ways of storing the numbers. 8. The number of three-letter words possible is 263.
The number of three-letter words that do not contain either a, e, i, o, u, or y is 203. Therefore the number of three-letter words that contain at least one of a, e, i, o, u, or y is 263 203 9576. Similarly, the number of four-letter words would be 264 204 296 976 and five-letter words would be 265 205 8 681 376. The number of three-, four-, or five-letter words will be 9576 296 976 8 681 376 8 987 928.
9. To determine the number of 5s, we look at the number
of terms that are divisible by 5x, x 1. x 1, 5, 5(2), 5(3), … , 5(200): when x 1, there are 200 5s. x 2, 25, 25(2), 25(3), … , 25(40): when x 2, there are an additional 40 5s. x 3, 125, 125(2), 125(3), 125(4), … , 125(8): when x 3, there are an additional 8 5s. x 4, 625: when x 4, there is 1 additional 5. Therefore the total number of 5s in the set is 200 40 8 1 249. 10. Let P be the set of sequences starting with A.
Therefore P {ABCDEF, ABCDFE, …} n(P) 1 5 · 4 · 3 · 2 · 1 120 Q is the set ending with F. Therefore Q {ABCDEF, BACDEF, …} n(Q) 5 · 4 · 3 · 2 · 1 · 1 120 P Q {ABCDEF, ACBDEF, …} n(P Q) 1 · 4 · 3 · 2 · 1 · 1 24 Therefore the number of sequences that start with A or end with F is n(P Q) n(P) n(Q) n(P Q)) 120 120 24 216. 11. Represent the set of integers with n distinct digits by
An, 1 n 3. Now n(A1) 9 n(A2) 9 · 9 81. (The first digit can be any of {1, 2, 3, … , 9}: 9 choices, and for each of these there are 9 choices for the second digit: one of the 8 not chosen for the first digit plus 0). n(A3) 9 · 9 · 8 648. The four-digit integers must start with 1 (since we are looking for integers between 1 and 2000), the second, third, and fourth digits are chosen from the remaining 9, 8, and 7 digits. Therefore we have 1 · 9 · 8 · 7 504 allowable fourdigit integers. Therefore there are 9 81 648 504 1242 positive integers between 1 and 2000 inclusive having distinct digits. Let On represent the set of integers with n distinct digits that will be odd. 1 n 3 O1 {1, 3, 5, 7, 9}, therefore n(O1) 5 n(O2) 8 · 5 40. (The last digit is odd, the first can be chosen by the remaining 8 digits. The first digit cannot be zero.) n(O3) 8 · 8 · 5 320. 1 8 7 4. The first digit must be 1, the units digit can be any one of {3, 5, 7, 9}, 4 choices, the second digit and the third digit can be any one of the remaining 8 and 7 digits.
154 Chapter 10: Introduction to Counting
Therefore there will be 224 allowable odd four-digit integers. Total number of odd integers is 5 40 320 224 589. 589 Fraction that is odd is . 1242 12. a. Choosing Cat there are 3 · 2 · 1 6 sequences,
Mouse there are 5 · 4 · 3 60 sequences, and in Goldfish there are 8 · 7 · 6 336 sequences. There will be 6 60 336 402 sequences of length three.
b. Ending in S, choosing Cat there are O, Mouse there
are 4 · 3 · 1 12, and choosing Goldfish there are 7 · 6 · 1 42. There are 0 12 42 54 sequences of length three ending in S. c. Start with a vowel: from Cat there are
1 · 2 1 2, Mouse there are 3 · 4 · 3 36, and Goldfish there are 2 · 7 · 6 84. In all, 122 sequences of length three start with a vowel. d. The number of sequences of length three that do not contain O will be: from Cat, 6; Mouse, 4 · 3 · 2 24; and from Goldfish, 7 · 6 · 5 210; and in total 240. The number of sequences containing O will be 402 240 162. 13. a. Let Cn represent the set of sequences of length n.
n 1. Therefore C1 {0, 1, 2, … , 9} and n(C1) 10 C2 {10, 11, 12, … , 99} and n(C2) 102 C3 {100, 101, … , 999} and n(C3) 103 and so on to n(C10) 1010. n(U) 10 102 103 … 1010. There is a geometric sequence with a(rn 1) n(U) , a 10, r 10, n 10 r1 10(1010 1) therefore n(U) 9 n(U) 11111111110.
b. Let An represent the set of sequences of length n
having unique digits. n 1.
A1 {0, 1, 2, … , 9}, n(A1) 9 n(A2) 10 9 90 (first digit any of the 10
n(A7) n(A6) 4 604 800 n(A8) n(A7) 3 1 814 400 n(A9) n(A8) 2 3 628 800 n(A10) n(A9) 1 3 628 800. Therefore n(A) is the sum of the above. n(A2) 9 864 100. c. Let En represent the set of sequences of length n
that contain no zeros. Therefore
E1 {1, 2, 3, … , 9} and n(E1) 9 n(E2) 9 9 81, n(E3) 93, n(E4) 94, n(E5) 95, … , n(E10) 910 n(E) is the sum of the above. Therefore n(E) 9 92 93 … 910 9(910 1) 8 n(E) 3 922 632 450 n(B) n(U) n(E) n(B) 7 188 478 660. 14. a. The number of sequences of length 3 will be
r · r · r r3. The number of sequences of length 3 that do not contain an A will be (r 1)3. Therefore the number of sequences containing at least one A is r3 (r 1)3 r3 – (r3 3r2 3r – 1) r3 – r3 3r2 – 3r 1 3r2 3r 1. b. If no repetition of symbols is allowed, the number
of sequences of length 3 will be r(r 1)(r 2). Excluding A, there will be (r 1)(r 2)(r 3) sequences of length 3. Therefore the number of sequences containing at least one A is r (r 1)(r 2) (r 1)(r 2)(r 3)
available digits, for each of these we can choose
= (r 1)(r 2)[r (r 3)]
any of the remaining 9 digits). Similarly
= 3(r 1)(r 2)
n(A3) 10 · 9 · 8 720
= 3r2 9r 6.
n(A4) n(A3) 7 5040 n(A5) n(A4) 6 30 240 n(A6) n(A5) 5 151 200
Chapter 10: Introduction to Counting 155
15. Represent the set of arithmetic sequences (x, y, z),
x < y < z, of length 3 with common difference n by An. Therefore A1 {(1, 2, 3), (2, 3, 4), (3, 4, 5), … , (7, 8, 9)} therefore n(A1) 7 A2 {(1, 3, 5), (2, 4, 6), (3, 5, 7), … , (5, 7, 9)} therefore n(A2) 5 A3 {(1, 4, 7), (2, 5, 8), (3, 6, 9)} therefore n(A3) 3 A4 {(1, 5, 9)}, n(A4) 1. Now n(A1) n(A2) n(A3) n(A4) 16. But each sequence in An can be reversed, therefore the number of sequences of length 3 that forms an arithmetic progression is 16 2 32. 16. Let An represent the set of binary sequences of
length n. Therefore n(A1) 2 n(A2) 22 n(A3) 23 and so on, to n(Ak – 1) 2k – 1 and n(Ak) 2k. Now the number of binary sequences of length less than k is n(A1) n(A2) n(A3) … n(Ak – 1) 2 22 23 … 2k – 1 This is a geometric series with a 2, r 2, n k 1 therefore n(A1) n(A2) n(A3) … n(Ak – 1) 2(2k – 1 1) 2k 2 n(Ak) 2.
Review Exercise 3. a. U {A3A2K1, N5C2P2, …}
A {N2R3N1, N4L2N7, …} B {A3K5B8, N8H8T8, …} C {X1Y3A7, P3A4K2, …} D {N5C2R2, A4B5N3, …}
b. There are 26 7 19 letters and 9 digits that can
be used with repetitions, therefore n(U) 19 · 9 · 19 · 9 · 19 · 9 193 · 93 5 000 211.
156 Chapter 10: Introduction to Counting
(The first, third, and fifth positions can be any of the 19 letters, and for each of these the second, fourth, and sixth positions can be any of the 9 digits. From the product rule we have (9 19)3 possible postal codes) n(A) 1 · 9 · 19 · 9 · 19 · 9 192 · 93 263 169. (The first letter must be N, one choice, the others follow as for n(U).) n(B) 19 · 9 · 19 · 9 · 19 · 9 263 169. (The last position must be 8, one choice.) n(C) codes using the letter A. Let X be the set not using the letter A, therefore n(X) 18 · 9 · 18 · 9 · 18 · 9 183 · 93. Therefore n(C) n(U) n(X) 193 · 93 183 · 93 93(193 183 n(C) 748 683. The letter N can be in the first position. There will be 18 letters that can then be placed in the third and fifth positions, giving 1 · 9 · 18 · 9 · 18 · 9 postal codes starting with N. If N is in the third position there will be 18 · 9 · 1 · 9 · 18 · 9 postal codes, and if N is fifth, there are 18 · 9 · 18 · 9 · 1 · 9 postal codes, therefore n(D) 182 · 93 3 708588. c. The number of postal codes starting with N or
ending with 8 is n(A B). Now n(A B) n(A) n(B) n(A B) n(A B) 1 · 9 · 19 · 9 · 19 · 1. (The first and last positions have one choice each. The second and fourth can be any of the 9 allowable digits and the third and fifth can be any of the allowable 19 letters.) Therefore n(A B) 192 · 93 193 · 92 192 · 92 n(A B) 789 507. 4. a. U {012, 509, …}
A {035, 246, …} B {048, 572, …} C {037, 146, …}
b. n(U) 10 · 9 · 8 720.
(Choice of 10 digits in the first position, and for each of these, 9 digits for the second position and 8 for the final position.) n(A) 5 · 9 · 8 360. (The first digit is even, so can be any of the 5; the second digit can be any of the remaining 9; and the third has 8 choices.) n(B) 9 · 8 · 5 360.
(The last digit must be even, therefore there are 5 choices for the last position. The first position has 9 possibilities and the second has a choice of 8.) The number of sequences containing only odd digits is 5 · 4 · 3 60. Therefore the number of sequences containing an even digit is n(C) n(u) 60 n(C) 660. c. A B {064, 274, …}
n(A B) 5 · 8 · 4 160. (The first and last digits must be even, hence there are 5 and 4 choices for these positions. There will be 8 possible digits for the middle position.)
7. Let A represent the set of integers that contain the
digit 7 and An the set of integers of length n that contain the digit 7. Therefore A1 {7} and n(A1) 1 A2 {17, 27, 37, … , 67, 70, 71, … , 79, 87, 97} n(A2) 6 10 2 18. The number of three-digit integers is 9 · 10 · 10 900. The number of three-digit integers that do not contain a 7 is 8 · 9 · 9 648. Therefore n(A3) 900 648 252. Therefore n(A) 1 18 252 n(A) 271. 8. a. The number of three-digit PIN numbers is 103;
the number of four-digit PIN numbers is 104; therefore the number of PIN numbers available is 103 104 11 000.
5. The number of binary sequences of length 6 that start
with 1 and end in zero is 24 (1 _ _ _ _ 0). Similarly, the number starting with zero and ending in 1 is 24 (0 _ _ _ _ 1), and the number of sequences starting and ending with 1 is 24 (1 _ _ _ _ 1). Therefore the number of sequences starting or ending with one is 24 24 24 3 24. The number of binary sequences of length 6 is 26. 3 24 3 Therefore the required fraction is . 26 4 1 (The student’s argument that of the sequences start 2 with 1 includes sequences of the form 1 _ _ _ _ 0 and 1 1 _ _ _ _ 1, and that of the sequences end in 1 2 includes the sequences of the form 0 _ _ _ _ 1 and 1 _ _ _ _ 1. The form 1 _ _ _ _ 1 is included twice, 1 which occurs in of the sequences. Hence he must 4 1 subtract from his sum of 1, giving the correct 4 3 fraction of .) 4 6. Local telephone numbers consist of 7 digits, the first
selected from the digits 2 to 9, 8 choices. The remaining 6 digits can be any of the 10 numbers from the set {0, 1, 2, … , 9}, therefore the number of usable telephone numbers is 8 106. The number of telephone numbers ending in 99 will be 8 104 (8 · 10 · 10 · 10 · 10 · 1 · 1; first digit selected from 8 available, last two digits must be 9, 1 choice for each, the other 4 digits can be selected from the 10 available with repetitions allowed). Fraction of numbers ending in 99 is 8 104 1 6 . 8 10 100
b. The number of three-digit PIN numbers starting
with 2 is 1 · 10 · 10 100 and four-digit PIN numbers starting with 2 is 1 · 10 · 10 · 10 1000. Therefore the number of PIN numbers starting with 2 is 100 1000 1100. c. The number of PIN numbers of length 3 that do not
have a 2 is 9 · 9 · 9 93 and of length 4 is 94, therefore the number of PIN numbers that do not have a two is 93 94 93 (1 9) 10 · 93. The number of PIN numbers having at least one two will be 11000 10 · 93 10(1100 729) 10(371) 3710.
Chapter 10 Test 1. U {1, 2, 3, … , 999} a. A is a subset of U whose elements are not a
multiple of 5. b.
A {5, 5(2), 5(3), … , 5(199)} therefore n(A) 199. n(A ) n(U) n(A) 999 199 n(A ) 800.
2. The Product Rule: If the first of two tasks can be done
in p ways, and for each of these ways, the second task can be done in q ways, then together the two tasks can be done in p · q ways.
Chapter 10: Introduction to Counting 157
3. a. A B is the set of six-letter words ending in -id
or -ic. A B is the set of six-letter words ending in -id and -ic. (This is not possible, hence n(A B) 0.) b.
n(A B) n(A) n(B) n(A) 4 · 3 · 2 · 1 · 1 · 1 24 n(B) 4 · 3 · 2 · 1 · 1 · 1 24 therefore n(A B) 48. (For n(A), since the last two letters must be -id, there is only one choice for the last two positions. The first letter can be any of the 4 remaining and for each of these the second, third, and fourth are selected from the remaining 3, 2, and 1 letters, hence n(A) 4 · 3 · 2 · 1 · 1 · 1 24. The argument for n(B) is similar.)
4. If A is first, the second letter can be any of the
remaining 6 letters (B, C, D, E, F, G), and for each of these selections the third letter is any of the remaining 5. Therefore the number of words starting with A is 1 · 6 · 5 30. Similarly, if B is first there will be 30 words. Therefore the number of arrangements with A or B first will be 60. 5. Binary sequences starting and ending with 1 will be of
the form 1 _ _ _ 1, of which there are 23. Starting and ending with 0 will be of the form 0 _ _ _ 0, of which there are 23. Therefore the number of binary sequences of length 5 that start or end in the same number is 23 23 16. 6. a. A {2(1), 2(2), 2(3), 2(4), 2(5), … , 2(25)}
B {5(1), 5(2), 5(3), … , 5(10)} Elements common to both sets is A B {10, 20, 30, 40, 50}. Stating n(A B) 25 10 35 has included 5 integers that have been counted twice.
b. n(A B) n(A) n(B) n(A B)
25 10 5 n(A B) 30.
b. If the letters are unique then the first position can
be any one of 26 letters, and for each of these the second letter can be any one of the remaining 25 letters, and for each of these the third letter can be any one of the remaining 24 letters, and the fourth letter can be selected from the remaining 23 letters. Therefore the number of four-letter passwords is 26 · 25 · 24 · 23 358 800. c. The number of passwords with no a is 254.
Therefore the number with at least one a is 264 254 66 351. 8. The paths will be of 4 forms. There is one way of
going directly from A to E. In A _ E, the second letter can be any one of 3 letters, therefore there are 3 paths of this form. In A _ _ E, the second position can be any one of 3 letters and for each of these the third position is any one of the 2 remaining letters. Therefore there are 3 2 6 paths of the form A _ _ E. A _ _ _ E will yield 3 · 2 · 1 6 different paths of this form, therefore the number of different paths from A to E is 1 3 6 6 16. 9. The final digit must be even. There are four
possibilities, 2, 4, 6, 8. If the final digit is 2 or 4, then the first digit can be any of 5, 6, 7, 8, 9, and there are 5 · 7 · 6 · 2 possible integers. If the final digit is 6 or 8, then there are only four possible choices for the first digit, and there are 4 · 7 · 6 · 2 possible integers. The total number of integers is 5 · 7 · 6 · 2 4 · 7 · 6 · 2 756. 10. Let A represent the set of integers between 1 and 1000
that do not contain a 7, and An represent the set of n digit numbers that do not contain a 7. Now A1 {2, 3, 4, 5, 6, 8, 9} therefore n(A1) 7. n(A2) 8 9 72. (The first digit can be any of the digits from the set {1, 2, 3, 4, 5, 6, 8, 9}, and for each of these the second digit can be any of the digits from
7. The password is a sequence of four letters from the
alphabet with repeated letters allowed. a. The number of passwords is
26 · 26 · 26 · 26 264 456 976. (Each position can be any one of the 26 letters.)
158 Chapter 10: Introduction to Counting
the set {0, 1, 2, 3, 4, 5, 6, 8, 9}.) Similarly n(A3) 8 · 9 · 9 648. Therefore n(A) n(A1) n(A2) n(A3) 7 72 648 n(A) 727.
Chapter 10 • Introduction to Counting Solutions for Selected Problems
d. Counting the number of integers ending in 9 we
have from each of 10 rows, 10 such integers: 9, 19, 29, … , 99 → 10 109, 119, 129, … , 199 → 10 209 → 10 .. .. . . 909, 919, … , 999 → 10 therefore n(H ) 100 and n(H) n(U) n(H ) 1000 100 n(H) 900.
Exercise 10.1 11. a. The result of the draw will form three-digit
numbers of the form 100a 10b c, a, b, c {1, 2, 3, … , 9} and a ≠ b ≠ c. b. Since the ball labelled 4 is selected first, the second
ball can be any of the remaining eight, and for each of these, the third ball can be any of the remaining seven, giving 8 7 56 subsets. Therefore n(A) 56. A similar argument applies when the second and third balls drawn are 4s, hence n(B) 3 56 168.
14. Letters A, B, and C are placed in envelopes a, b, and c.
Let the ordered triple (x, y, z) mean letter A is in envelope x, B in y, and C in z. The universal set will be U {(a, b, c), (a, c, b), (b, a, c), (b, c, a), (c, a, b), (c, b, a)}. No letters to the correct person will be the subset {(b, c, a,), (c, a, b)}.
12. a. The three-digit number will be of the form
100a 10b c, a, b, c {1, 2, 3, … , 9}. b. With the first ball labelled 4, the second ball can be
any of the balls labelled 1 through 9, and for each of these, the third ball can be any of the balls labelled one through nine, hence n(A) 9 9 81. The number of elements in U is n(U1) 9 · 9 · 9 729. (We get this from the argument that the first ball can be any of the nine. Since it is now replaced, the second can be any of nine as will the third after replacement of the second.) Now the number of elements in U, where no 4 is drawn, will be 8 · 8 · 8 512. (Each of the first, second, and third draws can be any of the balls numbered 1, 2, 3, 5, 6, 7, 8, 9). The number of three-digit numbers when 4 is selected will be n(B) 93 83 217. n(U1) > n(U) since U is a subset of U1. 13. U {1, 2, 3, … , 1000}. a. The integers divisible by 7 in factored form are
7(1), 7(2), 7(3), … , 7(142). 7 142 994, which is the lowest multiple of 7 less than 1000. n(E) 142. b. The perfect squares are 12, 22, 32, … , 312.
312 961 and n(F) 31. c. The integers divisible by 3 are
y
15.
(1, 1)
1 V V
x 1
Exercise 10.2 5. If A and B are disjoint, then n(A B) n(A) n(B).
If A and B have common elements, n(A B) ≠ 0, then n(A B) < n(A) n(B). Therefore n(A B) n(A) n(B).
8. With A and B disjoint, there are no elements common
to both A and B. The number of elements in the union of these two sets is the sum of the number of elements in both sets.
3(1), 3(2), 3(3), … , 3(333) therefore n(G) n(u) n(G ) 1000 333 n(G) 667.
Chapter 10: Introduction to Counting 149
11. Let the committee with two girls be P, one boy and
one girl Q, and two boys R. P {AB, AC, BC} Q {AD, AE, AF, BD, BE, BF, CD, CE, CF} R {DE, DF, EF} u P Q R. 13.
V: contain at least one 5. W: contain at least one 6. The complement of V W, V W is the set of twodigit integers that do not contain the digits 5 or 6. n(u) 9 10 90. n(V W ) 7 8 56 (the first digit is any one of 1, 2, 3, 4, 7, 8, 9, and for each of these the second digit can be any one of 0, 1, 2, 3, 4, 7, 8, 9). Therefore n(V W) n(U) n(V V W ) 90 56 n(V V W) 34.
j 4
5
6
7
8
3
4
5
6
7
2
3
4
5
6
1
2
3
4
5
1
2
3
4
i
7. Let A be the number of integers divisible by 3.
The labelling of a point represents i j c. c. All of the subsets in b are disjoint. d. The union of the subsets in b includes all of the
elements in P.
37 take Business 101, of which 42 19 23 are girls, hence 14 are boys. 14 boys take Business 101. A
B
B
A
10. Since the Ei, i 0, 1, 2, 3, are disjoint sets and
B
U E0 E1 E2 E3 then n(U) n(E0) n(E1) n(E2) n(E3).
AB
AB
A
A {3(1), 3(2), 3(3), … , 3(10)} therefore n(A) 10 therefore n(A ) n(U) n(A) 30 10 n(A ) 20. 8. Of 90 students, 42 are girls, therefore 48 are boys. Also
15. Consider n(A B) ≠ 0.
A
6. U: two-digit integers.
A
B
A
B
B
16. U (A B) (A B) (A B) (A B).
12. There are 365 days in a non-leap year. 365
7(52) 1, which gives 52 2 104 days that fall on a weekend. The extra day can fall on any day of the week. If it falls on a Saturday or Sunday there will be 104 1 105 days falling on a weekend, which is the maximum number possible.
13. a. The numbers divisible by 5, set A, are
Exercise 10.3 5. The ten numbers that start with 7 are 70, 71, 72, … ,
77, 78, 79, and those that end in 7 are 17, 27, 37, … , 77, 87, 97. The 77 is in both sets was counted twice.
A {5(1), 5(2), 5(3), … , 5(200)} therefore n(A) 200. b. The numbers divisible by 7, set B, are
B {7(1), 7(2), 7(3), … , 7(142)} therefore n(B) 142. c. Numbers divisible by both 7 and 5 are divisible by
35, set C, C {35(1), 35(2), 35(3), … , 35(28)} n(C) 28 n(A B).
150 Chapter 10: Introduction to Counting
d. n(A B) n(A) n(B) n(A B)
Exercise 10.4
200 142 28 314. The number of numbers divisible by neither 5 nor 7, n(A B ) 1000 314, is 686.
4. The number of letters available for postal codes is
n(X) 26 7 19. The number of digits is n(x) 10. There are 19 choices for the first X and for each of these there are 10 choices for the first x, 19 for the second X, 10 for the second x, 19 for the third X and 10 for the third x. Then the number of postal codes is 10 · 19 · 10 · 19 · 10 · 19 193 103 6 859 000.
e. Of the 200 numbers divisible by 5, 28 are also divisible
by 7. Therefore there are 200 28 172 numbers divisible by 5 but not divisible by 7. 14. The number of integers divisible by 7, the set A, is
5. 3 10 10 10 10 10 10. The first digit can be any one
n(A) 142 (from 13(c)). The integers divisible by 13, set B, B {13(1), 13(2), 13(3), … , 13(76)} therefore n(B) 76. Now A B {91(1), 91(2), 91(3), … , 91(10)} and n(A B) 10 n(A B) n(A) n(B) n(A B) 142 76 10 208. The number of integers divisible by 7 or 13 is 208.
of 3, 5, or 6, 3 choices. For each of these, the second digit can be any of the 10 digits. Similarly, the remaining digits can be any of 10. Hence from the product rule there will be 3 106 seven-digit telephone numbers starting with a 3, 5, or 6. 6. 2 4 3 2 1 1
The first person on the left can be either of the two tabled people, 2 choices, and the position of the extreme left then is filled with the other of the two tallest people. The second can be filled with any of the four remaining people, the third with 3, fourth with 2 and fifth in 1. Hence there are 2 · 4 · 3 · 2 · 1 · 1 48 possible arrangements.
17. Let A be the set of integers divisible by 2, n(A) 500.
B is the set of integers divisible by 3, therefore n(B) 333. C is the set of integers divisible by 5, therefore n(C) 200. Now A B {6(1), 6(2), 6(3), … , 6(166)} and n(A B) 166. A C {10(1), 20, 30, … , 10(100)} and n(A C) 100. B C {15(1), 15(2), 15(3), … , 15(66)} and n(B C) 66. A B C {30(1), 30(2), 30(3), … , 30(33)} and n(A B C) 33. Now n(A B C) = n(A) n(B) n(C) n(A B) n(A C) n(B C) n(A B C) = 500 333 200 166 100 66 33 = 734. 734 integers are divisible by 2, 3, or 5.
18. Define n(E1) so that
e
There are 6 choices in which the first box can be filled, for each of these the second box can be filled in 5 ways, the fourth in 4 ways, fifth in 3 ways, sixth in 2 ways, and the seventh in 1 way. Therefore the number of anagrams is 6 · 5 · 4 · 3 · 2 · 1 720. 8. a. b. Since there are only three letters, C, A, and T,
once the first letter is chosen, there are only two choices for the second letter and then one for the third letter. From the product rule, the number of different “words” is 3 · 2 · 1 6.
mushrooms, sausage, and onions is the same had we chosen sausage, mushrooms, and onions. Repetition is included in the 504 pizzas. Each selection of 3 items gives rise to 6 arrangements, hence there would be 504 6 84 different pizzas possible.
n(EiEj) be the sum of all possible intersecting pairs Ei Ej, 1 i, j n, i < j. n(EiEjEk) be the sum of all possible intersecting triples Ei Ej Ek, i 1, k n, i < j < k, and so on. Then n(Ei Ej Ek … En)
10. a. A possible answer sheet is T T F F F T F T T T.
= n(Ei) n(EiEj) n(EiEjEk) n(EiEjEkEl) … (1)
n
n(EiEjEk … En).
i
9. The product rule implies order. Choosing a pizza with
n(Ei) n(E1) n(E2) n(E3) … n(En)
–1
7.
b. Since each question can be either True or False,
there will be 210 1024 different answer sheets.
Chapter 10: Introduction to Counting 151
11. Since there are five possibilities for each question,
there are a possible 57 78 125 possible answer sheets. Since there are 30 000 students, every answer sheet could be different. 12. Consider a, e, i, o, and u as the only vowels for this
exercise. a. U {aab, pqr}
A {eez, ibc} B {pqr, pss} C {xyz, mno}
b. From the product law we have:
n(U) 26 · 26 · 26 17 576 n(A) 5 · 26 · 26 3380 n(B) 5 · 5 · 5 125 n(C) 26 · 25 · 24 15 600 c. n(A B) 0, since the acronym must start with
a vowel and the only letters that can be used are p, q, r, s, and t, none of which are vowels. d. A B represents the acronyms that start with
a vowel or are made up using only the letters p, q, r, s, and t. e. n(A B) n(A) n(B) n(A B)
3380 125 0 3505.
f. The number of acronyms in which all letters are
different is 26 · 25 · 24 15 600. The number of acronyms that use one letter at least twice is n(u) 15 600 1976. 13. Letters a, b, c, d, e, f are rearranged in n(u)
6 · 5 · 4 · 3 · 2 · 1 720 ways. The number of words that being with a is determined by the product rule as 1 · 5 · 4 · 3 · 2 · 1 120. Therefore the number of words that do not begin with a is 720 120 600. Or the first letter any of b, c, d, e, f and the product rule gives 5 · 5 · 4 · 3 · 2 · 1 600.
14. The first letter is any of the given 6, the second any
of 5, the third any of 4, and the fourth any of the remaining 3. From the product rule the number of four-letter words is 6 · 5 · 4 · 3 360. If the word begins with a, then the second letter is any of the remaining 5, the third any of 4, and the fourth any of 3, giving 1 · 5 · 4 · 3 60 words starting with a. 15 a. 9 · 10 · 10 · 10. The first digit can be any of 1, 2, 3,
4, 5, 6, 7, 8, or 9, 9 choices. The second, third, and fourth places can be any of the 10 digits, hence there are 9 · 10 · 10 · 10 9000 such integers.
b. The units digit is either 7 or 8, 2 choices. Hence
from the product rule we have 9 · 10 · 10 · 2 1800 integers ending in 7 or 8. c. If there are no repeated digits, then the second digit
has 9 possibilities, the third 8, and the fourth 7, giving 9 · 9 · 8 · 7 4536 integers. d. The number with repeated digits will be
9000 4536 4464. 16. There will be 26 26 10 62 symbols available. a. _ _ _ _ _ _ _ _ Each position can be any of the 62
symbols (with repetition) hence there will be 628 possible passwords. b. 10 _ _ _ _ _ _ 10 The first and last position have 10
choices. The remaining positions can be any of the 62 symbols, hence there are 626 102 passwords. c. With no repeated digits, there will be 6261 · 60 ·
59 · 58 · 57 · 56 · 55 different passwords. d. The number of passwords with no 9 is 618.
Therefore with at least one 9 there will be 628 618 passwords. 17. a. Represent each divisor as an ordered pair,
i.e., (a, b) 2a 3b. With 0 a 2 and 0 b 1 (0, 0) 1, (1, 0) 2, (2, 0) 4 (0, 1) 3, (1, 1) 6, (2, 1) 12. b. There are six sequences that can be formed as
shown in (a) as ordered pairs. c. 12 has 6 divisors. d. 144 24 · 32
Integer divisors of 144 can be written in the form 2a · 3b where 0 a 4, 0 b 2. There are 5 possible values of a, the first member of the sequence; and for each of these there are 3 possible values for b, the second member of the sequence; hence there will be 5 3 15 integer divisors of 144. e. For odd divisors, there can be no even factors,
hence the sequence has 0 as its first term, the second term is either 0, 1, or 2; hence there are 3 odd divisors. 18. a. 64 800 25 · 34 · 52.
Here we form three-term sequences where there are 6 choices for the first term (0, 1, 2, 3, 4, and 5); and for each of these, 5 choices for the second term and 3 for the third. Hence there are 6 · 5 · 3 90 integer divisors of 64 800. b. For even divisors, the first term of our sequence
152 Chapter 10: Introduction to Counting
must be one of 1, 2, 3, 4, or 5; 5 choices, hence there are 5 · 5 · 3 75 even divisors of 64 800.
19. a. n 2a3b5c
a 1, b 1, c 1. The first term of the three-term sequence has (a 1) choices; for each of these, the second term has (b 1), and the third term has (c 1). Hence there are (a 1)(b 1)(c 1) integer divisors of n.
365 · 364 · 363 · … · (365 n) 365
1 2
b. Now 1 > . n
365 · 364 · 363 · … · (365 n) 1 Therefore < 365n 2 for n 22, the fraction is 0.5243.
b. For an even divisor, a two must be included.
Therefore the first term of the sequence has a choices and there will be a(b 1)(c 1) even divisors of n. The fraction of even divisors is
Exercise 10.5 2. Sequence of length 6 using the 10 digits and 26
letters. If the letter is in the final position, there will be 26 · 10 · 9 · 8 · 7 · 6 passwords. The number of passwords will be the same if the letter is in the second, third, fourth, fifth, or sixth position. Therefore the number of passwords is 26 · 10 · 9 · 8 · 7 · 6 6 4 717 440.
a(b 1)(c 1) a . (a 1)(b 1)(c 1) a1 20. a. The first term of the sequence can be filled in m
ways; and for each of these, the second in (m 1) ways, and for each of these the third in (m 2) ways. From the product rule there will be m(m 1)(m 2) sequences of length three.
3. The number of binary sequences of length n is 2n. The
number of binary sequences with length of at most 5 will be the sum of the sequences having length 1, 2, 3, 4, and 5, i.e., 21 22 23 24 25 = 2 4 8 16 32 = 62.
b. Since the symbols can be repeated, the number of
sequences will be m · m · m m . 3
21. In a sequence of length r and the product rule there
will be r factors in the product, the last one being [m (r 1)] (m r 1). Hence the number of sequences will be m(m 1)(m 2) … (m r 1). With repetition allowed there will be mr sequences of length r. 22. a. Since the five people can have birthdays on the
same day, the number of sequences will be 3655. b. If the birthdays are distinct, the number of
sequences will be 365 · 364 · 363 · 362 · 361. Percent having distinct birthdays will be 365 · 364 · 363 · 362 · 361 0.972864 3655 97.29%. c. With two or more birthdays on the same day, we
have 100% 97.29% 2.71%. 23. a. The number of sequences that are possible is 365n.
With different birth dates, the number of sequences will be 365 · 364 · 363 · … · (365 n 1). With two or more birthdays on the same day, the fraction is 365 · 364 · 363 · … · (366 n) 1 . 365n
4.
0 22222 The number of binary sequences of length 6 that begins with a zero is 25. Similarly, the number of sequences of length 7 and 8 beginning with zero will be 26 and 27. Therefore the sum is 25 26 27 = 25 (1 2 4) = 25 7 = 224.
5. a. The number of one-letter words is 4; two-letter
words, 4 3 12; three-letter words, 4 · 3 · 2 24; and four-letter words, 4 · 3 · 2 · 1 24. The total number of words is 64. b. Number of words ending in a:
one-letter words 1; two-letter words, 3 · 1 3; three-letter words, 3 · 2 · 1 6; and four-letter words, 3 · 2 · 1 · 1 6. The number of words ending in a is 16. 1 Or of the words end in each of 4 1 a, b, c, or d. Therefore of 64 16 4 words end in a.
Chapter 10: Introduction to Counting 153
c. Number of words that do not contain an a:
one-letter words 3; two-letter words, 3 · 2 6; three-letter words, 3 · 2 · 1 6; and four-letter words 0. The number that do not contain an a is 15. Therefore the number of words that do contain an a is 64 15 49. 6. a. If repetition of letters is allowed,
one-letter word 4; two-letter word, 42 16; three-letter word 43 64; and four-letter word, 44 256. The number of words that can be created will be 340. b. Number of words that end in a:
one-letter: a 1; two-letter: _ a, 4 1 4; three-letter: _ _ a, 4 4 1 16; and four-letter: _ _ _ a, 43 1 64. The number of words ending in a is 85. c. Number of words that do not contain a:
one-letter: _ 3; two-letter: _ _ 3 3 9; three-letter: _ _ _ 33 27; and four-letter: _ _ _ _ 34 81. The number of words with no a is 120. Therefore the number of words containing an a will be 340 120 220. 7. The rectangular arrays that are possible are 1 by 10, 2
by 5, 5 by 2, and 10 by 1. In each array the numbers 1 to 10 can be arranged in 10 · 9 · 8 · 7 · 6 · 5 · 4 · 3 · 2 · 1 3 628 800 ways. There will be 3 628 800 4 14 515 200 ways of storing the numbers. 8. The number of three-letter words possible is 263.
The number of three-letter words that do not contain either a, e, i, o, u, or y is 203. Therefore the number of three-letter words that contain at least one of a, e, i, o, u, or y is 263 203 9576. Similarly, the number of four-letter words would be 264 204 296 976 and five-letter words would be 265 205 8 681 376. The number of three-, four-, or five-letter words will be 9576 296 976 8 681 376 8 987 928.
9. To determine the number of 5s, we look at the number
of terms that are divisible by 5x, x 1. x 1, 5, 5(2), 5(3), … , 5(200): when x 1, there are 200 5s. x 2, 25, 25(2), 25(3), … , 25(40): when x 2, there are an additional 40 5s. x 3, 125, 125(2), 125(3), 125(4), … , 125(8): when x 3, there are an additional 8 5s. x 4, 625: when x 4, there is 1 additional 5. Therefore the total number of 5s in the set is 200 40 8 1 249. 10. Let P be the set of sequences starting with A.
Therefore P {ABCDEF, ABCDFE, …} n(P) 1 5 · 4 · 3 · 2 · 1 120 Q is the set ending with F. Therefore Q {ABCDEF, BACDEF, …} n(Q) 5 · 4 · 3 · 2 · 1 · 1 120 P Q {ABCDEF, ACBDEF, …} n(P Q) 1 · 4 · 3 · 2 · 1 · 1 24 Therefore the number of sequences that start with A or end with F is n(P Q) n(P) n(Q) n(P Q)) 120 120 24 216. 11. Represent the set of integers with n distinct digits by
An, 1 n 3. Now n(A1) 9 n(A2) 9 · 9 81. (The first digit can be any of {1, 2, 3, … , 9}: 9 choices, and for each of these there are 9 choices for the second digit: one of the 8 not chosen for the first digit plus 0). n(A3) 9 · 9 · 8 648. The four-digit integers must start with 1 (since we are looking for integers between 1 and 2000), the second, third, and fourth digits are chosen from the remaining 9, 8, and 7 digits. Therefore we have 1 · 9 · 8 · 7 504 allowable fourdigit integers. Therefore there are 9 81 648 504 1242 positive integers between 1 and 2000 inclusive having distinct digits. Let On represent the set of integers with n distinct digits that will be odd. 1 n 3 O1 {1, 3, 5, 7, 9}, therefore n(O1) 5 n(O2) 8 · 5 40. (The last digit is odd, the first can be chosen by the remaining 8 digits. The first digit cannot be zero.) n(O3) 8 · 8 · 5 320. 1 8 7 4. The first digit must be 1, the units digit can be any one of {3, 5, 7, 9}, 4 choices, the second digit and the third digit can be any one of the remaining 8 and 7 digits.
154 Chapter 10: Introduction to Counting
Therefore there will be 224 allowable odd four-digit integers. Total number of odd integers is 5 40 320 224 589. 589 Fraction that is odd is . 1242 12. a. Choosing Cat there are 3 · 2 · 1 6 sequences,
Mouse there are 5 · 4 · 3 60 sequences, and in Goldfish there are 8 · 7 · 6 336 sequences. There will be 6 60 336 402 sequences of length three.
b. Ending in S, choosing Cat there are O, Mouse there
are 4 · 3 · 1 12, and choosing Goldfish there are 7 · 6 · 1 42. There are 0 12 42 54 sequences of length three ending in S. c. Start with a vowel: from Cat there are
1 · 2 1 2, Mouse there are 3 · 4 · 3 36, and Goldfish there are 2 · 7 · 6 84. In all, 122 sequences of length three start with a vowel. d. The number of sequences of length three that do not contain O will be: from Cat, 6; Mouse, 4 · 3 · 2 24; and from Goldfish, 7 · 6 · 5 210; and in total 240. The number of sequences containing O will be 402 240 162. 13. a. Let Cn represent the set of sequences of length n.
n 1. Therefore C1 {0, 1, 2, … , 9} and n(C1) 10 C2 {10, 11, 12, … , 99} and n(C2) 102 C3 {100, 101, … , 999} and n(C3) 103 and so on to n(C10) 1010. n(U) 10 102 103 … 1010. There is a geometric sequence with a(rn 1) n(U) , a 10, r 10, n 10 r1 10(1010 1) therefore n(U) 9 n(U) 11111111110.
b. Let An represent the set of sequences of length n
having unique digits. n 1.
A1 {0, 1, 2, … , 9}, n(A1) 9 n(A2) 10 9 90 (first digit any of the 10
n(A7) n(A6) 4 604 800 n(A8) n(A7) 3 1 814 400 n(A9) n(A8) 2 3 628 800 n(A10) n(A9) 1 3 628 800. Therefore n(A) is the sum of the above. n(A2) 9 864 100. c. Let En represent the set of sequences of length n
that contain no zeros. Therefore
E1 {1, 2, 3, … , 9} and n(E1) 9 n(E2) 9 9 81, n(E3) 93, n(E4) 94, n(E5) 95, … , n(E10) 910 n(E) is the sum of the above. Therefore n(E) 9 92 93 … 910 9(910 1) 8 n(E) 3 922 632 450 n(B) n(U) n(E) n(B) 7 188 478 660. 14. a. The number of sequences of length 3 will be
r · r · r r3. The number of sequences of length 3 that do not contain an A will be (r 1)3. Therefore the number of sequences containing at least one A is r3 (r 1)3 r3 – (r3 3r2 3r – 1) r3 – r3 3r2 – 3r 1 3r2 3r 1. b. If no repetition of symbols is allowed, the number
of sequences of length 3 will be r(r 1)(r 2). Excluding A, there will be (r 1)(r 2)(r 3) sequences of length 3. Therefore the number of sequences containing at least one A is r (r 1)(r 2) (r 1)(r 2)(r 3)
available digits, for each of these we can choose
= (r 1)(r 2)[r (r 3)]
any of the remaining 9 digits). Similarly
= 3(r 1)(r 2)
n(A3) 10 · 9 · 8 720
= 3r2 9r 6.
n(A4) n(A3) 7 5040 n(A5) n(A4) 6 30 240 n(A6) n(A5) 5 151 200
Chapter 10: Introduction to Counting 155
15. Represent the set of arithmetic sequences (x, y, z),
x < y < z, of length 3 with common difference n by An. Therefore A1 {(1, 2, 3), (2, 3, 4), (3, 4, 5), … , (7, 8, 9)} therefore n(A1) 7 A2 {(1, 3, 5), (2, 4, 6), (3, 5, 7), … , (5, 7, 9)} therefore n(A2) 5 A3 {(1, 4, 7), (2, 5, 8), (3, 6, 9)} therefore n(A3) 3 A4 {(1, 5, 9)}, n(A4) 1. Now n(A1) n(A2) n(A3) n(A4) 16. But each sequence in An can be reversed, therefore the number of sequences of length 3 that forms an arithmetic progression is 16 2 32. 16. Let An represent the set of binary sequences of
length n. Therefore n(A1) 2 n(A2) 22 n(A3) 23 and so on, to n(Ak – 1) 2k – 1 and n(Ak) 2k. Now the number of binary sequences of length less than k is n(A1) n(A2) n(A3) … n(Ak – 1) 2 22 23 … 2k – 1 This is a geometric series with a 2, r 2, n k 1 therefore n(A1) n(A2) n(A3) … n(Ak – 1) 2(2k – 1 1) 2k 2 n(Ak) 2.
Review Exercise 3. a. U {A3A2K1, N5C2P2, …}
A {N2R3N1, N4L2N7, …} B {A3K5B8, N8H8T8, …} C {X1Y3A7, P3A4K2, …} D {N5C2R2, A4B5N3, …}
b. There are 26 7 19 letters and 9 digits that can
be used with repetitions, therefore n(U) 19 · 9 · 19 · 9 · 19 · 9 193 · 93 5 000 211.
156 Chapter 10: Introduction to Counting
(The first, third, and fifth positions can be any of the 19 letters, and for each of these the second, fourth, and sixth positions can be any of the 9 digits. From the product rule we have (9 19)3 possible postal codes) n(A) 1 · 9 · 19 · 9 · 19 · 9 192 · 93 263 169. (The first letter must be N, one choice, the others follow as for n(U).) n(B) 19 · 9 · 19 · 9 · 19 · 9 263 169. (The last position must be 8, one choice.) n(C) codes using the letter A. Let X be the set not using the letter A, therefore n(X) 18 · 9 · 18 · 9 · 18 · 9 183 · 93. Therefore n(C) n(U) n(X) 193 · 93 183 · 93 93(193 183 n(C) 748 683. The letter N can be in the first position. There will be 18 letters that can then be placed in the third and fifth positions, giving 1 · 9 · 18 · 9 · 18 · 9 postal codes starting with N. If N is in the third position there will be 18 · 9 · 1 · 9 · 18 · 9 postal codes, and if N is fifth, there are 18 · 9 · 18 · 9 · 1 · 9 postal codes, therefore n(D) 182 · 93 3 708588. c. The number of postal codes starting with N or
ending with 8 is n(A B). Now n(A B) n(A) n(B) n(A B) n(A B) 1 · 9 · 19 · 9 · 19 · 1. (The first and last positions have one choice each. The second and fourth can be any of the 9 allowable digits and the third and fifth can be any of the allowable 19 letters.) Therefore n(A B) 192 · 93 193 · 92 192 · 92 n(A B) 789 507. 4. a. U {012, 509, …}
A {035, 246, …} B {048, 572, …} C {037, 146, …}
b. n(U) 10 · 9 · 8 720.
(Choice of 10 digits in the first position, and for each of these, 9 digits for the second position and 8 for the final position.) n(A) 5 · 9 · 8 360. (The first digit is even, so can be any of the 5; the second digit can be any of the remaining 9; and the third has 8 choices.) n(B) 9 · 8 · 5 360.
(The last digit must be even, therefore there are 5 choices for the last position. The first position has 9 possibilities and the second has a choice of 8.) The number of sequences containing only odd digits is 5 · 4 · 3 60. Therefore the number of sequences containing an even digit is n(C) n(u) 60 n(C) 660. c. A B {064, 274, …}
n(A B) 5 · 8 · 4 160. (The first and last digits must be even, hence there are 5 and 4 choices for these positions. There will be 8 possible digits for the middle position.)
7. Let A represent the set of integers that contain the
digit 7 and An the set of integers of length n that contain the digit 7. Therefore A1 {7} and n(A1) 1 A2 {17, 27, 37, … , 67, 70, 71, … , 79, 87, 97} n(A2) 6 10 2 18. The number of three-digit integers is 9 · 10 · 10 900. The number of three-digit integers that do not contain a 7 is 8 · 9 · 9 648. Therefore n(A3) 900 648 252. Therefore n(A) 1 18 252 n(A) 271. 8. a. The number of three-digit PIN numbers is 103;
the number of four-digit PIN numbers is 104; therefore the number of PIN numbers available is 103 104 11 000.
5. The number of binary sequences of length 6 that start
with 1 and end in zero is 24 (1 _ _ _ _ 0). Similarly, the number starting with zero and ending in 1 is 24 (0 _ _ _ _ 1), and the number of sequences starting and ending with 1 is 24 (1 _ _ _ _ 1). Therefore the number of sequences starting or ending with one is 24 24 24 3 24. The number of binary sequences of length 6 is 26. 3 24 3 Therefore the required fraction is . 26 4 1 (The student’s argument that of the sequences start 2 with 1 includes sequences of the form 1 _ _ _ _ 0 and 1 1 _ _ _ _ 1, and that of the sequences end in 1 2 includes the sequences of the form 0 _ _ _ _ 1 and 1 _ _ _ _ 1. The form 1 _ _ _ _ 1 is included twice, 1 which occurs in of the sequences. Hence he must 4 1 subtract from his sum of 1, giving the correct 4 3 fraction of .) 4 6. Local telephone numbers consist of 7 digits, the first
selected from the digits 2 to 9, 8 choices. The remaining 6 digits can be any of the 10 numbers from the set {0, 1, 2, … , 9}, therefore the number of usable telephone numbers is 8 106. The number of telephone numbers ending in 99 will be 8 104 (8 · 10 · 10 · 10 · 10 · 1 · 1; first digit selected from 8 available, last two digits must be 9, 1 choice for each, the other 4 digits can be selected from the 10 available with repetitions allowed). Fraction of numbers ending in 99 is 8 104 1 6 . 8 10 100
b. The number of three-digit PIN numbers starting
with 2 is 1 · 10 · 10 100 and four-digit PIN numbers starting with 2 is 1 · 10 · 10 · 10 1000. Therefore the number of PIN numbers starting with 2 is 100 1000 1100. c. The number of PIN numbers of length 3 that do not
have a 2 is 9 · 9 · 9 93 and of length 4 is 94, therefore the number of PIN numbers that do not have a two is 93 94 93 (1 9) 10 · 93. The number of PIN numbers having at least one two will be 11000 10 · 93 10(1100 729) 10(371) 3710.
Chapter 10 Test 1. U {1, 2, 3, … , 999} a. A is a subset of U whose elements are not a
multiple of 5. b.
A {5, 5(2), 5(3), … , 5(199)} therefore n(A) 199. n(A ) n(U) n(A) 999 199 n(A ) 800.
2. The Product Rule: If the first of two tasks can be done
in p ways, and for each of these ways, the second task can be done in q ways, then together the two tasks can be done in p · q ways.
Chapter 10: Introduction to Counting 157
3. a. A B is the set of six-letter words ending in -id
or -ic. A B is the set of six-letter words ending in -id and -ic. (This is not possible, hence n(A B) 0.) b.
n(A B) n(A) n(B) n(A) 4 · 3 · 2 · 1 · 1 · 1 24 n(B) 4 · 3 · 2 · 1 · 1 · 1 24 therefore n(A B) 48. (For n(A), since the last two letters must be -id, there is only one choice for the last two positions. The first letter can be any of the 4 remaining and for each of these the second, third, and fourth are selected from the remaining 3, 2, and 1 letters, hence n(A) 4 · 3 · 2 · 1 · 1 · 1 24. The argument for n(B) is similar.)
4. If A is first, the second letter can be any of the
remaining 6 letters (B, C, D, E, F, G), and for each of these selections the third letter is any of the remaining 5. Therefore the number of words starting with A is 1 · 6 · 5 30. Similarly, if B is first there will be 30 words. Therefore the number of arrangements with A or B first will be 60. 5. Binary sequences starting and ending with 1 will be of
the form 1 _ _ _ 1, of which there are 23. Starting and ending with 0 will be of the form 0 _ _ _ 0, of which there are 23. Therefore the number of binary sequences of length 5 that start or end in the same number is 23 23 16. 6. a. A {2(1), 2(2), 2(3), 2(4), 2(5), … , 2(25)}
B {5(1), 5(2), 5(3), … , 5(10)} Elements common to both sets is A B {10, 20, 30, 40, 50}. Stating n(A B) 25 10 35 has included 5 integers that have been counted twice.
b. n(A B) n(A) n(B) n(A B)
25 10 5 n(A B) 30.
b. If the letters are unique then the first position can
be any one of 26 letters, and for each of these the second letter can be any one of the remaining 25 letters, and for each of these the third letter can be any one of the remaining 24 letters, and the fourth letter can be selected from the remaining 23 letters. Therefore the number of four-letter passwords is 26 · 25 · 24 · 23 358 800. c. The number of passwords with no a is 254.
Therefore the number with at least one a is 264 254 66 351. 8. The paths will be of 4 forms. There is one way of
going directly from A to E. In A _ E, the second letter can be any one of 3 letters, therefore there are 3 paths of this form. In A _ _ E, the second position can be any one of 3 letters and for each of these the third position is any one of the 2 remaining letters. Therefore there are 3 2 6 paths of the form A _ _ E. A _ _ _ E will yield 3 · 2 · 1 6 different paths of this form, therefore the number of different paths from A to E is 1 3 6 6 16. 9. The final digit must be even. There are four
possibilities, 2, 4, 6, 8. If the final digit is 2 or 4, then the first digit can be any of 5, 6, 7, 8, 9, and there are 5 · 7 · 6 · 2 possible integers. If the final digit is 6 or 8, then there are only four possible choices for the first digit, and there are 4 · 7 · 6 · 2 possible integers. The total number of integers is 5 · 7 · 6 · 2 4 · 7 · 6 · 2 756. 10. Let A represent the set of integers between 1 and 1000
that do not contain a 7, and An represent the set of n digit numbers that do not contain a 7. Now A1 {2, 3, 4, 5, 6, 8, 9} therefore n(A1) 7. n(A2) 8 9 72. (The first digit can be any of the digits from the set {1, 2, 3, 4, 5, 6, 8, 9}, and for each of these the second digit can be any of the digits from
7. The password is a sequence of four letters from the
alphabet with repeated letters allowed. a. The number of passwords is
26 · 26 · 26 · 26 264 456 976. (Each position can be any one of the 26 letters.)
158 Chapter 10: Introduction to Counting
the set {0, 1, 2, 3, 4, 5, 6, 8, 9}.) Similarly n(A3) 8 · 9 · 9 648. Therefore n(A) n(A1) n(A2) n(A3) 7 72 648 n(A) 727.
