Page 407 - Discrete Mathematics and Its Applications

386 6 / Counting

Basic Counting Principles

We first present two basic counting principles, the product rule and the sum rule. Then we will
show how they can be used to solve many different counting problems.
The product rule applies when a procedure is made up of separate tasks.

THE PRODUCT RULE Suppose that a procedure can be broken down into a sequence of
two tasks. If there are n 1 ways to do the first task and for each of these ways of doing the first
task, there are n 2 ways to do the second task, then there are n 1 n 2 ways to do the procedure.

Examples 1–10 show how the product rule is used.

EXAMPLE 1 A new company with just two employees, Sanchez and Patel, rents a floor of a building with
12 offices. How many ways are there to assign different offices to these two employees?

Solution: The procedure of assigning offices to these two employees consists of assigning an
office to Sanchez, which can be done in 12 ways, then assigning an office to Patel different from
the office assigned to Sanchez, which can be done in 11 ways. By the product rule, there are
12 · 11 = 132 ways to assign offices to these two employees. ▲

EXAMPLE 2 The chairs of an auditorium are to be labeled with an uppercase English letter followed by a
positive integer not exceeding 100. What is the largest number of chairs that can be labeled
differently?

Solution: The procedure of labeling a chair consists of two tasks, namely, assigning to the seat
one of the 26 uppercase English letters, and then assigning to it one of the 100 possible integers.
The product rule shows that there are 26 · 100 = 2600 different ways that a chair can be labeled.
Therefore, the largest number of chairs that can be labeled differently is 2600. ▲

EXAMPLE 3 There are 32 microcomputers in a computer center. Each microcomputer has 24 ports. How
many different ports to a microcomputer in the center are there?

Solution: The procedure of choosing a port consists of two tasks, first picking a microcomputer
and then picking a port on this microcomputer. Because there are 32 ways to choose the micro-
computer and 24 ways to choose the port no matter which microcomputer has been selected,
the product rule shows that there are 32 · 24 = 768 ports. ▲

An extended version of the product rule is often useful. Suppose that a procedure is carried
out by performing the tasks T 1 ,T 2 ,...,T m in sequence. If each task T i , i = 1, 2,...,n, can be
done in n i ways, regardless of how the previous tasks were done, then there are n 1 · n 2 · ··· · n m
ways to carry out the procedure. This version of the product rule can be proved by mathematical
induction from the product rule for two tasks (see Exercise 72).

EXAMPLE 4 How many different bit strings of length seven are there?

Solution: Each of the seven bits can be chosen in two ways, because each bit is either 0 or 1.
7
Therefore, the product rule shows there are a total of 2 = 128 different bit strings of length
seven. ▲