Discrete Mathematics for Computer Science

Counting Principles 425

sections. Any combination of lecture, lab, and problem session is possible. How many

different ways can a single student be registered for the physics course?

Solution. To use the Multiplication Principle, we need to identify the steps of the proce-

dure and the number of outcomes possible for each step. We also must convince ourselves

that the process for each step does not depend on the process at any other step. This inde-

pendence will be obvious. The steps proceed as follows: Choose a section, choose a lab,

and choose a problem session. There are 6 possible outcomes for the first step, 11 for the

second, and 12 for the third. Therefore, the Multiplication Principle gives

(# Ways to register for physics course) = (# Choices for section) • (# Choices for lab)

• (# Choices for problem session)
  =6. 11 12

= (^792 0)
Example 3. Single characters displayed on a digital watch's display are formed by turn-
ing on some of the areas in a rectangular grid. Figure 7.2 shows the seven lines that a typical
digital watch uses to form characters. How many different characters can be formed?
a
f g b
e IC
d
Figure 7.2 Figures on a digital watch's display.
Solution. The digits can be represented as shown in Figure 7.3.
a a a

f1 lb lb g lb g lb fj lb

el Ic Ic eI Ic Ic

d d d

a a a a a

f g f g 1b f g lb

f[ g b

IC el Ic Ic el Ic

Ic

d d d

Figure 7.3 Representation of the digits.

Notice that a total of seven different line segments are used in forming the different
numerals. You can form a pattern of lines by indicating for each of the seven line segments
whether it is "on" or "off." Since there are seven line segments and each can be on or off