Page 522 - Discrete Mathematics and Its Applications

CH A P TER

8 Advanced Counting Techniques

8.1 Applications of anycountingproblemscannotbesolvedeasilyusingthemethodsdiscussedinChapter6.
Recurrence MOne such problem is: How many bit strings of length n do not contain two consecutive
Relations zeros? To solve this problem, let a n be the number of such strings of length n. An argument can
be given that shows that the sequence {a n } satisfies the recurrence relation a n+1 = a n + a n−1
8.2 Solving Linear
and the initial conditions a 1 = 2 and a 2 = 3. This recurrence relation and the initial conditions
Recurrence
determine the sequence {a n }. Moreover, an explicit formula can be found for a n from the equation
Relations
relating the terms of the sequence.As we will see, a similar technique can be used to solve many
8.3 Divide-and- different types of counting problems.
Conquer We will discuss two ways that recurrence relations play important roles in the study of
Algorithms and algorithms. First, we will introduce an important algorithmic paradigm known as dynamic
Recurrence programming. Algorithms that follow this paradigm break down a problem into overlapping
Relations subproblems. The solution to the problem is then found from the solutions to the subproblems
through the use of a recurrence relation. Second, we will study another important algorithmic
8.4 Generating
paradigm, divide-and-conquer. Algorithms that follow this paradigm can be used to solve a
Functions
problem by recursively breaking it into a fixed number of nonoverlapping subproblems until
8.5 Inclusion– these problems can be solved directly. The complexity of such algorithms can be analyzed using
Exclusion a special type of recurrence relation. In this chapter we will discuss a variety of divide-and-
conquer algorithms and analyze their complexity using recurrence relations.
8.6 Applications of
Inclusion– We will also see that many counting problems can be solved using formal power series,
Exclusion called generating functions, where the coefficients of powers of x represent terms of the sequence
we are interested in. Besides solving counting problems, we will also be able to use generating
functions to solve recurrence relations and to prove combinatorial identities.
Many other kinds of counting problems cannot be solved using the techniques discussed in
Chapter 6, such as: How many ways are there to assign seven jobs to three employees so that
each employee is assigned at least one job? How many primes are there less than 1000? Both
of these problems can be solved by counting the number of elements in the union of sets. We
will develop a technique, called the principle of inclusion–exclusion, that counts the number of
elements in a union of sets, and we will show how this principle can be used to solve counting
problems.
The techniques studied in this chapter, together with the basic techniques of Chapter 6, can
be used to solve many counting problems.

8.1 Applications of Recurrence Relations

Introduction

Recall from Chapter 2 that a recursive definition of a sequence specifies one or more initial terms
and a rule for determining subsequent terms from those that precede them. Also, recall that a
rule of the latter sort (whether or not it is part of a recursive definition) is called a recurrence
relation and that a sequence is called a solution of a recurrence relation if its terms satisfy the
recurrence relation.
In this section we will show that such relations can be used to study and to solve counting
problems. For example, suppose that the number of bacteria in a colony doubles every hour. If
a colony begins with five bacteria, how many will be present in n hours? To solve this problem,

501