Page 412 - Discrete Mathematics and Its Applications

6.1 The Basics of Counting 391

More Complex Counting Problems

Many counting problems cannot be solved using just the sum rule or just the product rule.
However, many complicated counting problems can be solved using both of these rules in
combination. We begin by counting the number of variable names in the programming language
BASIC. (In the exercises, we consider the number of variable names in JAVA.) Then we will
count the number of valid passwords subject to a particular set of restrictions.
EXAMPLE 15 In a version of the computer language BASIC, the name of a variable is a string of one or
two alphanumeric characters, where uppercase and lowercase letters are not distinguished. (An
alphanumeric character is either one of the 26 English letters or one of the 10 digits.) Moreover,
a variable name must begin with a letter and must be different from the five strings of two
characters that are reserved for programming use. How many different variable names are there
in this version of BASIC?

Solution: Let V equal the number of different variable names in this version of BASIC. Let V 1
be the number of these that are one character long and V 2 be the number of these that are two
characters long.Then by the sum rule, V = V 1 + V 2 . Note that V 1 = 26, because a one-character
variable name must be a letter. Furthermore, by the product rule there are 26 · 36 strings of length
two that begin with a letter and end with an alphanumeric character. However, five of these
are excluded, so V 2 = 26 · 36 − 5 = 931. Hence, there are V = V 1 + V 2 = 26 + 931 = 957
different names for variables in this version of BASIC. ▲

EXAMPLE 16 Each user on a computer system has a password, which is six to eight characters long, where
each character is an uppercase letter or a digit. Each password must contain at least one digit.
How many possible passwords are there?

Solution: Let P be the total number of possible passwords, and let P 6 , P 7 , and P 8 denote
the number of possible passwords of length 6, 7, and 8, respectively. By the sum rule, P =
P 6 + P 7 + P 8 . We will now find P 6 , P 7 , and P 8 . Finding P 6 directly is difficult. To find P 6 it is
easier to find the number of strings of uppercase letters and digits that are six characters long,
including those with no digits, and subtract from this the number of strings with no digits. By
6
the product rule, the number of strings of six characters is 36 , and the number of strings with
6
no digits is 26 . Hence,
6
6
P 6 = 36 − 26 = 2,176,782,336 − 308,915,776 = 1,867,866,560.
Similarly, we have

7
7
P 7 = 36 − 26 = 78,364,164,096 − 8,031,810,176 = 70,332,353,920
and
8
8
P 8 = 36 − 26 = 2,821,109,907,456 − 208,827,064,576
= 2,612,282,842,880.
Consequently,

P = P 6 + P 7 + P 8 = 2,684,483,063,360.
▲

EXAMPLE 17 Counting Internet Addresses In the Internet, which is made up of interconnected physical
networks of computers, each computer (or more precisely, each network connection of a com-
puter) is assigned an Internet address. In Version 4 of the Internet Protocol (IPv4), now in use,