Discrete Mathematics for Computer Science

424 CHAPTER 7 Counting and Combinatorics

a microcomputer, the customer must choose an appropriate software package, which can

be done in four ways no matter which microcomputer was chosen. Consequently, the total

number of choices is

(# Choices for microcomputer). (# Choices for software package) = 3 • 4

= 12

Fast Lease should therefore have 12 different leases available at all times.

The choices can be explicitly displayed using the tree shown in Figure 7.1. Each inte-

rior vertex of the tree-that is, each vertex with an edge to its right in the figure-represents

a point at which a choice can be made in a number of ways. Since a customer has three

choices for choosing a microcomputer, three branches of the tree emanate from the starting

point that is represented by the leftmost vertex. After choosing one of the three options for

a microcomputer, a customer must then choose one of the four software packages, giving

the 12 choices enumerated by the vertices at the right edge of the tree.

r software 1

micro 1 • software 2

software 3

i I software 4

j software

1

/micro2 software 2

"software 3

software 4

software 1

software 2

micro3 software 3

software 4

Figure 7.1 Choices for micros and software packages.

7.2.1 The Multiplication Principle

The problems of counting the number of possible tours for the TSP and of counting

the number of leases are among the counting problems solved using the Multiplication

Principle.

The Multiplication Principle

Let m E N. For a procedure of m successive distinct and independent steps with n 1

outcomes possible for the first step, n 2 outcomes possible for the second step .... and

n^1 m outcomes possible for the mth step, the total number of possible outcomes is

nl .n2 ... nm

Example 2. A university offers six sections of a physics course. Each student registered

for the physics course also registers for 1 of 11 lab sections and 1 of 12 problem session