Methods in Algorithmic Analysis

Chapter 8

Further Enumeration Methods

In this chapter, we continue the survey of enumeration methods begun in the previous one.

We look at several traditional combinatorial problems, such as counting trees, computing

the size of intersection of sets, and counting the number of ways of putting balls into bins.

We also introduce a versatile combinatorial method, the principle of inclusion and exclusion

(PIE). Beyond the usefulness of the specific results and formulas derived in the process, we

view this as an opportunity to exercise our marvelous tools: the generating functions (GF s)

used as enumerators.

A one-to-one correspondence between sequences of numbers and power series, called gener-

ating functions, was established in Chapter 6. The importance of such an observation is based

on the ability to transform certain operations on sequences into corresponding operations on

generating functions, which are easier to handle. A similar duality exists at the enumeration

level: manipulations of sets are reflected in operations on their enumerators.

The symbolic method of enumerating sets is a systematic elaboration of this simple intro-

duction, adding several operations, considering sets of elements that have structures—such

as graphs—and leading to the labeling of parts of such structures. Its origins lead to Pierre

Simon Laplace and Abraham de Moivre, but the modern formulation of the symbolic method,

as is the term itself, is due to Philippe Flajolet and his group at INRIA.

8.1 Enumeration of Trees

Algorithm designers have been using a large variety of tree-based data structures, and many

computations are implemented as operations on trees. Analyzing such algorithms amounts to

calculating tree features. We do not try here to exhaust the topic; books can be written about

it—and have been. Our intention is to introduce several important varieties, provide instances

that illustrate the versatility of the enumeration tools we have, and acquaint the reader with

some of the related techniques.

423