Methods in Algorithmic Analysis

Chapter 7

Enumeration with G e n e rating

Functions

In this chapter, we will again take up the topic of enumeration that was considered in Chap-

ter 2. Using generating functions (GFs), we are going to broaden our horizons by embracing

enumeration operators

on sets. This is not just a new application of GFs, it is a different point

of view. We now associate a GF not with a sequence but with a set. Later it will be shown how

the two approaches complement each other. This view of generating functions, like much of

the mathematics we use in the analysis of algorithms, goes back to Pierre Simon de Laplace

1

.

Much of this theory was developed by Leonhard Euler, and had a rebirth in the 20th century

with the appearance of the

Symbolic Method

, also called

Combinatorial Calculus

, since it

unifies these branches of mathematics.

The topics of enumeration, combinatorics, and number theory were called higher arithmetic

in previous periods, and were classified as pure mathematics. The need to analyze algorithms

transformed them to engineering mathematics since nearly all such analyses are reduced at

some point to an enumeration of features in combinatorial structures (such as strings, graphs,

or Turing machine traces, etc.). Generating functions provide the theoretical apparatus for

this field. We present and illustrate their uses in various problems on enumeration. Our

exposition, and much of its content, have been inspired by the work of Philippe Flajolet and

his students.

7.1 Definition of Enumerators

Let S be a countable set of elements, such as numbers, words, graphs, coins, computer pro-

grams, other sets, etc. When is such a set acceptable (or well-defined)? We already en-

countered this question, on page 80, and answered that a proper set definition provides an

1

Pierre Simon de Laplace (1749–1827) was one of the greatest French mathematicians.

355

356

Chapter 7. Enumeration with Generating Functions

unambiguous answer to the membership question, that is, whether an element belongs to the

set, or not. We use the notation a ∈ S to signify that a is an element in the set S, and a /∈ S

otherwise.

How can we determine that a set is acceptable? Technically, this is phrased as a re-

quirement of the set to have a characteristic function. Such a function, defin ed on the

universe of all elements potentially in the set, specifies the membership in the set. For

example, it may have the value one for the elements in the set and zero otherwise. In

nearly all practical situations, the membership pr oblem is simple. Difficulties sometimes

arise with sets of sets, or with sets that are defined by self-referential mea ns. Here is a

famous example: a grou p of men consists of two sets: those who shave themselves, and

those wh o are shaved by the barber (a man). To which set does the barber belong? This

is in fact a case of poor terminology. But sometimes the difficulty is genuine, as dealing

with sets that contain themselves. While this case is probably never relevant to the kind

of enumeratio ns we do, it serves as a good warning about the care needed in definitions.

Definition 7.1 (weight)

A weight function w of a set S assigns a non-negative integer to every element of the set.

Formally this is expressed by w : S −→ N. ⊳

While there is no formal reason for restriction of the range of the w eight function to be the set

of nonnegative integers only, the intended application, which uses these weights as powers,

suggests why we never use a different set of values. It should be noted that weight functions

with non-negative real values are used in many applications. For instance, the fuzzy set theory

considers a characteristic function that defines membership as a function with values in the

interval [0,1] rather than in binary set {0,1}, as we do. This theory was invented by Lotfi

A. Zadeh (1965) and it is widely used, for example, in digital image processing for spacial

filtering.

Definition 7.2 (enumerator)

Let S be a set for which a weight function w : S −→N is defined. Let S

(n)

= {a ∈S : w (a) = n}

be the subset of all elements from S having the weight n, n > 0. If all these subsets of S are

finite, we call the set S admissible with respect to the weight w and define the enumerator of

S as

ϕ

S

(z) =

∑

σ

∈S

z

w(

σ

)

=

∑

n>0

∑

σ

∈S

(n)

z

n

. (7.1)

Similarly, we define the exponential enu merator as

ˆ

ϕ

S

(z) =

∑

σ

∈S

z

w(

σ

)

w(

σ

)!

=

∑

n>0

∑

σ

∈S

(n)

z

n

n!

=

∑

n>0

|S

(n)

|

z

n

n!

. ⊳ (7.2)

In this definition, the letter z plays a double role: it is not just a mark for distinguishing

elements within the set S according to their weight, but also a variable, which could be used

for algebraic operations. Furthermore, every element of weight n is marked with z

n

.