Page 408 - Discrete Mathematics and Its Applications

6.1 The Basics of Counting 387

EXAMPLE 5 How many different license plates can be made if each plate contains a sequence of three
uppercase English letters followed by three digits (and no sequences of letters are prohibited,
even if they are obscene)?

Solution: There are 26 choices for each of the three uppercase English letters and ten choices for
26 choices 10 choices each of the three digits. Hence, by the product rule there are a total of 26 · 26 · 26 · 10 · 10 · 10 =
for each for each 17,576,000 possible license plates. ▲
letter digit

EXAMPLE 6 Counting Functions How many functions are there from a set with m elements to a set with
n elements?

Solution:A function corresponds to a choice of one of the n elements in the codomain for each of
m
the m elements in the domain. Hence, by the product rule there are n · n · ··· · n = n functions
3
from a set with m elements to one with n elements. For example, there are 5 = 125 different
functions from a set with three elements to a set with five elements. ▲

EXAMPLE 7 Counting One-to-One Functions How many one-to-one functions are there from a set with
m elements to one with n elements?

Solution: First note that when m>n there are no one-to-one functions from a set with m
elements to a set with n elements.
Counting the number of
Now let m ≤ n. Suppose the elements in the domain are a 1 ,a 2 ,...,a m . There are n ways
onto functions is harder.
We’ll do this in Chapter 8. to choose the value of the function at a 1 . Because the function is one-to-one, the value of the
function at a 2 can be picked in n − 1 ways (because the value used for a 1 cannot be used again).
In general, the value of the function at a k can be chosen in n − k + 1 ways. By the product rule,
there are n(n − 1)(n − 2) ··· (n − m + 1) one-to-one functions from a set with m elements to
one with n elements.
For example, there are 5 · 4 · 3 = 60 one-to-one functions from a set with three elements to
a set with five elements. ▲

EXAMPLE 8 The Telephone Numbering Plan The North American numbering plan (NANP) specifies the
format of telephone numbers in the U.S., Canada, and many other parts of North America. A
telephone number in this plan consists of 10 digits, which are split into a three-digit area code, a
three-digit office code, and a four-digit station code. Because of signaling considerations, there
are certain restrictions on some of these digits. To specify the allowable format, let X denote
a digit that can take any of the values 0 through 9, let N denote a digit that can take any of
the values 2 through 9, and let Y denote a digit that must bea0ora1. Two numbering plans,
which will be called the old plan, and the new plan, will be discussed. (The old plan, in use in
the 1960s, has been replaced by the new plan, but the recent rapid growth in demand for new
numbers for mobile phones and devices will eventually make even this new plan obsolete. In
Current projections are
that by 2038, it will be this example, the letters used to represent digits follow the conventions of the North American
necessary to add one or Numbering Plan.) As will be shown, the new plan allows the use of more numbers.
more digits to North In the old plan, the formats of the area code, office code, and station code are NYX, NNX, and
American telephone XXXX, respectively, so that telephone numbers had the form NYX-NNX-XXXX. In the new plan,
numbers.
the formats of these codes are NXX, NXX, and XXXX, respectively, so that telephone numbers
have the form NXX-NXX-XXXX. How many different North American telephone numbers are
possible under the old plan and under the new plan?

Solution: By the product rule, there are 8 · 2 · 10 = 160 area codes with format NYX and
8 · 10 · 10 = 800 area codes with format NXX. Similarly, by the product rule, there are
8 · 8 · 10 = 640 office codes with format NNX. The product rule also shows that there are
10 · 10 · 10 · 10 = 10,000 station codes with format XXXX.