Discrete Mathematics for Computer Science

444 CHAPTER 7 Counting and Combinatorics

The answer to the original question is then found by multiplying this answer by the

number of ways to choose the suit of the flush.

(# Hands with all cards from a given suit - # Straight flushes in that suit)

• (# Possible suits)
  = (C(13, 5) - C(10, 1)) .C(4, 1)
  = 5108
  The percentage of such hands is 5108/2,598,960 • 0.2%. U

7.5.7 Decomposition into Subproblems

Many problems can be solved by decomposing the original problem into a set of subprob-

lems. Two examples of this technique include finding how many different pizzas with a

certain number of toppings can be ordered in five years and finding how many poker hands

contain more Aces than Kings.

Example 10. Pat's Pizza claims that it stocks enough topping ingredients so that you can

order a pizza with a different combination of up to five ingredients every night for five

years. What is the least number n of topping ingredients that must be available to make

this claim true?

Solution. Split the problem into six cases, depending on how many ingredients are cho-

sen. The possibilities are to choose from zero to five ingredients for a pizza. The number

of different pizzas is

(# Pizzas with 0 ingredients) + (# Pizzas with 1 ingredient)

+ (# Pizzas with 2 ingredients) + (# Pizzas with 3 ingredients) + (# Pizzas with

4 ingredients) + (# Pizzas with 5 ingredients)

=C(n, 0) + C(n, 1) + C(n, 2) + C(n, 3) + C(n, 4) + C(n, 5)

This sum must be greater than 5(365) + 2 (the maximum number of days in five con-

secutive years, allowing for at most two leap years). The answer to the original question

involves finding the smallest n that makes the following inequality true:

C(n, 0) + C(n, 1) + C(n, 2) + C(n, 3) + C(n, 4) + C(n, 5) > 1827

which is the same as

l~n+ n(n - 1) +n(n - 1)(n - 2) n(n - 1)(n - 2)(n - 3)

2! 3! 4!

-+ n(n - 1)(n - 2)(n - 3)(n - 4) > 1827

5!

The answer is n = 13, since the expression has the value 2380 for 13 and only 1586 for

n =12. 0

In Example 10, it was not difficult to see how to break up the elements to count into six

cases. In the next example, however, the count for each of the cases will be more complex.

Example 11. How many poker hands have more Aces than Kings?