Discrete Mathematics for Computer Science

428 CHAPTER 7 Counting and Combinatorics

9 of Clubods 1Jack of Diamonds 5 of Clubs

9 of Dia ds JkQueen of Diamonds 4 of Clubs

9of Heaubs Quee of Diamonds 3 of Clubs

9 of Spades King of Diamonds 2 of Clubs

Ace of Diamonds 5 of Spades

10 of Hearts 4 of Spades

Jack of Hearts 3 of Spades

Queen of Hearts 2 of Spades

King of Hearts

Ace of Hearts

Figure 7.5 Card choices.

Set Decomposition Principle

Counting is not done using just the Multiplication Principle or the Addition Principle. In

fact, many problems are solved by breaking the problem into subproblems, each of which

can be solved without reference to any of the other subproblems. After solving each of

the subproblems, you combine these results to solve the original problem. The solution

of each subproblem may use the Addition Principle, the Multiplication Principle, or some

combination of both. Since the problem is broken down into subproblems that are solved

independently, the last step involves using the Addition Principle to add the number of

solutions of the subproblems to solve the original problem.

Example 6. Student registration for computer science courses in the spring semester in-

volves choosing two courses from Comp240, Comp225, and Comp326. If six sections of

Comp240, seven sections of Comp225, and five sections of Comp326 are offered, then how

many different registrations are possible? Assume that course conflicts are not an issue.

Solution. Break the problem into three different subproblems that represent the three

pairs of ways that courses can be chosen. Then, count the number of solutions for each

of these three subproblems separately using the Multiplication Principle. The final answer

uses the Addition Principle and sums the number of ways that each of the three subprob-

lems can be solved.

Subproblem 1: Choose Comp240 and Comp225:

(# Ways to choose Comp240) • (# Ways to choose Comp225) = 6. 7

Subproblem 2: Choose Comp240 and Comp326:

(# Ways to choose Comp240) • (# Ways to choose Comp326) = 6. 5

Subproblem 3: Choose Comp225 and Comp326:

(# Ways to choose Comp225) • (# Ways to choose Comp326) = (^7) • 5