Page 527 - Discrete Mathematics and Its Applications

506 8 / Advanced Counting Techniques

Remark: Notethat{a n }satisfiesthesamerecurrencerelationastheFibonaccisequence.Because
a 1 = f 3 and a 2 = f 4 it follows that a n = f n+2 .

Example 4 shows how a recurrence relation can be used to model the number of codewords
that are allowable using certain validity checks.

EXAMPLE 4 Codeword Enumeration A computer system considers a string of decimal digits a valid
codeword if it contains an even number of 0 digits. For instance, 1230407869 is valid,
whereas 120987045608 is not valid. Let a n be the number of valid n-digit codewords. Find
a recurrence relation for a n .

Solution: Note that a 1 = 9 because there are 10 one-digit strings, and only one, namely, the
string 0, is not valid. A recurrence relation can be derived for this sequence by considering how
a valid n-digit string can be obtained from strings of n − 1 digits. There are two ways to form
a valid string with n digits from a string with one fewer digit.
First, a valid string of n digits can be obtained by appending a valid string of n − 1 digits
with a digit other than 0. This appending can be done in nine ways. Hence, a valid string
with n digits can be formed in this manner in 9a n−1 ways.
Second, a valid string of n digits can be obtained by appendinga0toa string of length
n − 1 that is not valid. (This produces a string with an even number of 0 digits because the
invalid string of length n − 1 has an odd number of 0 digits.) The number of ways that this can
be done equals the number of invalid (n − 1)-digit strings. Because there are 10 n−1 strings of
length n − 1, and a n−1 are valid, there are 10 n−1 − a n−1 valid n-digit strings obtained by
appending an invalid string of length n − 1witha0.
Because all valid strings of length n are produced in one of these two ways, it follows that
there are

a n = 9a n−1 + (10 n−1 − a n−1 )
= 8a n−1 + 10 n−1

valid strings of length n. ▲

Example 5 establishes a recurrence relation that appears in many different contexts.

EXAMPLE 5 Find a recurrence relation for C n , the number of ways to parenthesize the product of n + 1 num-
bers, x 0 · x 1 · x 2 · ··· · x n , to specify the order of multiplication. For example, C 3 = 5 because
there are five ways to parenthesize x 0 · x 1 · x 2 · x 3 to determine the order of multiplication:

((x 0 · x 1 ) · x 2 ) · x 3 (x 0 · (x 1 · x 2 )) · x 3 (x 0 · x 1 ) · (x 2 · x 3 )
x 0 · ((x 1 · x 2 ) · x 3 ) x 0 · (x 1 · (x 2 · x 3 )).

Solution: To develop a recurrence relation for C n , we note that however we insert parentheses
in the product x 0 · x 1 · x 2 · ··· · x n , one “·” operator remains outside all parentheses, namely,
the operator for the final multiplication to be performed. [For example, in (x 0 · (x 1 · x 2 )) · x 3 ,
it is the final “·”, while in (x 0 · x 1 ) · (x 2 · x 3 ) it is the second “·”.] This final operator appears
between two of the n + 1 numbers, say, x k and x k+1 . There are C k C n−k−1 ways to insert
parentheses to determine the order of the n + 1 numbers to be multiplied when the final op-
erator appears between x k and x k+1 , because there are C k ways to insert parentheses in the
product x 0 · x 1 · ··· · x k to determine the order in which these k + 1 numbers are to be multi-
plied and C n−k−1 ways to insert parentheses in the product x k+1 · x k+2 · ··· · x n to determine