262
Sets, Combinatorics, and Probability
In Exercises 59–68, a hand consists of 1 card drawn from a standard 52-card deck with flowers on the back and
1 card drawn from a standard 52-card deck with birds on the back. A standard deck has 13 cards from each of
4 suits (clubs, diamonds, hearts, spades). The 13 cards have face value 2 through 10, jack, queen, king, or ace.
Each face value is a “kind” of card. The jack, queen, and king are “face cards.”
59. How many different hands are possible? (Note that a flower-ace-of-spades, bird-queen-of-hearts and a
flower-queen-of-hearts, bird-ace-of-spades are two different outcomes.)
60. How many hands consist of a pair of aces?
61. How many hands contain all face cards?
62. How many hands contain exactly 1 king?
63. How many hands consist of two of a kind (2 aces, 2 jacks, and so on)?
64. How many hands have a face value of 5 (aces count as 1, face cards count as 10)?
65. How many hands have a face value of less than 5 (aces count as 1, face cards count as 10)?
66. How many hands do not contain any face cards?
67. How many hands contain at least 1 face card?
68. How many hands contain at least 1 king?
69. Draw a decision tree to find the number of binary strings of length 4 that do not have consecutive 0s.
(Compare your answer with the one for Exercise 41 of Section 3.2.)
70. Draw a decision tree (use teams A and B) to find the number of ways the NBA playoffs can happen, where
the winner is the first team to win 4 out of 7.
71. Voting on a certain issue is conducted by having everyone put a red, blue, or green slip of paper into a hat.
Then the slips are pulled out one at a time. The first color to receive two votes wins. Draw a decision tree
to find the number of ways in which the balloting can occur.
72. In Example 39, prove the following facts, where C(n) = the total number of nodes in the decision tree at
level n, H(n) = the total number of nodes at level n resulting from an H toss, T(n) = the total number of
nodes at level n resulting from a T toss.
1
a. C(n) = H(n) + T(n)
b. H(n) = T(n − 1)
c. T(n) = H(n − 1) + T(n − 1)
d. H(n) = H(n − 2) + T(n − 2)
e. C(n) = C(n − 2) + C(n − 1) for n ≥ 3
f. C(n) = F(n + 1) where F(n) is the nth Fibonacci number
73. Use mathematical induction to extend the multiplication principle to a sequence of m events for any integer m, m ≥ 2.
74. Use mathematical induction to extend the addition principle to m disjoint events for any integer m, m ≥ 2.
75. Consider the product of n factors, x 1 # x 2 c x n . Such an expression can be fully parenthesized to indicate
the order of multiplication in a number of ways. For example, if n = 4, there are five ways to parenthesize:
x 1 # (x 2 # (x 3 # x 4 ))
x 1 # ((x 2 # x 3 ) # x 4 )
(x 1 # x 2 ) # (x 3 # x 4 )
(x 1 # (x 2 # x 3 )) # x 4
((x 1 # x 2 ) # x 3 ) # x 4
1 This problem was suggested by Mr. Tracy Castile, a former University of Hawaii at Hilo student.
Sets, Combinatorics, and Probability
In Exercises 59–68, a hand consists of 1 card drawn from a standard 52-card deck with flowers on the back and
1 card drawn from a standard 52-card deck with birds on the back. A standard deck has 13 cards from each of
4 suits (clubs, diamonds, hearts, spades). The 13 cards have face value 2 through 10, jack, queen, king, or ace.
Each face value is a “kind” of card. The jack, queen, and king are “face cards.”
59. How many different hands are possible? (Note that a flower-ace-of-spades, bird-queen-of-hearts and a
flower-queen-of-hearts, bird-ace-of-spades are two different outcomes.)
60. How many hands consist of a pair of aces?
61. How many hands contain all face cards?
62. How many hands contain exactly 1 king?
63. How many hands consist of two of a kind (2 aces, 2 jacks, and so on)?
64. How many hands have a face value of 5 (aces count as 1, face cards count as 10)?
65. How many hands have a face value of less than 5 (aces count as 1, face cards count as 10)?
66. How many hands do not contain any face cards?
67. How many hands contain at least 1 face card?
68. How many hands contain at least 1 king?
69. Draw a decision tree to find the number of binary strings of length 4 that do not have consecutive 0s.
(Compare your answer with the one for Exercise 41 of Section 3.2.)
70. Draw a decision tree (use teams A and B) to find the number of ways the NBA playoffs can happen, where
the winner is the first team to win 4 out of 7.
71. Voting on a certain issue is conducted by having everyone put a red, blue, or green slip of paper into a hat.
Then the slips are pulled out one at a time. The first color to receive two votes wins. Draw a decision tree
to find the number of ways in which the balloting can occur.
72. In Example 39, prove the following facts, where C(n) = the total number of nodes in the decision tree at
level n, H(n) = the total number of nodes at level n resulting from an H toss, T(n) = the total number of
nodes at level n resulting from a T toss.
1
a. C(n) = H(n) + T(n)
b. H(n) = T(n − 1)
c. T(n) = H(n − 1) + T(n − 1)
d. H(n) = H(n − 2) + T(n − 2)
e. C(n) = C(n − 2) + C(n − 1) for n ≥ 3
f. C(n) = F(n + 1) where F(n) is the nth Fibonacci number
73. Use mathematical induction to extend the multiplication principle to a sequence of m events for any integer m, m ≥ 2.
74. Use mathematical induction to extend the addition principle to m disjoint events for any integer m, m ≥ 2.
75. Consider the product of n factors, x 1 # x 2 c x n . Such an expression can be fully parenthesized to indicate
the order of multiplication in a number of ways. For example, if n = 4, there are five ways to parenthesize:
x 1 # (x 2 # (x 3 # x 4 ))
x 1 # ((x 2 # x 3 ) # x 4 )
(x 1 # x 2 ) # (x 3 # x 4 )
(x 1 # (x 2 # x 3 )) # x 4
((x 1 # x 2 ) # x 3 ) # x 4
1 This problem was suggested by Mr. Tracy Castile, a former University of Hawaii at Hilo student.