Bogart-81046 book April 27, 2005 17:12
1 COUNTING
1.1 BASIC COUNTING
Pages 7 to 8
Problem 1 Solution
The value of i ranges from 2 to n. When i = k, the variable j ranges from 2 to k.
Thus, there are at most k − 1 comparisons (because we stop if j = 2). Thus, the total
number of comparisons is
n(n − 1)
1 + 2 + ··· + n − 1 = .
2
The algorithm will make this number of comparisons if the original ordering is the
reverse of the sorted ordering.
Problem 2 Solution
Number the five teams 1–5. Team 1 must play all four others. Team 2 will be in one
of these games but must play in three more games with Teams 3, 4, and 5. Team 3
is in two of the games already mentioned and must still play Teams 4 and 5 for
two more games. Team 4 must play Team 5, in addition to playing in three of the
games already mentioned. Thus, there are 4 + 3 + 2 + 1 = 10 games. Alternatively,
there are five teams, each of which must play in four games, giving us 20 pairings
of two teams each. However, each game involves two of these pairings, so there are
20/2 = 10 games.
S1
,Bogart-81046 book April 27, 2005 17:12
Problem 3 Solution
The set of possible draws is a union of 52 sets (one for each possible first card), each
of size 51. So, by the product principle, there are 52 · 51 ways to draw the two cards.
Problem 4 Solution
The answer is the same as in Problem 3, except we can draw the cards in either order.
Therefore, the number of ways is 52 · 51/2 = 1326.
Problem 5 Solution
52 · 51 · 50, by two applications of the product principle.
Problem 6 Solution
10 · 9 = 90.
Problem 7 Solution
10
2
= 10 · 9/2 = 45.
Problem 8 Solution
10 · 9
2
, or 8 10
2
.
Problem 9 Solution
This formula counts the number of ways to choose a president and an executive
advisory board (not including the president) from a club of n people. The left side
chooses the president first, then the committee. The right side chooses the committee
first, then the president.
Problem 10 Solution
m · n.
Problem 11 Solution
By the product rule, there are 10 · 9 = 90 ways to choose two-scoop cones with
two different flavors. However, according to your mother’s rule, the order of scoops
doesn’t matter. Because each two-scoop cone can be ordered in two different ways
(e.g., chocolate over vanilla and vanilla over chocolate), we have 90/2 = 45 ways of
choosing two-scoop cones with different flavors. There are an additional ten cones
with the same flavor for both scoops, giving 55 possible cones.
S2 Chapter 1: Counting
,Bogart-81046 book April 27, 2005 17:12
Problem 12 Solution
Because order does matter, we have 10 · 9 = 90 ways to choose ice cream cones
with two distinct flavors, plus ten more with the same flavor for both scoops, giving
100 choices.
Problem 13 Solution
1 + 2 + 4 + · · · + 219 = 220 − 1 = 1,048,575. Your justification may be neither
principle, only the sum principle (the set of all pennies is the union of the set of pennies
on Day 1 with those on Day 2, and so on), or both principles (the set of pennies
you receive on Day i is the union of two sets of pennies, each of the size that you
received on Day i − 1). As long as your explanation makes sense, any of these
answers is fine.
Problem 14 Solution
5 · 3 · 3 · 3 = 135.
Problem 15 Solution
Yes; in Line 4, j could start at i + 1 rather than i.
1.2 COUNTING LISTS, PERMUTATIONS, AND SUBSETS
Pages 17 to 19
Problem 1 Solution
For each piece of fruit, we have n choices of who to give it to. So, by version 2 of the
product principle, the number of ways to pass out the fruit is n k .
Problem 2 Solution
f 1 (1) = a f 1 (2) = a f 1 (3) = a
f 2 (1) = a f 2 (2) = a f 2 (3) = b
f 3 (1) = a f 3 (2) = b f 3 (3) = a
f 4 (1) = a f 4 (2) = b f 4 (3) = b
f 5 (1) = b f 5 (2) = a f 5 (3) = a
f 6 (1) = b f 6 (2) = a f 6 (3) = b
f 7 (1) = b f 7 (2) = b f 7 (3) = a
f 8 (1) = b f 8 (2) = b f 8 (3) = b
None are one-to-one; all but f 1 and f 8 are onto.
1.2: Counting Lists, Permutations, and Subsets S3
, Bogart-81046 book April 27, 2005 17:12
Problem 3 Solution
f 1 (1) = a f 1 (2) = a
f 2 (1) = a f 2 (2) = b
f 3 (1) = a f 3 (2) = c
f 4 (1) = b f 4 (2) = a
f 5 (1) = b f 5 (2) = b
f 6 (1) = b f 6 (2) = c
f 7 (1) = c f 7 (2) = a
f 8 (1) = c f 8 (2) = b
f 9 (1) = c f 9 (2) = c
None of the functions are onto; all except f 1 , f 5 , and f 9 are one-to-one.
Problem 4 Solution
If we list S as x1 , x2 , . . . , xs , then there is a bijection between functions from S to T
and lists f(x1 ), f(x2 ), . . . , f(xs ). For each i, there are t choices for f(xi ). So, by the
product principle, there are t s functions from S to T.
Problem 5 Solution
We are asking for the number of k-element permutations of n children, which is n k ,
or zero, if k > n.
Problem 6 Solution
What matters is what subset of the n children get fruit, so the answer is n
k
. If k > n,
the answer is zero.
Problem 7 Solution
First, note that “a five-digit base 10 number” means a string of five digits, where the
first digit is not 0 and each digit is in the set {0, 1, . . . , 9}. By the product rule, the
number of these is 9 · 10 4 , or 90,000. If no two consecutive digits can be equal, then
there are nine choices for the first digit, nine for the second (any digit other than the
first), nine for the third (any digit other than the second), and so on. By the product
principle, the total number is 95 .
By the sum principle, the total number of five-digit numbers equals the number that
have no two consecutive digits equal plus the number that have at least one pair of
consecutive digits equal. Thus, letting x denote the number of the latter, we have
9 · 10 4 = 95 + x; so, x = 9 · 10 4 − 95 = 30,951.
S4 Chapter 1: Counting
1 COUNTING
1.1 BASIC COUNTING
Pages 7 to 8
Problem 1 Solution
The value of i ranges from 2 to n. When i = k, the variable j ranges from 2 to k.
Thus, there are at most k − 1 comparisons (because we stop if j = 2). Thus, the total
number of comparisons is
n(n − 1)
1 + 2 + ··· + n − 1 = .
2
The algorithm will make this number of comparisons if the original ordering is the
reverse of the sorted ordering.
Problem 2 Solution
Number the five teams 1–5. Team 1 must play all four others. Team 2 will be in one
of these games but must play in three more games with Teams 3, 4, and 5. Team 3
is in two of the games already mentioned and must still play Teams 4 and 5 for
two more games. Team 4 must play Team 5, in addition to playing in three of the
games already mentioned. Thus, there are 4 + 3 + 2 + 1 = 10 games. Alternatively,
there are five teams, each of which must play in four games, giving us 20 pairings
of two teams each. However, each game involves two of these pairings, so there are
20/2 = 10 games.
S1
,Bogart-81046 book April 27, 2005 17:12
Problem 3 Solution
The set of possible draws is a union of 52 sets (one for each possible first card), each
of size 51. So, by the product principle, there are 52 · 51 ways to draw the two cards.
Problem 4 Solution
The answer is the same as in Problem 3, except we can draw the cards in either order.
Therefore, the number of ways is 52 · 51/2 = 1326.
Problem 5 Solution
52 · 51 · 50, by two applications of the product principle.
Problem 6 Solution
10 · 9 = 90.
Problem 7 Solution
10
2
= 10 · 9/2 = 45.
Problem 8 Solution
10 · 9
2
, or 8 10
2
.
Problem 9 Solution
This formula counts the number of ways to choose a president and an executive
advisory board (not including the president) from a club of n people. The left side
chooses the president first, then the committee. The right side chooses the committee
first, then the president.
Problem 10 Solution
m · n.
Problem 11 Solution
By the product rule, there are 10 · 9 = 90 ways to choose two-scoop cones with
two different flavors. However, according to your mother’s rule, the order of scoops
doesn’t matter. Because each two-scoop cone can be ordered in two different ways
(e.g., chocolate over vanilla and vanilla over chocolate), we have 90/2 = 45 ways of
choosing two-scoop cones with different flavors. There are an additional ten cones
with the same flavor for both scoops, giving 55 possible cones.
S2 Chapter 1: Counting
,Bogart-81046 book April 27, 2005 17:12
Problem 12 Solution
Because order does matter, we have 10 · 9 = 90 ways to choose ice cream cones
with two distinct flavors, plus ten more with the same flavor for both scoops, giving
100 choices.
Problem 13 Solution
1 + 2 + 4 + · · · + 219 = 220 − 1 = 1,048,575. Your justification may be neither
principle, only the sum principle (the set of all pennies is the union of the set of pennies
on Day 1 with those on Day 2, and so on), or both principles (the set of pennies
you receive on Day i is the union of two sets of pennies, each of the size that you
received on Day i − 1). As long as your explanation makes sense, any of these
answers is fine.
Problem 14 Solution
5 · 3 · 3 · 3 = 135.
Problem 15 Solution
Yes; in Line 4, j could start at i + 1 rather than i.
1.2 COUNTING LISTS, PERMUTATIONS, AND SUBSETS
Pages 17 to 19
Problem 1 Solution
For each piece of fruit, we have n choices of who to give it to. So, by version 2 of the
product principle, the number of ways to pass out the fruit is n k .
Problem 2 Solution
f 1 (1) = a f 1 (2) = a f 1 (3) = a
f 2 (1) = a f 2 (2) = a f 2 (3) = b
f 3 (1) = a f 3 (2) = b f 3 (3) = a
f 4 (1) = a f 4 (2) = b f 4 (3) = b
f 5 (1) = b f 5 (2) = a f 5 (3) = a
f 6 (1) = b f 6 (2) = a f 6 (3) = b
f 7 (1) = b f 7 (2) = b f 7 (3) = a
f 8 (1) = b f 8 (2) = b f 8 (3) = b
None are one-to-one; all but f 1 and f 8 are onto.
1.2: Counting Lists, Permutations, and Subsets S3
, Bogart-81046 book April 27, 2005 17:12
Problem 3 Solution
f 1 (1) = a f 1 (2) = a
f 2 (1) = a f 2 (2) = b
f 3 (1) = a f 3 (2) = c
f 4 (1) = b f 4 (2) = a
f 5 (1) = b f 5 (2) = b
f 6 (1) = b f 6 (2) = c
f 7 (1) = c f 7 (2) = a
f 8 (1) = c f 8 (2) = b
f 9 (1) = c f 9 (2) = c
None of the functions are onto; all except f 1 , f 5 , and f 9 are one-to-one.
Problem 4 Solution
If we list S as x1 , x2 , . . . , xs , then there is a bijection between functions from S to T
and lists f(x1 ), f(x2 ), . . . , f(xs ). For each i, there are t choices for f(xi ). So, by the
product principle, there are t s functions from S to T.
Problem 5 Solution
We are asking for the number of k-element permutations of n children, which is n k ,
or zero, if k > n.
Problem 6 Solution
What matters is what subset of the n children get fruit, so the answer is n
k
. If k > n,
the answer is zero.
Problem 7 Solution
First, note that “a five-digit base 10 number” means a string of five digits, where the
first digit is not 0 and each digit is in the set {0, 1, . . . , 9}. By the product rule, the
number of these is 9 · 10 4 , or 90,000. If no two consecutive digits can be equal, then
there are nine choices for the first digit, nine for the second (any digit other than the
first), nine for the third (any digit other than the second), and so on. By the product
principle, the total number is 95 .
By the sum principle, the total number of five-digit numbers equals the number that
have no two consecutive digits equal plus the number that have at least one pair of
consecutive digits equal. Thus, letting x denote the number of the latter, we have
9 · 10 4 = 95 + x; so, x = 9 · 10 4 − 95 = 30,951.
S4 Chapter 1: Counting
