Page 409 - Discrete Mathematics and Its Applications

388 6 / Counting

Note that we have ignored Consequently, applying the product rule again, it follows that under the old plan there are
restrictions that rule out
N11 station codes for
160 · 640 · 10,000 = 1,024,000,000
most area codes.
different numbers available in North America. Under the new plan, there are

800 · 800 · 10,000 = 6,400,000,000

different numbers available. ▲

EXAMPLE 9 What is the value of k after the following code, where n 1 ,n 2 ,...,n m are positive integers, has
been executed?

k := 0
for i 1 := 1 to n 1
for i 2 := 1 to n 2
·
·
·
for i m := 1 to n m
k := k + 1

Solution: The initial value of k is zero. Each time the nested loop is traversed, 1 is added
to k. Let T i be the task of traversing the ith loop. Then the number of times the loop is traversed
is the number of ways to do the tasks T 1 , T 2 ,...,T m . The number of ways to carry out the
task T j , j = 1, 2,...,m,is n j , because the jth loop is traversed once for each integer i j with
1 ≤ i j ≤ n j . By the product rule, it follows that the nested loop is traversed n 1 n 2 ··· n m times.
Hence, the final value of k is n 1 n 2 ··· n m . ▲

EXAMPLE 10 Counting Subsets of a Finite Set Use the product rule to show that the number of different
|S|
subsets of a finite set S is 2 .
Solution: Let S be a finite set. List the elements of S in arbitrary order. Recall from
Section 2.2 that there is a one-to-one correspondence between subsets of S and bit strings
of length |S|. Namely, a subset of S is associated with the bit string witha1inthe ith position if
the ith element in the list is in the subset, anda0in this position otherwise. By the product rule,
there are 2 |S| bit strings of length |S|. Hence, |P(S)|= 2 . (Recall that we used mathematical
|S|
induction to prove this fact in Example 10 of Section 5.1.) ▲

The product rule is often phrased in terms of sets in this way: If A 1 ,A 2 ,...,A m are finite
sets, then the number of elements in the Cartesian product of these sets is the product of the
number of elements in each set. To relate this to the product rule, note that the task of choosing
an element in the Cartesian product A 1 × A 2 × ··· × A m is done by choosing an element
in A 1 , an element in A 2 ,..., and an element in A m . By the product rule it follows that

|A 1 × A 2 × ··· × A m |=|A 1 |·|A 2 |· · · · ·|A m |.

EXAMPLE 11 DNA and Genomes The hereditary information of a living organism is encoded using de-
oxyribonucleic acid (DNA), or in certain viruses, ribonucleic acid (RNA). DNA and RNA are
extremely complex molecules, with different molecules interacting in a vast variety of ways to