Chapter 1
Problems
1. (a) By the generalized basic principle of counting there are
26 ⋅ 26 ⋅ 10 ⋅ 10 ⋅ 10 ⋅ 10 ⋅ 10 = 67,600,000
(b) 26 ⋅ 25 ⋅ 10 ⋅ 9 ⋅ 8 ⋅ 7 ⋅ 6 = 19,656,000
2. 64 = 1296
3. An assignment is a sequence i1, …, i20 where ij is the job to which person j is assigned. Since
only one person can be assigned to a job, it follows that the sequence is a permutation of the
numbers 1, …, 20 and so there are 20! different possible assignments.
4. There are 4! possible arrangements. By assigning instruments to Jay, Jack, John and Jim, in
that order, we see by the generalized basic principle that there are 2 ⋅ 1 ⋅ 2 ⋅ 1 = 4 possibilities.
5. There were 8 ⋅ 2 ⋅ 9 = 144 possible codes. There were 1 ⋅ 2 ⋅ 9 = 18 that started with a 4.
6. Each kitten can be identified by a code number i, j, k, l where each of i, j, k, l is any of the
numbers from 1 to 7. The number i represents which wife is carrying the kitten, j then
represents which of that wife’s 7 sacks contain the kitten; k represents which of the 7 cats in
sack j of wife i is the mother of the kitten; and l represents the number of the kitten of cat k in
sack j of wife i. By the generalized principle there are thus 7 ⋅ 7 ⋅ 7 ⋅ 7 = 2401 kittens
7. (a) 6! = 720
(b) 2 ⋅ 3! ⋅ 3! = 72
(c) 4!3! = 144
(d) 6 ⋅ 3 ⋅ 2 ⋅ 2 ⋅ 1 ⋅ 1 = 72
8. (a) 5! = 120
7!
(b) = 1260
2!2!
11!
(c) = 34,650
4!4!2!
7!
(d) = 1260
2!2!
(12)!
9. = 27,720
6!4!
10. (a) 8! = 40,320
(b) 2 ⋅ 7! = 10,080
(c) 5!4! = 2,880
(d) 4!24 = 384
Chapter 1 1
,11. (a) 6!
(b) 3!2!3!
(c) 3!4!
12. (a) 305
(b) 30 ⋅ 29 ⋅ 28 ⋅ 27 ⋅ 26
20
13.
2
52
14.
5
10 12
15. There are possible choices of the 5 men and 5 women. They can then be paired up
5 5
in 5! ways, since if we arbitrarily order the men then the first man can be paired with any of
10 12
the 5 women, the next with any of the remaining 4, and so on. Hence, there are 5!
5 5
possible results.
6 7 4
16. (a) + + = 42 possibilities.
2 2 2
(b) There are 6 ⋅ 7 choices of a math and a science book, 6 ⋅ 4 choices of a math and an
economics book, and 7 ⋅ 4 choices of a science and an economics book. Hence, there are
94 possible choices.
17. The first gift can go to any of the 10 children, the second to any of the remaining 9 children,
and so on. Hence, there are 10 ⋅ 9 ⋅ 8 ⋅ ⋅ ⋅ 5 ⋅ 4 = 604,800 possibilities.
5 6 4
18. = 600
2 23
8 4 8 2 4
19. (a) There are + = 896 possible committees.
3 3 3 1 2
8 4 8 2 4
There are that do not contain either of the 2 men, and there are that
3 3 3 1 2
contain exactly 1 of them.
6 6 2 6 6
(b) There are + = 1000 possible committees.
3 3 1 23
2 Chapter 1
, 7 5 7 5 7 5 7 5
(c) There are + + = 910 possible committees. There are in
3 3 2 3 3 2 3 3
7 5
which neither feuding party serves; in which the feuding women serves; and
2 3
75
in which the feuding man serves.
3 2
6 2 6 6 6
20. + , +
5 1 4 5 3
7!
21. = 35. Each path is a linear arrangement of 4 r’s and 3 u’s (r for right and u for up). For
3!4!
instance the arrangement r, r, u, u, r, r, u specifies the path whose first 2 steps are to the right,
next 2 steps are up, next 2 are to the right, and final step is up.
4! 3!
22. There are paths from A to the circled point; and paths from the circled point to B.
2 !2 ! 2!1!
Thus, by the basic principle, there are 18 different paths from A to B that go through the
circled piont.
23. 3!23
52
25.
13, 13, 13, 13
12 12!
27. =
3, 4, 5 3!4!5!
28. Assuming teachers are distinct.
(a) 48
8 8!
(b) = = 2520.
2, 2, 2, 2 (2)
4
29. (a) (10)!/3!4!2!
3 7!
(b) 3
2 4 !2 !
30. 2 ⋅ 9! − 228! since 2 ⋅ 9! is the number in which the French and English are next to each other
and 228! the number in which the French and English are next to each other and the U.S. and
Russian are next to each other.
Chapter 1 3
, 31. (a) number of nonnegative integer solutions of x1 + x2 + x3 + x4 = 8.
11
Hence, answer is = 165
3
7
(b) here it is the number of positive solutions—hence answer is = 35
3
32. (a) number of nonnegative solutions of x1 + … + x6 = 8
13
answer =
5
(b) (number of solutions of x1 + … + x6 = 5) × (number of solutions of x1 + … + x6 = 3) =
10 8
5 5
33. (a) x1 + x2 + x3 + x4 = 20, x1 ≥ 2, x2 ≥ 2, x3 ≥ 3, x4 ≥ 4
Let y1 = x1 − 1, y2 = x2 − 1, y3 = x3 − 2, y4 = x4 − 3
y1 + y2 + y3 + y4 = 13, yi > 0
12
Hence, there are = 220 possible strategies.
3
15
(b) there are investments only in 1, 2, 3
2
14
there are investments only in 1, 2, 4
2
13
there are investments only in 1, 3, 4
2
13
there are investments only in 2, 3, 4
2
15 14 13 12
+ + 2 + = 552 possibilities
2 2 2 3
4 Chapter 1
Problems
1. (a) By the generalized basic principle of counting there are
26 ⋅ 26 ⋅ 10 ⋅ 10 ⋅ 10 ⋅ 10 ⋅ 10 = 67,600,000
(b) 26 ⋅ 25 ⋅ 10 ⋅ 9 ⋅ 8 ⋅ 7 ⋅ 6 = 19,656,000
2. 64 = 1296
3. An assignment is a sequence i1, …, i20 where ij is the job to which person j is assigned. Since
only one person can be assigned to a job, it follows that the sequence is a permutation of the
numbers 1, …, 20 and so there are 20! different possible assignments.
4. There are 4! possible arrangements. By assigning instruments to Jay, Jack, John and Jim, in
that order, we see by the generalized basic principle that there are 2 ⋅ 1 ⋅ 2 ⋅ 1 = 4 possibilities.
5. There were 8 ⋅ 2 ⋅ 9 = 144 possible codes. There were 1 ⋅ 2 ⋅ 9 = 18 that started with a 4.
6. Each kitten can be identified by a code number i, j, k, l where each of i, j, k, l is any of the
numbers from 1 to 7. The number i represents which wife is carrying the kitten, j then
represents which of that wife’s 7 sacks contain the kitten; k represents which of the 7 cats in
sack j of wife i is the mother of the kitten; and l represents the number of the kitten of cat k in
sack j of wife i. By the generalized principle there are thus 7 ⋅ 7 ⋅ 7 ⋅ 7 = 2401 kittens
7. (a) 6! = 720
(b) 2 ⋅ 3! ⋅ 3! = 72
(c) 4!3! = 144
(d) 6 ⋅ 3 ⋅ 2 ⋅ 2 ⋅ 1 ⋅ 1 = 72
8. (a) 5! = 120
7!
(b) = 1260
2!2!
11!
(c) = 34,650
4!4!2!
7!
(d) = 1260
2!2!
(12)!
9. = 27,720
6!4!
10. (a) 8! = 40,320
(b) 2 ⋅ 7! = 10,080
(c) 5!4! = 2,880
(d) 4!24 = 384
Chapter 1 1
,11. (a) 6!
(b) 3!2!3!
(c) 3!4!
12. (a) 305
(b) 30 ⋅ 29 ⋅ 28 ⋅ 27 ⋅ 26
20
13.
2
52
14.
5
10 12
15. There are possible choices of the 5 men and 5 women. They can then be paired up
5 5
in 5! ways, since if we arbitrarily order the men then the first man can be paired with any of
10 12
the 5 women, the next with any of the remaining 4, and so on. Hence, there are 5!
5 5
possible results.
6 7 4
16. (a) + + = 42 possibilities.
2 2 2
(b) There are 6 ⋅ 7 choices of a math and a science book, 6 ⋅ 4 choices of a math and an
economics book, and 7 ⋅ 4 choices of a science and an economics book. Hence, there are
94 possible choices.
17. The first gift can go to any of the 10 children, the second to any of the remaining 9 children,
and so on. Hence, there are 10 ⋅ 9 ⋅ 8 ⋅ ⋅ ⋅ 5 ⋅ 4 = 604,800 possibilities.
5 6 4
18. = 600
2 23
8 4 8 2 4
19. (a) There are + = 896 possible committees.
3 3 3 1 2
8 4 8 2 4
There are that do not contain either of the 2 men, and there are that
3 3 3 1 2
contain exactly 1 of them.
6 6 2 6 6
(b) There are + = 1000 possible committees.
3 3 1 23
2 Chapter 1
, 7 5 7 5 7 5 7 5
(c) There are + + = 910 possible committees. There are in
3 3 2 3 3 2 3 3
7 5
which neither feuding party serves; in which the feuding women serves; and
2 3
75
in which the feuding man serves.
3 2
6 2 6 6 6
20. + , +
5 1 4 5 3
7!
21. = 35. Each path is a linear arrangement of 4 r’s and 3 u’s (r for right and u for up). For
3!4!
instance the arrangement r, r, u, u, r, r, u specifies the path whose first 2 steps are to the right,
next 2 steps are up, next 2 are to the right, and final step is up.
4! 3!
22. There are paths from A to the circled point; and paths from the circled point to B.
2 !2 ! 2!1!
Thus, by the basic principle, there are 18 different paths from A to B that go through the
circled piont.
23. 3!23
52
25.
13, 13, 13, 13
12 12!
27. =
3, 4, 5 3!4!5!
28. Assuming teachers are distinct.
(a) 48
8 8!
(b) = = 2520.
2, 2, 2, 2 (2)
4
29. (a) (10)!/3!4!2!
3 7!
(b) 3
2 4 !2 !
30. 2 ⋅ 9! − 228! since 2 ⋅ 9! is the number in which the French and English are next to each other
and 228! the number in which the French and English are next to each other and the U.S. and
Russian are next to each other.
Chapter 1 3
, 31. (a) number of nonnegative integer solutions of x1 + x2 + x3 + x4 = 8.
11
Hence, answer is = 165
3
7
(b) here it is the number of positive solutions—hence answer is = 35
3
32. (a) number of nonnegative solutions of x1 + … + x6 = 8
13
answer =
5
(b) (number of solutions of x1 + … + x6 = 5) × (number of solutions of x1 + … + x6 = 3) =
10 8
5 5
33. (a) x1 + x2 + x3 + x4 = 20, x1 ≥ 2, x2 ≥ 2, x3 ≥ 3, x4 ≥ 4
Let y1 = x1 − 1, y2 = x2 − 1, y3 = x3 − 2, y4 = x4 − 3
y1 + y2 + y3 + y4 = 13, yi > 0
12
Hence, there are = 220 possible strategies.
3
15
(b) there are investments only in 1, 2, 3
2
14
there are investments only in 1, 2, 4
2
13
there are investments only in 1, 3, 4
2
13
there are investments only in 2, 3, 4
2
15 14 13 12
+ + 2 + = 552 possibilities
2 2 2 3
4 Chapter 1
