Chapter 6
Introduction to Gene r ating Func t ions
The time has come to introduce the most powerful tool we use in analysis of algorithms:
generating functions (GFs). They provide a natural and elegant way to deal with sequences
of numbers by associating a function (of a continuous variable) with a sequence. In this way
GFs provide a bridge between discrete and continuous mathematics. Generating functions,
like those we use below—and others with minor variations—support numerous applications
in other disciplines, such as probability and statistics, quantum mechanics, control theory,
signal processing, and on and on.
There are several ways to associate a function w ith a sequence of (real or complex) numbers
{a
n
}
n>0
. The most natural one is to consider a power series
a(z) =
∑
n>0
a
n
z
n
. (6.1)
Such a function a(z) is also known as an ordinary generating function (OGF). We obtain the
exponential generating function (EGF) by defining
ˆa(z) =
∑
n>0
a
n
z
n
n!
. (6.2)
Sometimes, it is convenient to introduce a generating function A(z) =
∑
n>0
a
n
g
n
(z) with
respect to a given sequence of functions {g
n
(z)}. Of these, the Appell polynomials are
more frequently used. The method of generating functions is naturally embraced by inte-
gral representations and formal Laurent series. This elegant technique
1
was developed by
G. P. Egorychev [37], but this topic is beyond the scope of our book.
In Chapter 12 we present a brief survey of the definitions and properties of the mathematical
infrastructure needed for generating functions. While it includes sufficient material for our
uses, the reader who would like to delve more deeply into these topics needs additional
sources. Happily, excellent texts exist. We recommend Henrici [62] and Egorychev [37]
for a detailed modern coverage.
1
Some of its applications are exposed in [58], [98].
271
272
Chapter 6. Introduction to Generating Functions
6.1 Generating Functions — Definitions
We present the two main types of GFs we shall use, ordinary (OGF) and exponential (EGF)
generating functions. They were invented by Abraham de Moivre (1667 – 1754) in the early
eighteenth century and, like much of discrete mathematics, came to prominence through the
work of Leonhard Euler (1707 – 1783) in the middle of that century. L. Euler used GFs to
investigate partitions, which are considered in §7.5.
6.1.1 Ordinary Generating Functions
Definition 6.1 For a given sequence of numbers {a
n
}
n>0
, the power series (6.1) is called the
ordinary generating function (OGF) of the sequence {a
n
} or z-transform of this sequence.
⊳
In almost all our applications, the terms of the sequence {a
n
}
n>0
are integers, but all the
properties of the GFs we discuss hold for all numbers in the complex plane. Convergence
of the power series (6.1) is
not
an issue in this chapter. There exists a theory of formal
power series, of which an excellent account is given by Ivan Niven [102] that allows us to
ignore convergence issues and also permits us to manipulate formal power series as we do
polynomials (for example, multiply them term by term). As a rule, we start all our sequences
at the zero index. Normally we don’t need to assume anything about elements with negative
indices. If they arise, w e shall need to say something definite about them (and what we often
say is that they vanish—equal zero).
We start with some basic examples—these may be viewed as a re-cap of some of the summa-
tion formulas used previously. Consider a sequence of identical values, namely, a
k
= C, k >
0. Then the corresponding OGF is
a(z) =
∑
k>0
C z
k
= C
∑
k>0
z
k
=
C
1 −z
. (6.3)
Similarly, let a
k
= r
k
, k > 0, where r is a given number. Then
a(z) =
∑
k>0
r
k
z
k
=
1
1 −rz
. (6.4)
The next example is a similar sequence having the corresponding generating function:
a
k
=
(
0, 0 6 k 6 2,
r
k
, k > 3,
=⇒ a(z) =
∑
k>3
r
k
z
k
=
r
3
z
3
1 −rz
.
The issue of convergence raises a question that should puzzle you:
If we say that convergence is not meaningful here, how can we use a formula,
such as Eq. (6.3), which, as we saw in calculus, is only true when the series
Get Methods in Algorithmic Analysis now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
