Discrete Mathematics for Computer Science

Permutations and Combinations 443

We now look at a noncard problem that uses the same technique for counting.

Example 8. An examination consists of 20 questions, of which the student must answer

any 12.

(a) How many different ways can a student choose questions to answer?

(b) The 20-question exam is split into three parts. There are 6 questions in the first part,

10 in the second part, and 4 in the third part. A student must choose three from the first

part, eight from the second part, and one from the third part. How many ways can a

student choose questions to answer?

Solution.

(a) The answer is just the number of different 12-element subsets of a 20-element set, or

C(20, 12) = 125,970.

(b) By the Multiplication Principle, the answer will be the product of the number of ways

to make choices in each category:

(# Possible choices) = (# Choices for part 1) • (# Choices for part 2)

• (# Choices for part 3)
  = C(6, 3) .C(10, 8) .C(4, 1)
  = 3600

75.6 Counting the Complement

We return to the idea of counting the complement introduced earlier. This time, it is a

useful technique, because direct counts often can involve detailed analysis to determine all

the cases. An illustration of this is given in Example 9.

Example 9. How many poker hands consist of five cards of the same suit, but not in

sequence? Such a poker hand is called aflush.

Solution. First, count the number of hands with all five cards from one suit. This count is
just the number of ways to pick five of the 13 possible values, and there are C(13, 5) such
hands. A poker hand with all five values in sequence is called a straight. A straight with all
the cards from the same suit is called a straight flush. We want to subtract the number of
straight flushes in this suit from C(13, 5) to get the number of flushes for the suit.
To find the number of straight flushes in a suit, note that all five cards in a sequence are
determined by the lowest card in the sequence. In the case of a straight, the rule is that the
Ace can be used as either the highest or the lowest card in the sequence. The card values

are arranged as

Ace 2 3 4 5 6 7 8 9 10 Jack Queen King Ace

The smallest card in a straight can be any one of the card values underlined. Therefore,
there are C(10, 1) straight flushes for a suit, so there are C(13, 5) - C(10, 1) flushes for a
suit.